Archive

Archive for the ‘编程技术’ Category

基础优化-最不坏的哈希表

December 8th, 2017 No comments

哈希表性能优化的方法有很多,比如:

  • 使用双 hash 检索冲突
  • 使用开放+封闭混合寻址法组织哈希表
  • 使用跳表快速定位冲突
  • 使用 LRU 缓存最近访问过的键值,不管表内数据多大,短时内访问的总是那么几个
  • 使用更好的分配器来管理 keyvaluepair 这个节点对象

上面只要随便选两条你都能得到一个比 unordered_map 快不少的哈希表,类似的方法还有很多,比如使用除以质数来归一化哈希值(x86下性能最好,整数除法非常快,但非x86就不行了,arm还没有整数除法指令,要靠软件模拟,代价很大)。

哈希表最大的问题就是过分依赖哈希函数得到一个正态分布的哈希值,特别是开放寻址法(内存更小,速度更快,但是更怕哈希冲突),一旦冲突多了,或者 load factor 上去了,性能就急剧下降。

Python 的哈希表就是开放寻址的,速度是快了,但是面对哈希碰撞攻击时,挂的也是最惨的,早先爆出的哈希碰撞漏洞,攻击者可以通过哈希碰撞来计算成千上万的键值,导致 Python / Php / Java / V8 等一大批语言写成的服务完全瘫痪。

后续 Python 推出了修正版本,解决方案是增加一个哈希种子,用随机数来初始化它,这都不彻底,开放寻址法对hash函数的好坏仍然高度敏感,碰到特殊的数据,性能下降很厉害。

经过最近几年的各种事件,让人们不得不把目光从“如何实现个更快的哈希表”转移到 “如何实现一个最不坏的哈希表”来,以这个新思路重新思考 hash 表的设计。

哈希表定位主要靠下面一个操作:

index_pos = hash(key) % index_size;

来决定一个键值到底存储在什么地方,虽然 hash(key) 返回的数值在 0-0xffffffff 之前,但是索引表是有大小限制的,在 hash 值用 index_size 取模以后,大量不同哈希值取模后可能得到相同的索引位置,所以即使哈希值不一样最终取模后还是会碰撞

第一种思路是尽量避免冲突,比如双哈希,比如让索引大小 index_size 保持质数式增长,但是他们都太过依赖于哈希函数本身;所以第二种思路是把注意力放在碰撞发生了该怎么处理上,比如多层哈希,开放+封闭混合寻址法,跳表,封闭寻址+平衡二叉树。

优化方向

今天我们就来实现一下最后一种,也是最彻底的做法:封闭寻址+平衡二叉树,看看最终性能如何?能否达到我们的要求?实现起来有哪些坑?其原理简单说起来就是,将原来封闭寻址的链表,改为平衡二叉树:

传统的封闭寻址哈希表,也是 Linux / STL 等大部分哈希表的实现,碰到碰撞时链表一长就挂掉,所谓哈希表+平衡二叉树就是:

将原来的链表(有序或者无序)换成平衡二叉树,这是复杂度最高的做法,同时也是最可靠的做法。发生碰撞时能将时间复杂度由 O(N) 降低到 O(logN),10个节点,链表的复杂度就是 10,而使用平衡二叉树的复杂度是 3;100个节点前者的时间是100,后者只有6.6 越往后差距约明显。

面临问题

树表混合结构(哈希表+平衡二叉树)的方法,Hash table – Wikipedia 上面早有说明,之所以一直没有进入各大语言/SDK的主流实现主要有四个问题:

  • 比起封闭寻址(STL,Java)来讲,节点少时,维持平衡(旋转等)会比有序链表更慢。
  • 比起开放寻址(python,v8实现)来讲,内存不紧凑,缓存不够友好。
  • 占用更多内存:一个平衡二叉树节点需要更多指针。
  • 设计比其他任何哈希表都要复杂。

