Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things

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

by BrowserUk (Patriarch)
on Aug 08, 2017 at 21:55 UTC ( [id://1197046] : note . print w/replies, xml ) Need Help??

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

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(Log2 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.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit