preliminary experiments

This page keeps track of some preliminary testing results of our sorted array implementations.

lauteschwein: Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz

Intel i7 (Haswell) with 32GB ram and 8192KB cache.

cacher.cpp estimates cache speed at 4.64136

morin@lauteschwein:~/research/veblayout/src$ ./main 250000000
n = 250000000
=======================================================
Running tests with 32-bit data and 32-bit indices (n = 250000000)
Allocating and filling sorted array...done (0.0805944s)
Building binary array...done (0.139101s)
Performing 10000000 binary searches...done in 3.62612s (sum = 2281243464)
Building veb array...done (1.41695s)
Performing 10000000 veb searches...done in 2.73215s (sum = 2281243464)
Building eytzinger array...done (0.520257s)
Performing 10000000 eytzinger searches...done in 2.40731s (sum = 2281243464)
Building binary array...done (0.133569s)
Performing 10000000 binary searches...done in 3.72441s (sum = 2281243464)
Building veb array...done (1.41455s)
Performing 10000000 veb searches...done in 2.78221s (sum = 2281243464)
Building eytzinger array...done (0.524548s)
Performing 10000000 eytzinger searches...done in 2.38858s (sum = 2281243464)
Building binary array...done (0.131802s)
Performing 10000000 binary searches...done in 3.62681s (sum = 2281243464)
Building veb array...done (1.4461s)
Performing 10000000 veb searches...done in 2.73456s (sum = 2281243464)
Building eytzinger array...done (0.523538s)
Performing 10000000 eytzinger searches...done in 2.37711s (sum = 2281243464)

Conclusion: Eytzinger is the winner by a fair margin.

scray: Intel(R) Atom(TM) CPU 330 @ 1.60GHz

Intel Atom with 4GB RAM and 512KB Cache (64 bytes wide).

cacher.cpp estimates cache speedup at 4.577

morin@scray:~/veblayout/src$ ./main 100000000
n = 100000000
=======================================================
Running tests with 32-bit data and 32-bit indices (n = 100000000)
Allocating and filling sorted array...done (0.833761s)
Building binary array...done (0.824151s)
Performing 10000000 binary searches...done in 28.1683s (sum = 1458087830)
Building veb array...done (7.38423s)
Performing 10000000 veb searches...done in 13.5411s (sum = 1458087830)
Building eytzinger array...done (2.10084s)
Performing 10000000 eytzinger searches...done in 26.6682s (sum = 1458087830)
Building binary array...done (0.822803s)
Performing 10000000 binary searches...done in 28.1339s (sum = 1458087830)
Building veb array...done (7.38394s)
Performing 10000000 veb searches...done in 13.5194s (sum = 1458087830)
Building eytzinger array...done (2.10199s)
Performing 10000000 eytzinger searches...done in 26.5491s (sum = 1458087830)
Building binary array...done (0.824031s)
Performing 10000000 binary searches...done in 28.189s (sum = 1458087830)
Building veb array...done (7.38363s)
Performing 10000000 veb searches...done in 13.5067s (sum = 1458087830)
Building eytzinger array...done (2.10208s)
Performing 10000000 eytzinger searches...done in 26.6288s (sum = 1458087830)

Conclusion: VEB is the winner, hands down:

soprano: Intel(R) Core(TM) i5-4670K CPU @ 3.40GHz

Intel i5 (Haswell) with 6144KB cache

cacher.cpp estimates cache speedup at 9.50131

archimedes: Intel(R) Xeon(R) CPU E5320 @ 1.86GHz

Intel Xeon with 8GB of RAM and 4096 KB cache

cacher.cpp estimates cache speedup at 20.3556

