SipHash performs badly on short msgs (< 100 bytes). And missing le64toh swap on key? about highwayhash

[jan-wassenberg]

Interesting result, thank you for sharing this.
It is difficult to draw conclusions from something like the sum of many runs. Would you like to integrate your code into the benchmark.cc? If it is indeed faster there, and you're willing to share your code, we could open-source it here.

2: the input key is given as an integer. Byte order only arises when loaded from bytes, as we do for the input message.

[operamint]

I would gladly share the code - I'll integrate into benchmark.cc. In the meantime, here are some more numbers.
UPDATED: Latest numbers:

benchmark_siphash_vs.exe

 input len    hh::SipHash    fh::SipHash   speedup    hh::HighwayHash   speedup
         7          1.43s          0.84s     1.71x              0.88s     0.95x
         8          1.34s          0.79s     1.70x              0.74s     1.07x
        31          0.44s          0.33s     1.34x              0.35s     0.95x
        32          0.47s          0.35s     1.34x              0.15s     2.34x
        44          0.38s          0.30s     1.26x              0.16s     1.94x
        63          0.33s          0.27s     1.20x              0.19s     1.43x
        64          0.34s          0.28s     1.20x              0.09s     3.09x
      1024          0.23s          0.21s     1.06x              0.04s     5.63x
   1048576          0.21s          0.21s     1.02x              0.03s     6.21x

 input len  hh::SipHash13  fh::SipHash13   speedup
         7          1.17s          0.63s     1.85x
         8          1.05s          0.51s     2.07x
        31          0.32s          0.21s     1.51x
        32          0.33s          0.21s     1.53x
        44          0.25s          0.18s     1.39x
        63          0.21s          0.16s     1.31x
        64          0.21s          0.16s     1.31x
      1024          0.12s          0.12s     0.95x
   1048576          0.11s          0.12s     0.96x

freewayhash::SipHash     checksum: 18411327082586722758
highwayhash::SipHash     checksum: 18411327082586722758
highwayhash::HighwayHash checksum: 7346031164972754926

benchmark_siphash_gnu.exe

 input len    hh::SipHash    fh::SipHash   speedup    hh::HighwayHash   speedup
         7          1.37s          0.75s     1.82x              0.94s     0.80x
         8          1.14s          0.71s     1.59x              0.80s     0.89x
        31          0.42s          0.30s     1.42x              0.22s     1.36x
        32          0.41s          0.33s     1.24x              0.17s     1.91x
        44          0.36s          0.28s     1.28x              0.17s     1.63x
        63          0.31s          0.25s     1.26x              0.12s     2.00x
        64          0.30s          0.27s     1.11x              0.09s     2.87x
      1024          0.20s          0.20s     1.00x              0.05s     4.32x
   1048576          0.20s          0.20s     1.00x              0.03s     6.55x

 input len  hh::SipHash13  fh::SipHash13   speedup
         7          1.03s          0.56s     1.84x
         8          0.81s          0.45s     1.78x
        31          0.31s          0.19s     1.68x
        32          0.27s          0.19s     1.42x
        44          0.24s          0.17s     1.37x
        63          0.19s          0.16s     1.20x
        64          0.19s          0.16s     1.21x
      1024          0.11s          0.12s     0.89x
   1048576          0.11s          0.12s     0.89x

freewayhash::SipHash     checksum: 18411327082586722758
highwayhash::SipHash     checksum: 18411327082586722758
highwayhash::HighwayHash checksum: 7346031164972754926

2. My bad. Yes, only when key is given as bytes it should be done.

[operamint]

Hi Jan, I have forked the project, if you're interested.

1. Added freewayhash::SipHash. "A freeway is a "controlled-access" highway — also known as an express highway — that's designed exclusively for high-speed vehicular traffic.". As from above table, it is approx. 2x - 1.2x faster for 7 - 63 bytes input lengths.
2. Integrated into benchmark.cc, but I find my own benchmarks show better differentiation: Larger differences on short inputs. On the flip side, your HighwayHash seems more like 6x faster than SipHash on long inputs, rather than your claimed 5x. Maybe your benchmarking framework has some overhead that flattens the results a bit?
3. I also included a "no-branch" (no if), simpler freewayhash::v2::SipHash that requires multiples of 8 bytes in Update(), where you put the remaining in Finalize(). But technically, as it contains a conditional loop it is not branch free?

[jan-wassenberg]

Hi, thanks for integrating and testing! I didn't see the benchmark.cc results in your commit/readme - can you share those?

I find my own benchmarks show better differentiation: Larger differences on short inputs
Maybe your benchmarking framework has some overhead that flattens the results a bit?

Yes, this is by design. A long loop will lead to near-perfect icache and branch prediction, whereas our benchmark deliberately interferes with this by randomizing the input lengths.