Take the 2-minute tour ×


I am working on a fairly computationally intensive project for a computational linguistics project, but the problem I have is quite general and hence I expect that a solution would be interesting to others as well.


The key aspect of this particular program I must write is that it must:

  1. Read through a large corpus (between 5G and 30G, and potentially larger stuff down the line)
  2. Process the data on each line.
  3. From this processed data, construct a large number of vectors (dimensionality of some of these vectors is > 4,000,000). Typically it is building hundreds of thousands of such vectors.
  4. These vectors must all be saved to disk in some format or other.

Steps 1 and 2 are not hard to do efficiently: just use generators and have a data-analysis pipeline. The big problem is operation 3 (and by connection 4)

Parenthesis: Technical Details

In case the actual procedure for building vectors affects the solution:

For each line in the corpus, one or more vectors must have its basis weights updated.

If you think of them in terms of python lists, each line, when processed, updates one or more lists (creating them if needed) by incrementing the values of these lists at one or more indices by a value (which may differ based on the index).

Vectors do not depend on each other, nor does it matter which order the corpus lines are read in.

Attempted Solutions

There are three extrema when it comes to how to do this:

  1. I could build all the vectors in memory. Then write them to disk.
  2. I could build all the vectors directly on the disk, using shelf of pickle or some such library.
  3. I could build the vectors in memory one at a time and writing it to disk, passing through the corpus once per vector.

All these options are fairly intractable. 1 just uses up all the system memory, and it panics and slows to a crawl. 2 is way too slow as IO operations aren't fast. 3 is possibly even slower than 2 for the same reasons.


A good solution would involve:

  1. Building as much as possible in memory.
  2. Once memory is full, dump everything to disk.
  3. If bits are needed from disk again, recover them back into memory to add stuff to those vectors.
  4. Go back to 1 until all vectors are built.

The problem is that I'm not really sure how to go about this. It seems somewhat unpythonic to worry about system attributes such as RAM, but I don't see how this sort of problem can be optimally solved without taking this into account. As a result, I don't really know how to get started on this sort of thing.


Does anyone know how to go about solving this sort of problem? I python simply not the right language for this sort of thing? Or is there a simple solution to maximise how much is done from memory (within reason) while minimising how many times data must be read from the disk, or written to it?

Many thanks for your attention. I look forward to seeing what the bright minds of stackoverflow can throw my way.

Additional Details

The sort of machine this problem is run on usually has 20+ cores and ~70G of RAM. The problem can be parallelised (à la MapReduce) in that separate vectors for one entity can be built from segments of the corpus and then added to obtain the vector that would have been built from the whole corpus.

Part of the question involves determining a limit on how much can be built in memory before disk-writes need to occur. Does python offer any mechanism to determine how much RAM is available?

share|improve this question
depends on how the vectors are built and whether they depend on each other. –  knitti Sep 11 '11 at 21:13
@knitti Thanks for asking. I don't know if it's relevant to the solution, but I'll trust your intuition. I've added the answers to your question (I hope!) to the section "Technical Details" in the problem description. –  Edward Grefenstette Sep 11 '11 at 21:16
your result set (the vectors) needs space in the terabyte area (naive estimate 4 000 000 x 100 000 x 1..2 bytes) so going through the corpus is actually the smaller problem. How do you plan to write the data? –  knitti Sep 11 '11 at 21:33
@knitti The vectors are typically fairly sparse. In practice I use numpy.sparse.lil_matrix instances, and write them as .npy files, but I'm open to doing things differently, though. –  Edward Grefenstette Sep 11 '11 at 21:38
sounds like a big map/reduce problem for Hadoop: one pass,map creates a file of vectors from each input file, and a second pass, reduce combines the output files into one. –  Chris Sep 11 '11 at 21:39
show 4 more comments

11 Answers

up vote 5 down vote accepted

take a look at pytables. One of the advantages is you can work with very large amounts of data, stored on disk, as if it were in memory.

edit: Because the I/O performance will be a bottleneck (if not THE bottleneck), you will want to consider SSD technology: high I/O per second and virtually no seeking times. The size of your project is perfect for todays affordable SSD 'drives'.