morin@archimedes:~/git/research/veblayout/src$ ./main 250000000
n = 250000000
=======================================================
Running tests with 32-bit data and 32-bit indices (n = 250000000)
Allocating and filling sorted array...done (0.681754s)
Building binary array...done (0.998662s)
Performing 10000000 binary searches...done in 12.2883s (sum = 2281243464)
Building veb array...done (6.05147s)
Performing 10000000 veb searches...done in 7.84779s (sum = 2281243464)
Building eytzinger array...done (2.25575s)
Performing 10000000 eytzinger searches...done in 8.24873s (sum = 2281243464)
Building binary array...done (0.998436s)
Performing 10000000 binary searches...done in 12.2857s (sum = 2281243464)
Building veb array...done (6.05125s)
Performing 10000000 veb searches...done in 7.84389s (sum = 2281243464)
Building eytzinger array...done (2.25607s)
Performing 10000000 eytzinger searches...done in 8.25474s (sum = 2281243464)
Building binary array...done (0.998516s)
Performing 10000000 binary searches...done in 12.2896s (sum = 2281243464)
Building veb array...done (6.05018s)
Performing 10000000 veb searches...done in 7.84748s (sum = 2281243464)
Building eytzinger array...done (2.25568s)
Performing 10000000 eytzinger searches...done in 8.24491s (sum = 2281243464)

Conclusion: VEB wins by a small margin.

mirzakhani: Intel(R) Xeon(R) CPU E3-1230 V2 @ 3.30GHz

Intel Xeon 32GB of RAM and 8192KB cache

cacher.cpp estimates cache speedup at 12.3

n = 250000000
=======================================================
Running tests with 32-bit data and 32-bit indices (n = 250000000)
Allocating and filling sorted array...done (0.116472s)
Building binary array...done (0.183873s)
Performing 10000000 binary searches...done in 4.67474s (sum = 2281243464)
Building veb array...done (1.81622s)
Performing 10000000 veb searches...done in 3.43703s (sum = 2281243464)
Building eytzinger array...done (0.661015s)
Performing 10000000 eytzinger searches...done in 2.9876s (sum = 2281243464)
Building binary array...done (0.179296s)
Performing 10000000 binary searches...done in 4.67549s (sum = 2281243464)
Building veb array...done (1.81612s)
Performing 10000000 veb searches...done in 3.43371s (sum = 2281243464)
Building eytzinger array...done (0.661322s)
Performing 10000000 eytzinger searches...done in 2.98743s (sum = 2281243464)
Building binary array...done (0.178619s)
Performing 10000000 binary searches...done in 4.67551s (sum = 2281243464)
Building veb array...done (1.81619s)
Performing 10000000 veb searches...done in 3.43559s (sum = 2281243464)
Building eytzinger array...done (0.661588s)
Performing 10000000 eytzinger searches...done in 2.98783s (sum = 2281243464)

Conclusion: Eytzinger wins by a fair margin.

tiny: Intel(R) Atom(TM) CPU D2700 @ 2.13GHz

Intel Atom with 512KB cache and 4GB memory

cacher.cpp estimates cache speedup at 3.42839

morin@tiny:~/git/research/veblayout/src$ ./main 100000000
n = 100000000
=======================================================
Running tests with 32-bit data and 32-bit indices (n = 100000000)
Allocating and filling sorted array...done (0.505866s)
Building binary array...done (0.4065s)
Performing 10000000 binary searches...done in 17.2454s (sum = 1458087830)
Building veb array...done (4.47732s)
Performing 10000000 veb searches...done in 9.21084s (sum = 1458087830)
Building eytzinger array...done (1.43322s)
Performing 10000000 eytzinger searches...done in 16.5361s (sum = 1458087830)
Building binary array...done (0.414031s)
Performing 10000000 binary searches...done in 17.247s (sum = 1458087830)
Building veb array...done (4.47725s)
Performing 10000000 veb searches...done in 9.19879s (sum = 1458087830)
Building eytzinger array...done (1.43319s)
Performing 10000000 eytzinger searches...done in 16.6703s (sum = 1458087830)
Building binary array...done (0.410211s)
Performing 10000000 binary searches...done in 17.2412s (sum = 1458087830)
Building veb array...done (4.47767s)
Performing 10000000 veb searches...done in 9.18918s (sum = 1458087830)
Building eytzinger array...done (1.4327s)
Performing 10000000 eytzinger searches...done in 16.4906s (sum = 1458087830)

Conclusion: VEB wins by a large margin.