提高特征码扫描效率的一些个人经验(zz)

• 应该从算法的角度来改进，不要寄希望于通过内嵌汇编或用汇编改写来达到目的。举个例子：一个O(n*n*n)的算法肯定比O(n)的慢，除非数据 量很小，否则无论怎么用汇编优化都不可能快到哪里去。不过有一种例外：流水线UV管道的汇编优化，主要要考虑如何让指令不阻塞地并行处理。不过笔者最后还 是不推荐汇编优化，因为这给引擎的移植带来了困难。 
• 算法可以考虑用KMP、BM…… 
• 用以上的算法有局限性：当特征数多了以后，效率会直线下降，这是因为它们无法并行处理，这时可以考虑用AC-BM算法或DFA（确定有限自动机），但AC-BM算法、DFA的缺点是建库很麻烦。 
• 当使用hash的时候，原则是：第一，优先使特征离散开来；第二，尽可能使用简单的hash函数，越简单越好，因为hash函数参与计算的量是很 大的；第三，尽可能不使用mod操作，因为这个跟除法一样耗费时间；第四，hash的效率其实是不稳定的（取决于特征被离散的程度），想办法消除这个不稳 定值。 
• 多线程或多实例我认为是不必要的，因为当算法足够高效（或足够低效）的时候，CPU占用率往往已经超过了90%，这意味着已经没有多余的CPU资源来进行额外的加速了。但多核除外。
  
• 最后一点：考虑通过CPU的缓存机制来提高效率，我记得Intel的L2 cache貌似是64KB，AMD的L2 cache貌似是512KB（N年没关注过了，肯定不准，请CPU爱好者自行google），因此算法的关键部分所需要的空间复杂度最好不要超过这个大小。