数学研发论坛

 找回密码
 欢迎注册
楼主: gxqcn

[讨论] 重启大整数库 HugeCalc 的研发工作

  [复制链接]
 楼主| 发表于 2020-2-18 13:52:28 | 显示全部楼层
谢谢!

刚刚我也查到了,从 C++17 起,有 std::aligned_alloc 可用了

现在看来,软件上,新的 C++ 的标准越来越给力了;
但硬件 CPU 对 64 位整数运算支持的指令,尤其是  SIMD,还是相当欠缺。

点评

MS 居然有这么个非标函数:_aligned_malloc;既然已实现了,为何不直接将其标准化?  发表于 2020-2-20 14:55
好像也是不行,呵呵  发表于 2020-2-18 15:29
int *p = new((std::align_val_t)64)int[100]; 这种写法行不行?  发表于 2020-2-18 15:17
很遗憾,测试了下,VS2019 现在居然还不支持这个函数:std::aligned_alloc()  发表于 2020-2-18 14:46
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-18 14:35:07 | 显示全部楼层
你可以试验直接使用mulx指令看看。只要多条指令之间没有数据依赖关系,硬件会自动并行化,不一定需要用SIMD
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-19 13:22:42 | 显示全部楼层
gxqcn 发表于 2020-2-18 11:41
有两个问题请教大家:

内部的基数是32或者64bits.
gmp.h中有如下定义,这个gmp.h在编译时生成,默认的32位环境是32,64位环境是64. 不过可以配置为其它值,有效取值是32,64和x32,最后一个不知道啥意思,我这里make时出错。
  1. #define GMP_LIMB_BITS  32
复制代码


如在64位环境编译为32为的库,可使用下列命令
  1. ./configure ABI=32
复制代码

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-19 13:45:42 | 显示全部楼层
有啥新的进展没?

点评

已回复,见 60#  发表于 2020-2-24 09:52
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-19 13:46:01 | 显示全部楼层
看了下GMP代码,GMP只在64位的版本中,在下列文件中用到了256位寄存器(ymm寄存器)的vmovdqa和movdqu指令,没有用到avx512指令。其它部分也未用到avx指令。
  1. x86_64/fastavx/copyi.asm
  2. x86_64/fastavx/copyd.asm
复制代码

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-19 15:44:43 | 显示全部楼层
我记得好多年前,GMP 的主页上提到它内部基数的位数,与系统指针的位数并不相等,好像64位下是 52bits 还是 56bits 来着,但刚才去查没查到。

另外,相同的计算结果,32位与64位版本,效率比大概是多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-23 20:42:03 | 显示全部楼层
实际测试了一下,64位版本的效能大约为32位版本的2.6倍左右,比想象的要低一些。
我的电脑是Intel(R) Xeon(R) CPU E5-2670,sandybridge架构。
下面是测试数据。
为了便于比较,1个长度单位为32bits,时间单位为微秒。使用16进制字符串赋值,仅测试函数mpn_mul的运行时间。
例如,行"1024*1024        158        59        2.68" 表示,被乘数长度和乘数的长度都是1024*32比特,32位版本运行时间为158微秒,64位版本运行时间是58微秒,64位版本的速度是32版本的2.68倍。

