4 ms·

That divmod can be replaced with table walking like CRC code does for division and remainder of fixed values, which is certainly fast, and does not require bign

That divmod can be replaced with table walking like CRC code does for division and remainder of fixed values, which is certainly fast, and does not require bignums. Unless you now want to claim all CRC code is also slow as hell or requires bignums. These are solved problems. Many compilers even expand the code inline to generate fix size divides into mult and shift. Here's a 4 year old Hacker news thread on compiler tricks then [1]. They're even better now. [1] https://news.ycombinator.com/item?id=8368639 https://news.ycombinator.com/item?id=8368639

a1369209993 8y ago
> Many compilers even expand the code inline to generate fix size divides into mult and shift. Specificly, u8 divmod 58 can be reduced to a u8->u16 multiply, a right shift, and three conditional subtractions; that's not great, but on a modern CPU it's a afterthought compared to the quadratic loop over the input size.
ur-whale 8y ago
>Many compilers even expand the code inline to generate fix size divides into mult and shift. This is what I meant when I said: >even when the compiler gets smart about it because it's a constant.
- ChrisLomont 8y ago
  You also claimed it's dog slow, and earlier you claimed it requires a big num lib. All of these are wrong. Many compiler/architecture combinations can reduce the divmod to one asm instruction, that on some architectures is very quick. If it is slower than shift/mult trick, that compiler can choose to do that. Go look at some decent implementations and the assembly they generate. Don't spread unfounded or unchecked claims.
  - nkurz 8y ago
    It's OK for different people have different impressions about the speed of dogs. On x64 for 64-bit registers, built-in assembly DIV is about 10 times slower than MUL, and 10 times faster than a lookup from RAM. Whether this makes it fast or slow depends on what you are trying to do. I'm interested in your comment that "some architectures" have a fast divmod. Do you actually know of one where it's faster than a shift and a multiplication? Or the same? We're finishing up a paper where this would be very relevant information.
    - ChrisLomont 8y ago
      Intel flavors often do both with a single idiv instruction. Agner Fog has performance tables for many variants [1]. I’d guess a few pipeline to similar per loop cost of shift and add. I suppose if you’re writing a paper you’re aware of quite a bit of literature on exactly this problem. Recent papers have quite fast methods to do this. I’ve not looked at recent state of the art to see if 58 has a near zero cost divmod, but numbers of many forms do. I’d not be surprised if state of the art has it reduced to a few non-mem access branchless no division instructions on most architectures. Maybe later I’ll poke at 58 and see what I can design. I’ve made quite a few such algorithms over the years. [1] https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf
      - nkurz 8y ago
        I feel comfortable with the x64 approaches, but am much less familiar with the efficiency of other architectures. The paper also benchmarks ARM (which is relatively faster) and Power 8 (which I don't understand well). I'd be particularly interested in knowing if any other architectures are much faster for division/modulus (which would weaken the paper) or much slower (which would strengthen it). I'm might be exposing my ignorance, but what's 58 in this context? Is this an ARM Cortex series, or something else?
        a1369209993 8y ago
        58 is the number we're trying to divide by. (It's a constant, so there's a bunch of clever optimizations we can do; I don't think anyone is claiming fully-general division is fast by any standards beyond "round trip to memory".)
        nkurz 8y ago
        I feel silly, but thank you for the polite explanation of what is now obvious.
        BeeOnRope 8y ago

a1369209993 8y ago

> Many compilers even expand the code inline to generate fix size divides into mult and shift. Specificly, u8 divmod 58 can be reduced to a u8->u16 multiply, a right shift, and three conditional subtractions; that's not great, but on a modern CPU it's a afterthought compared to the quadratic loop over the input size.

ur-whale 8y ago

>Many compilers even expand the code inline to generate fix size divides into mult and shift. This is what I meant when I said: >even when the compiler gets smart about it because it's a constant.

ChrisLomont 8y ago
You also claimed it's dog slow, and earlier you claimed it requires a big num lib. All of these are wrong. Many compiler/architecture combinations can reduce the divmod to one asm instruction, that on some architectures is very quick. If it is slower than shift/mult trick, that compiler can choose to do that. Go look at some decent implementations and the assembly they generate. Don't spread unfounded or unchecked claims.
- nkurz 8y ago
  It's OK for different people have different impressions about the speed of dogs. On x64 for 64-bit registers, built-in assembly DIV is about 10 times slower than MUL, and 10 times faster than a lookup from RAM. Whether this makes it fast or slow depends on what you are trying to do. I'm interested in your comment that "some architectures" have a fast divmod. Do you actually know of one where it's faster than a shift and a multiplication? Or the same? We're finishing up a paper where this would be very relevant information.
  - ChrisLomont 8y ago
    Intel flavors often do both with a single idiv instruction. Agner Fog has performance tables for many variants [1]. I’d guess a few pipeline to similar per loop cost of shift and add. I suppose if you’re writing a paper you’re aware of quite a bit of literature on exactly this problem. Recent papers have quite fast methods to do this. I’ve not looked at recent state of the art to see if 58 has a near zero cost divmod, but numbers of many forms do. I’d not be surprised if state of the art has it reduced to a few non-mem access branchless no division instructions on most architectures. Maybe later I’ll poke at 58 and see what I can design. I’ve made quite a few such algorithms over the years. [1] https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf
    - nkurz 8y ago
      I feel comfortable with the x64 approaches, but am much less familiar with the efficiency of other architectures. The paper also benchmarks ARM (which is relatively faster) and Power 8 (which I don't understand well). I'd be particularly interested in knowing if any other architectures are much faster for division/modulus (which would weaken the paper) or much slower (which would strengthen it). I'm might be exposing my ignorance, but what's 58 in this context? Is this an ARM Cortex series, or something else?
      - a1369209993 8y ago
        58 is the number we're trying to divide by. (It's a constant, so there's a bunch of clever optimizations we can do; I don't think anyone is claiming fully-general division is fast by any standards beyond "round trip to memory".)
        nkurz 8y ago
        I feel silly, but thank you for the polite explanation of what is now obvious.
      - BeeOnRope 8y ago