6 ms·

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 b

by IvyMike 12y ago

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 http://goo.gl/LhPeH "

nly 12y ago
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).
- deleted 12y ago
  [deleted]
- ridiculous_fish 12y ago
  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: uint64_t div10(uint64_t y) { const uint64_t magic = 0xCCCCCCCCCCCCCCCDULL; __uint128_t prod = magic * (__uint128_t)y; return (uint64_t)(prod >> (64 + 3)); } See http://libdivide.com http://libdivide.com for how to get this codegen with runtime constants (I am the author).
  - deleted 12y ago
    [deleted]
  - nly 12y ago
    Why did you create libdivide, and how long did it take you to grasp the algorithm and produce a correct implementation?
    - ridiculous_fish 12y ago
      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-episode-i.html http://ridiculousfish.com/blog/posts/labor-of-division-episo... . I advise anyone interested in learning more to start there, instead of the Granlund paper.
      - mvanotti 12y ago
        Oh God. I spent hours trying to understand how it works, when I saw it yesterday :/ I wish I had seen your link!
      - pbsd 12y ago
        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 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 which has a shorter critical path.
        kazagistar 12y ago
        > when we know that an integer is a multiple of some constant How is a compiler supposed to track that information? That requires some serious dependent typing.
        pbsd 12y ago
        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.
  - mattgodbolt 12y ago
    Clang since at least v3.0 has done this automatically at -O1 and above - no need to use this cool, but ungainly, and hard-to-maintain approach. http://goo.gl/Cx0E0c http://goo.gl/Cx0E0c
    - nly 12y ago
      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.
  - temujin 12y ago
    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.

by IvyMike 12y ago

nly 12y ago

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).

deleted 12y ago
[deleted]
ridiculous_fish 12y ago
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: uint64_t div10(uint64_t y) { const uint64_t magic = 0xCCCCCCCCCCCCCCCDULL; __uint128_t prod = magic * (__uint128_t)y; return (uint64_t)(prod >> (64 + 3)); } See http://libdivide.com http://libdivide.com for how to get this codegen with runtime constants (I am the author).
- deleted 12y ago
  [deleted]
- nly 12y ago
  Why did you create libdivide, and how long did it take you to grasp the algorithm and produce a correct implementation?
  - ridiculous_fish 12y ago
    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-episode-i.html http://ridiculousfish.com/blog/posts/labor-of-division-episo... . I advise anyone interested in learning more to start there, instead of the Granlund paper.
    - mvanotti 12y ago
      Oh God. I spent hours trying to understand how it works, when I saw it yesterday :/ I wish I had seen your link!
    - pbsd 12y ago
      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 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 which has a shorter critical path.
      - kazagistar 12y ago
        > when we know that an integer is a multiple of some constant How is a compiler supposed to track that information? That requires some serious dependent typing.
        pbsd 12y ago
        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.
- mattgodbolt 12y ago
  Clang since at least v3.0 has done this automatically at -O1 and above - no need to use this cool, but ungainly, and hard-to-maintain approach. http://goo.gl/Cx0E0c http://goo.gl/Cx0E0c
  - nly 12y ago
    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.
- temujin 12y ago
  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.