share|improve this answer
HDF5 is certainly an appealing format for this sort of problem. I've had a lot of problem getting pytables to work on our lab computers, but I'm looking into it. Thanks for the recommendation! –  Edward Grefenstette Sep 11 '11 at 22:09
On the hardware side, the size of your project is perfect for todays affordable SSD 'drives'. Because the I/O performance will be a bottleneck (if not THE bottleneck), you will want to consider SSD technology: e.g. this one high I/O per second and virtually no seeking times –  Remi Sep 11 '11 at 22:26
This project easily generates gigs and gigs of vector data. While you're right that it's not completely insane to do this sort of thing on SSD technology at this stage, we'd still have to buy quite a few of them or a fairly large single SSD. They are still expensive, and I can't see myself writing a grant asking for three grand for one SSD just yet ;) You're completely correct, though. The bottleneck is disk IO, and as SSDs get cheaper, this sort of work will be easier and easier to do! –  Edward Grefenstette Sep 11 '11 at 22:50
another way to reduce the IO bottleneck is to serialise the reads and writes. I did this making objects derived from 'threading.Thread', each responsible for a part of a simulation, which had to acquire the 'threading.Lock' before they could do any saving or reading. That way, average seek times (numbers of seek) were greatly reduced, and soon the 'objects' themselves performed their calculations and savings in such timing that they did not block each other anymore; kind of simple automated and adaptive optimization of the calculating/saving schedule! –  Remi Sep 12 '11 at 15:48
add comment

A couple libraries come to mind which you might want to evaluate:

  • joblib - Makes parallel computation easy, and provides transparent disk-caching of output and lazy re-evaluation.

  • mrjob - Makes it easy to write Hadoop streaming jobs on Amazon Elastic MapReduce or your own Hadoop cluster.

share|improve this answer
These sound like interesting libraries. I'll certainly take a look at them, thanks! –  Edward Grefenstette Sep 11 '11 at 22:02
add comment

You didn't mention either way, but if you're not, you should use NumPy arrays for your lists rather than native Python lists, which should help speed things up and reduce memory usage, as well as making whatever math you're doing faster and easier.

If you're at all familiar with C/C++, you might also look into Cython, which lets you write some or all of your code in C, which is much faster than Python, and integrates well with NumPy arrays. You might want to profile your code to find out which spots are taking the most time, and write those sections in C.

It's hard to say what the best approach will be, but of course any speedups you can make in critical parts of will help. Also keep in mind that once RAM is exhausted, your program will start running in virtual memory on disk, which will probably cause far more disk I/O activity than the program itself, so if you're concerned about disk I/O, your best bet is probably to make sure that the batch of data you're working on in memory doesn't get much greater than available RAM.

share|improve this answer
We use numpy sparse matrices for this, because the vectors are fairly sparse. Indeed speedups are handy, but the real task here seems to be determining (possibly at run time) how much of the task can be done in memory before a write needs to be done. –  Edward Grefenstette Sep 11 '11 at 21:54
What's the best way to make sure that the batch of data I'm working on in memory doesn't go above the available RAM? This is really the crux of the problem... –  Edward Grefenstette Sep 11 '11 at 22:18
add comment

Two ideas:

  1. Use numpy arrays to represent vectors. They are much more memory-efficient, at the cost that they will force elements of the vector to be of the same type (all ints or all doubles...).

  2. Do multiple passes, each with a different set of vectors. That is, choose first 1M vectors and do only the calculations involving them (you said they are independent, so I assume this is viable). Then another pass over all the data with second 1M vectors.

It seems you're on the edge of what you can do with your hardware. It would help if you could describe what hardware (mostly, RAM) is available to you for this task. If there are 100k vectors, each of them with 1M ints, this gives ~370GB. If multiple passes method is viable and you've got a machine with 16GB RAM, then it is about ~25 passes -- should be easy to parallelize if you've got a cluster.

share|improve this answer
The workhorse machine I plan on running this on has ~70G RAM and 24 Intel Xeon 3.47GHz cores. –  Edward Grefenstette Sep 11 '11 at 21:44
add comment

Think about using an existing in-memory DB solution like Redis. The problem of switching to disk once RAM is gone and tricks to tweak this process should already be in place. Python client as well.

Moreover this solution could scale vertically without much effort.

share|improve this answer
add comment

Use a database. That problem seems large enough that language choice (Python, Perl, Java, etc) won't make a difference. If each dimension of the vector is a column in the table, adding some indexes is probably a good idea. In any case this is a lot of data and won't process terribly quickly.

