4 ms·

> The code is a bit technical, but remarkably, it does not require a table. Those constants being used look a lot like a table.

dzaima 5y ago
The list of arguments to _mm512_setr_epi64 are just reciprocals of powers of 10, multiplied by 2^52. The scalar code uses division by powers of 10, which'd compile down to similar multiplication constants; you just don't see them because the compiler does that for the scalar code, but you have to do so manually for AVX-512. And permb_const is a list of indices for the result characters within the vector register - the algorithm works on 64-bit integers, but the result must be a list of bytes, so it picks out every 8th one.
adrian_b 5y ago
I assume that he referred to the fact that the code does not need an array in memory, with constant values that must be accessed with indexed loads. Using such a table in memory can be relatively slow, as proven by the benchmarks for this method. There are constants, but they are used directly as arguments for the AVX-512 intrinsics. They must still be loaded into the AVX-512 registers from memory, but they are loaded from locations already known at compile-time and the loads can be scheduled optimally by the compiler, because they are not dependent on any other instructions. For a table stored in an array in memory, the loads can be done only after the indices are computed and the loads may need to be done in a random order, not in the sequential order of the memory locations. When the latencies of the loads cannot be hidden, they can slow a lot any algorithm.
- orlp 5y ago
  If your program is sufficiently large and diverse the constants embedded in the instructions are no better than a table load/lookup. The jump to the conversion routine is unpredictable, and the routine will not be in the instruction cache, causing the CPU to stall while waiting for the instructions to load from RAM. This will never show up in a microbenchmark where the function's instructions are always hot. In fact, a lot of microbenchmarking software "warms up" the code by calling it a bunch of times before starting to time it, to maximize the chances of them being able to ignore this reality.
  - dzaima 5y ago
    The AVX-512 constants aren't embedded in the instructions, but the address to load being static means the CPU can start to cache them when the decoder gets to them, possibly even before it knows that the input to the function is. In contrast, for the scalar code, the CPU must complete the divisions (which'll become multiplications, but even those still have relatively high latency) before it can even begin to look for what to cache.
- nitwit005 5y ago
  The code itself sits in memory, which means the "table" is still in memory.
stncls 5y ago
Especially given the fact that the table in the baseline code is only 200 bytes. That's less than four AVX-512 registers!

dzaima 5y ago

The list of arguments to _mm512_setr_epi64 are just reciprocals of powers of 10, multiplied by 2^52. The scalar code uses division by powers of 10, which'd compile down to similar multiplication constants; you just don't see them because the compiler does that for the scalar code, but you have to do so manually for AVX-512. And permb_const is a list of indices for the result characters within the vector register - the algorithm works on 64-bit integers, but the result must be a list of bytes, so it picks out every 8th one.

adrian_b 5y ago

I assume that he referred to the fact that the code does not need an array in memory, with constant values that must be accessed with indexed loads. Using such a table in memory can be relatively slow, as proven by the benchmarks for this method. There are constants, but they are used directly as arguments for the AVX-512 intrinsics. They must still be loaded into the AVX-512 registers from memory, but they are loaded from locations already known at compile-time and the loads can be scheduled optimally by the compiler, because they are not dependent on any other instructions. For a table stored in an array in memory, the loads can be done only after the indices are computed and the loads may need to be done in a random order, not in the sequential order of the memory locations. When the latencies of the loads cannot be hidden, they can slow a lot any algorithm.

orlp 5y ago
If your program is sufficiently large and diverse the constants embedded in the instructions are no better than a table load/lookup. The jump to the conversion routine is unpredictable, and the routine will not be in the instruction cache, causing the CPU to stall while waiting for the instructions to load from RAM. This will never show up in a microbenchmark where the function's instructions are always hot. In fact, a lot of microbenchmarking software "warms up" the code by calling it a bunch of times before starting to time it, to maximize the chances of them being able to ignore this reality.
- dzaima 5y ago
  The AVX-512 constants aren't embedded in the instructions, but the address to load being static means the CPU can start to cache them when the decoder gets to them, possibly even before it knows that the input to the function is. In contrast, for the scalar code, the CPU must complete the divisions (which'll become multiplications, but even those still have relatively high latency) before it can even begin to look for what to cache.
nitwit005 5y ago
The code itself sits in memory, which means the "table" is still in memory.

stncls 5y ago

Especially given the fact that the table in the baseline code is only 200 bytes. That's less than four AVX-512 registers!