kdbush
kdbush copied to clipboard
Added basic comparison of flatbush and kdbush
Was just curious to see which one is faster. The test is obviously not complete, but gives a good starting point for more tests (e.g. different distributions/different search count, etc.)
For the basic example I indexed 100,000 uniformly distributed points inside [-1,000; 1,000) region and then performed 10 lookups using both algorithms. Got this result:
> node perf/runBenchmark.js
kdbush x 42.65 ops/sec ±0.68% (55 runs sampled)
flatbush x 52.67 ops/sec ±0.32% (66 runs sampled)
Fastest is flatbush
> npm version
{
kdbush: '3.0.0',
npm: '6.14.5',
ares: '1.16.0',
brotli: '1.0.7',
cldr: '37.0',
icu: '67.1',
llhttp: '2.0.4',
modules: '83',
napi: '6',
nghttp2: '1.41.0',
node: '14.4.0',
openssl: '1.1.1g',
tz: '2019c',
unicode: '13.0',
uv: '1.37.0',
v8: '8.1.307.31-node.33',
zlib: '1.2.11'
}
Note, if we perform more searches (e.g. a 1,000), the difference between two modules becomes negligible.