Optimize fixed format

[vitaut]

Switching to a different scaling (10**(-dec_exp-1)) and splitting the last decimal digit gave a significant speed up for the exponential format. However, the fixed format is currently suboptimal because we recombine the top 15-16 digits with the last digit for compatibility with the old SIMD code in

zmij/zmij.cc

Line 1254 in 7c97c16

dec.sig = dec.sig * 10 + dec.last_digit;

We need to revise this SIMD path to make it more efficient.

[vitaut]

Recombination is gone now and SIMD replaced with a simpler table-driven approach.

[TobiSchluter]

Here's a little experiment that uses the same table-driven approach for all exponents that is currently used for small exponents. In order to be branchless, it always outputs the exponent string, but the table is updated to contain len == 0 for the exponents in the fixed range, so the end pointer is not advanced to include it.

TobiSchluter@ae0914b

The adds about 12kb (which are VERY repetitive, outside the fixed range all the entries are the same) to the size of libzmij.a (23kb -> 35kb), and it is performance-neutral on basic benchmarking. It passes all dtoa tests, ftoa is broken. Perf shows the expected reduction in total branches, and it seems like it's straightforward to turn this into SIMD code but I didn't have time to try this yet.

Edit: just had a chance to benchmark this on an M5: there it goes from 3.9ns without this patch to 4.1ns with this patch, on my Zen4 it goes from 8.3ns to 8.8ns. Both large enough to make me doubt that this approach can be salvaged. Again, the Tiger Lake is just built ... different.

[vitaut]

BTW I added https://github.com/vitaut/zmij/blob/main/test/abtest.py that should simplify evaluating optimizations.

[vitaut]

With recent (and upcoming) optimizations zmij is now about the same as xjb on fixed formatting - here are the results from antares's benchmark:

=== double benchmark (5000 rounds × 91932 values, 100 warmup) ===
  zmij_cpp                   459660000 calls       3151.14 ms total      6.86 ± 0.27 ns/call  (sink=7896585000)
  xjb                        459660000 calls       3173.97 ms total      6.91 ± 0.28 ns/call  (sink=7896789000)

So we can close it now.

[TobiSchluter]

I noticed that the code now shuffles twice (once for bswap, once for the !extra_digit case). Since I had previously had the same idea with the second shuffle, but couldn't express it as elegantly as you, I also have a hacked-together version that combines them. Not too hard, but it's difficult to get consistent performance with the combination since one needs either one more byte near bswap or one more constant (both forcing a load from another cache-line) or one additional instruction (shift or alignr). I just wanted to mention it because I won't be able to continue this work until sometime next week, but thought you might have a better idea than the ones I had so far.

[vitaut]

Good idea! As usual a PR would be welcome when you have time. I don't have a better suggestion how to merge the shuffles.

[TobiSchluter]

PR here #137