search

silentbicycle / skiparray

unrolled skip list library for C
ISC License
21 stars 2 forks source link

Benchmarks hit assert on 32-bit platforms #7

Closed acfoltzer closed 5 years ago

acfoltzer commented 5 years ago

Tested by compiling with -m32 on x86_64 Linux, and with the WASI toolchain for WebAssembly. The benchmarks fail in get_nonexistent with an assertion failure:

get_sequential                 limit 1000000   242.029 msec,  0.242 usec per,    4131.736 K ops/sec
get_random_access              limit 1000000   599.006 msec,  0.599 usec per,    1669.432 K ops/sec
Assertion failed: v == 0 (src/bench.c: get_nonexistent: 191)

Interestingly, at least when compiled with -m32, the theft-based tests all pass, so this must be hitting something the test suite doesn't cover.

silentbicycle commented 5 years ago

Thanks for reporting this! It looks like a 32-bit rollover issue in the benchmarks. I ran the tests many times with a 32-bit build, but didn't run the benchmarks much in that environment, and missed it.

The root cause is that the get_nonexistent benchmark is using numeric keys < limit as in the set, and keys > limit as not present (to benchmark lookup failure), but it's also multiplying the key by a 4-digit prime to cause strided access, and with 32 bits and a sufficiently large benchmark limit, that can roll over and hit the keys < limit.

silentbicycle commented 5 years ago

Closed by v0.1.1 release.

This didn't get automatically closed because I'd set develop to be the default branch (for pull requests), and apparently that also impacts "Fixes #x" messages closing issues?