Efficient code for tallying entries in very large lists

I am dealing with data sets containing tens of millions of (hashable) entries and simply using the Tally function to count the frequency of each unique list element maxes out available memory. What's the most efficient way to perform this sort of operation on very large lists?

Some clarifications:

1. I actually don't need all values. I need all values that occur more than once and a sizeable majority of the values occur only once.
2. The datasets themselves do fit in memory in their entirety.
-
Do you need to count the occurrences of all values, or just -say- the first n –  belisarius Feb 7 '13 at 22:10
What about the datasets themselves - do they fit in memory in their entirety, or if not, how do you currently store and load / work with them? –  Leonid Shifrin Feb 7 '13 at 22:13
I should have specified -- thank you for the clarifying questions. 1) I actually don't need all values. I need all values that occur more than once and a sizeable majority of the values occur only once. 2) The datasets themselves do fit in memory in their entirety. –  hailekofi Feb 7 '13 at 22:21
Fortunately the results from several Tally operations are very easy to combine. You could break the data into pieces (maybe not even loading all pieces into memory), then doing piece by piece Tally. Finally, combine the results. You can even parallelize for better performance, ParallelCombine uses precisely this pattern. –  Szabolcs Feb 7 '13 at 22:31
Since you have data in their entirety, your question looks to me as a duplicate of this one, and you can use my solution there, which implements the idea suggested by @Szabolcs. –  Leonid Shifrin Feb 7 '13 at 22:33

Preamble

I will discuss here two methods for doing computations on very large data sets which don't fit into memory. The first method is based on sequential reading of chunks of data from a file. The second method is based on converting a data set to a file-backed list representation. The unifying idea for both methods is the use of iterators as a useful abstraction to separate data-fetching mechanism from the computation proper.

Since the all-data-fit-into-memory solution has been already given here, I will now show how to augment it by an iterator which would read from a file.

Here we create a sample file (~500 Mb) of random integers:

file = $TemporaryPrefix <> "test.dat"; Do[BinaryWrite[file, RandomInteger[10^4, 10^5], "Integer32"], {1000}]; Close[file];  Here is one possible way to make an iterator: ClearAll[makeIterator]; makeIterator[file_, chunkSize_, type_String] := Module[{ctr = 0, stream = OpenRead[file, BinaryFormat -> True]}, { iterator[ Function[ If[# === {}, None, #] &@ BinaryReadList[stream, type, chunkSize] ] ], stream }];  The above function opens a stream, constructs an iterator and returns a list of both (I didn't include error-handling here, but that can be easiy added). Now, assuming that one takes the function lazyTally from the linked post, and other functions it depends on, and defines them, here is the code to compute Tally on the data in the file: iteratorAndStream = makeIterator[file, 10^5, "Integer32"]; (tally = lazyTally[First@iteratorAndStream]); // AbsoluteTiming Close[Last@iteratorAndStream] (* {40.643555,Null} *)  By playing with the size of the chunk of data, one can trade memory for speed and get faster execution but use more memory. For example, for the chunk size of 10^7, I get the running time of about 3.5 seconds. One can also generalize this toy example to more complicated cases where files contain records with different types of entries. Using file-backed lists I will now show how one can gain certain speedup with respect to the previous method by converting a file to a file-backed list representation with larger granularity. How much faster this will be depends on whether the problem is IO-bound or the main bottleneck is in the computation (for this particular problem it is rather the latter). This method can be practical if you need to do many operations / computations on a data set, since it will give you • much faster reads • coarse-grained random access • familiar high-level list abstraction The setup To start using it, first load the framework: Import["https://gist.github.com/lshifr/2696189/raw/largeData.m"]  Now, to speed things up by using mx files, define: $fileNameFunction = mxFileName;
$importFunction = mxImport;$exportFunction = mxExport;
$compressFunction = Identity;$uncompressFunction = Identity;


You will have to designate some directory to store the files, for example:

$dir = "C:\\Temp\\LargeData";  Converting data file to a file-backed list representation You will also want to pick the chunk size defining granularity of the file-backed list. I will pick a larger one than used before for the read-from-file iterator: $chunkSize = 3*10^6;


Now, here is the code to transfer the content of the file to the file-backed representation (variable ourTest):

iteratorAndStream = makeIterator[file, $chunkSize , "Integer32"]; initList[ourTest]; Module[{next}, While[(next = getNext[First[iteratorAndStream]]) =!= None, appendTo[ourTest, next, DestinationDirectory :>$dir]
]];
Close[Last@iteratorAndStream];
storeMainList[ourTest, DestinationDirectory :> $dir]  This code executes in about 10 seconds on my machine. Note that appendTo is careful to release the memory for the stored part right after the part has been stored on disk, so at any given time only one chunk of data needs to be stored in RAM. Construcing the iterator for a file-backed-list, and the computation Here is a fairly straight-forward implementation for an iterator over a file-backed list: ClearAll[makeFileBackedListIterator]; makeFileBackedListIterator[fblist_] := Module[{ctr = 0}, iterator[ Function[ If[ctr >= Length[fblist], None, With[{result = fblist[[++ctr]]}, releasePart[fblist, ctr]; result]]]]];  The only non-trivial part here is an explicit call to the releasePart function to release the memory used to store a given part. Finally, the computation: iter = makeFileBackedListIterator[ourTest]; (tallyFB = lazyTally[iter]); // AbsoluteTiming (* {3.285156, Null} *)  And we can check, that the result is the same as the previous one: tallyFB ===tally (* True *)  while the computation took 10 times less time. One can also see that the memory use has been fairly modest: MaxMemoryUsed[] (* 117825552 *)  Fair data access speed comparison If we had used the same chunk size also in the first method, we would have observed that the actual timing difference for the same chunk size is about 2 times only. The speed-up here is not as dramatic because the main bottleneck for this toy problem is in computation rather than IO. This can be confirmed by the following measurement: iter = makeFileBackedListIterator[ourTest]; While[getNext[iter] =!= None] // Timing (* {0.312500, Null} *)  This shows that the actual run-time of pure iteration is 10 times less than the full run-time. This is, of course, good, because most of the time is spent on the actual computation, but this is also what limits the speed advantage of using the file - backed list format, in this problem. For the previous method, we would have to run this code (where we use the same chunk size as for a file-backed list version): iteratorAndStream = makeIterator[file,$chunkSize,"Integer32"];
While[getNext[First@iteratorAndStream ]=!=None]//Timing
Close[Last@iteratorAndStream];

(* {2.093750,Null} *)


which shows, that for this chunk size, BinaryReadList is indeed almost an order of magnitude slower. For more complex data structures one may get more speedup from using the file-backed lists, since in our example the first method using BinaryReadList is also quite efficient.

Summary

I have demonstrated two ways of doing the computation for the large data sets which don't fit into memory. The unifying idea here is to use the iterator abstraction, which decouples the specific way the data is being fetched from the general computation that must be performed on the data.

The first method of sequential reading from a disk is the most straightforward one. However, if one needs to work with a given data set more than once, converting such data set to a file-backed list representation may have advantages, both in terms of speed and in terms of generality, since file-backed list format gives a coarse-grained random access to data.

-
Amazingly detailed post--cheers! I'm pouring over it now. Just to clarify: iterator is an iterating function like Do, Table, etc to be defined as needed? –  hailekofi Feb 9 '13 at 15:40
@hailekofi Thanks for the accept :-). I used this opportunity to connect to some of the things I've done earlier. Re: iterator - this is just an abstraction, a data type, if you wish. It is created along the lines of this answer of mine. So, yes, it is a task of the user to construct an iteator for any given specific situation. Basically, the only requirement here is that iterator contains a function which, when called with zero arguments, returns some result. This result will be interpreted as "next" value ... –  Leonid Shifrin Feb 9 '13 at 16:16
@hailekofi ... provided by an iterator. So, you construct some function f which, when called as f[], returns the next result from your collection or set you want to iterate through. Then, the iterator in this setup is iterator[f]. From this point on, the rest of the code knows what to do with this, without being concerned with exactly how your iterator function f works. –  Leonid Shifrin Feb 9 '13 at 16:17