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

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:

如何优雅的使用 Vim

June 20th, 2017 No comments

根据 Bram 前后几个关于高效使用 Vim的视频,大家每天需要花很多时间来编辑:代码、文档、邮件、日志 等等,除去这些外,还要分时间参加会议和人沟通,每个人的时间却都是不够的,优雅使用 Vim 无外乎:

  • 检测不高效的地方:你的整个工作流里,什么地方比较浪费时间?
  • 寻找一个更快的方式:官方文档,学习他人经验,自己编写 VimScript
  • 使它习惯化:开始使用,并且不断完善

以上三点反复循环,能让你的 Vim 越来越顺手。所以重点是根据自己的工作流不断迭代。而不是象大部分教程那样教你安装一大堆插件。插件都是别人写的为了解决通用需求而提炼的东西,和每个人的具体需求都有差别。上面这三点我屡试不爽,随着时间增长,有种越来越顺手的感觉,举几个我具体碰到的例子:

问题1:边开发边参考网上解决方案的问题

比如碰到问题搜到一段代码,需要试一下,一会又看会 Chrome ,一会又切回 GVim 里去写代码,反复 ALTTAB,有时候中间使用了一下资源管理器或者其他程序,ALTTAB 的顺序就会被打乱,你一切换就切跑了,十分低效。

于是我用 VimScript + 内嵌 Python 写了一个功能,按快捷键可以让 GVim 在透明/不透明两种状态间自由切换:

就是 VimScript 简单封装一个函数,里面用内嵌 Python 找到 GVim 的顶层 HWND,并设置透明度。平时默认不透明,需要参考其他资料时切换成透明,参考完了又快捷键切换回来,感觉比缘来切来切去顺畅很多。

问题2:浏览文档时的窗口滚动问题

比如你在抄写或者改写一段代码,窗口分为左右两个,左边是你引用参考的源代码,右边是你正在编辑的源代码。你抄着抄着,抄到左边最后一行了,或者你想前后看看正在引用的文本,你就需要将焦点从右边切换到左边,滚动,再切换交点回来,十分麻烦,于是撸一小段 VimScript 来解决这个问题:

" 0:up, 1:down, 2:pgup, 3:pgdown, 4:top, 5:bottom
function! Tools_PreviousCursor(mode)
    if winnr('$') <= 1
        return
    endif
    noautocmd silent! wincmd p
    if a:mode == 0
        exec "normal! \<c-y>"
    elseif a:mode == 1
        exec "normal! \<c-e>"
    elseif a:mode == 2
        exec "normal! ".winheight('.')."\<c-y>"
    elseif a:mode == 3
        exec "normal! ".winheight('.')."\<c-e>"
    elseif a:mode == 4
        normal! gg
    elseif a:mode == 5
        normal! G
    elseif a:mode == 6
        exec "normal! \<c-u>"
    elseif a:mode == 7
        exec "normal! \<c-d>"
    elseif a:mode == 8
        exec "normal! k"
    elseif a:mode == 9
        exec "normal! j"
    endif
    noautocmd silent! wincmd p
endfunc

把这个函数绑定到 ALTU, ALTD 两个按键上,你正在编辑着当前文档时,不用退出 INSERT 模式,更不用切换窗口交点,直接 ALTU, ALTD,就可以上下滚动正在参考的文档内容了,有了这个改进后,我的工作又高效了那么一点点。

同理,Quickfix 窗口经常用来查看编译错误,或者 Grep 结果,我也写了一个专门针对 Quickfix 窗口的滚屏函数,不用切焦点随时浏览 Quickfix 内容。

Read more…

Categories: 随笔 Tags:

Emacs/Vim 深度比较

December 25th, 2016 No comments

生命在于折腾,折腾完了 Atom Editor,开始跟着陈斌大婶和 purcell的配置折腾 Emacs,比较下。很多人都在比较键位,比较插件,这是十分肤浅的,我们比较点深入的东西:

代码结构

  • Emacs 源代码:eLisp 79%, C 21%
  • Vim 源代码:C 52%, VimScript 48%

从代码结构上来讲,Emacs的代码最多的是 elisp,C代码只是一个微内核,Vim 里C代码还是大头。当然不排除 24.X, 25.X以后 Emacs源代码里带了好几个重量级的包,而 Vim向来比较精简一些,官方没带啥大点的插件有关。去除自带插件后,Emacs的 elisp代码比例应该会下降很多,不过总体来说,Emacs有更多组件使用 elisp开发而成,也就是说可以被用户修改或者替换的地方比 Vim要多,当然速度也会相应慢一点(比如 Emacs新打开上万行的文件连续按住PageDown时cpu 100%占满),不过比较大 JB,Atom Editor来说,还是快不少。

系统接口

大框架基本类似:

  • Vim 可以操作: buffer, window, tabpage, 光标,marker, region 跳转表等等。
  • Emacs 可以操作:buffer, window, frame, 光标,marker,region 异步进程 等等。

Vim 有 local,Emacs有 mode,Vim有事件触发,Emacs有各种钩子,基本大框架类似的。