len1*len2        32 bits lib(us)        64bits lib(us)        64bits/32bits
64*64        98        109        0.90
70*70        95        137        0.69
76*76        90        133        0.68
83*83        96        126        0.76
91*91        87        115        0.76
99*99        86        117        0.74
108*108        75        114        0.66
117*117        70        107        0.65
128*128        85        105        0.81
140*140        72        102        0.71
152*152        58        100        0.58
166*166        65        92        0.71
181*181        74        82        0.90
197*197        43        82        0.52
215*215        49        79        0.62
235*235        55        72        0.76
256*256        62        79        0.78
279*279        72        68        1.06
304*304        79        52        1.52
332*332        91        61        1.49
362*362        102        69        1.48
395*395        117        40        2.93
431*431        133        46        2.89
470*470        147        45        3.27
512*512        153        57        2.68
558*558        172        64        2.69
609*609        79        74        1.07
664*664        88        85        1.04
724*724        98        50        1.96
790*790        112        43        2.60
861*861        126        49        2.57
939*939        143        52        2.75
1024*1024        158        59        2.68
1117*1117        178        66        2.70
1218*1218        205        78        2.63
1328*1328        230        85        2.71
1448*1448        264        95        2.78
1579*1579        285        111        2.57
1722*1722        323        125        2.58
1878*1878        410        140        2.93
2048*2048        423        155        2.73
2233*2233        464        176        2.64
2435*2435        521        202        2.58
2656*2656        582        226        2.58
2896*2896        690        251        2.75
3158*3158        763        288        2.65
3444*3444        830        325        2.55
3756*3756        923        375        2.46
4096*4096        1041        423        2.46
4467*4467        1201        454        2.65
4871*4871        1307        500        2.61
5312*5312        1487        569        2.61
5793*5793        1629        878        1.86
6317*6317        1834        714        2.57
6889*6889        2069        825        2.51
7512*7512        2345        882        2.66
8192*8192        2786        1009        2.76
8933*8933        2911        1118        2.60
9742*9742        3257        1382        2.36
10624*10624        3691        1429        2.58
11585*11585        3739        1570        2.38
12634*12634        4516        1767        2.56
13777*13777        4804        1954        2.46
15024*15024        5088        2005        2.54
16384*16384        6253        2385        2.62
17867*17867        6504        2612        2.49
19484*19484        6835        3021        2.26
21247*21247        8121        3168        2.56
23170*23170        8149        3246        2.51
25268*25268        10851        3903        2.78
27554*27554        10377        4024        2.58
30048*30048        10720        4285        2.50
32768*32768        13784        5325        2.59
35734*35734        14027        5509        2.55
38968*38968        16639        6388        2.60
42495*42495        17409        6805        2.56
46341*46341        17479        6860        2.55
50535*50535        22117        8583        2.58
55109*55109        22461        9167        2.45
60097*60097        22850        9098        2.51
65536*65536        31509        11979        2.63
71468*71468        32104        12324        2.60
77936*77936        34722        13251        2.62
84990*84990        41021        17141        2.39
92682*92682        43234        15444        2.80
101070*101070        50055        19123        2.62
110218*110218        50431        19881        2.54
120194*120194        53285        19809        2.69
131072*131072        70961        26338        2.69
142935*142935        71727        27189        2.64
155872*155872        85549        32807        2.61
169979*169979        100685        32574        3.09
185364*185364        118300        33296        3.55
202141*202141        114053        41074        2.78
220436*220436        118086        42328        2.79
240387*240387        120861        42334        2.85
262144*262144        160000        61190        2.61
285870*285870        166417        62167        2.68
311744*311744        177583        68385        2.60
339959*339959        213000        81006        2.63
370728*370728        218389        83596        2.61
404281*404281        253199        115366        2.19
440872*440872        257377        102662        2.51
480774*480774        261366        112603        2.32
524288*524288        349563        135294        2.58
571740*571740        360441        137598        2.62
623487*623487        427958        167993        2.55
679917*679917        450731        171983        2.62
741455*741455        454241        177001        2.57
808563*808563        556654        217155        2.56
881744*881744        546546        217261        2.52
961548*961548        551027        228512        2.41
1048576*1048576        739869        295126        2.51
1143480*1143480        811496        304789        2.66
1246974*1246974        881269        349131        2.52
1359835*1359835        939293        375359        2.50
1482910*1482910        1023155        431470        2.37
1617125*1617125        1148907        479196        2.40
1763488*1763488        1251408        479356        2.61
1923097*1923097        1361736        543979        2.50
2097152*2097152        1562511        627422        2.49
2286960*2286960        1667559        655844        2.54
2493948*2493948        1861228        755660        2.46
2719670*2719670        1979308        799447        2.48
2965821*2965821        2183367        903321        2.42
3234251*3234251        2404021        990645        2.43
3526975*3526975        2648709        1070849        2.47
3846194*3846194        2811668        1134798        2.48
4194304*4194304        3270555        1332069        2.46
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-23 22:10:40 | 显示全部楼层
64位basecase mul的原代码,见 mpn/x86_64/coreisbr/mul_basecase.asm,AT&T格式

  1. dnl  AMD64 mpn_mul_basecase optimised for Intel Sandy bridge and Ivy bridge.

  2. dnl  Contributed to the GNU project by Torbjörn Granlund.

  3. dnl  Copyright 2003-2005, 2007, 2008, 2011-2013 Free Software Foundation, Inc.

  4. dnl  This file is part of the GNU MP Library.
  5. dnl
  6. dnl  The GNU MP Library is free software; you can redistribute it and/or modify
  7. dnl  it under the terms of either:
  8. dnl
  9. dnl    * the GNU Lesser General Public License as published by the Free
  10. dnl      Software Foundation; either version 3 of the License, or (at your
  11. dnl      option) any later version.
  12. dnl
  13. dnl  or
  14. dnl
  15. dnl    * the GNU General Public License as published by the Free Software
  16. dnl      Foundation; either version 2 of the License, or (at your option) any
  17. dnl      later version.
  18. dnl
  19. dnl  or both in parallel, as here.
  20. dnl
  21. dnl  The GNU MP Library is distributed in the hope that it will be useful, but
  22. dnl  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  23. dnl  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  24. dnl  for more details.
  25. dnl
  26. dnl  You should have received copies of the GNU General Public License and the
  27. dnl  GNU Lesser General Public License along with the GNU MP Library.  If not,
  28. dnl  see https://www.gnu.org/licenses/.

  29. include(`../config.m4')

  30. C cycles/limb        mul_1                mul_2                mul_3                addmul_2
  31. C AMD K8,K9
  32. C AMD K10
  33. C AMD bull
  34. C AMD pile
  35. C AMD steam
  36. C AMD bobcat
  37. C AMD jaguar
  38. C Intel P4
  39. C Intel core
  40. C Intel NHM
  41. C Intel SBR         2.5                 2.5                 -                 2.95
  42. C Intel IBR         2.4                 2.3                 -                 2.68
  43. C Intel HWL         2.35                 2.0                 -                 2.5
  44. C Intel BWL
  45. C Intel atom
  46. C VIA nano

  47. C The inner loops of this code are the result of running a code generation and
  48. C optimisation tool suite written by David Harvey and Torbjorn Granlund.

  49. C TODO
  50. C  * Fix the addmul_2 fluctuation affecting SBR.
  51. C  * Improve feed-in code, avoiding zeroing of many registers and dummy adds in
  52. C    the loops at the expense of code size.
  53. C  * Adjoin a mul_3, avoiding slow mul_1 for odd vn.
  54. C  * Consider replacing the 2-way mul_2 code with 4-way code, for a very slight
  55. C    speedup.
  56. C  * Further micro-optimise.

  57. C When playing with pointers, set this to $2 to fall back to conservative
  58. C indexing in wind-down code.
  59. define(`I',`$1')


  60. define(`rp',      `%rdi')
  61. define(`up',      `%rsi')
  62. define(`un_param',`%rdx')
  63. define(`vp',      `%rcx')
  64. define(`vn',      `%r8')

  65. define(`un',      `%rbx')

  66. define(`w0',        `%r10')
  67. define(`w1',        `%r11')
  68. define(`w2',        `%r12')
  69. define(`w3',        `%r13')
  70. define(`n',        `%rbp')
  71. define(`v0',        `%r9')

  72. ABI_SUPPORT(DOS64)
  73. ABI_SUPPORT(STD64)

  74. ASM_START()
  75.         TEXT
  76.         ALIGN(16)
  77. PROLOGUE(mpn_mul_basecase)
  78.         FUNC_ENTRY(4)
  79. IFDOS(`        mov        56(%rsp), %r8d        ')
  80.         push        %rbx
  81.         push        %rbp
  82.         mov        un_param, un                C free up rdx
  83.         neg        un

  84.         mov        (up), %rax                C shared for mul_1 and mul_2
  85.         lea        (up,un_param,8), up        C point at operand end
  86.         lea        (rp,un_param,8), rp        C point at rp[un-1]

  87.         mov        (vp), v0                C shared for mul_1 and mul_2
  88.         mul        v0                        C shared for mul_1 and mul_2

  89.         test        $1, R8(vn)
  90.         jz        L(do_mul_2)

  91. L(do_mul_1):
  92.         test        $1, R8(un)
  93.         jnz        L(m1x1)

  94. L(m1x0):mov        %rax, w0                C un = 2, 4, 6, 8, ...
  95.         mov        %rdx, w1
  96.         mov        8(up,un,8), %rax
  97.         test        $2, R8(un)
  98.         jnz        L(m110)

  99. L(m100):lea        2(un), n                C un = 4, 8, 12, ...
  100.         jmp        L(m1l0)

  101. L(m110):lea        (un), n                        C un = 2, 6, 10, ...
  102.         jmp        L(m1l2)

  103. L(m1x1):mov        %rax, w1                C un = 1, 3, 5, 7, ...
  104.         mov        %rdx, w0
  105.         test        $2, R8(un)
  106.         jz        L(m111)

  107. L(m101):lea        3(un), n                C un = 1, 5, 9, ...
  108.         test        n, n
  109.         js        L(m1l1)
  110.         mov        %rax, -8(rp)
  111.         mov        %rdx, (rp)
  112.         pop        %rbp
  113.         pop        %rbx
  114.         FUNC_EXIT()
  115.         ret

  116. L(m111):lea        1(un), n                C un = 3, 7, 11, ...
  117.         mov        8(up,un,8), %rax
  118.         jmp        L(m1l3)

  119.         ALIGN(16)                C FIXME
  120. L(m1tp):mov        %rdx, w0
  121.         add        %rax, w1
  122. L(m1l1):mov        -16(up,n,8), %rax
  123.         adc        $0, w0
  124.         mul        v0
  125.         add        %rax, w0
  126.         mov        w1, -24(rp,n,8)
  127.         mov        -8(up,n,8), %rax
  128.         mov        %rdx, w1
  129.         adc        $0, w1
  130. L(m1l0):mul        v0
  131.         mov        w0, -16(rp,n,8)
  132.         add        %rax, w1
  133.         mov        %rdx, w0
  134.         mov        (up,n,8), %rax
  135.         adc        $0, w0
  136. L(m1l3):mul        v0
  137.         mov        w1, -8(rp,n,8)
  138.         mov        %rdx, w1
  139.         add        %rax, w0
  140.         mov        8(up,n,8), %rax
  141.         adc        $0, w1
  142. L(m1l2):mul        v0
  143.         mov        w0, (rp,n,8)
  144.         add        $4, n
  145.         jnc        L(m1tp)

  146. L(m1ed):add        %rax, w1
  147.         adc        $0, %rdx
  148.         mov        w1, I(-8(rp),-24(rp,n,8))
  149.         mov        %rdx, I((rp),-16(rp,n,8))

  150.         dec        R32(vn)
  151.         jz        L(ret2)

  152.         lea        8(vp), vp
  153.         lea        8(rp), rp
  154.         push        %r12
  155.         push        %r13
  156.         push        %r14
  157.         jmp        L(do_addmul)

  158. L(do_mul_2):
  159. define(`v1',        `%r14')
  160.         push        %r12
  161.         push        %r13
  162.         push        %r14

  163.         mov        8(vp), v1

  164.         test        $1, R8(un)
  165.         jnz        L(m2b1)

  166. L(m2b0):lea        (un), n
  167.         xor        w0, w0
  168.         mov        %rax, w2
  169.         mov        %rdx, w1
  170.         jmp        L(m2l0)

  171. L(m2b1):lea        1(un), n
  172.         xor        w1, w1
  173.         xor        w2, w2
  174.         mov        %rax, w0
  175.         mov        %rdx, w3
  176.         jmp        L(m2l1)

  177.         ALIGN(32)
  178. L(m2tp):mul        v0
  179.         add        %rax, w0
  180.         mov        %rdx, w3
  181.         adc        $0, w3
  182. L(m2l1):mov        -8(up,n,8), %rax
  183.         mul        v1
  184.         add        w1, w0
  185.         adc        $0, w3
  186.         add        %rax, w2
  187.         mov        w0, -8(rp,n,8)
  188.         mov        %rdx, w0
  189.         adc        $0, w0
  190.         mov        (up,n,8), %rax
  191.         mul        v0
  192.         add        %rax, w2
  193.         mov        %rdx, w1
  194.         adc        $0, w1
  195.         add        w3, w2
  196. L(m2l0):mov        (up,n,8), %rax
  197.         adc        $0, w1
  198.         mul        v1
  199.         mov        w2, (rp,n,8)
  200.         add        %rax, w0
  201.         mov        %rdx, w2
  202.         mov        8(up,n,8), %rax
  203.         adc        $0, w2
  204.         add        $2, n
  205.         jnc        L(m2tp)

  206. L(m2ed):mul        v0
  207.         add        %rax, w0
  208.         mov        %rdx, w3
  209.         adc        $0, w3
  210.         mov        I(-8(up),-8(up,n,8)), %rax
  211.         mul        v1
  212.         add        w1, w0
  213.         adc        $0, w3
  214.         add        %rax, w2
  215.         mov        w0, I(-8(rp),-8(rp,n,8))
  216.         adc        $0, %rdx
  217.         add        w3, w2
  218.         mov        w2, I((rp),(rp,n,8))
  219.         adc        $0, %rdx
  220.         mov        %rdx, I(8(rp),8(rp,n,8))

  221.         add        $-2, R32(vn)
  222.         jz        L(ret5)
  223.         lea        16(vp), vp
  224.         lea        16(rp), rp


  225. L(do_addmul):
  226.         push        %r15
  227.         push        vn                        C save vn in new stack slot
  228. define(`vn',        `(%rsp)')
  229. define(`X0',        `%r14')
  230. define(`X1',        `%r15')
  231. define(`v1',        `%r8')

  232. L(outer):
  233.         mov        (vp), v0
  234.         mov        8(vp), v1
  235.         mov        (up,un,8), %rax
  236.         mul        v0
  237.         test        $1, R8(un)
  238.         jnz        L(a1x1)

  239. L(a1x0):mov        (rp,un,8), X0
  240.         xor        w0, w0
  241.         mov        %rdx, w1
  242.         test        $2, R8(un)
  243.         jnz        L(a110)

  244. L(a100):lea        2(un), n                C un = 4, 8, 12, ...
  245.         add        %rax, X0
  246.         adc        $0, w1
  247.         mov        (up,un,8), %rax
  248.         mul        v1
  249.         mov        8(rp,un,8), X1
  250.         jmp        L(lo0)

  251. L(a110):lea        (un), n                        C un = 2, 6, 10, ...
  252.         xor        w3, w3
  253.         jmp        L(lo2)

  254. L(a1x1):mov        (rp,un,8), X1
  255.         xor        w2, w2
  256.         xor        w1, w1
  257.         test        $2, R8(un)
  258.         jz        L(a111)

  259. L(a101):lea        3(un), n                C un = 1, 5, 9, ...
  260.         mov        %rdx, w3
  261.         add        %rax, X1
  262.         mov        (up,un,8), %rax
  263.         mov        8(rp,un,8), X0
  264.         adc        $0, w3
  265.         jmp        L(top)

  266. L(a111):lea        1(un), n                C un = 3, 7, 11, ...
  267.         jmp        L(lo3)

  268.         ALIGN(32)
  269. L(top):        mul        v1
  270.         mov        %rdx, w0
  271.         add        %rax, X0
  272.         adc        $0, w0
  273.         add        w1, X1
  274.         adc        $0, w3
  275.         add        w2, X0
  276.         adc        $0, w0
  277.         mov        -16(up,n,8), %rax
  278.         mul        v0
  279.         add        %rax, X0
  280.         mov        %rdx, w1
  281.         adc        $0, w1
  282.         mov        -16(up,n,8), %rax
  283.         mul        v1
  284.         mov        X1, -24(rp,n,8)
  285.         mov        -8(rp,n,8), X1
  286.         add        w3, X0
  287.         adc        $0, w1
  288. L(lo0):        mov        %rdx, w2
  289.         mov        X0, -16(rp,n,8)
  290.         add        %rax, X1
  291.         adc        $0, w2
  292.         mov        -8(up,n,8), %rax
  293.         add        w0, X1
  294.         adc        $0, w2
  295.         mul        v0
  296. L(lo3):        add        %rax, X1
  297.         mov        %rdx, w3
  298.         adc        $0, w3
  299.         mov        -8(up,n,8), %rax
  300.         mul        v1
  301.         add        w1, X1
  302.         mov        (rp,n,8), X0
  303.         adc        $0, w3
  304.         mov        %rdx, w0
  305.         add        %rax, X0
  306.         adc        $0, w0
  307.         mov        (up,n,8), %rax
  308.         mul        v0
  309.         add        w2, X0
  310.         mov        X1, -8(rp,n,8)
  311.         mov        %rdx, w1
  312.         adc        $0, w0
  313. L(lo2):        add        %rax, X0
  314.         adc        $0, w1
  315.         mov        (up,n,8), %rax
  316.         add        w3, X0
  317.         adc        $0, w1
  318.         mul        v1
  319.         mov        8(rp,n,8), X1
  320.         add        %rax, X1
  321.         mov        %rdx, w2
  322.         adc        $0, w2
  323.         mov        8(up,n,8), %rax
  324.         mov        X0, (rp,n,8)
  325.         mul        v0
  326.         add        w0, X1
  327.         mov        %rdx, w3
  328.         adc        $0, w2
  329.         add        %rax, X1
  330.         mov        8(up,n,8), %rax
  331.         mov        16(rp,n,8), X0                C useless but harmless in final iter
  332.         adc        $0, w3
  333.         add        $4, n
  334.         jnc        L(top)

  335. L(end):        mul        v1
  336.         add        w1, X1
  337.         adc        $0, w3
  338.         add        w2, %rax
  339.         adc        $0, %rdx
  340.         mov        X1, I(-8(rp),-24(rp,n,8))
  341.         add        w3, %rax
  342.         adc        $0, %rdx
  343.         mov        %rax, I((rp),-16(rp,n,8))
  344.         mov        %rdx, I(8(rp),-8(rp,n,8))

  345.         addl        $-2, vn
  346.         lea        16(vp), vp
  347.         lea        16(rp), rp
  348.         jnz        L(outer)

  349.         pop        %rax                C deallocate vn slot
  350.         pop        %r15
  351. L(ret5):pop        %r14
  352.         pop        %r13
  353.         pop        %r12
  354. L(ret2):pop        %rbp
  355.         pop        %rbx
  356.         FUNC_EXIT()
  357.         ret
  358. EPILOGUE()
复制代码


反汇编后的原代码,Intel格式 
  1. 00000000000008a0 <__gmpn_mul_basecase>:
  2. 8a0:        53                           push   rbx
  3. 8a1:        55                           push   rbp
  4. 8a2:        48 89 d3                     mov    rbx,rdx
  5. 8a5:        48 f7 db                     neg    rbx
  6. 8a8:        48 8b 06                     mov    rax,QWORD PTR [rsi]
  7. 8ab:        48 8d 34 d6                  lea    rsi,[rsi+rdx*8]
  8. 8af:        48 8d 3c d7                  lea    rdi,[rdi+rdx*8]
  9. 8b3:        4c 8b 09                     mov    r9,QWORD PTR [rcx]
  10. 8b6:        49 f7 e1                     mul    r9
  11. 8b9:        41 f6 c0 01                  test   r8b,0x1
  12. 8bd:        0f 84 d7 00 00 00            je     99a <__gmpn_mul_basecase+0xfa>
  13. 8c3:        f6 c3 01                     test   bl,0x1
  14. 8c6:        75 1e                        jne    8e6 <__gmpn_mul_basecase+0x46>
  15. 8c8:        49 89 c2                     mov    r10,rax
  16. 8cb:        49 89 d3                     mov    r11,rdx
  17. 8ce:        48 8b 44 de 08               mov    rax,QWORD PTR [rsi+rbx*8+0x8]
  18. 8d3:        f6 c3 02                     test   bl,0x2
  19. 8d6:        75 06                        jne    8de <__gmpn_mul_basecase+0x3e>
  20. 8d8:        48 8d 6b 02                  lea    rbp,[rbx+0x2]
  21. 8dc:        eb 58                        jmp    936 <__gmpn_mul_basecase+0x96>
  22. 8de:        48 8d 2b                     lea    rbp,[rbx]
  23. 8e1:        e9 7d 00 00 00               jmp    963 <__gmpn_mul_basecase+0xc3>
  24. 8e6:        49 89 c3                     mov    r11,rax
  25. 8e9:        49 89 d2                     mov    r10,rdx
  26. 8ec:        f6 c3 02                     test   bl,0x2
  27. 8ef:        74 13                        je     904 <__gmpn_mul_basecase+0x64>
  28. 8f1:        48 8d 6b 03                  lea    rbp,[rbx+0x3]
  29. 8f5:        48 85 ed                     test   rbp,rbp
  30. 8f8:        78 1c                        js     916 <__gmpn_mul_basecase+0x76>
  31. 8fa:        48 89 47 f8                  mov    QWORD PTR [rdi-0x8],rax
  32. 8fe:        48 89 17                     mov    QWORD PTR [rdi],rdx
  33. 901:        5d                           pop    rbp
  34. 902:        5b                           pop    rbx
  35. 903:        c3                           ret   
  36. 904:        48 8d 6b 01                  lea    rbp,[rbx+0x1]
  37. 908:        48 8b 44 de 08               mov    rax,QWORD PTR [rsi+rbx*8+0x8]
  38. 90d:        eb 3d                        jmp    94c <__gmpn_mul_basecase+0xac>
  39. 90f:        90                           nop
  40. 910:        49 89 d2                     mov    r10,rdx
  41. 913:        49 01 c3                     add    r11,rax
  42. 916:        48 8b 44 ee f0               mov    rax,QWORD PTR [rsi+rbp*8-0x10]
  43. 91b:        49 83 d2 00                  adc    r10,0x0
  44. 91f:        49 f7 e1                     mul    r9
  45. 922:        49 01 c2                     add    r10,rax
  46. 925:        4c 89 5c ef e8               mov    QWORD PTR [rdi+rbp*8-0x18],r11
  47. 92a:        48 8b 44 ee f8               mov    rax,QWORD PTR [rsi+rbp*8-0x8]
  48. 92f:        49 89 d3                     mov    r11,rdx
  49. 932:        49 83 d3 00                  adc    r11,0x0
  50. 936:        49 f7 e1                     mul    r9
  51. 939:        4c 89 54 ef f0               mov    QWORD PTR [rdi+rbp*8-0x10],r10
  52. 93e:        49 01 c3                     add    r11,rax
  53. 941:        49 89 d2                     mov    r10,rdx
  54. 944:        48 8b 04 ee                  mov    rax,QWORD PTR [rsi+rbp*8]
  55. 948:        49 83 d2 00                  adc    r10,0x0
  56. 94c:        49 f7 e1                     mul    r9
  57. 94f:        4c 89 5c ef f8               mov    QWORD PTR [rdi+rbp*8-0x8],r11
  58. 954:        49 89 d3                     mov    r11,rdx
  59. 957:        49 01 c2                     add    r10,rax
  60. 95a:        48 8b 44 ee 08               mov    rax,QWORD PTR [rsi+rbp*8+0x8]
  61. 95f:        49 83 d3 00                  adc    r11,0x0
  62. 963:        49 f7 e1                     mul    r9
  63. 966:        4c 89 14 ef                  mov    QWORD PTR [rdi+rbp*8],r10
  64. 96a:        48 83 c5 04                  add    rbp,0x4
  65. 96e:        73 a0                        jae    910 <__gmpn_mul_basecase+0x70>
  66. 970:        49 01 c3                     add    r11,rax
  67. 973:        48 83 d2 00                  adc    rdx,0x0
  68. 977:        4c 89 5f f8                  mov    QWORD PTR [rdi-0x8],r11
  69. 97b:        48 89 17                     mov    QWORD PTR [rdi],rdx
  70. 97e:        41 ff c8                     dec    r8d
  71. 981:        0f 84 cd 02 00 00            je     c54 <__gmpn_mul_basecase+0x3b4>
  72. 987:        48 8d 49 08                  lea    rcx,[rcx+0x8]
  73. 98b:        48 8d 7f 08                  lea    rdi,[rdi+0x8]
  74. 98f:        41 54                        push   r12
  75. 991:        41 55                        push   r13
  76. 993:        41 56                        push   r14
  77. 995:        e9 ef 00 00 00               jmp    a89 <__gmpn_mul_basecase+0x1e9>
  78. 99a:        41 54                        push   r12
  79. 99c:        41 55                        push   r13
  80. 99e:        41 56                        push   r14
  81. 9a0:        4c 8b 71 08                  mov    r14,QWORD PTR [rcx+0x8]
  82. 9a4:        f6 c3 01                     test   bl,0x1
  83. 9a7:        75 0e                        jne    9b7 <__gmpn_mul_basecase+0x117>
  84. 9a9:        48 8d 2b                     lea    rbp,[rbx]
  85. 9ac:        4d 31 d2                     xor    r10,r10
  86. 9af:        49 89 c4                     mov    r12,rax
  87. 9b2:        49 89 d3                     mov    r11,rdx
  88. 9b5:        eb 68                        jmp    a1f <__gmpn_mul_basecase+0x17f>
  89. 9b7:        48 8d 6b 01                  lea    rbp,[rbx+0x1]
  90. 9bb:        4d 31 db                     xor    r11,r11
  91. 9be:        4d 31 e4                     xor    r12,r12
  92. 9c1:        49 89 c2                     mov    r10,rax
  93. 9c4:        49 89 d5                     mov    r13,rdx
  94. 9c7:        eb 24                        jmp    9ed <__gmpn_mul_basecase+0x14d>
  95. 9c9:        0f 1f 00                     nop    DWORD PTR [rax]
  96. 9cc:        66 2e 0f 1f 84 00 00         nop    WORD PTR cs:[rax+rax*1+0x0]
  97. 9d3:        00 00 00
  98. 9d6:        66 2e 0f 1f 84 00 00         nop    WORD PTR cs:[rax+rax*1+0x0]
  99. 9dd:        00 00 00
  100. 9e0:        49 f7 e1                     mul    r9
  101. 9e3:        49 01 c2                     add    r10,rax
  102. 9e6:        49 89 d5                     mov    r13,rdx
  103. 9e9:        49 83 d5 00                  adc    r13,0x0
  104. 9ed:        48 8b 44 ee f8               mov    rax,QWORD PTR [rsi+rbp*8-0x8]
  105. 9f2:        49 f7 e6                     mul    r14
  106. 9f5:        4d 01 da                     add    r10,r11
  107. 9f8:        49 83 d5 00                  adc    r13,0x0
  108. 9fc:        49 01 c4                     add    r12,rax
  109. 9ff:        4c 89 54 ef f8               mov    QWORD PTR [rdi+rbp*8-0x8],r10
  110. a04:        49 89 d2                     mov    r10,rdx
  111. a07:        49 83 d2 00                  adc    r10,0x0
  112. a0b:        48 8b 04 ee                  mov    rax,QWORD PTR [rsi+rbp*8]
  113. a0f:        49 f7 e1                     mul    r9
  114. a12:        49 01 c4                     add    r12,rax
  115. a15:        49 89 d3                     mov    r11,rdx
  116. a18:        49 83 d3 00                  adc    r11,0x0
  117. a1c:        4d 01 ec                     add    r12,r13
  118. a1f:        48 8b 04 ee                  mov    rax,QWORD PTR [rsi+rbp*8]
  119. a23:        49 83 d3 00                  adc    r11,0x0
  120. a27:        49 f7 e6                     mul    r14
  121. a2a:        4c 89 24 ef                  mov    QWORD PTR [rdi+rbp*8],r12
  122. a2e:        49 01 c2                     add    r10,rax
  123. a31:        49 89 d4                     mov    r12,rdx
  124. a34:        48 8b 44 ee 08               mov    rax,QWORD PTR [rsi+rbp*8+0x8]
  125. a39:        49 83 d4 00                  adc    r12,0x0
  126. a3d:        48 83 c5 02                  add    rbp,0x2
  127. a41:        73 9d                        jae    9e0 <__gmpn_mul_basecase+0x140>
  128. a43:        49 f7 e1                     mul    r9
  129. a46:        49 01 c2                     add    r10,rax
  130. a49:        49 89 d5                     mov    r13,rdx
  131. a4c:        49 83 d5 00                  adc    r13,0x0
  132. a50:        48 8b 46 f8                  mov    rax,QWORD PTR [rsi-0x8]
  133. a54:        49 f7 e6                     mul    r14
  134. a57:        4d 01 da                     add    r10,r11
  135. a5a:        49 83 d5 00                  adc    r13,0x0
  136. a5e:        49 01 c4                     add    r12,rax
  137. a61:        4c 89 57 f8                  mov    QWORD PTR [rdi-0x8],r10
  138. a65:        48 83 d2 00                  adc    rdx,0x0
  139. a69:        4d 01 ec                     add    r12,r13
  140. a6c:        4c 89 27                     mov    QWORD PTR [rdi],r12
  141. a6f:        48 83 d2 00                  adc    rdx,0x0
  142. a73:        48 89 57 08                  mov    QWORD PTR [rdi+0x8],rdx
  143. a77:        41 83 c0 fe                  add    r8d,0xfffffffe
  144. a7b:        0f 84 cd 01 00 00            je     c4e <__gmpn_mul_basecase+0x3ae>
  145. a81:        48 8d 49 10                  lea    rcx,[rcx+0x10]
  146. a85:        48 8d 7f 10                  lea    rdi,[rdi+0x10]
  147. a89:        41 57                        push   r15
  148. a8b:        41 50                        push   r8
  149. a8d:        4c 8b 09                     mov    r9,QWORD PTR [rcx]
  150. a90:        4c 8b 41 08                  mov    r8,QWORD PTR [rcx+0x8]
  151. a94:        48 8b 04 de                  mov    rax,QWORD PTR [rsi+rbx*8]
  152. a98:        49 f7 e1                     mul    r9
  153. a9b:        f6 c3 01                     test   bl,0x1
  154. a9e:        75 36                        jne    ad6 <__gmpn_mul_basecase+0x236>
  155. aa0:        4c 8b 34 df                  mov    r14,QWORD PTR [rdi+rbx*8]
  156. aa4:        4d 31 d2                     xor    r10,r10
  157. aa7:        49 89 d3                     mov    r11,rdx
  158. aaa:        f6 c3 02                     test   bl,0x2
  159. aad:        75 1c                        jne    acb <__gmpn_mul_basecase+0x22b>
  160. aaf:        48 8d 6b 02                  lea    rbp,[rbx+0x2]
  161. ab3:        49 01 c6                     add    r14,rax
  162. ab6:        49 83 d3 00                  adc    r11,0x0
  163. aba:        48 8b 04 de                  mov    rax,QWORD PTR [rsi+rbx*8]
  164. abe:        49 f7 e0                     mul    r8
  165. ac1:        4c 8b 7c df 08               mov    r15,QWORD PTR [rdi+rbx*8+0x8]
  166. ac6:        e9 9b 00 00 00               jmp    b66 <__gmpn_mul_basecase+0x2c6>
  167. acb:        48 8d 2b                     lea    rbp,[rbx]
  168. ace:        4d 31 ed                     xor    r13,r13
  169. ad1:        e9 eb 00 00 00               jmp    bc1 <__gmpn_mul_basecase+0x321>
  170. ad6:        4c 8b 3c df                  mov    r15,QWORD PTR [rdi+rbx*8]
  171. ada:        4d 31 e4                     xor    r12,r12
  172. add:        4d 31 db                     xor    r11,r11
  173. ae0:        f6 c3 02                     test   bl,0x2
  174. ae3:        74 19                        je     afe <__gmpn_mul_basecase+0x25e>
  175. ae5:        48 8d 6b 03                  lea    rbp,[rbx+0x3]
  176. ae9:        49 89 d5                     mov    r13,rdx
  177. aec:        49 01 c7                     add    r15,rax
  178. aef:        48 8b 04 de                  mov    rax,QWORD PTR [rsi+rbx*8]
  179. af3:        4c 8b 74 df 08               mov    r14,QWORD PTR [rdi+rbx*8+0x8]
  180. af8:        49 83 d5 00                  adc    r13,0x0
  181. afc:        eb 22                        jmp    b20 <__gmpn_mul_basecase+0x280>
  182. afe:        48 8d 6b 01                  lea    rbp,[rbx+0x1]
  183. b02:        e9 7d 00 00 00               jmp    b84 <__gmpn_mul_basecase+0x2e4>
  184. b07:        0f 1f 44 00 00               nop    DWORD PTR [rax+rax*1+0x0]
  185. b0c:        66 2e 0f 1f 84 00 00         nop    WORD PTR cs:[rax+rax*1+0x0]
  186. b13:        00 00 00
  187. b16:        66 2e 0f 1f 84 00 00         nop    WORD PTR cs:[rax+rax*1+0x0]
  188. b1d:        00 00 00
  189. b20:        49 f7 e0                     mul    r8
  190. b23:        49 89 d2                     mov    r10,rdx
  191. b26:        49 01 c6                     add    r14,rax
  192. b29:        49 83 d2 00                  adc    r10,0x0
  193. b2d:        4d 01 df                     add    r15,r11
  194. b30:        49 83 d5 00                  adc    r13,0x0
  195. b34:        4d 01 e6                     add    r14,r12
  196. b37:        49 83 d2 00                  adc    r10,0x0
  197. b3b:        48 8b 44 ee f0               mov    rax,QWORD PTR [rsi+rbp*8-0x10]
  198. b40:        49 f7 e1                     mul    r9
  199. b43:        49 01 c6                     add    r14,rax
  200. b46:        49 89 d3                     mov    r11,rdx
  201. b49:        49 83 d3 00                  adc    r11,0x0
  202. b4d:        48 8b 44 ee f0               mov    rax,QWORD PTR [rsi+rbp*8-0x10]
  203. b52:        49 f7 e0                     mul    r8
  204. b55:        4c 89 7c ef e8               mov    QWORD PTR [rdi+rbp*8-0x18],r15
  205. b5a:        4c 8b 7c ef f8               mov    r15,QWORD PTR [rdi+rbp*8-0x8]
  206. b5f:        4d 01 ee                     add    r14,r13
  207. b62:        49 83 d3 00                  adc    r11,0x0
  208. b66:        49 89 d4                     mov    r12,rdx
  209. b69:        4c 89 74 ef f0               mov    QWORD PTR [rdi+rbp*8-0x10],r14
  210. b6e:        49 01 c7                     add    r15,rax
  211. b71:        49 83 d4 00                  adc    r12,0x0
  212. b75:        48 8b 44 ee f8               mov    rax,QWORD PTR [rsi+rbp*8-0x8]
  213. b7a:        4d 01 d7                     add    r15,r10
  214. b7d:        49 83 d4 00                  adc    r12,0x0
  215. b81:        49 f7 e1                     mul    r9
  216. b84:        49 01 c7                     add    r15,rax
  217. b87:        49 89 d5                     mov    r13,rdx
  218. b8a:        49 83 d5 00                  adc    r13,0x0
  219. b8e:        48 8b 44 ee f8               mov    rax,QWORD PTR [rsi+rbp*8-0x8]
  220. b93:        49 f7 e0                     mul    r8
  221. b96:        4d 01 df                     add    r15,r11
  222. b99:        4c 8b 34 ef                  mov    r14,QWORD PTR [rdi+rbp*8]
  223. b9d:        49 83 d5 00                  adc    r13,0x0
  224. ba1:        49 89 d2                     mov    r10,rdx
  225. ba4:        49 01 c6                     add    r14,rax
  226. ba7:        49 83 d2 00                  adc    r10,0x0
  227. bab:        48 8b 04 ee                  mov    rax,QWORD PTR [rsi+rbp*8]
  228. baf:        49 f7 e1                     mul    r9
  229. bb2:        4d 01 e6                     add    r14,r12
  230. bb5:        4c 89 7c ef f8               mov    QWORD PTR [rdi+rbp*8-0x8],r15
  231. bba:        49 89 d3                     mov    r11,rdx
  232. bbd:        49 83 d2 00                  adc    r10,0x0
  233. bc1:        49 01 c6                     add    r14,rax
  234. bc4:        49 83 d3 00                  adc    r11,0x0
  235. bc8:        48 8b 04 ee                  mov    rax,QWORD PTR [rsi+rbp*8]
  236. bcc:        4d 01 ee                     add    r14,r13
  237. bcf:        49 83 d3 00                  adc    r11,0x0
  238. bd3:        49 f7 e0                     mul    r8
  239. bd6:        4c 8b 7c ef 08               mov    r15,QWORD PTR [rdi+rbp*8+0x8]
  240. bdb:        49 01 c7                     add    r15,rax
  241. bde:        49 89 d4                     mov    r12,rdx
  242. be1:        49 83 d4 00                  adc    r12,0x0
  243. be5:        48 8b 44 ee 08               mov    rax,QWORD PTR [rsi+rbp*8+0x8]
  244. bea:        4c 89 34 ef                  mov    QWORD PTR [rdi+rbp*8],r14
  245. bee:        49 f7 e1                     mul    r9
  246. bf1:        4d 01 d7                     add    r15,r10
  247. bf4:        49 89 d5                     mov    r13,rdx
  248. bf7:        49 83 d4 00                  adc    r12,0x0
  249. bfb:        49 01 c7                     add    r15,rax
  250. bfe:        48 8b 44 ee 08               mov    rax,QWORD PTR [rsi+rbp*8+0x8]
  251. c03:        4c 8b 74 ef 10               mov    r14,QWORD PTR [rdi+rbp*8+0x10]
  252. c08:        49 83 d5 00                  adc    r13,0x0
  253. c0c:        48 83 c5 04                  add    rbp,0x4
  254. c10:        0f 83 0a ff ff ff            jae    b20 <__gmpn_mul_basecase+0x280>
  255. c16:        49 f7 e0                     mul    r8
  256. c19:        4d 01 df                     add    r15,r11
  257. c1c:        49 83 d5 00                  adc    r13,0x0
  258. c20:        4c 01 e0                     add    rax,r12
  259. c23:        48 83 d2 00                  adc    rdx,0x0
  260. c27:        4c 89 7f f8                  mov    QWORD PTR [rdi-0x8],r15
  261. c2b:        4c 01 e8                     add    rax,r13
  262. c2e:        48 83 d2 00                  adc    rdx,0x0
  263. c32:        48 89 07                     mov    QWORD PTR [rdi],rax
  264. c35:        48 89 57 08                  mov    QWORD PTR [rdi+0x8],rdx
  265. c39:        83 04 24 fe                  add    DWORD PTR [rsp],0xfffffffe
  266. c3d:        48 8d 49 10                  lea    rcx,[rcx+0x10]
  267. c41:        48 8d 7f 10                  lea    rdi,[rdi+0x10]
  268. c45:        0f 85 42 fe ff ff            jne    a8d <__gmpn_mul_basecase+0x1ed>
  269. c4b:        58                           pop    rax
  270. c4c:        41 5f                        pop    r15
  271. c4e:        41 5e                        pop    r14
  272. c50:        41 5d                        pop    r13
  273. c52:        41 5c                        pop    r12
  274. c54:        5d                           pop    rbp
  275. c55:        5b                           pop    rbx
  276. c56:        c3                           ret   
复制代码

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-24 09:11:51 | 显示全部楼层
liangbch 发表于 2020-2-23 20:42
实际测试了一下,64位版本的效能大约为32位版本的2.6倍左右,比想象的要低一些。
我的电脑是Intel(R) Xeo ...
谢谢!非常感谢!这样,我对 x64 平台的性能有个预期目标了。


其实,从测试数据来看,2.6 倍已经是非常不错了(甚至好于预期),如果不是 OS 处理的差异,仅就算法层面来说。

在 gmp-man-6.2.0.pdf 中:
The overheads grow as O(Nr), whereas in an r = 2k FFT they grow only as
O(N log r).
这里的对数,可以当成以 2 为底的对数。


以比例最大的 3.55 为例(185364*185364),
\(L=185364, b=32\)
\(N(b)=L/b=5792.625\)
\(r(b)=log_2^{N(b)}=12.500\)
\(f(b)=N(b) r(b)\)
\(\D \text{ratio}=\frac{f(b)}{f(2b)}=\frac{2 r(b)}{r(b)-1}=2.174\)

替换 \(L=4194304\),可得对应的 \(\text{ratio}=2*22/(22-1)=2.095\)


从以上粗略的推导来看,
如果算法同处于 FFT 级别,随着 \(L\) 的增大, \(\text{ratio}\) 将递减,但下限始终在 \(2.0\) 之上,
而测试数据也正好印证了此结论。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-24 09:44:40 | 显示全部楼层

我最近在搭框架,
已声明了一些基础操作需要的函数,尤其是一些运算符的重载接口。
比如:构造、赋值、输出、比较、四则运算、位运算的等接口。
从已完成的部分来看,比十多年前的接口更合理。
比如命名方式:参照 stl 的命名方式,全小写加下划线。

其中,四则运算,仅完成了 +、- 部分(尚待优化);*/% 还未开始;&^| 位运算仅声明。
余下的比较重要的是:乘法部分的实现,以及 C++11 线程池的支持,
前者已有积累,后者需探索一下。

在完成四则运算之后,才会继续去考虑模幂算法,探索大整数素性检测;
而后再加上一些数论或整数函数,这样才初见雏形。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-5-16 13:17 , Processed in 0.071333 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表