所以虽然早就有人提出,但是一直都是一个边缘方法,并未进入主流实现。而最近两年随着各大语言暴露出来的各种哈希碰撞攻击,和原有设计基本无力应对坏一些的情况,于是又开始寻求这种树表混合结构是否还有优化的空间。

先来解决第一个问题,如果二叉树节点只有3-5个,那还不如使用有序链表,这是公认的事实,Java 8 最新实现的树表混合结构里,引入了一个 TREEIFY_THRESHOLD = 8 的常量,同一个索引内(或者叫同一个桶/slot/bucket内),冲突键值小于 8 的,使用链表,大于这个阈值时当前 index 内所有节点进行树化操作(treeify)。

Java 8 靠这个方法有效的解决了第一个问题和第三个问题,最终代替了原有 java4-7 一直在使用的 HashMap 老实现,那么我们要使用 Java 8 的方法么?

不用,今天我们换种实现。

Read more…

Categories: 编程技术 Tags:

AVL/RBTREE 实际比较

December 8th, 2017 No comments

网上对 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 树高27,和一千万个节点的 AVL树相同,而一千万个节点的 RBTREE 树高 33,比 AVL 多了 6 层,这还不是最坏情况,最坏情况 AVL 只有 1.440 * log(n + 2) – 0.328, 而 RBTREE 是 2 * log(n + 1),也就是说同样100万个节点,AVL最坏情况是 28 层,rbtree 最坏可以到 39 层。

谣言3:AVL树删除节点是需要回溯到根节点

我以前也是这么写 AVL 树的,后来发现根据 AVL 的定义,可以做出两个推论,再平衡向上回溯时:

插入更新时:如当前节点的高度没有改变,则上面所有父节点的高度和平衡也不会改变。
删除更新时:如当前节点的高度没有改变且平衡值在 [-1, 1] 区间,则所有父节点的高度和平衡都不会改变。

根据这两个推论,AVL的插入和删除大部分时候只需要向上回溯一两个节点即可,范围十分紧凑。

谣言4:虽然二者插入一万个节点总时间类似,但是rbtree树更平均,avl有时很快,有时慢很多,rbtree 只需要旋转两次重新染色就行了,比 avl 平均

完全说反了,avl是公认的比rbtree平均的数据结构,插入时间更为平均,rbtree才是不均衡,有时候直接插入就返回了(上面是黑色节点),有时候插入要染色几个节点但不旋转,有时候还要两次旋转再染色然后递归到父节点。该说法最大的问题是以为 rbtree 插入节点最坏情况是两次旋转加染色,可是忘记了一条,需要向父节点递归,比如:当前节点需要旋转两次重染色,然后递归到父节点再旋转两次重染色,再递归到父节点的父节点,直到满足 rbtree 的5个条件。这种说法直接把递归给搞忘记了,翻翻看 linux 的 rbtree 代码看看,再平衡时那一堆的 while 循环是在干嘛?不就是向父节点递归么?avl和rbtree 插入和删除的最坏情况都需要递归到根节点,都可能需要一路旋转上去,否则你设想下,假设你一直再树的最左边插入1000个新节点,每次都想再局部转两次染染色,而不去调整整棵树,不动根节点,可能么?只是说整个过程avl更加平均而已。

比较结论

Read more…

Categories: 编程技术 Tags:

如何写一个视频编码器演示篇

December 24th, 2015 2 comments

先前写过《视频编码原理简介》,有朋友问光代码和文字不太真切,能否补充几张图片,今天我们演示一下:

这是第一帧画面:P1(我们的参考帧)

output1

这是第二帧画面:P2(需要编码的帧)

output2

从视频中截取的两张间隔1-2秒的画面,和实际情况类似,下面我们参考P1进行几次运动搜索:

搜索演示1:搜索P2中车辆的车牌在P1中最接近的位置(上图P1,下图P2)

search1

这是一个演示程序,鼠标选中P2上任意16×16的Block,即可搜索出P1上的 BestMatch 宏块。虽然车辆在运动,从远到近,但是依然找到了最接近的宏块坐标。

(点击 more 阅读剩下内容)

Read more…

