| 技术论坛 |
|
|
| ≡技术区≡ ① |
| DELPHI技术 |
| lazarus/fpc/Free Pascal |
| 移动应用开发 |
| Web应用开发 |
| 数据库专区 |
| 报表专区 |
| 网络通讯 |
| 开源项目 |
| 论坛精华贴 |
| ≡发布区≡ ② |
| 发布代码 |
| 发布控件 |
| 文档资料 |
| 经典工具 |
| ≡事务区≡ ③ |
| 网站意见 |
| 盒子之家 |
| 招聘应聘 |
| 信息交换 |
| 论坛信息 |
|||
|
| 导航： | 论坛 -> DELPHI技术 斑竹:liumazi,sephil | |||||
| 作者： |
|
2011/7/16 10:48:13 | ||||
| 标题： |
|
加入我的收藏 | ||||
| 楼主： | 前两天做了个测试，结果 XE 带的 hash 算法速度居然跟 perl 的速度差不多 http://bbs.2ccc.com/topic.asp?topicid=382126 昨天研究了一下原因，好在源代码中给出了 delphi 用到的 BobJenkinsHash 算法的出处。 http://burtleburtle.net/bob/c/lookup3.c 于是我就改了改测试了一下。因为现在 XE 的 Generics.Defaults 已经被我替换掉了，所以我这里列出用 Pulsar（XE2 beta）编译测试的结果（好在还能生成64位的）： (ms) [x86] [x64] Pas: 3681 2262 MSVC: 671 765 MinGW: 702 624 于是我就发扬自己动手的精神，把 gcc/cl 生成的代码嵌到 Generics.Defaults.pas 里，速度得到大幅提升。这回在家里测试，perl 中 hash 部分花的时间是 0.45s，delphi 版本 hash 部分花了 0.23s，速度快了一倍。 还是忍不住要说，这个对比可以看到 delphi 的“优化能力”有多糟糕，同样的算法，花的时间是别的编译器的3~5倍。 不过这个测试中，pulsar 生成的64位程序速度倒是比32位快了近40%，算是个好消息。回头再去找变快了的原因，看到底是体系架构带来的变化，还是 pulsar x64 优化能力真的提高了。 测试用的文件、源代码和用来替换的文件打包上传到盒子 FTP 了（hash_replacement_by_eGust.rar 上传不了附件，只好扔 ftp 了），替换方法在 readme 中有说明。 回头等 xe2 出了正式版我再弄64位的，gcc 弄出来的 at&t 汇编没法直接用，折腾起来不是一般麻烦 ---------------------------------------------- cnblogs中我写的关于Delphi的blog，欢迎访问： http://www.cnblogs.com/egust/ |
|||||
| 作者： |
|
2011/7/16 10:57:43 | ||||
| 1楼： | “x64优化能力挺高”。。。这个很难。可能是指令长度以及寄存器数量的问题。 ---------------------------------------------- - |
|||||
| 作者： |
|
2011/7/16 11:01:19 | ||||
| 2楼： | PS：优化能力差也给我辈破解带来极大好处，最简单的常数除法优化，如果真用了，那么看起来还真得费点脑子，现在好多了，直接div xxx，看着多明显。。。 反正我看起d编译的release程序的反编译比vc 的release轻松多了，一个像是在看小说，一个像是看文言文。 ---------------------------------------------- - |
|||||
| 作者： |
|
2011/7/16 11:16:11 | ||||
| 3楼： | 说到 x64 的寄存器我就觉得 m$ 很气人，16个通用的只留给用户7个，simd 更过分，只有6个随便用。你说一操作系统要那么多寄存器干嘛，学学人家 linux/bsd 之类的，通用的给用户9个，xmm 随便用，多好 ---------------------------------------------- cnblogs中我写的关于Delphi的blog，欢迎访问： http://www.cnblogs.com/egust/ |
|||||
| 作者： |
|
2011/7/16 22:31:01 | ||||
| 4楼： | 你可以看一下我的博客上面有一个Pulsar X64的优化分析. 其实X64倒是没做太多优化. 但是楼主的需求有个特别的原因X64会比32位快. 因为Hash无非是做摘要.要把所有的数据走一遍,中间用到了若干位运算或者数学运算. 就处理的数据量或者位运算量,而32位一次处理的是4字节,64位一次处理8字节.X64天然就比32位快. 其他和计算位数无关的代码,Debug版X64比32位略快.但是Release版X64比32位则慢了好几倍.和Debug版基本一样. 说明易博龙现在X64编译器仅仅是可以中规中矩的工作,但是完全没做优化 ---------------------------------------------- 武稀松http://www.raysoftware.cn |
|||||
| 作者： |
|
2011/7/17 6:23:21 | ||||
| 5楼： |  http://bbs.2ccc.com/topic.asp?topicid=382126
好像不太公平吧，这里明显做了两次lookup，还有两次是否存在的判断，多了一倍的工作量。 ---------------------------------------------- - |
|||||
| 作者： |
|
2011/7/17 20:37:07 | ||||
| 6楼： | AdamWu 我没明白你的重点……delphi 的优化能力不用我说显然你也应该知道。 像脚本语言那样字典数据结构能直接当左值用的，我能想到的编译语言只有 D。于是为了公平起见，我边查资料边写了自己的第1个 D 语言程序，并用 dmd 编译，hash 部分就两句： foreach(string ln; lines) counts[ln]++; 这部分时间是 0.13s。 公平比较的话，因为 .net 的 Dictionory<,> 和 delphi 自带的使用方法一样，所以我又写了个 C# 版本的： if (dict.TryGetValue(k, out v)) dict[k] = v + 1; else dict.Add(k, 1); hash 部分的测试结果： x86 x64 C# 0.25 0.25 Pulsar 0.53 0.45 XE 0.28（使用替换后的 BobJenkinsHash） ---------------------------------------------- cnblogs中我写的关于Delphi的blog，欢迎访问： http://www.cnblogs.com/egust/ |
|||||
| 作者： |
|
2011/7/18 8:50:28 | ||||
| 7楼： | delphi 加入 inline的试试？ ---------------------------------------------- 不喧哗 自有声 心静 思远 志行千里 |
|||||
| 作者： |
|
2011/7/18 12:50:25 | ||||
| 8楼： | 不替换 rtl 文件补丁版，只要引用该单元即可生效 unit patchBobJenkinsHash; {$DEFINE AutoPatch} interface function BobJenkinsHash(const Data; Len, InitData: Integer): Integer; procedure ReplaceFunc(OldFunc, NewFunc: Pointer); {$IFNDEF AutoPatch} procedure ManualPatch; inline; {$ENDIF} implementation uses Generics.Defaults, Windows; procedure ManualPatch; inline; begin ReplaceFunc(@Generics.Defaults.BobJenkinsHash, @BobJenkinsHash); end; procedure ReplaceFunc(OldFunc, NewFunc: Pointer); var jumper : packed record jmp : Byte; off : Integer; end; n : DWORD; begin jumper.jmp := $E9; jumper.off := Integer(NewFunc) - Integer(OldFunc) - 5; WriteProcessMemory(GetCurrentProcess, OldFunc, @jumper, SizeOf(jumper), n); end; {$REGION 'func doBobJenkinsHash(const Data; Len, InitData: Integer): Integer; stdcall;'} procedure doBobJenkinsHash; asm // Line 165 mov ecx, [ESP+$0C] mov eax, [ESP+$8] // Line 168 mov edx, [ESP+$4] push ebx push ebp push esi lea ebx, DWORD PTR [ecx+eax*4-559038737] push edi mov ecx, ebx mov esi, ebx test dl, 3 jne @@LN55 // Line 169 mov ebp, edx // Line 173 cmp eax, 12 // 0000000cH jbe @@LN64 // Line 169 lea edx, DWORD PTR [eax-13] mov eax, -1431655765 // aaaaaaabH mul edx shr edx, 3 inc edx mov [ESP+$1C], edx db $8d, $49, $00 // npad 3 @@LL54: // Line 177 add ebx, DWORD PTR [ebp+8] add ecx, DWORD PTR [ebp+4] // Line 178 sub esi, ebx add esi, DWORD PTR [ebp] mov eax, ebx rol eax, 4 xor eax, esi add ebx, ecx sub ecx, eax // Line 179 sub [ESP+$18], 12 // 0000000cH mov edi, eax rol edi, 6 xor edi, ecx add eax, ebx sub ebx, edi mov edx, edi rol edx, 8 xor edx, ebx add edi, eax sub eax, edx mov esi, edx rol esi, 16 // 00000010H xor esi, eax add edx, edi mov ecx, esi ror ecx, 13 // 0000000dH sub edi, esi xor ecx, edi add esi, edx mov ebx, ecx sub edx, ecx rol ebx, 4 xor ebx, edx add ecx, esi // Line 180 add ebp, 12 // 0000000cH dec [ESP+$1C] jne @@LL54 // Line 194 cmp DWORD PTR [ESP+$18], 12 // 0000000cH ja @@LN14 mov eax, DWORD PTR [ESP+$18] @@LN64: jmp DWORD PTR @@LN70[eax*4] @@LN50: // Line 196 add ebx, DWORD PTR [ebp+8] @@LN46: add ecx, DWORD PTR [ebp+4] @@LN42: add esi, DWORD PTR [ebp] jmp @@LN14 @@LN49: // Line 197 mov edx, DWORD PTR [ebp+8] add ecx, DWORD PTR [ebp+4] and edx, 16777215 // 00ffffffH add ebx, edx add esi, DWORD PTR [ebp] jmp @@LN14 @@LN48: // Line 198 movzx eax, WORD PTR [ebp+8] add ecx, DWORD PTR [ebp+4] add ebx, eax add esi, DWORD PTR [ebp] jmp @@LN14 @@LN47: // Line 199 movzx edx, BYTE PTR [ebp+8] add ecx, DWORD PTR [ebp+4] add ebx, edx add esi, DWORD PTR [ebp] jmp @@LN14 @@LN45: // Line 201 mov eax, DWORD PTR [ebp+4] and eax, 16777215 // 00ffffffH add ecx, eax add esi, DWORD PTR [ebp] jmp @@LN14 @@LN44: // Line 202 movzx edx, WORD PTR [ebp+4] add ecx, edx add esi, DWORD PTR [ebp] jmp @@LN14 @@LN43: // Line 203 movzx eax, BYTE PTR [ebp+4] add ecx, eax add esi, DWORD PTR [ebp] jmp @@LN14 @@LN41: // Line 205 mov edx, DWORD PTR [ebp] and edx, 16777215 // 00ffffffH jmp @@LN69 @@LN40: // Line 206 movzx eax, WORD PTR [ebp] add esi, eax jmp @@LN14 @@LN39: // Line 207 movzx edx, BYTE PTR [ebp] jmp @@LN69 @@LN38: pop edi pop esi pop ebp // Line 208 mov eax, ebx pop ebx // Line 303 ret 12 // 0000000cH @@LN55: // Line 211 test dl, 1 jne @@LN36 // Line 212 mov ebp, edx // Line 216 cmp eax, 12 // 0000000cH jbe @@LN65 // Line 212 lea edx, DWORD PTR [eax-13] mov eax, -1431655765 // aaaaaaabH mul edx shr edx, 3 inc edx mov [ESP+$1C], edx @@LL35: // Line 219 movzx edi, WORD PTR [ebp+4] movzx eax, WORD PTR [ebp+6] // Line 221 movzx edx, WORD PTR [ebp+2] add edi, ecx movzx ecx, WORD PTR [ebp+8] shl eax, 16 // 00000010H add edi, eax movzx eax, WORD PTR [ebp+10] add ebx, ecx movzx ecx, WORD PTR [ebp] shl eax, 16 // 00000010H add ebx, eax shl edx, 16 // 00000010H add edx, ecx sub edx, ebx add edx, esi mov eax, ebx rol eax, 4 add ebx, edi xor eax, edx sub edi, eax mov ecx, eax rol ecx, 6 xor ecx, edi // Line 222 sub [ESP+$18], 12 // 0000000cH add eax, ebx sub ebx, ecx mov edi, ecx rol edi, 8 xor edi, ebx add ecx, eax sub eax, edi mov esi, edi rol esi, 16 // 00000010H xor esi, eax add edi, ecx sub ecx, esi mov eax, esi ror eax, 13 // 0000000dH xor ecx, eax add esi, edi mov ebx, ecx sub edi, ecx rol ebx, 4 xor ebx, edi add ecx, esi // Line 223 add ebp, 12 // 0000000cH dec DWORD PTR [ESP+$1C] jne @@LL35 // Line 228 cmp DWORD PTR [ESP+$18], 12 // 0000000cH ja @@LN14 mov eax, DWORD PTR [ESP+$18] @@LN65: jmp DWORD PTR @@LN71[eax*4] @@LN31: // Line 230 movzx eax, WORD PTR [ebp+10] movzx edx, WORD PTR [ebp+8] shl eax, 16 // 00000010H add ebx, edx add ebx, eax @@LN67: // Line 231 movzx eax, WORD PTR [ebp+6] movzx edx, WORD PTR [ebp+4] shl eax, 16 // 00000010H add ecx, edx add ecx, eax @@LN23: // Line 232 movzx eax, WORD PTR [ebp+2] movzx edx, WORD PTR [ebp] shl eax, 16 // 00000010H add esi, edx add esi, eax // Line 233 jmp @@LN14 @@LN30: // Line 234 movzx eax, BYTE PTR [ebp+10] shl eax, 16 // 00000010H add ebx, eax @@LN29: // Line 235 movzx edx, WORD PTR [ebp+8] add ebx, edx // Line 238 jmp @@LN67 @@LN28: // Line 239 movzx eax, BYTE PTR [ebp+8] add ebx, eax @@LN27: // Line 240 movzx eax, WORD PTR [ebp+4] movzx edx, WORD PTR [ebp+6] shl edx, 16 // 00000010H add ecx, eax // Line 241 movzx eax, WORD PTR [ebp] add ecx, edx movzx edx, WORD PTR [ebp+2] shl edx, 16 // 00000010H add esi, eax // Line 242 jmp @@LN69 @@LN26: // Line 243 movzx edx, BYTE PTR [ebp+6] shl edx, 16 // 00000010H add ecx, edx @@LN25: // Line 244 movzx eax, WORD PTR [ebp+4] // Line 245 movzx edx, WORD PTR [ebp+2] add ecx, eax movzx eax, WORD PTR [ebp] shl edx, 16 // 00000010H add esi, eax // Line 246 jmp @@LN69 @@LN24: // Line 247 movzx edx, BYTE PTR [ebp+4] movzx eax, WORD PTR [ebp+2] add ecx, edx movzx edx, WORD PTR [ebp] shl eax, 16 // 00000010H add esi, edx add esi, eax jmp @@LN14 @@LN22: // Line 250 movzx eax, BYTE PTR [ebp+2] shl eax, 16 // 00000010H add esi, eax @@LN21: // Line 251 movzx edx, WORD PTR [ebp] // Line 252 jmp @@LN69 @@LN20: // Line 253 movzx eax, BYTE PTR [ebp] add esi, eax jmp @@LN14 @@LN36: // Line 259 mov edi, edx // Line 262 cmp eax, 12 // 0000000cH jbe @@LN66 // Line 259 lea edx, DWORD PTR [eax-13] mov eax, -1431655765 // aaaaaaabH mul edx shr edx, 3 inc edx mov [ESP+$1C], edx jmp @@LL17 //lea esp, [esp] db $8d, $a4, $24 dd 0 nop //npad 10 @@LL17: // Line 271 movzx eax, BYTE PTR [edi+7] movzx edx, BYTE PTR [edi+6] shl eax, 8 add eax, edx movzx edx, BYTE PTR [edi+5] shl eax, 8 add eax, edx movzx edx, BYTE PTR [edi+4] add edx, ecx // Line 275 movzx ecx, BYTE PTR [edi+10] movzx ebp, BYTE PTR [edi+8] shl eax, 8 add edx, eax movzx eax, BYTE PTR [edi+11] shl eax, 8 add eax, ecx movzx ecx, BYTE PTR [edi+9] shl eax, 8 add eax, ecx // Line 276 movzx ecx, BYTE PTR [edi+3] add ebp, ebx movzx ebx, BYTE PTR [edi+2] shl ecx, 8 add ecx, ebx movzx ebx, BYTE PTR [edi+1] shl ecx, 8 add ecx, ebx movzx ebx, BYTE PTR [edi] shl ecx, 8 add ecx, ebx shl eax, 8 add ebp, eax sub ecx, ebp add ecx, esi mov eax, ebp rol eax, 4 xor eax, ecx add ebp, edx sub edx, eax mov ecx, eax rol ecx, 6 xor ecx, edx // Line 277 sub DWORD PTR [ESP+$18], 12 // 0000000cH add eax, ebp sub ebp, ecx mov ebx, ecx rol ebx, 8 xor ebx, ebp add ecx, eax sub eax, ebx mov esi, ebx rol esi, 16 // 00000010H xor esi, eax add ebx, ecx sub ecx, esi mov eax, esi ror eax, 13 // 0000000dH xor ecx, eax add esi, ebx mov edx, ecx sub ebx, ecx rol edx, 4 xor ebx, edx add ecx, esi // Line 278 add edi, 12 // 0000000cH dec DWORD PTR [ESP+$1C2] jne @@LL17 // Line 282 cmp DWORD PTR [ESP+$18], 12 // 0000000cH ja @@LN14 mov eax, DWORD [ESP+$18] @@LN66: jmp DWORD PTR @@LN72[eax*4] @@LN13: // Line 284 movzx eax, BYTE PTR [edi+11] shl eax, 24 // 00000018H add ebx, eax @@LN12: // Line 285 movzx edx, BYTE PTR [edi+10] shl edx, 16 // 00000010H add ebx, edx @@LN11: // Line 286 movzx eax, BYTE PTR [edi+9] shl eax, 8 add ebx, eax @@LN10: // Line 287 movzx edx, BYTE PTR [edi+8] add ebx, edx @@LN9: // Line 288 movzx eax, BYTE PTR [edi+7] shl eax, 24 // 00000018H add ecx, eax @@LN8: // Line 289 movzx edx, BYTE PTR [edi+6] shl edx, 16 // 00000010H add ecx, edx @@LN7: // Line 290 movzx eax, BYTE PTR [edi+5] shl eax, 8 add ecx, eax @@LN6: // Line 291 movzx edx, BYTE PTR [edi+4] add ecx, edx @@LN5: // Line 292 movzx eax, BYTE PTR [edi+3] shl eax, 24 // 00000018H add esi, eax @@LN4: // Line 293 movzx edx, BYTE PTR [edi+2] shl edx, 16 // 00000010H add esi, edx @@LN3: // Line 294 movzx eax, BYTE PTR [edi+1] shl eax, 8 add esi, eax @@LN2: // Line 295 movzx edx, BYTE PTR [edi] @@LN69: // Line 205 add esi, edx @@LN14: // Line 301 xor ebx, ecx mov eax, ecx rol eax, 14 // 0000000eH sub ebx, eax mov eax, ebx rol eax, 11 // 0000000bH mov edx, ebx xor edx, esi sub edx, eax xor ecx, edx mov eax, edx ror eax, 7 sub ecx, eax xor ebx, ecx mov eax, ecx rol eax, 16 // 00000010H sub ebx, eax mov eax, ebx mov edi, eax mov esi, eax xor esi, edx rol edi, 4 sub esi, edi mov edx, esi rol edx, 14 // 0000000eH xor ecx, esi sub ecx, edx pop edi pop esi mov edx, ecx ror edx, 8 xor eax, ecx pop ebp sub eax, edx pop ebx // Line 303 ret 12 // 0000000cH //npad 2 mov edi, edi nop @@LN70: dd @@LN38, @@LN39, @@LN40, @@LN41, @@LN42, @@LN43, @@LN44, @@LN45, @@LN46, @@LN47, @@LN48, @@LN49, @@LN50 @@LN71: dd @@LN38, @@LN20, @@LN21, @@LN22, @@LN23, @@LN24, @@LN25, @@LN26, @@LN27, @@LN28, @@LN29, @@LN30, @@LN31 @@LN72: dd @@LN38, @@LN2, @@LN3, @@LN4, @@LN5, @@LN6, @@LN7, @@LN8, @@LN9, @@LN10, @@LN11, @@LN12, @@LN13 end; {$ENDREGION} function BobJenkinsHash(const Data; Len, InitData: Integer): Integer; asm push ECX push EDX push EAX call doBobJenkinsHash end; {$IFDEF AutoPatch} begin ManualPatch; {$ENDIF} end. ---------------------------------------------- cnblogs中我写的关于Delphi的blog，欢迎访问： http://www.cnblogs.com/egust/ |
|||||
| 作者： |
|
2011/7/18 15:44:59 | ||||
| 9楼： | Dictionary内部的实现也对测试有一定影响的。 Delphi的用的是linear probing加上exponential grow，有一个性能缺陷，就是每次grow的时候，需要重新hash所有的条目。 要真实的体现hash的性能的话，可以先设定Capacity成一个巨大的数，这样在Add的时候避免触发重新Hash。(并不是说触发rehash就不公平，其他的实现也有可能会rehash，但问题是可能在不同的时候触发，没法准确把握，就造成测试有很大的偏差) 其实要测试hash算法性能的话，不一定非要绑在TDictionary上啊，生成一堆随机String，然后直接hash就行了... ---------------------------------------------- - |
|||||
| 作者： |
|
2011/7/18 18:13:40 | ||||
| 10楼： | …… 我在顶楼贴的显然就是纯 hash 的对比结果啊 ---------------------------------------------- cnblogs中我写的关于Delphi的blog，欢迎访问： http://www.cnblogs.com/egust/ |
|||||
| 作者： |
|
2011/7/31 13:30:15 | ||||
| 11楼： | XE2 64 位质量果然还是堪忧啊…… 今天本打算把 MinGW64 版本移植给 Pulsar beta8，结果 BASM 碰到了一大堆问题。能换个法子处理的都忍了，最后碰到了无解的问题： @@L: ... 不论是 lea 还是 dd/dq，编译器居然无法生成 @@L 的正确地址。这下没辙了，我总不能再写个 linker 吧……报了 bug 等以后修正了，看来64位要下个版本质量才能及格。 ---------------------------------------------- cnblogs中我写的关于Delphi的blog，欢迎访问： http://www.cnblogs.com/egust/ |
|||||
| 作者： |
|
2011/8/1 16:27:50 | ||||
| 12楼： | 都是高人，佩服，佩服！ 看来delphi的速度越来越让人关注了！ ---------------------------------------------- -http://blog.163.com/xxxp_163/ |
|||||
| 信息 |
| 登陆以后才能回复 |
