Random Posts
Tags
Categories
Recent Comments
- 小肥 on GDB 从裸奔到穿戴整齐
- flandre on 异步事件模型的 Self-pipe trick
- inv on 异步事件模型的 Self-pipe trick
- skywind on 异步事件模型的 Self-pipe trick
- skywind on 异步事件模型的 Self-pipe trick
Links
Meta
Category Archives: 编程技术
基础优化-最不坏的哈希表
哈希表性能优化的方法有很多，比如： 使用双 hash 检索冲突 使用开放+封闭混合寻址法组织哈希表 使用跳表快速定位冲突 使用 LRU 缓存最近访问过的键值，不管表内数据多大，短时内访问的总是那么几个 使用更好的分配器来管理 key_value_pair 这个节点对象 上面只要随便选两条你都能得到一个比 unordered_map 快不少的哈希表，类似的方法还有很多，比如使用除以质数来归一化哈希值（x86下性能最好，整数除法非常快，但非x86就不行了，arm还没有整数除法指令，要靠软件模拟，代价很大）。 哈希表最大的问题就是过分依赖哈希函数得到一个正态分布的哈希值，特别是开放寻址法（内存更小，速度更快，但是更怕哈希冲突），一旦冲突多了，或者 load factor 上去了，性能就急剧下降。 Python 的哈希表就是开放寻址的，速度是快了，但是面对哈希碰撞攻击时，挂的也是最惨的，早先爆出的哈希碰撞漏洞，攻击者可以通过哈希碰撞来计算成千上万的键值，导致 Python / Php / Java / V8 等一大批语言写成的服务完全瘫痪。 后续 Python 推出了修正版本，解决方案是增加一个哈希种子，用随机数来初始化它，这都不彻底，开放寻址法对hash函数的好坏仍然高度敏感，碰到特殊的数据，性能下降很厉害。 经过最近几年的各种事件，让人们不得不把目光从“如何实现个更快的哈希表”转移到 “如何实现一个最不坏的哈希表”来，以这个新思路重新思考 hash 表的设计。 哈希表定位主要靠下面一个操作： index_pos = hash(key) … Continue reading
AVL/RBTREE 实际比较
网上对 AVL被批的很惨，认为性能不如 rbtree，这里给 AVL 树平反昭雪。最近优化了一下我之前的 AVL 树，总体跑的和 linux 的 rbtree 一样快了： 他们都比 std::map 快很多（即便使用动态内存分配，为每个新插入节点临时分配个新内存）。 项目代码在：skywind3000/avlmini 其他 AVL/RBTREE 评测也有类似的结论，见：STL AVL Map 谣言1：RBTREE的平均统计性能比 AVL 好 统计下来一千万个节点插入 AVL 共旋转 7053316 次（先左后右算两次），RBTREE共旋转 5887217 次，RBTREE看起来少是吧？应该很快？但是别忘了 RBTREE 再平衡的操作除了旋转外还有再着色，每次再平衡噼里啪啦的改一片颜色，父亲节点，叔叔，祖父，兄弟节点都要访问一圈，这些都是代价，再者平均树高比 AVL 高也成为各项操作的成本。 谣言2：RBTREE 一般情况只比 AVL 高一两层，这个代价忽略不计 纯粹谣言，随便随机一下，一百万个节点的 RBTREE … Continue reading
如何实现一个真正高性能的spin_lock？
应用层用spinlock的最大问题是不能跟kernel一样的关中断（cli/sti），假设并发稍微多点，线程1在lock之后unlock之前发生了时钟中断，一段时间后才会被切回来调用unlock，那么这段时间中另一个调用lock的线程不就得空跑while了？这才是最浪费cpu时间的地方。所以不能关中断就只能sleep了，怎么着都存在巨大的冲突代价。 尤其是多核的时候，假设 Kernel 中任务1跑在 cpu1上，任务 2跑在 cpu2上，任务1进入lock之前就把中断关闭了，不会被切走，调用unlock的时候，不会花费多少时间，cpu2上的任务2在那循环也只会空跑几个指令周期。 看看 Kernel 的 spinlock: #define _spin_lock_irq(lock) \ do { \ local_irq_disable(); \ preempt_disable(); \ _raw_spin_lock(lock); \ __acquire(lock); \ } while (0) 看到里面的 local_irq_disable() 了么？实现如下： #define local_irq_disable() \ __asm__ __volatile__(“cli”: : :”memory”) 倘若不关闭中断，任务1在进入临界区的时候被切换走了，50ms以后才能被切换回来，即使原来临界区的代码只需要0.001ms就跑完了，可cpu2上的任务2还会在while那里干耗50ms，所以不能禁止中断的话只能用 sleep来避免空跑while浪费性能。 … Continue reading
为何很多 C++开源库都爱自己实现 string？
C++ 不是号称不限制你的开发方式么，每个库想怎么搞就怎么搞，这明明就是 C++的优势，不知道大家抱怨个啥？哈哈 接着说 std::string 的性能问题，举个具体例子吧，之前接手过一个项目，别的部门同事自己撸的一套 DirectUI 系统，用 tinyxml 解析界面节点，项目简单的时候没啥，随着ui越来越复杂，数千个节点，每个xml节点若干属性，每个属性就是一个字符串，我记得好像有500+ KB的 xml要解析，而且这部分界面还没法延迟初始化，必须启动加载时做完，启动十分慢。profile下来，很多时间卡在 tinyxml上，整个过程接近 3秒，费时最前的操作卡在处理各种字符串的操作上。 把 tinyxml 换成其他 xml库 ？没那么容易，项目各处模块都在依赖 tinyxml的各种接口和类。一开始觉得内部的 TiXmlString 实现有问题，换成 std::string，vc 2012下时间从3秒增加到4秒，更不靠谱（vs2012应该已经有所谓SSO了），所以人家 tinyxml 这里用自己的 TiXmlString 肯定也是比较过的，不然干嘛不用 std::string 。
学习视频编解码知识需要哪些前置知识？
如果要随便学学，便于日后使用那花两个星期买本书，配合网上文章就行了。 如果你想自己动手改 x264，为其添加一些你想要的东西，那么下面步骤你得耐心走完： 1: JPEG编码不但要学，还要自己实现，这是图像编码的基础，理解下yuv, dct, 量化，熵编码（不用参考 libjpeg，太庞大，建议参考 tinyjpeg.c，单文件） 2: MPEG2编码要学，现代编码器都是 block based 的，而 block based编码器的祖先就在MPEG2，理解下帧内编码，帧间预测，运动矢量，残差图等基础概念。具体代码可以看早期版本的 ffmpeg 的 avcodec，比如 mpeg12enc.c 代码也就1000多行，容易看，不过其中牵扯很多ffmpeg的内部数据结构，比如 picture, DCTELEM，各种 table，bitstream，vlc, swscale 等公共模块，缺点是文档少，优点是读了这些对你读其他 ffmpeg代码有帮助。 3: 自己实现一个类 MPEG2 编码器，最好自己从头实现个编码器，具体实现方式可以参考我的上面提到的 “视频编码技术简介”。 4: 参照 MPEG2的原理阅读 h.264的相关文章和书籍，了解和MPEG2的异同，比如先从intra入手，并且阅读 x264的早期版本代码，比如 2005年的版本，重点阅读 common 目录，基本的数据结构都在那里了，基本的图像，宏块，预测等都在那里了，阅读完以后阅读 … Continue reading
如何写一个视频编码器演示篇
先前写过《视频编码原理简介》，有朋友问光代码和文字不太真切，能否补充几张图片，今天我们演示一下： 这是第一帧画面：P1（我们的参考帧） 这是第二帧画面：P2（需要编码的帧） 从视频中截取的两张间隔 1-2 秒的画面，和实际情况类似，下面我们参考 P1 进行几次运动搜索： 搜索演示1：搜索 P2 中车辆的车牌在 P1 中最接近的位置（上图 P1，下图 P2） 这是一个演示程序，鼠标选中 P2 上任意 16×16 的 Block，即可搜索出 P1 上的 BestMatch 宏块。虽然车辆在运动，从远到近，但是依然找到了最接近的宏块坐标。 （点击 more 阅读剩下内容）
内存拷贝优化（3）-深入优化
今天继续在原来内存拷贝代码上优化： 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 最新代码测试结果（可以对比老的表看新版本性能是否有所提升）：
内存拷贝优化（2）-全尺寸拷贝优化
四年前写过一篇小内存拷贝优化：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