键位设置也都很灵活,会配置的话,可以把 Emacs键位全部弄成 Vim的,比如 Evil,或者Vim里面也可以配制成进去就自动进入插入模式,全部用 Emacs键位。

具体到比如 buffer 或者窗口里面,Emacs的窗口或者 buffer /window 属性更多一些,Vim也有一些 Emacs没有的基础设施,比如 jumplist, quickfix之类的,不过 Emacs也可以用插件实现,实现 jumplist没问题,比较独立,但每个插件实现一个类似的 quickfix的东西,实在是比较蛋疼。

脚本语言

VimScript 类似 Lua,但更啰嗦些,没啥好说的,要上手可能就是2-3天的样子,主要是实际编写中熟悉各种 Vim内部结构体系,以及api。

EmacsLisp 类似 clisp,稍微有些区别而已。clisp中的向量: (vector 1 2 3 4) 在 elisp中可以用中括号来表示:[1 2 3 4] 这样对减少小括号数量有一些帮助,代码读起来没那么拗口,可惜实际写 elisp的过程中,向量用的并不多,各种插件用的最多的还是 list,alist,plist 几种容器,小括号还是满天飞,如果不借助编辑器的匹配,缩进,还有彩虹括号(不同层次的括号用不同颜色的小插件)代码很难阅读,自己写好写点,看别人代码要对括号对半天(特别是他们把很多写一行的话)。

Lisp变量可视范围比较好用,局部变量可以 “遮盖住” 全局变量,比如你在 VimScript里面要临时跳转到一个新目录需要这么写:

let cd = haslocaldir()? "cd" : "lcd"
let saved = getcwd()
silent! exec cd "my new directory"
......
silent! exec cd saved

而 elisp里面,利用局部变量遮盖特性,简单的:

(let ((default-directory "my new directory"))
  .....
  )

在这个 let的作用范围内,buffer的全局变量 default-directory 被新定义的同名局部变量给遮盖住了,里面的代码(包括调用外面定义的函数)取这个名字的变量,都会取到你新定义的变量,作用范围结束就恢复了,这样比 vimscript方便不少,类似的用法还有 (with-selected-window new-window...) 把当前窗口设置成 new-window并做一些事情,当离开代码作用域以后,自动恢复成先前的窗口,如果VimScript来做这事情,又需要保存前窗口,然后跳转,最后又恢复。

VimScript在 vim6.0及以前的时代里比 EmacsLisp弱很多,连个 List,HashTable之类的容器都没有,怎么写复杂的程序嘛,Vim7.0以后补充了字典和列表还有三元式,简单面向对象等,终于可以写点复杂的东西了,而 Vim下很多传奇性的插件,其实也正是 7.0以后才出现的。Vim8.0以后又进一步补充了匿名函数和 partial function (类似简陋版的 curry 函数)等等特性,除了啰嗦外,写点复杂东西问题不大,比如前久有人用 VimScript写了一个 C编译器,可以在Vim里跑 C脚本。

Lisp里面的宏类似C++模版加强版,C++模版只有一层,定义好模版,然后生成代码。Lisp的宏可以先用程序生成模版,再由模版生成代码,类似模版的模版。不过实际使用中,为了不让自己的代码飞的太远,难以维护,大部分插件开发者在 elisp里面最多就是 require一下 common lisp的兼容包,用一些 common lisp里面诸如 loop, for, incf, case 之类的通用宏,自己定义也限于定义一些小工具,没有人丧心病狂的搞一些影响程序结构的东西,定义成另外一门语言。

大部分插件开发者实际上还是把它当作充满括号的 lua 来用,除去一些便利性外,麻烦也还是挺多的。

异步进程

早期的 Vim没有异步进程操作,导致很多插件没有 Emacs那么顺畅,比如生成 tag或者编译,Vim只有傻等着,Emacs可以同时做其他事情,Vim8.0以后异步接口和后台时钟等也比较完善了,假以时日各大常见插件能逐步发挥 8.0特性的时候,相信也能带来一致的体验,包括纯vimscript实现的 shell,以及 gdb集成,发邮件等,问题不大。

Read more…

Categories: 随笔 Tags:

Aix 折腾手记

December 8th, 2016 No comments

早年开发工作主要在 FreeBSD进行,2006年后来切换到 Linux下,期间穿插使用了一下 Solaris,所以我的网络库一直都是只支持这三个系统。为了让网络库支持更多平台,网上购置了一台 IBM AIX 小型机,因为其他大部分非 Linux系统,今天基本都可以在虚拟机里面安装了,而 AIX系统,你真的没法虚拟。

弄了几天以后,发现真他妈的麻烦,强大是强大,但是真的太琐碎了,相比之下,Linux/FreeBSD之流基本是傻瓜了。不看说明直接操作 AIX的话,可能连开机都麻烦,或者关机没关对,下次直接启动不了。

文字终端就没什么好拍的了,先上一张图形桌面的靓照吧:

是的你没看错,这就是 AIX 7,2012年的操作系统,就是那么的霸道,四处透着古典 Unix的味道。这样的机器今天还跑在各大银行的机房里,AIX系统管理员也拿着比 Linux系统管理员多几倍的工资,虽然工作岗位比较稀少。

