哇擦，传说中的堆栈溢出和快速排序

stack overflow

堆栈溢出和快速排序这两个概念对开发人员来说并不陌生，但是通知都只是听说过，真正开发过程中却很少会遇到。我也是敲代码好些行后非常有幸撞上了，而且还是两个一起出现的，这其中过程的滋味还是相当酸爽，值得回味。

问题背景：

某项目中有个POI离线检索功能，比如搜索附近的加油站，底层引擎逻辑提供了一个C函数。

输入：经纬点，搜索范围半径，搜索类别。

输出：按照距离由近到远排好序的POI结果列表。

这是一个C函数，是同步接口，所以我在OC 上层做了一次封装，改成了异步调用，在子线程中执行。

问题现象：

（1）如果搜索加油站，酒店等匹配结果数据较少的类型，功能正常；

（2）如果搜索饭店，酒店这种匹配结果较多的类型时，则会导致程序Crash。Crash时线程堆栈显示crash在搜索子线程，Crash对应的代码行不固定，每次crash时都不一样，略诡异，但是都是Crash在对搜索结果进行快速排序的那个快排函数中；

（3）如果我减少搜索范围的半径，再搜索饭店或者酒店时，功能又正常了。

问题分析：

（1）只有检索结果列表中元素比较多的时候才出现问题，元素较少时功能正常；

（2）快速排序函数是非常标准的实现，而且大多数类别的搜索都是正常的，所以应该可以排除嫌疑。但是Crash线程调用堆栈却显示挂在了快速排序函数里面。说明函数的执行环境有问题；

快速排序函数代码

（3）该函数是放在子线程中执行的。难道是子线程默认堆栈空间太小，快速排序递归层级过多时因为堆栈溢出导致crash？特意查了一些苹果官方文档，

apple堆栈大小说明

iOS系统中子线程默认堆栈大小是512K，果然比较小。

问题解决方案：

（1）直接增大子线程的堆栈大小。我用的是Cocoa的线程NSThread，直接通过setStackSize方法配置线程堆栈大小，需要注意的是配置的stacksize最小值是16k，而且必须是4K的整数倍。需要在线程开始执行之前进行配置（NSThread 对象的start方法调用之前）。

调整堆栈大小

（2）对快速排序做优化。

问题总结：

1、关于堆栈溢出

一般情况下应用程序是不需要考虑堆和栈的大小的，但是事实上堆和栈都不是无上限的，过多的递归会导致栈溢出，过多的alloc变量会导致堆溢出。默认情况下iOS主线程1M，子线程512K。

iOS 应用程序执行时内存布局如下图所示：

内存空间

在应用程序分配的内存空间里面，最低地址位是固定的代码段和数据段，往上是堆，向上生长，用来存放全局变量，对于 ObjC对象来说，就是 alloc 出来的变量，都会放进这里，堆不够用的时候就会往上申请空间。最顶部高地址位是栈，向下生长，局部的基本类型变量都会放进栈里，函数调用时参数、返回地址等信息都是放在栈里。 ObjC 的对象都是以指针进行操控的，局部变量的指针都在栈里，全局的变量的指针在堆里。

所以预防堆栈溢出的方法：

（1）避免层次过深的递归调用；

（2）不要使用过多的局部变量，控制局部变量的大小；

（3）避免分配占用空间太大的对象，并及时释放;

（4）实在不行，适当的情景下调用系统API修改线程的堆栈大小；

2、关于快速排序的优化

快速排序是数据结构课程中介绍的最基础的一种算法。这里单独拿出来聊这个话题，主要是想强调两个事情，第一，基础真的很重要；第二，基础算法在实际编程中确实可能用到不多，大部分情况下都是直接调用系统的封装好的接口即可，但并不代表不会遇到，并且校招面试中出现几率也是比较大的。

关于快速排序的优化，百度里面一搜能找到很多方法，甚至还有不少人用这个题目来写各种小论文。我这里也简单分享一下我觉得比较容易实现且效果较好的方法。

我们先看看快速排序的标准教科书实现：