I have done some benchmarks of various cprng_fast implementations:
arc4-mtx The libkern implementation from
netbsd-current, which uses a spin mutex to
serialize access to a single, shared arc4
state.
arc4-nomtx Mutex calls #ifdeffed out. What was in
NetBSD prior to 2012. This implementation
is not correct.
arc4-percpu New implementation of cprng_fast using percpu
state and arc4 as the core stream cipher.
Uses the arc4 implementation from
sys/crypto/arc4, slightly modified to give an
entry point that skips the xor.
hc128-percpu Same new implementation but with hc128 as the
core stream cipher. Differs from what I
posted earlier in that all use of inline
functions in the public API has been removed.
hc128-inline Percpu iplementation I posted earlier with all
noted bugs fixed; uses inlines in header file
which expose some algorithm guts to speed up
cprng_fast32().
PROCEDURE
All implementations were modified to rekey every 512MB of output and
to use the CPU cycle counter to time the generation of 4MB using
1,000,000 calls to cprng_fast32() after each rekeying.
All implementations were tested on a SuperMicro rackmount server with
an H8QC8+ motherboard, 4 dual-core Opteron 880 CPUs, and 32GB of
DDR400 RAM. System memory bandwidth was measured at 7,732 MB/sec
using the STREAM benchmark. Memory and cache latencies were not
measured.
All implementations were run in a GENERIC kernel compiled with
"no options DIAGNOSTIC".
The cpb and single-stream tests were run 3 times per kernel and the
median result chosen; the 4-stream test was run once per kernel
due to the very long runtimes for some cases.
The following tests were run:
1) Cycles-per-byte, 32 bit request: at initial keying of
the generator and each automatic rekeying.
2) Generate 4GB of data by requesting 256 bytes at a time
from userspace using a small C program that loops around
the kern.arandom sysctl call. Values are in seconds.
3) Generate 16GB of data by running 4 copies of the generator
program in parallel. Values are in seconds.
RESULTS
kernel cpb (32 bit) 4GB (1 way) 16GB (4 ways) Scaling Factor
------ ------------ ----------- ------------- --------------
arc4-mtx 35 42.58 398.83 0.106
arc4-nomtx 24 42.12 2338.92 0.018
arc4-percpu 27 33.63 41.59 0.808
hc128-percpu 21 23.75 34.90 0.680
hc128-inline 19 22.66 31.75 0.713
DISCUSSION
The immediate surprise here is the performance of the "arc4-nomtx" variant:
it is almost as fast as the percpu HC128 for a single stream of 32 bit requests
but an order of magnitude worse than "arc4-mtx" for 4 streams in parallel.
This is likely because of severe memory and cache contention caused by
multiple CPUs attempting to update the (improperly) "shared" ARC4 state in
parallel. The mutex-laden variant, "arc4-mtx", performs worse than everything
else when run in parallel -- but still an order of magnitude better than the
original, mutex-free arc4.
Optimization is hard. Let's go shopping!
The performance of arc4-percpu shows that, for a uniprocessor generating
a single stream of requests, the cost of the per-cpu data references
and bookkeeping are about 15% for short requests, which are the worst
case. Perhaps an explicitly uniprocessor variant would be justified in
some cases.
All HC128 variants are faster than all ARC4 variants.
The percpu ARC4 variant scales better than either percpu HC128 variant,
likely due to better cache efficiency of its smaller state array,
but is still slower in absolute terms when run 4-way on this system;
almost 25% slower than the variant of HC128 which uses inlines.
Inlining improves the performance of the percpu HC128 by about 10%, but
this is extremely sensitive to factors which are difficult to control,
such as the quality of compiler cache blocking for the target architecture
and CPU model. In fact, with the code compiled for a generic x86-64 CPU,
defining DIAGNOSTIC, which adds a single not-taken branch prior to every
invocation of the HC128 cipher in the cycles-per-byte test case, *reduces*
cycles-per-byte to 17 or 18. This is an area for further work.
Due to the additional implementation complexity required to buffer their
output, ciphers from the SALSA family were not tested. Details at 11.
CONCLUSIONS
Personally, I'd go with the HC128 variant without the ugly inlining. We
restrict bytes-on-key to 512MB -- the best current attack on HC128 requires
2^65 bytes to distinguish its keystream, so I think it's a reasonable choice
at this time. Percpu ARC4 is really a strawman; RC4 is just not safe at any
speed any longer. Let's test SALSA20 and discuss further.
We should run some of these benchmarks on big-endian systems and systems
that are architecturally unlike the OOO x86-64 I used for my tests.