Categories: 编程技术 Tags:

内存拷贝优化(3)-深入优化

December 20th, 2015 5 comments

今天继续在原来内存拷贝代码上优化:

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

最新代码测试结果(可以对比老的表看新版本性能是否有所提升):

Read more…

Categories: 编程技术 Tags: ,

内存拷贝优化(2)-全尺寸拷贝优化

December 18th, 2015 No comments

四年前写过一篇小内存拷贝优化: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 指令集支持,gcc编译时需要 –msse2 一下,点击(more)展开代码,测试结果附在源文件最后注释部分:

Read more…

Categories: 编程技术 Tags: ,

视频编码原理简介

November 24th, 2015 2 comments

要彻底理解视频编码原理,看书都是虚的,需要实际动手,实现一个简单的视频编码器:

知识准备:基本图像处理知识,信号的时域和频域问题,熟练掌握傅立叶正反变换,一维、二维傅立叶变换,以及其变种,dct变换,快速dct变换。

来自知乎问题:http://www.zhihu.com/question/22567173/answer/73610451 

第一步:实现有损图像压缩和解压

参考 JPEG原理,将RGB->YUV,然后Y/U/V看成三张不同的图片,将其中一张图片分为 8×8的block进行 dct变换(可以直接进行二维dct变换,或者按一定顺序将8×8的二维数组整理成一个64字节的一维数组),还是得到一个8×8的整数频率数据。于是表示图像大轮廓的低频信号(人眼敏感的信号)集中在 8×8的左上角;表示图像细节的高频信号集中在右下角。

接着将其量化,所谓量化,就是信号采样的步长,8×8的整数频率数据块,每个数据都要除以对应位置的步长,左上角相对重要的低频信号步长是1,也就是说0-255,是多少就是多少。而右下角是不太重要的高频信号,比如步长取10,那么这些位置的数据都要/10,实际解码的时候再将他们*10恢复出来,这样经过编码的时候/10和解码的时候*10,那么步长为10的信号1, 13, 25, 37就会变成规矩的:0, 10, 20, 30, 对小于步长10的部分我们直接丢弃了,因为高频不太重要。

经过量化以后,8×8的数据块左上角的数据由于步长小,都是比较离散的,而靠近右下角的高频数据,都比较统一,或者是一串0,因此图像大量的细节被我们丢弃了,这时候,我们用无损压缩方式,比如lzma2算法(jpeg是rle + huffman)将这64个byte压缩起来,由于后面高频数据步长大,做了除法以后,这些值都比较小,而且比较靠近,甚至右下部分都是一串0,十分便于压缩。

JPEG图像有个问题就是低码率时 block边界比较严重,现代图片压缩技术往往要配合一些de-block算法,比如最简单的就是边界部分几个像素点和周围插值模糊一下。

做到这里我们实现了一个同 jpeg类似的静态图片有损压缩算法。在视频里面用来保存I帧数据。

第二步:实现宏块误差计算

视频由连续的若干图像帧组成,分为 I帧,P帧,所谓I帧,就是不依赖就可以独立解码的视频图像帧,而P帧则需要依赖前面已解码的视频帧,配合一定数据才能生成出来。所以视频中I帧往往都比较大,而P帧比较小,如果播放器一开始收到了P帧那么是无法播放的,只有收到下一个I帧才能开始播放。I帧多了视频就变大,I帧少了,数据量是小了,但视频受到丢包或者数据错误的影响却又会更严重。

那么所谓运动预测编码,其实就是P帧的生成过程:继续将图片分成 16×16的block(为了简单只讨论yuv的y分量压缩)。I帧内部单帧图片压缩我们采用了8×8的block,而这里用16×16的block来提高帧间编码压缩率(当然也会有更多细节损失),我们用 x, y表示像素点坐标,而s,t表示block坐标,那么坐标为(x,y)的像素点所属的block坐标为:

s = x / 16 = x >> 4
t = y / 16 = y >> 4

接着要计算两个block的相似度,即矢量的距离,可以表示为一个256维矢量(16×16)像素点色彩距离的平方,我们先定义两个颜色的误差为:

