Correct. I am curious why although I imagine it has to do with caching (fewer cache misses). Apparently he addresses it in the video but I haven't watched it yet.
On a meta-note, I'm really happy to see more highly technical submissions like this hitting and sticking on the front page.
EDIT: from the slides:
Prefer 32 bit ints to all other sizes
1. 64 bit may make some code slower [no additional explanation given]
2. 8, 16 bit computation use conversion to 32 bits and back
Yes, caching. 32 bit quantities are often sufficient, and take up less space in cache.
Additionally, code that handles 32-bit registers in x86_64 is often shorter than its 64-bit counterpart due to the lack of REX prefixes in instructions. This also reduces the instruction cache footprint. Some instructions like integer division and multiplication are also faster when handling 32-bit quantities, but this depends on the microarchitecture in question.
"Additionally, code that handles 32-bit registers in x86_64 is often shorter than its 64-bit counterpart due to the lack of REX prefixes in instructions."
Excellent point, thank you. I was only thinking about the data cache. Interestingly, I believe 64-bit ARM (AArch64) instructions are still only 32 bits long though I haven't confirmed via google. Maybe someone can correct me.
Pointers would be an exception, of course. As others wrote he's talking about general data. Just because 64-bit ints are faster on 64-bit processors than on 32-bit processors doesn't mean you should use them when a 32-bit int would suffice.
Pointers don't have to be the exception. I'm working on a programming language runtime where objects are stored as a 32-bit value, with 3/4 of the range representing an integer, and 1/4 of the range (30 bits) representing a pointer. Given the constraint that pointer objects are aligned to 8 bytes, the 30-bits multiplied by 8 results in an 8GB addressable memory space. Pages within that space can be allocated using mmap with MAP_FIXED flag. Smaller memory usage results in more things in cache, resulting in higher performance.
So, your pointers will not be able to address bytes individually? No char pointers, or is it 8 byte chars? Or is this a completely different language without raw pointers?
On x86-64 linux you can `mmap` with the `MAP_32BIT` flag which gives you memory in the 32 bit address space.
As 32-bit writes to registers get implicitly zero-extended you can store and load those pointers in 32 bit without any performance drawbacks.
This all is a bit hackish. With the x32 abi you can simply have 32 bit pointers everywhere.
Your comment would have been amusingly surreal if there were no closing tags for the <uint32_t> stuff in the article. I'm almost disappointed that there were. I wonder who was responsible for that particular bug in the Facebook formatting code.
This post misses one of the most fundamental and important optimisations for 'digits10' that his compiler is likely doing for him: turning the divide by 10 in to a multiply by using a multiplicative inverse mod 2^64
Doesn't this quote from the article address that? Or was it a late add?
"Truth be told, it's a multiplication because many compilers transform all divisions by a constant into multiplications; see e.g. http://goo.gl/LhPeH "
Guess I missed it. Interestingly it seems to be impossible to do this optimisation yourself in C or C++ and get either Clang or GCC to generate the same machine code (on x86-64).
It is possible to coax that codegen out of clang. The trick is that you need the high half of the product, so you must use a larger type, in this case __uint128_t:
The algorithm was esoteric, confined to compilers. But there was no technical reason why it could not be implemented in a library: just nobody had done it yet. It was a hole waiting to be filled. It's also really fun to embarrass the compiler!
A deep understanding of the algorithm took me a long time, I think a few months. That was mainly due a lack of information describing the technique. The paper that Andrei linked to (Granlund-Montgomery) is dense and contains a significant error, which I was never able to get resolved. Henry Warren's celebrated Hacker's Delight is more accessible, but is also more of a proof-of-correctness than a learning resource. So my intuitive understanding came from my own investigating and playing around, which is what lead me to find an improvement on the algorithm.
Implementing libdivide took me maybe six months of my hobby time. It's not just the core algorithm - there's a lot of auxiliary functions, for example to compute the high half of a 64 bit multiply in SSE. But working at that level is tons of fun.
Incidentally, I wrote up what I hope to be the most accessible (yet still rigorous) description of the algorithm at http://ridiculousfish.com/blog/posts/labor-of-division-episo... . I advise anyone interested in learning more to start there, instead of the Granlund paper.
There is one oft-forgotten case that neither compilers nor (seemingly) libdivide seem to handle: when we know that an integer is a multiple of some constant, and we just want to get the result of the exact division.
This case allows for a simpler method, exemplified here (it also works for signed integers, but more care is needed with the shifting): http://goo.gl/D5q9IO
EDIT: On second thought, compilers are also not doing their best job on that example. f1 could be simplified to
mov rax, 4865095698
add edi, 1
imul rdi
shrd rax, rdx, 39
ret
It's not (by itself, at least). But you can give it hints, as in my example above (with __builtin_unreachable; other compilers have similar facilities, like __assume in MSVC). The compiler should, in theory, be able to deduce that x % 113 is always 0, and therefore must be a multiple of 113.
GCC has done this for 20 years... the point is this optimisation requires a wider integer type than 64bits (in this case, apparently, 67 bits). This optimisation is potentially important for anything generating bytecode, or native code inside a JIT.
Thanks a lot for this work, btw; I found your labor of division blog posts last year and integrated your code into my permutation generation logic, to very nice effect.
Just an FYI for anyone reading: It's not the multiplicative inverse of 10 modulo 2^64. Multiplying by it only works if the number is divisible by 10.
What it's happening here is something more clever:
let z be: (2^67 + 2)/10.
2^67 isn't divisible by 10 (that's why we add 2).
z = 14757395258967641293L
Now, I claim that
n/10 = floor(z * n/ 2^67)
z is an integer, but it represents the exact division of
(2^67 + 2)/10
we distribute the n:
(n * 2^67)/10 + 2 * n/10
we distribute the 2^67 division:
(n * 2^67)/(10 * 2^67) + 2 * n / (10 * 2^67)
simplify the terms:
n/10 + n/(10 * 2^66) [1]
Now:
floor(x/d + c) == floor(x/d) if c < 1/d
we want to take floor of that number[1], but as
n/(10 * 2^66) < 1/10
(the maximum value for n is 2^64 - 1), it follows that
floor(z * n / 2^67) = n/10.
That's what the code is doing:
0xcccccccccccccccd is 14757395258967641293L
the multiplication of z * n fits in 128 bits, and the mul instruction stores the higher 64 bits of $rax * $rdx into $rdx.
We need to divide by 2^67, whichs is shift 3 67 bits to the right. If we take the higher part (rdx) we get the higher 64 bits, and then we shift 3 bits to the right (shr $0x3, %rax) and that's our answer :).
I'd be interested in seeing how much of this advice applies to architectures other than x86.
As a side note, definitely don't follow the advice about using position-dependent code unless you are working in a very performance-intensive and isolated environment. Just a single non-relocatable module/dll completely undermines the benefits of ASLR, so an attacker with a copy of your program will have a much easier time crafting an attack against it.
A lot of it generally holds true if you're programming for x86/x64, ARM, or PowerPC. The "hierarchy of speed" could use some updating, I think these days it is more along the lines of:
1. Comparisons (no branch, just compare)
2. u/int add/subtract/bit operations
3. FP mul
4. FP add/sub
5. FP div
6. u/int mul
7. indexed array access (data in L1, including latency for data to move to registers)
8. u/int div
That rough order seems to generally hold on a modern Haswell processor or the in-order PowerPC cores in an Xbox 360, though the cycle counts will vary.
Being thoughtful with respect how you access your data, paying attention to the effects of access patterns on caching, will almost always help regardless of the target architecture :)
1. Comparisons (no branch, just compare) 2. u/int add/subtract/bit operations
Is there a reason you follow Andrei's lead and suggest that comparisons operations are faster than integer subtraction? At least for x64 on Intel, I think they would always be the same speed and thus should be grouped together. Are they different on the other platforms?
The only justification I can think of for that statement is that on modern processors (Sandy Bridge and above), micro-op fusion in the decode stage can fuse a comparison with a branch that immediately follows it, turning it into a "compare and branch" micro-op.
I didn't really get the benefits of not using PIC. My understanding is that, at compile time, the compiler will generate relative branches rather than absolute jumps, which is stored as an immediate in the instruction. Is it different for x86? Where's the speed advantage coming from?
It's not relative vs absolute, no. Jumps and call instructions have been using PC-relative values right from the start. You might be thinking of RIP-relative addressing, which is useful in PIC to access globals.
The problem is that there is no way to know at compile time the position of an instruction relative to its target. Non-PI code handles this by having the linker update the relevant constants in the machine code. PI code has to function without modification, so it must indirect through a global table.
It's this indirection that causes the speed hit. On the other hand, PI code benefits from the ability to share code pages, so it can be faster in some circumstances.
Another presentation by Andrei on similar matters from GoingNative 2013: Writing Quick Code in C++, Quickly [0]. From memory, it has (at least) these three majors points
* Measure, then optimize
* Pay attention to data layout to keep the cache hot
On my random forays into C++, I saw different things. Here were my three most important optimizations.
1. Replace strings with integers wherever possible. Create a mapping table, use the indexes.
2. Layout related objects close in memory. Even if it requires special data structures to do. Suppose that if I need A I am likely to need B soon. If B is physically close to A, then I am likely to find it in cache, which is about 10x as fast. So, for instance, don't store a tree as a bunch of random pointers. Store it as offsets inside of a fixed container of memory.
3. Process data according to how it is laid out in memory. For instance walk through a vector, don't do random access into it. Again this is all about trying to make sure that stuff is in cache as often as possible.
For the second and third points I found it was a case of do it perfectly or don't worry about it. For example if I am missing cache regularly in three places, fixing one only mades my code 50% faster. Fixing the second one almost doubled my speed. Getting the last one was an order of magnitude speed increase.
After making sure you're using the correct basic algorithms, cache optimization is probably the one major thing that's really worth thinking about.
Even with hyperthreading and all the other fancy tricks that modern CPUs have, it's still a huge deal. I learned about all this stuff in general terms at university years ago, but it didn't really click until recently that even when the CPU is at 100%, it's very very often stuck waiting for a memory read to complete.
>The speed hierarchy of operations is:
>
> comparisons
> (u)int add, subtract, bitops, shift
> floating point add, sub (separate unit!)
> ...
> (u)int division, remainder
This can't be right. A comparison necessitates either a branch or a cmov, and there's no way that either of those is faster than a basic ALU operation.
You can’t reasonably even talk about the “speed” of operations in isolation. You can discuss their latency in isolation (in which case a branch or cmov, on average, really is faster than some ALU operations), but that has essentially nothing to do with their actual impact on performance in situ, except for in the most unusual cases.
Throughput is somewhat more reasonable, but then large parts of the hierarchy collapse entirely. A more reasonable approach is to think about resource (ALU, LSU, branch, cache, etc) pressure, but that doesn’t fit nicely into a soundbite and requires actual thought.
It's a matter of semantics, but this does not contradict the parent. Under-the-hood in assembly, this is split into two operations: a comparison (cmp), and then a second operation that sets 'b'. This could be done with a branch (jl), a conditional move (cmovl), or a conditional set (setl). You can see the various solutions used by different compilers with mattgodbolt's GCC explorer: http://gcc.godbolt.org/#%7B%22version%22%3A3%2C%22filterAsm%...
For the vast majority of code there is a branch anyway because the comparison result is used in an conditional statement. This means a good inlining compiler probably generates one branch for the comparison plus conditional.
i.e. this is why measuring the whole is so important in isolation it is slower but in more complicated code it is likely to be faster.
Liked it. A good, well reasoned advice from an expert. I especially like him making the point that too often good discussions are being smoothed.
I'll compliment that with another advice. On any modern Linux there is "perf top". If you haven't yet, I'd suggest learning how to use it. And using it.
In a lot of cases when speed matters. With fpmath=fast, I've seen compilers do that for you, but not always, as it potentially changes the answer very slightly.
Could someone explain why array writes are so expensive? I understand that a write would mark a cache line as dirty (significantly increasing eviction time cause you have to write-back) and that it could probably prevent the compiler from enregistering stuff. However, I don't get the aliasing and the "a write is really a read and a write" argument.
62 comments
[ 3.0 ms ] story [ 75.5 ms ] threadWait, how is that possible? Like, you can have amd64 optimized code that uses 32-bit pointers?
On a meta-note, I'm really happy to see more highly technical submissions like this hitting and sticking on the front page.
EDIT: from the slides:
Prefer 32 bit ints to all other sizes
1. 64 bit may make some code slower [no additional explanation given]
2. 8, 16 bit computation use conversion to 32 bits and back
Additionally, code that handles 32-bit registers in x86_64 is often shorter than its 64-bit counterpart due to the lack of REX prefixes in instructions. This also reduces the instruction cache footprint. Some instructions like integer division and multiplication are also faster when handling 32-bit quantities, but this depends on the microarchitecture in question.
Excellent point, thank you. I was only thinking about the data cache. Interestingly, I believe 64-bit ARM (AArch64) instructions are still only 32 bits long though I haven't confirmed via google. Maybe someone can correct me.
http://www.arm.com/files/downloads/ARMv8_Architecture.pdf
Correct, but I wouldn’t say “still”, since some “thumb” AArch32 instructions are 16b.
This all is a bit hackish. With the x32 abi you can simply have 32 bit pointers everywhere.
"Truth be told, it's a multiplication because many compilers transform all divisions by a constant into multiplications; see e.g. http://goo.gl/LhPeH "
A deep understanding of the algorithm took me a long time, I think a few months. That was mainly due a lack of information describing the technique. The paper that Andrei linked to (Granlund-Montgomery) is dense and contains a significant error, which I was never able to get resolved. Henry Warren's celebrated Hacker's Delight is more accessible, but is also more of a proof-of-correctness than a learning resource. So my intuitive understanding came from my own investigating and playing around, which is what lead me to find an improvement on the algorithm.
Implementing libdivide took me maybe six months of my hobby time. It's not just the core algorithm - there's a lot of auxiliary functions, for example to compute the high half of a 64 bit multiply in SSE. But working at that level is tons of fun.
Incidentally, I wrote up what I hope to be the most accessible (yet still rigorous) description of the algorithm at http://ridiculousfish.com/blog/posts/labor-of-division-episo... . I advise anyone interested in learning more to start there, instead of the Granlund paper.
This case allows for a simpler method, exemplified here (it also works for signed integers, but more care is needed with the shifting): http://goo.gl/D5q9IO
EDIT: On second thought, compilers are also not doing their best job on that example. f1 could be simplified to
which has a shorter critical path.How is a compiler supposed to track that information? That requires some serious dependent typing.
http://goo.gl/Cx0E0c
What it's happening here is something more clever:
2^67 isn't divisible by 10 (that's why we add 2). Now, I claim that z is an integer, but it represents the exact division of we distribute the n: we distribute the 2^67 division: simplify the terms: Now: we want to take floor of that number[1], but as (the maximum value for n is 2^64 - 1), it follows that That's what the code is doing: 0xcccccccccccccccd is 14757395258967641293L the multiplication of z * n fits in 128 bits, and the mul instruction stores the higher 64 bits of $rax * $rdx into $rdx.We need to divide by 2^67, whichs is shift 3 67 bits to the right. If we take the higher part (rdx) we get the higher 64 bits, and then we shift 3 bits to the right (shr $0x3, %rax) and that's our answer :).
Cool trick.
As a side note, definitely don't follow the advice about using position-dependent code unless you are working in a very performance-intensive and isolated environment. Just a single non-relocatable module/dll completely undermines the benefits of ASLR, so an attacker with a copy of your program will have a much easier time crafting an attack against it.
1. Comparisons (no branch, just compare) 2. u/int add/subtract/bit operations 3. FP mul 4. FP add/sub 5. FP div 6. u/int mul 7. indexed array access (data in L1, including latency for data to move to registers) 8. u/int div
That rough order seems to generally hold on a modern Haswell processor or the in-order PowerPC cores in an Xbox 360, though the cycle counts will vary.
Being thoughtful with respect how you access your data, paying attention to the effects of access patterns on caching, will almost always help regardless of the target architecture :)
Is there a reason you follow Andrei's lead and suggest that comparisons operations are faster than integer subtraction? At least for x64 on Intel, I think they would always be the same speed and thus should be grouped together. Are they different on the other platforms?
The problem is that there is no way to know at compile time the position of an instruction relative to its target. Non-PI code handles this by having the linker update the relevant constants in the machine code. PI code has to function without modification, so it must indirect through a global table.
It's this indirection that causes the speed hit. On the other hand, PI code benefits from the ability to share code pages, so it can be faster in some circumstances.
* Measure, then optimize
* Pay attention to data layout to keep the cache hot
* Techniques for devirtualization
[0] http://channel9.msdn.com/Events/GoingNative/2013/Writing-Qui...
1. Replace strings with integers wherever possible. Create a mapping table, use the indexes.
2. Layout related objects close in memory. Even if it requires special data structures to do. Suppose that if I need A I am likely to need B soon. If B is physically close to A, then I am likely to find it in cache, which is about 10x as fast. So, for instance, don't store a tree as a bunch of random pointers. Store it as offsets inside of a fixed container of memory.
3. Process data according to how it is laid out in memory. For instance walk through a vector, don't do random access into it. Again this is all about trying to make sure that stuff is in cache as often as possible.
For the second and third points I found it was a case of do it perfectly or don't worry about it. For example if I am missing cache regularly in three places, fixing one only mades my code 50% faster. Fixing the second one almost doubled my speed. Getting the last one was an order of magnitude speed increase.
Even with hyperthreading and all the other fancy tricks that modern CPUs have, it's still a huge deal. I learned about all this stuff in general terms at university years ago, but it didn't really click until recently that even when the CPU is at 100%, it's very very often stuck waiting for a memory read to complete.
If you're going to be doing a lot of comparisons of identical strings, use boost::flyweight<std::string>.
Throughput is somewhat more reasonable, but then large parts of the hierarchy collapse entirely. A more reasonable approach is to think about resource (ALU, LSU, branch, cache, etc) pressure, but that doesn’t fit nicely into a soundbite and requires actual thought.
A branch miss on the other hand is much more expensive, about 14 cycles last time I was testing (on a core i5 desktop cpu from a few years ago).
i.e. this is why measuring the whole is so important in isolation it is slower but in more complicated code it is likely to be faster.
http://people.cs.clemson.edu/~dhouse/courses/405/papers/opti...
I'll compliment that with another advice. On any modern Linux there is "perf top". If you haven't yet, I'd suggest learning how to use it. And using it.