我说几个编程复杂度不高，算法书上少见，存在感低，但优化效果不俗的算法：&br&&br&一、Sunday字符串查找算法(通常速度很快，但极端情况下是O(MN)，拳打KMP，脚踢BM)&br&&br&二、左偏堆(一种可合并堆，合并操作复杂度为O(logn)，比二项堆和斐波那契堆编程难度小得多，时间常数也小)&br&&br&三、三向切分快速排序(在数组重复元素很多时很有效)&br&&br&四、同时寻找数组最大最小值(算法导论上有，由2n次比较优化到1.5n次比较)&br&&br&五、BFPRT算法(寻找数组第m小的元素，最坏为O(n))&br&&br&六、回文子串寻找算法(给出字符串的每个字符的回文半径，复杂度最坏O(n))
我说几个编程复杂度不高，算法书上少见，存在感低，但优化效果不俗的算法： 一、Sunday字符串查找算法(通常速度很快，但极端情况下是O(MN)，拳打KMP，脚踢BM) 二、左偏堆(一种可合并堆，合并操作复杂度为O(logn)，比二项堆和斐波那契堆编程难度小得多，时间…
放几张优化图：&br&引自database system concepts 6-th edition 书中的例子&br&朴素的数据在文件页中的存储结构：&br&&img src=&/e3a985a10defeb662e43db_b.png& data-rawwidth=&212& data-rawheight=&167& class=&content_image& width=&212&&&br&当要删除或插入数据的时候，需要移动其他很多记录&br&&br&&br&自由链表（Free List）：&br&&img src=&/e25acdb283cc369be7df9c44f013e78f_b.png& data-rawwidth=&326& data-rawheight=&226& class=&content_image& width=&326&&&br&通过指针的改动，避免了对数据的位置改动，插值时顺着指针找出空位插入，并修改前后指针即可。&br&&br&&br&插入处理：&br&&img src=&/f4d7c3fc7d7ac9e674881_b.png& data-rawwidth=&432& data-rawheight=&356& class=&origin_image zh-lightbox-thumb& width=&432& data-original=&/f4d7c3fc7d7ac9e674881_r.png&&&br&下面是数据库索引优化：&br&&img src=&/ffe0cdca202dea483ebc3_b.png& data-rawwidth=&577& data-rawheight=&197& class=&origin_image zh-lightbox-thumb& width=&577& data-original=&/ffe0cdca202dea483ebc3_r.png&&&br&原本用二分法查找一条记录需要从硬盘读取log2(1000000)个Page，加了Index后只需读取4个，从硬盘读取到内存比在内存中搜索慢得多，因此减少读取数量可以显著提高效率。&br&&br&&br&二级索引的使用：&br&&img src=&/e8c487d32bf7dcc6747800_b.png& data-rawwidth=&592& data-rawheight=&275& class=&origin_image zh-lightbox-thumb& width=&592& data-original=&/e8c487d32bf7dcc6747800_r.png&&&br&对索引的排序间接排好了原数据&br&哈希表索引:&br&&img src=&/36cebecaffb_b.png& data-rawwidth=&478& data-rawheight=&455& class=&origin_image zh-lightbox-thumb& width=&478& data-original=&/36cebecaffb_r.png&&&br&通过哈希函数寻找记录对应的bucket，从而快速找到记录，缺点是无法快速找到指定范围的记录，比如找1&x&500&br&&br&&br&网格文件：&br&&img src=&/9b69b6f2b9d872fcb1f9e39b7558ac44_b.png& data-rawwidth=&592& data-rawheight=&401& class=&origin_image zh-lightbox-thumb& width=&592& data-original=&/9b69b6f2b9d872fcb1f9e39b7558ac44_r.png&&&br&瞬间找到指定范围的记录， 如要找5K&x&=100k 3&=y&=4 的返回Bi对应的那片右上角区域的所有指针即可&br&&br&&br&比特图&br&&img src=&/24b7fd4d6eab26153b46ce_b.png& data-rawwidth=&592& data-rawheight=&206& class=&origin_image zh-lightbox-thumb& width=&592& data-original=&/24b7fd4d6eab26153b46ce_r.png&&&br&寻找income-level不为L4的，对L4对位取反即可，income-level为L1或L2的，L1，L2对位取或即可。
放几张优化图： 引自database system concepts 6-th edition 书中的例子 朴素的数据在文件页中的存储结构： 当要删除或插入数据的时候，需要移动其他很多记录 自由链表（Free List）： 通过指针的改动，避免了对数据的位置改动，插值时顺着指针找出空位插入…
&a data-hash=&160e9eeaefbf& href=&///people/160e9eeaefbf& class=&member_mention& data-editable=&true& data-title=&@夏洋& data-tip=&p$b$160e9eeaefbf& data-hovercard=&p$b$160e9eeaefbf&&@夏洋&/a& 的代码，避免了 if (!diff) ...; 及 x ? a : b 这些比较和分支。&br&&div class=&highlight&&&pre&&code class=&language-c&&&span class=&cp&&#define POPULATE_RIGHT(X) \&/span&
&span class=&cp&&
X |= X && 1;\&/span&
&span class=&cp&&
X |= X && 2;\&/span&
&span class=&cp&&
X |= X && 4;\&/span&
&span class=&cp&&
X |= X && 8;\&/span&
&span class=&cp&&
X |= X && 16&/span&
&span class=&cp&&#define REPLICATE_LSB(X) \&/span&
&span class=&cp&&
X |= X && 1;\&/span&
&span class=&cp&&
X |= X && 2;\&/span&
&span class=&cp&&
X |= X && 4;\&/span&
&span class=&cp&&
X |= X && 8;\&/span&
&span class=&cp&&
X |= X && 16&/span&
&span class=&cp&&#define SELECT(COND, A, B) ((COND) & (A)) | (~(COND) & (B))&/span&
&span class=&kt&&int&/span& &span class=&nf&&compare&/span&&span class=&p&&(&/span&&span class=&kt&&uint32_t&/span& &span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&kt&&uint32_t&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&kt&&uint32_t&/span& &span class=&n&&diff&/span& &span class=&o&&=&/span& &span class=&n&&a&/span& &span class=&o&&^&/span& &span class=&n&&b&/span&&span class=&p&&;&/span&
&span class=&n&&POPULATE_RIGHT&/span&&span class=&p&&(&/span&&span class=&n&&diff&/span&&span class=&p&&);&/span&
&span class=&kt&&uint32_t&/span& &span class=&n&&greater&/span& &span class=&o&&=&/span& &span class=&n&&a&/span& &span class=&o&&&&/span& &span class=&p&&(&/span&&span class=&n&&diff&/span& &span class=&o&&^&/span& &span class=&p&&(&/span&&span class=&n&&diff&/span& &span class=&o&&&&&/span& &span class=&mi&&1&/span&&span class=&p&&));&/span&
&span class=&n&&POPULATE_RIGHT&/span&&span class=&p&&(&/span&&span class=&n&&greater&/span&&span class=&p&&);&/span&
&span class=&n&&REPLICATE_LSB&/span&&span class=&p&&(&/span&&span class=&n&&greater&/span&&span class=&p&&);&/span&
&span class=&kt&&uint32_t&/span& &span class=&n&&non_zero&/span& &span class=&o&&=&/span& &span class=&n&&diff&/span& &span class=&o&&&&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span&
&span class=&n&&REPLICATE_LSB&/span&&span class=&p&&(&/span&&span class=&n&&non_zero&/span&&span class=&p&&);&/span&
&span class=&k&&return&/span& &span class=&n&&SELECT&/span&&span class=&p&&(&/span&&span class=&n&&non_zero&/span&&span class=&p&&,&/span& &span class=&n&&SELECT&/span&&span class=&p&&(&/span&&span class=&n&&greater&/span&&span class=&p&&,&/span& &span class=&mi&&1&/span&&span class=&p&&,&/span& &span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&),&/span& &span class=&mi&&0&/span&&span class=&p&&);&/span&
&span class=&p&&}&/span&
&/code&&/pre&&/div&这样应该更符合题目要求。&br&用位操作做比较的意义不大，但使用 SELECT() 这种方式去避免分支，在 SIMD 编程中是很常用的技巧。
的代码，避免了 if (!diff) ...; 及 x ? a : b 这些比较和分支。 #define POPULATE_RIGHT(X) \
X |= X && 1;\
X |= X && 2;\
X |= X && 4;\
X |= X && 8;\
X |= X && 16
#define REPLICATE_LSB(X) \
X |= X && 1;\
X |= X && 2;\
我印象最深的还是Quake的那个快速平方根倒数算法：&br&&a href=&///?target=https%3A//en.wikipedia.org/wiki/Fast_inverse_square_root& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Fast inverse square root&i class=&icon-external&&&/i&&/a&
我印象最深的还是Quake的那个快速平方根倒数算法：
平方根倒数快速算法&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&该算法的本质其实就是牛顿迭代法（Newton-Raphson Method，简称NR），而NR的基础则是泰勒级数（Taylor Series）。NR是一种求方程的近似根的方法。首先要估计一个与方程的根比较靠近的数值，然后根据公式推算下一个更加近似的数值，不断重复直到可以获得满意的精度。其公式如下：&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&函数：&img src=&///equation?tex=y%3Df%28x%29& alt=&y=f(x)& eeimg=&1&&&br&其一阶导数为：&img src=&///equation?tex=yx%5E%7B%27%7D%3Df%5E%7B%27%7D%28x%29++& alt=&yx^{'}=f^{'}(x)
& eeimg=&1&&&br&则方程：&img src=&///equation?tex=f%28x%29%3D0& alt=&f(x)=0& eeimg=&1&& 的第n+1个近似根为&br&&img src=&///equation?tex=x%5Bn%2B1%5D+%3D+x%5Bn%5D+-+f%28x%5Bn%5D%29+%2F+f%27%28x%5Bn%5D%29& alt=&x[n+1] = x[n] - f(x[n]) / f'(x[n])& eeimg=&1&&&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br& NR最关键的地方在于估计第一个近似根。如果该近似根与真根足够靠近的话，那么只需要少数几次迭代，就可以得到满意的解。&p&现在回过头来看看如何利用牛顿法来解决我们的问题。求平方根的倒数，实际就是求方程&img src=&///equation?tex=1%2F%28x%5E2%29-a%3D0& alt=&1/(x^2)-a=0& eeimg=&1&&的解。将该方程按牛顿迭代法的公式展开为：&br&&img src=&///equation?tex=x%5Bn%2B1%5D%3D1%2F2%2Ax%5Bn%5D%2A%283-a%2Ax%5Bn%5D%2Ax%5Bn%5D%29& alt=&x[n+1]=1/2*x[n]*(3-a*x[n]*x[n])& eeimg=&1&&&br& 将1/2放到括号里面，就得到了上面那个函数的倒数第二行。&/p&&p&接着，我们要设法估计第一个近似根。这也是上面的函数最神奇的地方。它通过某种方法算出了一个与真根非常接近的近似根，因此它只需要使用一次迭代过程就获得了较满意的解。它是怎样做到的呢？所有的奥妙就在于这一行：&br&i = 0x5f3759df - (i && 1); // 计算第一个近似根&/p&&p&代码如下&/p&&p&float Q_rsqrt( float number )&br&{&br&&br&float x2,&br&const float threehalfs = 1.5F;&br&&br&x2 = number * 0.5F;&br&y =&br&i = * ( long * ) &y; // evil floating point bit level hacking&br&i = 0x5f3759df - ( i && 1 ); // what the fuck?&br&y = * ( float * ) &i;&br&y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration&br&// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed&br&&br&#ifndef Q3_VM&br&#ifdef __linux__&br&assert( !isnan(y) ); // bk010122 - FPE?&br&#endif&br&#endif&br&&br&}&/p&
平方根倒数快速算法 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 该算法的本质其实就是牛顿迭代法（Newton-Raphson Method，简称NR），而NR的基础则是泰勒级数（Taylor Series）。NR是一种求方程的近似根的方法。首先要估计一个…
manacher马拉车算法&br&&a href=&///?target=https%3A//en.m.wikipedia.org/wiki/Longest_palindromic_substring& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&en.m.wikipedia.org/wiki&/span&&span class=&invisible&&/Longest_palindromic_substring&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&
manacher马拉车算法
很多人知道Quake 3里著名的inverse sqrt，很少有人知道有个fast sqrt。我们老板大概20多年前想到的sqrt算法：&br&&br&&div class=&highlight&&&pre&&code class=&language-c&&&span class=&kt&&float&/span& &span class=&nf&&fast_sqrt&/span&&span class=&p&&(&/span&&span class=&kt&&float&/span& &span class=&n&&x&/span&&span class=&p&&)&/span&
&span class=&p&&{&/span&
&span class=&kt&&uint32_t&/span& &span class=&n&&x_bits&/span& &span class=&o&&=&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span&
&span class=&n&&x_bits&/span& &span class=&o&&=&/span& &span class=&o&&*&/span&&span class=&p&&((&/span&&span class=&kt&&uint32_t&/span&&span class=&o&&*&/span&&span class=&p&&)&/span& &span class=&o&&&&/span&&span class=&n&&x&/span&&span class=&p&&);&/span&
&span class=&c1&&//猜猜这是什么？&/span&
&span class=&n&&x_bits&/span& &span class=&o&&=&/span& &span class=&p&&(&/span&&span class=&n&&x_bits&/span& &span class=&o&&&&&/span& &span class=&mi&&1&/span&&span class=&p&&)&/span& &span class=&o&&+&/span& &span class=&mi&&&/span&&span class=&p&&;&/span&
&span class=&k&&return&/span& &span class=&o&&*&/span&&span class=&p&&((&/span&&span class=&kt&&float&/span&&span class=&o&&*&/span&&span class=&p&&)&/span& &span class=&o&&&&/span&&span class=&n&&x_bits&/span&&span class=&p&&);&/span&
&span class=&p&&}&/span&
&/code&&/pre&&/div&&br&这个算法可以在几个instruction内算好sqrt，纯bit运算，不相信的可以试试。&br&&br&当然这个算法的误差大概在3%左右，如果后面接两个牛顿迭代可以把误差控制在2个bit（即0.000025%）。&br&&br&神奇吧～最神奇的是，这个算法不光可以算sqrt，还可以算log，如果细心的朋友会发现这个算法和著名的inverse sqrt其实是同源的。&br&&br&至于为什么是这个神奇的数字，就留给大家思考吧！
很多人知道Quake 3里著名的inverse sqrt，很少有人知道有个fast sqrt。我们老板大概20多年前想到的sqrt算法： float fast_sqrt(float x)
uint32_t x_bits = 0;
x_bits = *((uint32_t*) &x);
//猜猜这是什么？
x_bits = (x_bits && 1) + ;…
如果楼主不是为了竞赛刷题，可以先抛开书本上的什么状态转移方程什么的，可以教你一个民科点的思路O(∩_∩)O：&br&我们面对的是一个求最优解或统计之类的问题，这个问题基于“我们要模拟完成一个大任务”，这个大任务可以分成若干步骤，每个步骤有若干种决策，每个步骤完成后，就到达了一个阶段性状态&br&比如，你要从A地到Z地，没有直达，所以第一步需要到一个中间地点，比如H或I，第二步再前进，比如到P或Q，最后到达Z，每一步有若干决策，比如第一步你可以决定到H或I的中的某个，大致就是这样一个模型，可以自己画个地图看看&br&等等，你大概发现问题了，如果第一步到H和I都可以，第二步到P和Q都可以，那我每一步只选最优，不就用贪心得到结果了吗，没错，如果你需要经历的每个阶段状态跟决策无关，那就贪心得到结果好了，理解贪心了吗：）&br&&img src=&/2e92ec10acf_b.png& data-rawwidth=&503& data-rawheight=&106& class=&origin_image zh-lightbox-thumb& width=&503& data-original=&/2e92ec10acf_r.png&&&br&然而现实情况可能是，你第一步的选择会影响后面的分支，比如你第一步可以选择到H或I，但是到了H后，你只能选择经过P或Q到Z了，而如果到了I，你只能选择R或S到Z，这样一来，即便第一步到H或I你选择了较好的一条路，也不保证最终结果最优，因为比如你选了H，那万一I-R-Z的路要比H开始到Z的路径短了更多，最优路径可能是A-I-R-Z，所以你要把这些路都尝试一遍，才知道哪个最优，理解穷举了么？：）&br&&img src=&/f86b00eab3623_b.png& data-rawwidth=&393& data-rawheight=&207& class=&content_image& width=&393&&OK，我们稍微改下题设，假如从I出发不是到R和S，而是到Q或R，会如何&br&&img src=&/ced5f77fcf6aa3e31ea9dc1212cba7a3_b.png& data-rawwidth=&377& data-rawheight=&152& class=&content_image& width=&377&&诚然，我们可以用穷举每条路来解决这个问题，需要穷举的路径数和上面的图一样，但是，我们可以有更快的办法，你不用将A-H-Q-Z和A-I-Q-Z两条路单独计算，因为他们有状态交点，结合第一张图的思想，可以敏锐地感觉到，我们只需要计算到每个有共同状态的位置求各阶段的最优，最后每阶段选最优组合贪心组合起来就行，因为各阶段完成的状态点是大家都有的嘛，因此，咱们先计算A-H-Q和A-I-Q，选个最好的，然后跟Q到Z中最好的拼起来，就是最优了，没必要把所有路径都搞一遍（虽然图里面Q到Z直达，但你可以发挥想象力，将其想象成各种分支的一条复杂道路），这样一来就把一个x^(a+b+c+...)的计算次数降低为x^a+x^b+x^c...，其中x代表每次的决策次数（简单点假设每次决策次数都一样），abc代表每个阶段的步骤数&br&因此，我们可以从A开始，向Z进行BFS，并对BFS中每个点保存最优状态，如果有不同的路径BFS到了同一个点，留最好的一条就行，比如上面这个，你的算法可能先从A-H-Q搜到了Q这个位置，之后从A-I-Q又到了这里，留最好的一条，最后一轮从PQR三个点到Z，就结束了，相对第二章图要少一次运算&br&如果你理解了，恭喜你已经能有效解决很多需要DP的问题了，同时还学会了解图论的单源最短路径问题呢&br&&br&最后用经典的0-1背包问题做个例子，巩固一下吧，这个任务是，我们从N个物品选若干塞到可以承受最大重量W的包包里面，要价值最大，因此就可以将任务分成N个步骤，每个步骤面对第i号物品，决策有两条：选，还是放弃，这里的状态，就是影响之后步骤决策的因素，在这里，就是“背包的剩余空间”&br&比如，物品的重量是1,2,3,4,5,6，W=12，从头决策，0表示放弃，1表示选，BFS三次后有八种状态：&br&000 剩12&br&001 剩9&br&……（略）&br&110 剩9&br&……（略）&br&前三次步骤后，001和110到达了同样的状态，都是剩余可装重量9的东西，这样在剩下的决策中，这俩分支走的路都是一样的，跟你之前是选了001还是110没有任何关系（无后效性），因此只要看001价值大，还是110价值大就可以了，8个状态减少为7个，继续BFS下去，每一轮都合并同样状态，完成后，从最后一轮的所有状态中，找到价值最大的就ok了&br&由于状态最多有W+1个，进行N轮，因此复杂度O(NW)，书上说的状态迁移方程的办法其实跟这个过程很类似，不过对于有些题目，比起BFS+状态合并，状态方程的分析可以做更好的优化，如引入单调队列什么的，但BFS+状态合并可以让你得到一个没有追求极限但是也比较快的解决方案了，结合具体问题有时候更适合，比如根据问题的实际需求，搜索可以限界剪枝减少工作量，我在工作中就用过，替换了同事从wiki抄的DP算法，效率能提升一些&br&&br&============我是补充的分割线====================&br&&br&下午由于上班，写得比较仓促，已经有同学指出我的思路其实就是将问题转换为图中求路径，的确是这样的，这个做法虽然很多时候比教科书的状态转移方程做法稍慢，但一招就能覆盖很多问题，比如下面三道：&br&&a href=&///?target=https%3A//projecteuler.net/problem%3D81& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Problem 81 - Project Euler&i class=&icon-external&&&/i&&/a&&br&&a href=&///?target=https%3A//projecteuler.net/problem%3D82& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Problem 82 - Project Euler&i class=&icon-external&&&/i&&/a&&br&&a href=&///?target=https%3A//projecteuler.net/problem%3D83& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Problem 83 - Project Euler&i class=&icon-external&&&/i&&/a&&br&这三道题都是走矩阵，要求走过的节点的值的和最小，81是只能往右和往下，一眼就是DP，82是可以上下右，可以按列DP，83是上下左右都可以，就用不上DP了，然而用单源最短路径可以通杀&br&因为我从开始学算法就很懒，总是追求最少的招数解决尽量多的问题，在复杂度达到了也不太会尽量追求更快，所以ACM被虐很惨，刷题请慎用，也请OJ大神们轻拍：）&br&&br&可能关于“状态是怎么决定的”这个问题上面描述比较简略，就再补充一下，其实就是可能影响下一个步骤决策的因素，都是当前状态，比如上面的01背包，每次的决策是选或不选，但是如果剩余W已经不够了，就只剩下“不选”一条决策可用了，因此用剩余W来做状态&br&再比如这题：&br&&a href=&///?target=https%3A//projecteuler.net/problem%3D191& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Problem 191 - Project Euler&i class=&icon-external&&&/i&&/a&&br&抽象后其实是说：一个由L、O、A组成的长度为30的字符串，不能出现连续3个或以上的A，最多出现一个L，有多少个这样的字符串？&br&很明显需要30步决策，每次决策时候要从3个字母里面选合法的，O任何情况都合法，L在没出现过的情况下合法，A则在现有串最后不是AA时候合法，因此状态就是是否出现过L和最后两个字母中A的分布情况的一个组合，L是否出现有两个值，A的分布有**，A*，*A，AA四种（*代表O或L，不用展开了），所以就是2*4=8种状态啦&br&&br&最后留个小题，是以前做考官时候经常用的一道面试题，印象中有算法基础的同学六七成都能立即说“用DP”，然而一问状态转移就晕了^_^：&br&在约定的规则下，以数字数组的形式输入一手斗地主的牌，设计算法计算这手牌最少几把可以出完&br&注意这里只是用斗地主做个例子，不代表牌数限制为20张，可以看做是一个N个数字根据规则分组的问题，说斗地主是因为之前是做游戏行业的，而且面试时候这样说比较容易降低同学们的紧张度，同时也是一个暗示：大家都知道斗地主靠贪心法是得不到最优出牌顺序的吧，哈。。。
如果楼主不是为了竞赛刷题，可以先抛开书本上的什么状态转移方程什么的，可以教你一个民科点的思路O(∩_∩)O： 我们面对的是一个求最优解或统计之类的问题，这个问题基于“我们要模拟完成一个大任务”，这个大任务可以分成若干步骤，每个步骤有若干种决策，…
有很多例子可以参考。题主可以考虑参考斯坦福编译原理进阶课程 &a href=&///?target=http%3A//suif.stanford.edu/%7Ecourses/cs243/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&CS243&i class=&icon-external&&&/i&&/a& 的课程作业所用的框架 JoeQ。&br&CS243课程是Monica Lam上的，是龙书作者之一，而龙书也是这门课的教材，正好适合题主的情况；JoeQ则是Monica的得意门生之一的John Whaley设计并实现的。&br&&br&CS243课程堆JoeQ的介绍：&a href=&///?target=http%3A//suif.stanford.edu/%7Ecourses/cs243/joeq/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Intro to JoeQ&i class=&icon-external&&&/i&&/a&&br&相关课件：&a href=&///?target=http%3A//suif.stanford.edu/%7Ecourses/cs243/lectures/joeq_2016.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&suif.stanford.edu/~cour&/span&&span class=&invisible&&ses/cs243/lectures/joeq_2016.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&基于Joeq的数据流分析的作业：&a href=&///?target=http%3A//suif.stanford.edu/%7Ecourses/cs243/hw2/hw2.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&HW 2 | CS243&i class=&icon-external&&&/i&&/a&&br&JoeQ项目自身的网站：&a href=&///?target=http%3A//joeq.sourceforge.net/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&joeq virtual machine and compiler infrastructure&i class=&icon-external&&&/i&&/a&&br&&br&以原始的JoeQ（而不是CS243课程的改造版）为例，LivenessAnalysis在这里：&br&&a href=&///?target=https%3A//sourceforge.net/p/joeq/svn/HEAD/tree/trunk/joeq_core/joeq/Compiler/Dataflow/LivenessAnalysis.java& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&joeq virtual machine / SVN /
/trunk/joeq_core/joeq/Compiler/Dataflow/LivenessAnalysis.java&i class=&icon-external&&&/i&&/a&&br&它的transfer function是用bitvector形式做的：&a href=&///?target=https%3A//sourceforge.net/p/joeq/svn/HEAD/tree/trunk/joeq_core/joeq/Compiler/Dataflow/GenKillTransferFunction.java& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&sourceforge.net/p/joeq/&/span&&span class=&invisible&&svn/HEAD/tree/trunk/joeq_core/joeq/Compiler/Dataflow/GenKillTransferFunction.java&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&br&不过在非SSA形式上做数据流分析真的已经有点落后于潮流了。题主在了解完对非SSA形式如何做数据流分析之后，最好进一步学习一下如何在SSA形式上做数据流分析——或许会觉得人生整个都不一样了（逃&br&（在非SSA形式上做数据流分析就算现在当然还是有用的，例如说对内存里的值做数据流分析多少还是得用传统技巧）
有很多例子可以参考。题主可以考虑参考斯坦福编译原理进阶课程
的课程作业所用的框架 JoeQ。 CS243课程是Monica Lam上的，是龙书作者之一，而龙书也是这门课的教材，正好适合题主的情况；JoeQ则是Monica的得意门生之一的John Whaley设计并实现的。 CS…
&b&Go的GC完胜JVM GC？&/b&&br&&br&作为在2TB的GC堆上能维持在& 10ms GC暂停时间的Azul Systems的Zing JVM…&br&而且Zing JVM的C4 GC是一种完全并发的、会整理堆内存的GC（Fully Concurrent Mark-Compact GC），不但mark阶段可以是并发的，在整理（compaction）阶段也是并发的，所以在GC堆内不会有内存碎片化问题；而Go 1.5/1.6GC是一种部分并发的、不整理堆内存的GC（Mostly-Concurrent Mark-Sweep），虽然实现已经做了很多优化但终究还是能有导致堆内存碎片化的workload，当碎片化严重时Go GC的性能就会下降。&br&&br&简短回答是：不，Go 1.6的GC并没有在GC pause方面“完胜”JVM的GC。&br&&br&我们有实际客户在单机十几TB内存的服务器上把Zing JVM这2TB GC堆的支持推到了极限，有很多Java对象，外带自己写的基于NIO的native memory内存管理器，让一些Java对象后面挂着总共10TB左右的native memory，把这服务器的能力都用上了。在这样的条件下Zing JVM的GC还是可以轻松维持在& 5ms的暂停时间，根本没压力；倒是Linux上自带的glibc的ptmalloc2先“挂”了——它不总是及时归还从OS申请来的内存，结果把这没开swap的服务器给跑挂了…&br&（注意上面的单位都是TB。）&br&&br&Zing JVM的C4 GC跟其它JVM GC相比，最大的特征其实还不是它“不暂停”（或者说只需要暂停非常非常短的时间），而是它对运行的Java程序的特征不敏感，可以对各种不同的workload都保持相同的暂停时间表现。这样要放在前面强调，因为下面的讨论就要涉及workload了。&br&&br&后面再补充点关于Zing JVM的GC的讨论。先放几个传送门：&br&&ul&&li&&a href=&/question//answer/& class=&internal&&Azul Systems 是家什么样的公司？ - RednaxelaFX 的回答&/a&&br&&/li&&li&&a href=&/question//answer/& class=&internal&&Java 大内存应用（10G 以上）会不会出现严重的停顿？ - RednaxelaFX 的回答&/a&&br&&/li&&li&&a href=&/question//answer/& class=&internal&&C++ 短期内在华尔街的买方和卖方还是唯一选择吗？ - RednaxelaFX 的回答&/a&&br&&/li&&/ul&&br&要跟JVM比GC性能的话不要光看HotSpot VM啊。&br&&br&&b&Go的低延迟GC的适用场景和实际性能如何？&/b&&br&&br&其实很重要的注意点就是：每种GC都有自己最舒服的workload类型——Zing的C4 GC是少有的例外。&br&题主给的那张演示稿没有指出这benchmark测的是啥类型的workload，也没有说明这个workload运行了多长时间，这数据对各种不同情况到底有多少代表性还值得斟酌。最公平的做法是把benchmark用的Go程序移植到Java，然后用HotSpot VM的CMS GC也跑跑看，对比一下。&br&&br&作为一种CMS（&b&Mostly&/b&-Concurrent Mark-Sweep）GC实现，Go的GC最舒服的应用场景是当程序自身的分配行为不容易导致碎片堆积，并且程序分配新对象的速度不太高的情况。&br&&b&而如果遇到一个程序会导致碎片逐渐堆积，并且/或者程序的分配速度非常高的时候，Go的CMS就会跟不上，从而掉进长暂停的深渊。&/b&这就涉及到低延迟模式能撑多久多问题。&br&具体怎样的情况会导致碎片堆积大家有兴趣的话我回头可以来补充。主要是跟对象大小的分布、对象之间的引用关系的特征、对象生命期的特征相关的。&br&&br&这里让我举个跟Go没关系的例子来说明讨论这类问题时要小心的陷阱。&br&要评测JVM/JDK性能，业界有几个常用的标准benchmark，例如SPECjvm98 / SPECjvm2008，SPECjbb2005 / SPECjbb2013，DaCapo等。其中有不少benchmark都是，其声称要测试的东西，跟它实际运行中的瓶颈其实并不一致。&br&&br&SPECjbb2005就是个很出名的例子。JVM实现者们很快就发现，这玩儿实际测的其实是GC暂停时间——如果能避免在测试过程中发生full GC，成绩就会不错。于是大家一股脑的都给自己的GC添加启发条件，让JVM实现们能刚刚好在SPECjbb2005的测试时间内不发生full GC——但其实很多此类“调优”的真相是只要在多运行那么几分钟可能就要发生很长时间的full GC暂停了。&br&&br&所以说要讨论一个GC的性能水平如何，不能只靠看别人说在某个没有注明的workload下的表现，而是得具体看这个workload的特征、运行时间长度以及该GC的内部统计数据所表现出的“健康程度”再来综合分析。&br&&br&&b&Go CMS GC与HotSpot CMS GC的实现的比较&/b&&br&&br&Go GC目前的掌舵人是Richard L. Hudson大大，是个靠谱的人。&br&他之前就有过设计并发GC的经验，设计了Sapphire GC算法。&br&Sapphire: Copying GC Without Stopping the World&br&ftp://ftp.cs.umass.edu/pub/osl/papers/sapphire-2003.pdf&br&设计了并发Copying GC的他在Go里退回到用CMS感觉实属无奈。虽然&a href=&///?target=https%3A///golang/go/issues/12416& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&未来Go可能会尝试用能移动对象的GC&i class=&icon-external&&&/i&&/a&，在Go 1.5的时候它的GC还是不移动对象的，而外部跟Go交互的C代码也多少可能依赖了这个性质。要不移动对象做并发GC，最终就会得到某种形式的CMS。&br&&br&Go的CMS实现得比较细致的地方是它的pacing heuristics，或者说“并发GC的启动时机”。这是属于“策略”（policy）方面做得细致。HotSpot VM的CMS GC则这么多年来都没得到足够多的关爱，其实尚未发挥出其完全的能力，还有不少改进/细化的余地，特别是在策略方面。&br&而在“机制”（mechanism）方面，Go的CMS GC其实与HotSpot VM的CMS GC相比是非常相似的。都是只基于incremental update系write-barrier的&b&Mostly&/b&-Concurrent Mark-Sweep。两者的工作流程中最核心的步骤都是：&br&&ol&&li&Initial marking：扫描根集合&/li&&li&Concurrent marking：并发扫描整个堆&/li&&li&Re-marking：重新扫描在(2)的过程中发生了变化/可能遗漏了的引用&/li&&li&Concurrent sweeping&/li&&/ol&具体到实现，两者在上述核心工作流程上有各自不同的扩展/优化。&br&&br&两者的(1)都是stop-the-world的，这是两者的GC暂停的主要来源之一。&br&HotSpot VM的CMS GC的(3)也是stop-the-world的，而且这个暂停还经常比(1)的暂停时间要更长；Go 1.6 CMS GC则在此处做了比较细致的实现，尽可能只一个个goroutine暂停而不全局暂停——只要不是全局暂停都不算在用户关心的“暂停时间”里，这样Go版就比HotSpot版要做得好了。&br&（无独有偶，Android Runtime（ART）也有一个CMS GC实现，而它也选择了把上述两种暂停中的一个变为了每个线程轮流暂停而不是全局暂停，不过它是在(1)这样做的，而不是在(3)——这是Android 5.0时的状况。新版本我还没看）&br&&br&HotSpot版CMS对(3)的细化优化是，在真正进入stop-the-world的re-marking之前，先尝试做一段时间的所谓并发的“abortable concurrent pre-cleaning”，尝试并发的追赶应用程序对引用关系的改变，以便缩短re-marking的暂停时间。不过这里实现得感觉还不够好，还可以继续改进的。&br&&br&有个有趣的细节，Go版CMS在(3)中重新扫描goroutine的栈时，只需要扫描靠近栈顶的部分栈帧，而不需要扫描整个栈——因为远离栈顶的栈帧可能在(2)的过程中根本没改变过，所以可以做特殊处理；HotSpot版CMS在(3)中扫描栈时则需要重新扫描整个栈，没抓住机会减少扫描开销。Go版CMS就是在众多这样的细节上比HotSpot版的更细致。&br&&br&再举个反过来的细节。目前HotSpot VM里所有GC都是分代式的，CMS GC在这之中属于一个old gen GC，只收集old gen；与其配套使用的还有专门负责收集young gen的Parallel New GC（ParNew），以及当CMS跟不上节奏时备份用的full GC。分代式GC很自然的需要使用write barrier，而CMS GC的concurrent marking也需要write barrier。HotSpot VM就很巧妙的把这两种需求的write barrier做在了一起，共享一个非常简单而高效的write barrier实现。&br&Go版CMS则需要在不同阶段开启或关闭write barrier，实现机制就会稍微复杂一点点，write barrier的形式也稍微慢一点点。&br&&br&从效果看Go 1.6的CMS GC做得更好，但HotSpot VM的CMS GC如果有更多投入的话也完全可以达到一样的效果；并且，得益于分代式GC，HotSpot VM的CMS GC目前能承受的对象分配速度比Go的更高，这算是个优势。&br&&br&（待续）
Go的GC完胜JVM GC？ 作为在2TB的GC堆上能维持在& 10ms GC暂停时间的Azul Systems的Zing JVM… 而且Zing JVM的C4 GC是一种完全并发的、会整理堆内存的GC（Fully Concurrent Mark-Compact GC），不但mark阶段可以是并发的，在整理（compaction）阶段也是并发…
已有帐号？
无法登录？
社交帐号登录
141 人关注
4461 条内容
165 人关注
5825 人关注
249 条内容
988 人关注
334 条内容
643 人关注
199 条内容