PixelDiff(c1, c2) = (c1- c2) ^ 2

Read more…

Categories: 编程技术 Tags:

Android Arm 编译优化选项评测

August 25th, 2015 3 comments

用不同测试用例具体测试 softfp, armv7-a, cortax 等优化选项,看选项不同性能差别多大。首先设计下面几个测试用例,包含字符串处理、复杂逻辑、整数运算、浮点运算几个方面:

  • compress:进行 LZO/LZW 大规模压缩,测试搜索,字符串匹配,复杂分支等性能
  • resample:进行一系列整数 DSP 运算,包括 resample 和 fir low pass
  • int add:一亿次整数加法
  • int mul:一亿次整数乘法
  • int div:一亿次整数除法
  • float add:一亿次浮点加法
  • float mul:一亿次浮点乘法
  • float div:一亿次浮点除法
  • const div:一亿次整数除以常数255
  • matrix:若干次矩阵乘法运算,同时考察浮点数乘法加法
  • normalize:若干次矢量归一化运算,同时考察浮点数乘法,除法,加法,sqrt

其次对安卓的几个 gcc 的编译选项进行分别测试:

  • -mfloat-abi=softfp,如果有硬件浮点处理器将会使用硬件,如果没有会转移到软件模拟
  • -march=armv7-a,生成适合 armv7a 架构的代码
  • -mtune=cortex-9,代码生成按照 cortex-9 进行调优
  • –mfpu=neon,使用 neon 进行硬件浮点运算,决定 softfp 的硬件方式到底用这个
  • -mfpu=vfp,使用 vfp 进行硬件浮点运算,决定 softfp 的硬件方式用这个

测试硬件:

  • 桌面电脑:Intel® Core™ i5-2520M CPU @ 2.50GHz
  • 安卓手机:三星,双核 CPU 1.73GHz armv7-a cortex-9

结果如下:

Read more…

Categories: 编程技术 Tags:

Android 命令行调试 C/C++ 程序

August 25th, 2015 No comments

传统方式调试 NDK 开发的程序比较麻烦,先要编译成 JNI,又要导出 java接口,还要再写一个 java 工程,改一个地方又要连续改几处,这样效率是很低的。最频繁使用的关键工作路径(编译/调试环节)如果能极致简化,那么可以带来开发效率的成倍提升。其实安卓官方是提供了命令行调试方法的,将你需要调试的 C代码用 NDK直接编译成可执行,然后到设备上执行:

使用 NDK 导出独立工具链,方便以后使用,在 cygwin 下面,将 $NDK 环境变量代表的路径设置好,然后:

cd $NDK
chmod -R 755 *
build/tools/make-standalone-toolchain.sh –ndk-dir=$NDK –platform=android-9 –arch=arm –install-dir=/…../path-to-android-9

这样就导出了一套针对 API9 的独立工具链(包含 gcc, ld, ndk必要文件),以后方便使用,比如导出到 d:\android-9下面,那么以后可以跳过 cygwin,直接编译我们的 Hello World:

d:\android-9\bin\arm-linux-androideabi-gcc.exe hello.c –o hello

于是你可以在命令行下直接开发 Android 的非 GUI 应用程序了。

调试也很简单,用 adb push 上传到 /data/local/tmp 下面,并且设置可执行模式为 755:

adb push hello /data/local/tmp/hello
adb shell chmod 755 /data/local/tmp/hello

运行就是直接:

adb shell /data/local/tmp/hello

不要传到其他目录,比如 /sdcard,这些目录 mount时有 NOEXEC 权限,不能给文件增加可执行权限,而 /data/local/tmp 就是留给大家调试命令行用的,并且不需要 root 权限。

可以编写一些脚本,每次编译好自动上传,配置到你的 Editplus/Vim/Npp 中,一键编译上传,一键运行。比起以前调试下 C代码还需要写一大堆 jni 和 java 的方式,效率高极了。

Categories: 编程技术 Tags: