Oenhan Google Reader

    Oen 通过 Google 阅读器发送给您的内容：     gdb的基本工作原理是什么？ 于 10-10-28 通过 SpongeLiu的blog 作者：sponge 还是面某M的时候，面试官问我："用过gdb么？" 答："用过，调了两年bug了"。"那好，给我解释下gdb是怎么工作的？或者说跟内核什么地方有关系？"。 是阿， gdb凭什么可以调试一个程序？凭什么能够接管一个程序的运行？ 我以前也想过这样的问题，但是后来居然忘记去查看了。我想到了我们的二进制翻译器，想到了intel的pin，Dynamo。这些都是将翻译后的代码放到codecache中去运行，然后接管整个程序的执行。gdb是不是也一样呢？ 如果真是这样，为什么我记得用gdb跑一个程序，这个程序会有一个单独的进程？gdb的attach功能又是怎么实现的？ 想了想，我还是没有答上来。面试就是由这么一个又一个细节的小杯具最后汇集成一个大杯具。 那么，gdb到底是凭什么接管的一个进程的执行呢？其实，很简单， 通过一个系统调用：ptrace 。ptrace系统调用的原型如下： #include <sys/ptrace.h>   long ptrace ( enum __ptrace_request request , pid_t pid , void * addr , void * data ) ; 说明：ptrace系统调用提供了一种方法来让父进程可以观察和控制其它进程的执行，检查和改变其核心映像以及寄存器。 主要用来实现断点调试和系统调用跟踪。（man手册） 其实，说到这里，一切原理层面应该都比较明朗了（且先不去管内核中是怎么实现ptrace的）。gdb就是调用这个系统调用，然后通过一些参数来控制其他进程的执行的。 下面我们来看ptrace函数中request参数的一些主要选项： PTRACE_TRACEME： 表示本进程将被其父进程跟踪，交付给这个进程...

    Oen 通过 Google 阅读器发送给您的内容：     字符串匹配的Boyer-Moore算法 于 13-5-2 通过 阮一峰的网络日志 上一篇文章，我介绍了 KMP算法 。 但是，它并不是效率最高的算法，实际采用并不多。各种文本编辑器的"查找"功能（Ctrl+F），大多采用 Boyer-Moore算法 。 Boyer-Moore算法不仅效率高，而且构思巧妙，容易理解。1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。 下面，我根据Moore教授自己的 例子 来解释这种算法。 1. 假定字符串为"HERE IS A SIMPLE EXAMPLE"，搜索词为"EXAMPLE"。 2. 首先，"字符串"与"搜索词"头部对齐，从尾部开始比较。 这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符肯定不是要找的结果。 我们看到，"S"与"E"不匹配。这时， "S"就被称为"坏字符"（bad character），即不匹配的字符。 我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。 3. 依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在搜索词"EXAMPLE"之中。所以，将搜索词后移两位，两个"P"对齐。 4. 我们由此总结出 "坏字符规则" ： 　　后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置 如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。 以"P"为例，它作为"坏字符"，出现在搜索词的第6位（从0开...

    Oen 通过 Google 阅读器发送给您的内容：     字符串匹配的KMP算法 于 13-5-1 通过 阮一峰的网络日志 字符串匹配 是计算机的基本任务之一。 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ 许多算法可以完成这个任务， Knuth-Morris-Pratt算法 （简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。 这种算法不太容易理解，网上有很多 解释 ，但读起来都很费劲。直到读到 Jake Boxer 的文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。 1. 首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。 2. 因为B与A不匹配，搜索词再往后移。 3. 就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。 4. 接着比较字符串和搜索词的下一个字符，还是相同。 5. 直到字符串有一个字符，与搜索词对应的字符不相同为止。 6. 这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。 7. 一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。 8. 怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。 9. 已知空格与D不匹配时，前...

    Han 通过 Google 阅读器发送给您的内容：     关于缓存（上） 于 13-4-24 通过 搜索技术博客－淘宝 作者：liaoran 缓存概述 商业世界中常说的一句话是"现金为王"。在技术世界里，与之相近的一个说法是"缓存为王"。 缓存在构建高性能web站点中有着举足轻重的作用， sql优化， 算法优化所带来的效果可能远远不如缓存带来的优化效果。但是缓存的使用并不是零成本的，首先的一个问题是，任何缓存的增加，都会带来两大问题： 数据不一致。 系统复杂度大幅度增加。 解决这两个问题需要以下一些方法，首先是去掉缓存。不要为了用缓存而用缓存，缓存不必要时，应该果断去掉，从而降低系统出错的可能性，降低系统复杂度。有些对数据实时性，准确性要求极高的系统，不能使用缓存。其次是分析需求，不同的业务会有不同的缓存策略，仔细分析变化与不变的数据，将不变的数据长时间缓存，变化的数据根据数据的业务意义和实时性要求动态调整缓存时间和存储方式。最后就是增加开发人员自身的能力，后面会详细提及各种问题的处理方法。 关于缓存的设计其实也脱离不了计算机基本的设计思想。数据结构与算法是计算机软件设计永恒的主题，算法的优劣需要考虑算法的时间和空间复杂度。多数优秀的算法都采用空间换时间的方式。涉及到缓存也不例外，缓存的设计需要考虑缓存的占用空间和命中率。我们当然希望缓存占用空间小，命中率高。命中率高是缓存设计的重要考察因素， 是提高系统性能的关键。占用空间越小，需要的成本越低。低成本，高效能的缓存设计是我们追求的目标。这没有固定的设计方法和公式，需要根据不同的业务灵活调整，但是，关于缓存在业务开发中的设计方法，有一些比较常用的思路与模式，借鉴这些模式，我们可以复用或创新，解决新的业务中所出现的问题，下面我就简单总结一些常用的缓存设计方法和应用场景，抛砖引玉，希望能对以后的开发有所帮助。 缓存不可变对象的复杂计算 第一个简单的缓存方式叫做缓存不可变对象的复...

    Han 通过 Google 阅读器发送给您的内容：     google group varint 无损压缩解压算法的高效实现 改进版 于 13-4-17 通过 搜索技术博客－淘宝 作者：野王 之前实现了一个版本: google group varint 无损压缩解压算法的高效实现 近期对其进行了一次改进，性能提升 20%，测试数据如下： 压缩和解压 100万个整数 (4M) 新版本： encode time consumed: 0.003252 s ; decode time consumed: 0.003769 s 老版本： encode time consumed: 0.005198 s ; decode time consumed: 0.004909 s 这样 1秒钟 能解压 1G 的数据，够惊人的吧 不废话，上代码， 有兴趣的自己看，如果我的注释不够清晰，请联系我修改 /****************************************************************** * Created on: 2011-4-26 * Author: yewang@taobao.com clm971910@gmail.com * * Desc : 提供uint32的 varint 压缩和解压功能 * 提供group varint的高效实现 * ******************************************************************/ #ifndef VARI...

    Han 通过 Google 阅读器发送给您的内容：     Lua 5.2.2 中的一处 Bug 于 13-4-18 通过 云风的 BLOG 作者：云风 前几天, Lua 5.2.2 发布了, 主要是修复了 4 个 Lua 5.2.1 中已知的 bug . 其中包括前段时间一个同学和我在 email 交流中讨论的一个问题. 我把 Lua 5.2.2 更新到公司项目的主干上，同时需要对我的那本 《 Lua 源码欣赏 》做一些更新，需要把这次的代码更改同步到书里去。这个工作很繁琐，但有它的价值。比如我发现了 Lua 5.2.2 比 5.2.1 的更改远不只官方宣布了 4 处 bugfix ，还有一些小调整，让 Lua 的源码更规整一些。 阿楠同学因为这段时间一直在维护 UniLua 这个 C# 版的 Lua 项目，我就随便和他通告了一下这次的一些代码变更，方便他同步到 UniLua 项目中去。 讨论之中，他提到 luaD_precall 函数的实现有些诡异之处，没有看明白。我顺着他指出的位置又仔细阅读了一下，果然发现这里存在一个隐藏很深的 Bug 。 准确说，这不是 Lua 5.2 引入的新 Bug ， 至少在 Lua 5.1 年代就存在了。只不过很难触碰到触发条件。 理解了代码后，我构造了一小段 Lua 代码，可以让 Bug 暴露出来。 function f(p1,p2,p3,p4,p5,p6,p7,p8,p9,...) local a1,a2,a3,a4,a5,a6,a7 local a8,a9,a10,a11,a12,a13,a14 end f() 运行这段 Lua 代码会让 Lua 虚拟机崩溃。我的修复 patch 如下： diff --git a/src/ldo.c b/src/ldo.c index aafa3dc..a901e6c 100644 --- a/src/ldo.c +++ b/src/ldo.c @@ -324,7 +324,7 @@ int luaD_...

    Han 通过 Google 阅读器发送给您的内容：     为什么你写不好一个快速排序? 谈程序员的职业发展 于 13-4-10 通过 A programmer's life 我常常在想，当初我若不离开完美，现在肯定也是总监级的title了，收入比现在高一倍不止。但是另一方面，在编码能力上我甚至不如某些刚毕业的本科生。比如，快速排序的算法我很熟悉，就一句话："随机选一个元素，用它把输入集分成两半，对这两半继续递归，然后将递归得到（已排好序）的结果合并"。但几个月前看算法书的时候自己尝试写了一下快速排序，发现远远是另外一回事。虽然我对这个算法很清楚，但是用C++实现的时候充满了疑惑，写出来的代码BUG很多，调了很久才调对。相反，如果拿这个做面试题去面应届生，我相信对北大清华的学生通过率应该很高，至少过半。那么我比他们多了6-7年的工作经验，这些经验又是什么呢？ 工作经验是人生最容易积攒的财富，只增不减。钱和不动资产，差不多也是如此。所以要想向年轻人炫耀成功项目，牛B的经历，是很容易的事情。在一个很好的平台上，与聪明的人共事，顺水推舟，再加上运气不是太差的话，工作3-5年后，必然会有一个值得吹嘘的项目。比如我就老喜欢说我第一次做游戏就带着人做了梦诛，在线多少万多少万，等等。 但是呢，对一个程序员来说，最核心的价值是什么？是快速的把想法，变成无bug的正确代码的能力。像前面提到的快速排序，如果需求已经很明确，怎么实现已经很清楚， 语言你自己选， 工具你随便挑。20分钟内代码写不出来，写不对，那就自己的问题，水平差。 我之前走了一条弯路，听信软件工程的人说，不要重复造轮子。于是就忽视了这些基础训练。" 不要重复造轮子"这句话在公司里是对的，但是在下班后，或是在学校，在自己写代码练手的时候，就绝对是错的。重写那些经典的算法，是绝佳的思维练习。写二分查找的时候，需要根据区间的长度是奇数还是偶数，判断结...