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

[BrowserUk]

I've run Perl's hashes up to 30 billion keys/2 terabytes (ram) and they are 1 to 2 orders of magnitude faster, and ~1/3rd the size of storing the same data (64-bit integers) in an sqlite memory-based DB. And the performance difference increases as the size grows.

Part of the difference is that however fast the C/C++ DB code is, calling into it from Perl, adds a layer of unavoidable overhead that Perl's built-in hashes do not have.

The second part is that indexing very large, sparse ranges of data can be done in one of two ways:

1. Hashing.

   Perl's hashing and storage algorithms trade space for speed and are effectively optimal for speed: O(1) + amortised growth costs.

   The latter adds a small constant, and can be completely eliminated by pre-sizing.

2. Pre-sort or binary tree -- which are effectively equivalent.

   Either mechanism is minimum: O(Log₂ N) + DB transactions, journaling and other DB maintenance costs.

   Some, but not all of the extra costs can be disabled.

In the end, O(1) trumps O(log N) and native trumps calling out to C.

From compiled-to-native code -- whatever language -- it is possible to tailor solutions to the lookup domain that will out-perform Perl's native hashes. Judy arrays, radix trees, compressed bitmaps, simplified&tailored hash-arrays, but any of those mechanisms fall short once you add the overhead of calling out from Perl.