Add an option to use `range` as a generator function

[HatulaPro]

Sometimes you really only need the first item that matches your query, and getting the whole list just adds unnecessary work.

We could optimize this by adding a version of KDBush.range or KDBush.within that instead of returning an array with every single match, are implemented using generators

I'm happy to open a PR :)

Real world example:
maplibre/maplibre-gl-js#6192 (comment)

[mourner]

Definitely a reasonable use case, and there was a similar request in flatbush mourner/flatbush#56. I'm not sure it's worth adding more duplicate range/within versions though, and making it a generator might be an overkill — we want to solve the issue with the most minimal and simple change possible.

One option is to introduce a maxResults parameter which, when set, gets the methods to return early after a result array grows — let's try this, and make sure to benchmark the change so that not providing maxResults doesn't affect performance vs before the change.

[gdborton]

@mourner just found this issue while looking into something similar... I'm using kdbush for a game and creating new dynamic arrays in the hot path is leading to more GC than I want at the moment.

I'm going to patch locally so that .within uses a generator, but just wanted to add some weight to this issue if you're still thinking it through.

[gdborton]

Me again.

I did switch to the iterator approach, but I think for my use case it's actually the wrong way to go.

I was originally trying to avoid allocating arrays in each frame for each unit in the game (checking their distance), as I thought gc was going to be my primary performance problem.

I think that worked, but it turns out that iterators are much slower than arrays.

See this jsperf:
https://jsperf.app/ziwuzo/2

Another sort of related issue w/ iterators is that I can't cache look ups. Before this optimization I could have stored lookups for players that hadn't moved and avoided repeating any distance calculations.

For anyone else reading trying to squeeze every bit of juice, my new plan will be to pass a Set to within and then add to that instead of allocating to the array.

Then outside the .within call, I can maintain a pool of sets and cache them for equal look up values.

^ I dunno if that's something you want to handle in this lib directly, but maybe something to consider.

[mourner]

@gdborton thanks for sharing! Your use case sounds like it would benefit from an equivalent to a change I did recently in Flatbush in mourner/flatbush#68 — being able to pass a filter function to a search method that can also act as a visitor of sorts.

[gdborton]

That would probably work for the OP post here, but I don't think it'd work for me. I'm really trying to get to 0 allocations and the embedded dynamically sized array is something I'm hoping to avoid. At a high level I'm going to do this...

findUnitsInRange(x, y, dist) {
  const key = `${Math.floor(x)}-${Math.floor(y)}-${dist}`;
  const cached = cache.get(key);
  if (cached) return cached;
  const set = getSetFromPool(); // returns an empty pre-allocated set
  bush.within(x, y, dist, set); // modified to add to the set
  cache.set(key, set);
  return set;
}

[gdborton]

Buh nuance 🙈 realized while implementing that I'll need to map the indexes returned back to the original objects, so yeah callback would help. Still wanna avoid the additional allocation in .within though.

New solution:

findUnitsInRange(x, y, dist) {
  const key = `${Math.floor(x)}-${Math.floor(y)}-${dist}`;
  const cached = cache.get(key);
  if (cached) return cached;
  const set = getSetFromPool(); // returns an empty pre-allocated set
  bush.within(x, y, dist, (index) => {
    set.add(monsters[index]);
  }); // modified to callback w/ index
  cache.set(key, set);
  return set;
}