Databases
StackOverflow2013
Postsdbo
POOptimizing x64 assembler MUL loop
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POOptimizing x64 assembler MUL loop
    primarykey
    data
    text
    <p>I'm writing math code which needs to multiply large numbers fast. It breaks down to multiplications of an array of integers with a single integer. In C++ this looks like this (on unsigned's):</p> <pre><code>void muladd(unsigned* r, const unsigned* a, unsigned len, unsigned b) { unsigned __int64 of = 0; // overflow unsigned i = 0; // loop variable while (i &lt; len) { of += (unsigned __int64)a[i] * b + r[i]; r[i] = (unsigned)of; of &gt;&gt;= 32; ++i; } r[i] = (unsigned)of; // save overflow } </code></pre> <p>I unrolled this loop manually, converted it to 64 bit and worked on the .asm compiler output to optimize it further. The main .asm loop now looks like this:</p> <pre><code>mov rax, rdi ; rdi = b mul QWORD PTR [rbx+r10*8-64] ; rdx:rax = a[i] * b; r10 = i mov rsi, QWORD PTR [r14+r10*8-64] ; r14 = r; rsi = r[i] add rax, rsi adc rdx, 0 add rax, r11 ; r11 = of (low part) adc rdx, 0 mov QWORD PTR [r14+r10*8-64], rax ; save result mov r11, rdx ; this repeats itself 8 times with different offsets </code></pre> <p>When I benchmark this, I find that it takes about 6.3 cycles on avarage per multiplication on my Core2 Quad. </p> <p>My question is: can I speed this up somehow? Unfortunately, I see no way to avoid one of the additions and the multiplication always needs RDX:RAX, so I need to move the data around and can not sort of "multiply in parallel".</p> <p>Any ideas anyone?</p> <p><strong>Update:</strong> After some more testing, I've managed to bring the speed up to about 5.4 cycles per 64-bit MUL (that includes all add, move and loop overhead). I guess this is about the best you can get on a Core2, since the Core2 does not have a very fast MUL instruction: it has a throughput of 3 and a latency of 6 (resp. 7) cycles. Sandy bridge will be much better with a throughput of 1 and a latency of 3 (resp. 4) cycles.</p> <p>Regarding the much lesser number for GMP: I got that from their source code and it seems to me that it is a theoretical number. But what's sure is that it's a number that was calculated for an AMD K9 CPU. And from what I have read I gather the AMDs have a faster MUL unit than the (older) Intel chips.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. UScxxl
    1. UScxxl
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POOptimizing x64 assembler MUL loop
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POOptimizing x64 assembler MUL loop
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POOptimizing x64 assembler MUL loop
      1. USNemo
      1. VTFavorite
    1. COYou might want to take a look at some of the assembly routines in GMP. They have a function that does exactly this and is written in assembly for most processors including x64.
      singulars
      1. POOptimizing x64 assembler MUL loop
      1. USMysticial
    2. COGMP really has good support for a fast mul_basecase and appearantly it takes them some 2.35 cycles per MUL, very nice. If I understood it correctly, they multiply two vectors interleaved, that seems to keep the dependencies low and improve overflow handling.
      singulars
      1. POOptimizing x64 assembler MUL loop
      1. UScxxl
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload