Check the implementation of teju to make sure that we do not penalize the algorithm

[lemire]

We should make sure we run a fair benchmark.

[jaja360]

I started looking into this.
When I run our benchmark on integer numbers, I get the following:

❯ ./build/benchmarks/benchmark -v 1000000 -m integer_uniform -a "teju_jagua dragonbox ryu"
...
dragonbox                     :  1257.45 MB/s (+/- 4.3 %)    19.71 MB    63.78 Mfloat/s      10.17 i/B   210.32 i/f (+/- 0.0 %)      4.21 c/B    86.95 c/f (+/- 2.1 %)      2.42 i/c     25.13 b/f    126.28 bm/f      5.55 GHz
ryu                           :   866.80 MB/s (+/- 0.6 %)    19.71 MB    43.97 Mfloat/s      18.87 i/B   390.05 i/f (+/- 0.0 %)      6.10 c/B   126.03 c/f (+/- 0.1 %)      3.09 i/c     34.01 b/f    208.29 bm/f      5.54 GHz
teju_jagua                    :  1027.62 MB/s (+/- 0.5 %)    19.71 MB    52.12 Mfloat/s      14.39 i/B   297.50 i/f (+/- 0.0 %)      5.13 c/B   106.02 c/f (+/- 0.4 %)      2.81 i/c     25.11 b/f    166.04 bm/f      5.53 GHz
...

When I run Teju's own internal benchmark (I tried both the commit we currently use, and the latest upstream commit 3 days ago), I get:

./build/gcc.release.make/bin/benchmark
...
[ RUN      ] double.integers

teju      (mean  ) =  1.303 ns
          (stddev) =  0.086 ns
          (rel.  ) =  1.000

dragonbox (mean  ) =  4.207 ns
          (stddev) =  0.526 ns
          (rel.  ) =  3.229

ryu       (mean  ) =  1.509 ns
          (stddev) =  0.171 ns
          (rel.  ) =  1.158
...

Results are similar for centered and uncentered floating values as they are for integers.
Obviously, the two benchmarks show completely different results. I'll investigate further tomorrow.

[jaja360]

I tried running teju_jagua in our benchmark without the to_chars part (I make the function simply return 0). I get:

with to_chars: 19.71 ns/f
without to_chars: 10.33 ns/f

So, almost half of the total time of teju is our string generation !

Considering this, and your discovery in #34 that dragonbox is sometimes faster than just our string generation, I'm starting to think that the problem is not that teju is too slow in our benchmark, but that dragonbox is too fast ;)

[jaja360]

I'll try to see if it is possible to use dragonbox's string generation (https://github.com/jk-jeon/dragonbox/blob/master/source/dragonbox_to_chars.cpp) in our evaluation of teju, to see if that makes the result more similar to those of teju project's own benchmark.

[lemire]

@jaja360 Great. It might be useful to use instructions as a metric.

[jaja360]

OK, I managed to call directly the dragonbox to_chars internal representation with the teju algorithm. Here is the results before:

❯ ./build/benchmarks/benchmark -a "teju_jagua,dragonbox,ryu" -f ./data/canada.txt
dragonbox                     :  1100.13 MB/s (+/- 0.6 %)     2.09 MB     17.09 ns/f    58.52 Mfloat/s
                                   21.38 i/B   401.98 i/f (+/- 0.0 %)      4.97 c/B    93.42 c/f (+/- 0.4 %)
                                    4.30 i/c      0.00 b/f                 0.00 bm/f      5.47 GHz
ryu                           :   802.43 MB/s (+/- 0.5 %)     2.09 MB     23.43 ns/f    42.68 Mfloat/s
                                   30.61 i/B   575.43 i/f (+/- -0.0 %)      6.89 c/B   129.51 c/f (+/- 0.2 %)
                                    4.44 i/c      0.00 b/f                 0.00 bm/f      5.53 GHz
teju_jagua                    :   758.15 MB/s (+/- 1.1 %)     2.09 MB     24.80 ns/f    40.33 Mfloat/s
                                   25.62 i/B   481.63 i/f (+/- 0.0 %)      7.28 c/B   136.89 c/f (+/- 0.9 %)
                                    3.52 i/c      0.00 b/f                 0.00 bm/f      5.52 GHz

And the results of teju when using dragonbox's to_chars for the string generation:

teju_with_dragonbox_to_chars  :   827.70 MB/s (+/- 0.9 %)     2.09 MB     22.71 ns/f    44.03 Mfloat/s
                                   21.42 i/B   402.72 i/f (+/- 0.0 %)      6.62 c/B   124.49 c/f (+/- 0.7 %)
                                    3.23 i/c      0.00 b/f                 0.00 bm/f      5.48 GHz

So, teju becomes faster than ryu, but still a long way to beat dragonbox like it does in teju's own benchmark. I looked at the code, but can't see why the results are so different. The mystery remains for now...

I uploaded the change to another branch (6dc168e) if we want to test this again eventually.

[jaja360]

For fun, I tried to test the opposite : leave teju like it was, and make dragonbox use our own to_chars. Dragonbox becomes much slower than it was !

dragonbox                     :   925.50 MB/s (+/- 0.5 %)     2.09 MB     20.31 ns/f    49.23 Mfloat/s
                                   24.54 i/B   461.38 i/f (+/- -0.0 %)      5.97 c/B   112.15 c/f (+/- 0.2 %)
                                    4.11 i/c      0.00 b/f                 0.00 bm/f      5.52 GHz

[lemire]

@jaja360 This suggests that, at least in some cases, dragonbox has a very fast to_chars routine?

That's unexpected to me. Our routine seems fast.

What about benchmarking the two head-to-head? We have the facilities in place to do so, I think. See our benchmark code.

[jaja360]

@lemire OK, so we found that to_chars can explain a part of the difference in speed between our benchmark and teju's benchmark. However, there's still most discrepancy between both benchmark that I can't find an explanation. Can you take a look ?

[lemire]

@jaja360 On my todo. Sorry for the delay.

[lemire]

I am getting to it!!!

[lemire]

@jaja360 Sorry for the delay!!!

[jaja360]

No problem, take your time ;)

[lemire]

@jaja360 The issue is tricky. I am still investigating it.

[lemire]

I am going to close this. We shall add teju when we have a clearer path forward.