下面来感受一下你想正常开关机,安装软件的话要怎么弄:

Read more…

Categories: 随笔 Tags:

Linux 网桥设置

December 8th, 2016 No comments

在公司机房的物理机上架设 KVM虚拟化的时候,经常需要配置网桥,先要安装网桥工具:

apt-get install bridge-utils   
apt-get install uml-utilities

编辑 /etc/network/interfaces,参考下面配置加入网桥配置信息:

auto lo
iface lo inet loopback

auto eth0
iface eth0 inet manual

auto br0
iface br0 inet static
    address 192.168.10.6
    netmask 255.255.255.0
    network 192.168.10.0
    broadcast 192.168.10.255
    dns-search dell1
    bridge_ports eth0
    bridge_stp off
    bridge_fd 0
    bridge_maxwait 0

auto eth1
iface eth1 inet manual

auto br1
iface br1 inet static
    address 14.152.50.6
    netmask 255.255.255.192
    network 14.152.50.0
    broadcast 14.152.50.63
    gateway 14.152.50.1
    bridge_ports eth1
    bridge_stp off
    bridge_fd 0
    bridge_maxwait 0
    # dns-* options are implemented by the resolvconf package, if installed
    dns-nameservers 114.114.114.114
    dns-search dell1

auto eth2
iface eth2 inet manual

auto br2
iface br2 inet static
    address 112.93.114.2
    netmask 255.255.255.224
    network 112.93.114.0
    broadcast 112.93.114.255
    gateway 112.93.114.1
    bridge_ports eth2
    bridge_stp off
    bridge_maxwait 0
    dns-nameservers 114.114.114.114
    dns-search dell1

上面配置针对双线接入多 IP的情况,这样 br0-br2就可以给虚拟机 guest使用了,br0是内网,br1-br2是电信或者联通出口。

Categories: 随笔 Tags:

Linux 硬件时区折腾备忘

December 8th, 2016 No comments

前段时间折腾家中 Nas的虚拟化服务,有时候虚拟机系统时间总是快8个小时。Guest这边设好了,到了 物理机就会慢8个小时。网上说只要修改/etc/default/rcS中的 UTC=no就行了,但还是没反映,没办法,一步步找问题。发现在/etc/rcS.d/S05hwclock.sh有这样一段话:

# 2012-02-16 Roger Leigh rleigh@debian.org
# - Use the UTC/LOCAL setting in /etc/adjtime rather than
# the UTC setting in /etc/default/rcS. Additionally
# source /etc/default/hwclock to permit configuration.

 
也就是说时间是按照/etc/adjtime设置的,而不是/etc/default/rcS,晕倒。查了下adjtime文件,原来这个才是现在调整时间的设置文件,那个rcS已经被忽略了,也就是网上的那些方法只适合以前的系统,看来走了不少弯路啊。

将 /etc/adjtime 第三行由 UTC 改为 LOCAL 即可。

Categories: 随笔 Tags:

Linux 线上系统调优备忘

December 8th, 2016 No comments

大公司呆久了,都会对 SA的依赖十分强烈,很多事情 SA都帮我们搞定了。如今控制成本,没有招聘 SA,又没有购买 VPS,从买物理机开始到 IDC部署,服务器调优,虚拟机管理,全部都是自己来,才发现,安装一台 Linux机器自己玩很简单,但是要达到线上服务器的标准,还有若干调优工作需要做,有 SA的日志是多幸福的事情啊。

物理机设备驱动

Dell服务器默认安装系统后会报找不到驱动:

W: Possible missing firmware /lib/firmware/tigon/tg3_tso5.bin

因为 Debian/Ubuntu 的包都是开源的,默认开源驱动性能不行,于是需要添加 non-free源:

deb http://ftp.de.debian.org/debian main contrib non-free
deb-src http://ftp.de.debian.org/debian main contrib non-free

然后:

apt-get update
apt-get install firmware-linux-free firmware-linux-nonfree

解决 Dell驱动报错问题。

配置限制

查看 /etc/security/limits.conf 没有就新建,加入 core 和 nofile 的相关配置,比如:

* soft nofile 65536
* hard nofile 65536
* soft core unlimited
* hard core unlimited
# End of file

之类的,不用到 ~/.bashrc 里面调用 ulimit。

网卡多队列

打开内核网卡多队列支持,避免网卡中断都集中在 cpu0 上处理,多队列打开后,可以让网卡中断均摊到各个 cpu上,对提高并发十分有用:

wget http://skywind3000.github.io/install/set_irq_affinity.sh

放到 /etc/config 目录下面(没有就新建),然后在 /etc/rc.local 里面加一行,每次重启就跑 set_irq_affinity.sh 且必须用 bash跑,参数传入需要开启多队列的网卡,以下是 /etc/rc.local 的内容:

/bin/bash 
/etc/set_irq_affinity.sh eth0 eth1 eth2

exit 0

下面是 setirqaffinity.sh 的代码:

Read more…

Categories: 随笔 Tags: