Re^3: Fastest way to lookup a point in a set

[oiskuu]

You did not answer his question though. Can you batch the queries or do you need to run them one by one?

If batching is allowed, then LanX has more or less revealed the solution. The problem is then very similar to sorting, and the fastest way to sort is probably the usual radix sort. (Maybe with AVX512 the balance has tipped in favor of merge sort; but I haven't tested that.)

Once you have binned/sorted the queries, the lookup is essentially a linear pass over the (sorted) dataset. Don't loop over queries, map them.

[eyepopslikeamosquito]

Thanks for the tip. There is some scope for batching, I believe, and I hadn't thought of sorting. I'll write a new root node in the next day or so with details on the full problem.

Update: the new root node: High Performance Game of Life