mourner / kdbush

A fast static index for 2D points
ISC License
637 stars 69 forks source link

Added basic comparison of flatbush and kdbush #34

Closed anvaka closed 1 year ago

anvaka commented 4 years ago

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.

mourner commented 1 year ago

Thanks for the PR and sorry for not responding earlier — now that I've released v4, I'd like to follow up with more elaborate benchmarks (e.g. keep indexing and search separate), and in the same place (in bench.js), so I'm closing this. But the idea of adding Flatbush for comparison is certainly a good one.