Tag Archives: 优化

定点数这玩意儿并不是什么新东西，早年 CPU 浮点性能不够，定点数技巧大量活跃于各类图形图像处理的热点路径中。今天 CPU 浮点上来了，但很多情况下整数仍然快于浮点，因此比如：libcario (gnome/quartz 后端）及 pixman 之类的很多库里你仍然找得到定点数的身影。那么今天我们就来看看使用定点数到底能快多少。 简单用一下的话，下面这几行宏就够了： #define cfixed_from_int(i) (((cfixed)(i)) << 16) #define cfixed_from_float(x) ((cfixed)((x) * 65536.0f)) #define cfixed_from_double(d) ((cfixed)((d) * 65536.0)) #define cfixed_to_int(f) ((f) >> 16) #define cfixed_to_float(x) ((float)((x) / 65536.0f)) #define cfixed_to_double(f) ((double)((f) / 65536.0)) … Continue reading →

真金不怕火炼，我先前在《C 语言有什么奇技淫巧？》中给出的整数快速除以 255 的公式： #define div_255_fast(x) (((x) + (((x) + 257) >> 8)) >> 8) 有人觉得并没有快多少，还给出了测试： 红色为 255 快除法的消耗时间，看他的测试好像也只快了那么一点，是这样的么？ 并非如此，我们只要把测试用例中的 long long j 改成 int j 就有比较大的性能提升了： 链接：http://quick-bench.com/t3Y2-b4isYIwnKwMaPQi3n9dmtQ 这才是真实的快除法性能。 原评测的作者其他地方都是用 int ，这里故意改成 64 位去和原始的 / 255 对齐，引入一个干扰项，得到一个比较慢的结果，到底是为了黑而黑呢？还是别的什么原因？ 编译器生成的 / 255 … Continue reading →

C 语言的魔法数不胜数，我在《C 语言有什么奇技淫巧？》中过给快速范围判断的公式，将： if (x >= minx && x <= maxx) … 改做： if (((x – minx) | (maxx – x)) >= 0) … 能有一倍的性能提升，我也提到，如果你的数据 99% 都是超出范围的那继续用 && 最快。今天再给大家介绍另外一种新写法，它有更均衡的性能，并且在最坏的情况下，任然表现良好： if ((unsigned)(x – minx) <= (unsigned)(maxx – minx)) … 该公式在各种测试数据中能有更均衡的表现，类型安全狂们可以写作： if … Continue reading →

C 语言的技巧有很多，列一些和性能有关的： 快速范围判断 经常要批量判断某些值在不在范围内，如果 int 检测是 [0, N) 的话： if (x >= 0 && x < N) … 众所周知，现代 CPU 优化，减分支是重要手段，上述两次判断可以简写为： if (((unsigned int)x) < N) … 减少判断次数。如果 int 检测范围是 [minx, maxx] 这种更常见的形式的话，怎么办呢？ if (x >= minx && x <= … Continue reading →

今天继续在原来内存拷贝代码上优化： 1. 修改了小内存方案：由原来64字节扩大为128字节，由 int 改为 xmm，小内存性能提升 80% 2. 修改了中内存方案：从4个xmm寄存器并行拷贝改为8个并行拷贝+prefetch，提升20%左右 3. 去除目标地址头部对齐的分支判断，用一次xmm拷贝完成目标对齐，性能替升10%。 4. 增加测试用例：为贴近实际，增加了随机访问，10MB空间内（绝对大于L2尺寸）随机位置和长度的测试 为避免随机数生成影响结果，提前生成随机数，最终平均性能达到gcc4.9配套标准库的2倍以上： https://github.com/skywind3000/FastMemcpy 最新代码测试结果（可以对比老的表看新版本性能是否有所提升）：

四年前写过一篇小内存拷贝优化：http://www.skywind.me/blog/archives/143 纠结了一下还是把全尺寸拷贝优化代码发布出来吧，没啥好保密的， 如今总结一下全尺寸内存拷贝优化的要点： 1. 策略区别：64字节以内用小内存方案，64K以内用中尺寸方案，大于64K用大内存拷贝方案。 2. 查表跳转：拷贝不同小尺寸内存，直接跳转到相应地址解除循环。 3. 目标对齐：64字节以上拷贝的先用普通方法拷贝几个字节让目标地址对齐，好做后面的事情。 4. 矢量拷贝：并行一次性读入N个矢量到 sse2 寄存器，再并行写出。 5. 缓存预取：使用 prefetchnta ，提前预取数据，等到真的要用时数据已经到位。 6. 内存直写：使用 movntdq 来直写内存，避免缓存污染。   部分理论，见论文：《Using Block Prefetch for Optimized Memory Performance》   但论文考虑问题比较单一，所以实际代码写的比论文复杂不少，目前在各个尺寸上基本平均能够加速 40%，比较GCC 4.9, VS2012的 memcpy，不排除未来的 libc, crt库继续完善以后，能够达到下面代码的速度。但我看libc和crt的 memcpy代码已经很久没人更新了，不知道他们还愿意继续优化下去么？ 行了，具体实现各位读代码吧，需要 SSE2 … Continue reading →

通常工程里不推荐自己写内存分配器，因为你费力写一个出来99%可能性没有内置的好，且内存出bug难调试 不过看书之余，你也可以动手自己试试，当个玩具写写玩玩： 1. 实现教科书上的内存分配器： 做一个链表指向空闲内存，分配就是取出一块来，改写链表，返回，释放就是放回到链表里面，并做好归并。注意做好标记和保护，避免二次释放，还可以花点力气在如何查找最适合大小的内存快的搜索上，减少内存碎片，有空你了还可以把链表换成伙伴算法，写着玩嘛。 2. 实现固定内存分配器： 即实现一个 FreeList，每个 FreeList 用于分配固定大小的内存块，比如用于分配 32字节对象的固定内存分配器，之类的。每个固定内存分配器里面有两个链表，OpenList 用于存储未分配的空闲对象，CloseList用于存储已分配的内存对象，那么所谓的分配就是从 OpenList 中取出一个对象放到 CloseList 里并且返回给用户，释放又是从 CloseList 移回到 OpenList。分配时如果不够，那么就需要增长 OpenList：申请一个大一点的内存块，切割成比如 64 个相同大小的对象添加到 OpenList中。这个固定内存分配器回收的时候，统一把先前向系统申请的内存块全部还给系统。 3. 实现 FreeList 池： 在你实现了 FreeList的基础上，按照不同对象大小（8字节，16字节，32，64，128，256，512，1K。。。64K），构造十多个固定内存分配器，分配内存时根据内存大小查表，决定到底由哪个分配器负责，分配后要在头部的 header 处（ptr[-sizeof(char*)]处）写上 cookie，表示又哪个分配器分配的，这样释放时候你才能正确归还。如果大于64K，则直接用系统的 malloc作为分配，如此以浪费内存为代价你得到了一个分配时间近似O（1）的内存分配器，差不多实现了一个 memcached 的 slab 内存管理器了，但是先别得意。此 slab 非彼 … Continue reading →