kdbush icon indicating copy to clipboard operation
kdbush copied to clipboard

Added basic comparison of flatbush and kdbush

Open anvaka opened this issue 5 years ago • 0 comments

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.

anvaka avatar Aug 24 '20 06:08 anvaka