chrisarg

Sometimes one has to make compromises between speed of execution and memory, other times one may not have to be. While working towards a fairly (at least in my mind) complete solution to map Nanopore Sequencing files, I ran against the need to create and access fairly large hash of arrays (think of 1M - 100Mof keys), with each array itself consisting of a a fixed number of elements.

The hash of arrays is a fairly straightforward and fast data structure to create in Perl, the memory overhead can be substantial as the number of keys and values scale upwards. While in my application (at least as envisioned now!) the hash will be created, aggregated over (group by for those into python-pandas or r-data.table vernacular) and then discarded, there are use cases in which the data should be preserved to avoid the computational expensive part of generating them via approximate string matching in biological databases.

So what are the options of generating online, storing within Perl and then accessing hash of arrays that may also serialization and disk storage?

I tested the first 3 solutions with the following script that uses the Memory::Usage module to track both memory usage and time execution using a very intuitive interface, and supplemented with file size stats  (for the size of the DBM::Deep file) and queries to the Redis server about memory use.

First, the self-explanatory (I hope) profiling script. It creates a long string that is used as key, and also as an element of the array that the key points to

In the script above we create the entries of the data structures on the fly, store them and then access them, but without doing any processing. I also tested a version of the script in which the keys were replaced by a (stringified) number, to see how well the 3 storage approaches handle the first case of a very long key.

First, let's look at the case of numerical keys. Here is the output of the script for 1,000 - 10,000 and 100,000 numerical keys

We see that the execution time and memory usage scales linearly for all 3 storage engines, with DBM::Deep being the slowest (and the most  storage hungry when one counts the size of the disk file and the memory consumed within Perl (as given by the Memory::Usage module, all values in kilobytes). The humble hash of arrays was by far the fastest (only 3 seconds to populate 100,000 keys, <1sec to access them), but consumed lots and lots of memory (about 110MB), and Redis gave an intermediate performance (9 seconds to populate, ~64MB memory consumption and 8 seconds to read through the database of keys/values).

The relevant figures for the case of "long-string" keys are shown below and the conclusions are not materially different.