share|improve this answer
Forgive my ignorance of databases, but won't this approach: a) Require disk writes every time I update a vector, just like solution 3? b) Make the storage of these vectors horrible? (Most of them are quite sparse, and there are a lot, so we want to minimise the space they take on disk as much as possible)? I'm not very familiar with databases, so there might be obvious ways around these problems... –  Edward Grefenstette Sep 11 '11 at 22:01
The sparseness wasn't clear. A database is all about the disk, but most implement caching mechanisms to batch disk writes. –  Chris Sep 13 '11 at 2:16
add comment

I'd suggest to do it this way:

1) Construct the easy pipeline you mentioned

2) Construct your vectors in memory and "flush" them into a DB. ( Redis and MongoDB are good candidates)

3) Determine how much memory this procedure consumes and parallelize accordingly ( or even better use a map/reduce approach, or a distributed task queue like celery)

Plus all the tips mentioned before (numPy etc..)

share|improve this answer
add comment

Hard to say exactly because there are a few details missing, eg. is this a dedicated box? Does the process run on several machines? Does the avail memory change?

In general I recommend not reimplementing the job of the operating system.

Note this next paragraph doesn't seem to apply since the whole file is read each time: I'd test implementation three, giving it a healthy disk cache and see what happens. With plenty of cache performance might not be as bad as you'd expect.

You'll also want to cache expensive calculations that will be needed soon. In short, when an expensive operation is calculated that can be used again, you store it in a dictionary (or perhaps disk, memcached, etc), and then look there first before calculating again. The Django docs have a good introduction.

share|improve this answer
The main problem with option 3 is that it basically maximises the IO operations you need to make. Vector components need to be read and then written back to disk (after increment) every time a vector needs to be updated. For some entities vectors are being built for, this can happen a lot in the corpus. Building an entire vector in memory and then writing it (once) is the most optimal solution, but has some problems. –  Edward Grefenstette Sep 11 '11 at 21:56
1) The box is not dedicated. It is either run as a job on my research group's workhorse computer (70G, 24 CPUs) or on a super computer (I would like to avoid having to do this). 2) The process probably could run on several machines, each of which builds all the vectors for part of the corpus (map) and then finally they are added (reduce) to get the final vector. However, I have no experience running a process over several machines, so wouldn't exactly know how to do this other, although I could figure out an ad-hoc way I'm sure. I'm willing to learn if there's a canonical way to do this! –  Edward Grefenstette Sep 11 '11 at 22:04
Could you perhaps kindly describe how you'd "cache expensive calculations" a little more? –  Edward Grefenstette Sep 11 '11 at 22:10
Ok, I think I don't completely understand the pipleline. Updated. –  Gringo Suave Sep 11 '11 at 23:14
add comment

From another comment I infer that your corpus fits into the memory, and you have some cores to throw at the problem, so I would try this:

  • Find a method to have your corpus in memory. This might be a sort of ram disk with file system, or a database. No idea, which one is best for you.
  • Have a smallish shell script monitor ram usage, and spawn every second another process of the following, as long as there is x memory left (or, if you want to make things a bit more complex, y I/O bandwith to disk):

    • iterate through the corpus and build and write some vectors
  • in the end you can collect and combine all vectors, if needed (this would be the reduce part)

share|improve this answer
add comment

Many of the methods discussed by others on this page are very helpful, and I recommend that anyone else needing to solve this sort of problem look at them.

One of the crucial aspects of this problem is deciding when to stop building vectors (or whatever you're building) in memory and dump stuff to disk. This requires a (pythonesque) way of determining how much memory one has left.

It turns out that the psutil python module does just the trick.

For example say I want to have a while-loop that adds stuff to a Queue for other processes to deal with until my RAM is 80% full. The follow pseudocode will do the trick:

while (someCondition):
   if psutil.phymem_usage().percent > 80.0:

This way you can have one process tracking memory usage and deciding that it's time to write to disk and free up some system memory (deciding which vectors to cache is a separate problem).

PS. Props to to Sean for suggesting this module.

share|improve this answer
add comment

Split the corpus evenly in size between parallel jobs (one per core) - process in parallel, ignoring any incomplete line (or if you cannot tell if it is incomplete, ignore the first and last line of that each job processes).

That's the map part.

Use one job to merge the 20+ sets of vectors from each of the earlier jobs - That's the reduce step.

You stand to loose information from 2*N lines where N is the number of parallel processes, but you gain by not adding complicated logic to try and capture these lines for processing.

share|improve this answer
add comment

Your Answer


