A lot of people have questions like this:
I've got a 100MB CSV file. I read it in to a list, populated with a csv.DictReader, and my computer starts swapping. Why?
Let's look at what it takes to store a 100MB file as a list of dicts of strings.

But first, let's look at how to solve this problem, instead of how to understand it.

Very often, you don't actually need the whole thing in memory; you're just, e.g., reading the rows from one CSV file, processing each one independently, and writing out the result to a different CSV file. You can do that by using the csv.DictReader as an iterator—for each row in the reader, write a row to the writer, without storing it anywhere. Then you only need enough memory for one row at a time.

Even if you do more global work (where one row's processing may depend on another row far away), do you really need this all in memory, or just in some accessible form? If you read the CSV and use it to iteratively build a database (whether a SQL database, a dbm, or your favorite kind of NoSQL store), you can get reasonably fast random access with bounded memory usage.

Where does the memory go?

First, let's make it specific. We've got 200K rows of 25 columns of an average of 20 characters. All of the characters are ASCII. We're using 64-bit CPython 3.4. (I'll explain how changing each of these assumptions can change things as I go along.)

Reading the file into memory

If you just open the file and write contents = f.read(), you get a 100MB string. That takes 100MB of memory for the string storage, plus 48 bytes for a str header, plus possibly 1 byte for a NUL terminator. So, still effectively just 100MB.

How do I know this? Well, you can read the source, but it's easier to just call sys.getsizeof on an empty string.

This only works because we're using CPython 3.3+ with all-ASCII data. Python 3.x strings are Unicode. In CPython 3.0-3.2, that means either 2 or 4 bytes per character, depending on your build, which would mean 200MB or 400MB. In 3.3 and later, strings are one byte per character if they're pure ASCII, two if they're pure BMP, and four otherwise. Of course you can stay with un-decoded bytes objects instead of strings—and in Python 2.7, that's often what you'd do.

Splitting into lines

If you read in a list of lines, with contents = list(f), you get 200K strings, each of which has that 48-byte header on top of its 500-byte string data. So, that's an extra 9.2MB.

Plus, the list itself has a 48-byte header, and it also needs to store references to all of those strings. In CPython, each of those references is a pointer, so in 64-bit-land, that's 8 bytes. Also, lists have extra slack on the end. (Why? Expanding a list requires allocating a new chunk of memory, copying all the old values over, and freeing the old chunk. That's expensive. If you did that for every append, lists would be too slow to use. But if you leave room for extra values on each expansion—with the extra room proportional to the current size—the reallocations and copies amortize out to essentially free. The cost is a bit of wasted space.) Let's assume it's 220K pointers; that's an extra 1.7MB.

Splitting into columns

If you split each line into 25 columns, whether by using contents = [line.split(',') for line in f] or by using contents = list(csv.reader(f)), you get 200K * 25 strings, each of which has that 48-byte header, plus 200K lists, each with a 48-byte header plus a bit over 25 pointers, plus of course the original list of 220K pointers. Now we're talking about 281MB.

Storing in dicts

If you convert each line into a dict instead of a list, e.g., by using contents = list(csv.DictReader(f)), you've got the same strings. (You don't get a bunch of separate copies of the key strings; each dict just references the same strings.)

The only difference is that instead of 200K lists, you have 200K dicts. A dict is bigger than a list for three reasons. First, each slot in a dict has to hold a hash value, a key pointer, and a value pointer, instead of just a value pointer. Seconds, dicts are more complicated, so they have bigger headers. Finally, dicts need more slack than lists (because they're more expensive to copy when they expand, because you have to reprobe every hash instead of just copying a big buffer of memory, and because hash tables work best with specific types of numbers for their capacity).

So, the 200K * (48 + 25 * 8) part is unchanged, but the 200K * (48 + 27 * 8) turns into 200K * (96 + 32 * 24). Now we're talking 624MB.

Couldn't Python do better?

One obvious thing Python could so is to store each dict as two pieces: a hash table full of keys and their hashes, which would be shared by all those 200K rows, plus a hash table full of just values, which would be separate for each row. CPython 3.4+ actually has the ability to do this, but it only gets triggered in special cases, like the attribute dictionaries of objects of the same type. (And yes, this means that if you replace that list of dicts with a list of instances of some class, you will actually save some memory.)

You could take this even farther by using a shared hash table full of keys, hashes, and indices, and then each separate dict would just have an array of values, without the need for that extra slack. PyPy 2.0+ can do this, although I'm not sure exactly where it get triggered (except that I am sure that the class trick would work here, and work even better than in CPython).

Beyond that, is there a way we could get rid of the "boxing", the need to store both the strings and the array full of pointers to those strings?

Well, if all of your column values are about the same length, then you could store the strings directly in the hash table (or array). See fixedhash for a quick&dirty implementation of a hash table with fixed-size keys. But typically, a CSV file has some columns that are only 2 or 3 characters long, and others than are 50 characters or longer, so you'd be wasting more space than you'd be saving.

Failing that, you could replace the 8-byte strings with small integer indices into a giant string. How small could this be? Well, your string is 100MB long, so that takes 27 bits. If your longest column value is 64 characters long, you need another 7 bits for the length. So that's 34 bits. Accessing arrays by bits is slow and complicated, but by bytes can be reasonable, which means you can use 5 bytes instead of 8 for each string. This cuts 38% out of the cost of one of the smaller but still significant parts of your storage.

But ultimately, you're talking about having 5 million objects alive. That's going to take a good chunk of memory to store. The only way to avoid that is to not store all those objects. 
1

View comments

It's been more than a decade since Typical Programmer Greg Jorgensen taught the word about Abject-Oriented Programming.

Much of what he said still applies, but other things have changed. Languages in the Abject-Oriented space have been borrowing ideas from another paradigm entirely—and then everyone realized that languages like Python, Ruby, and JavaScript had been doing it for years and just hadn't noticed (because these languages do not require you to declare what you're doing, or even to know what you're doing). Meanwhile, new hybrid languages borrow freely from both paradigms.

This other paradigm—which is actually older, but was largely constrained to university basements until recent years—is called Functional Addiction.
5

I haven't posted anything new in a couple years (partly because I attempted to move to a different blogging platform where I could write everything in markdown instead of HTML but got frustrated—which I may attempt again), but I've had a few private comments and emails on some of the old posts, so I decided to do some followups.

A couple years ago, I wrote a blog post on greenlets, threads, and processes.
6

Looking before you leap

Python is a duck-typed language, and one where you usually trust EAFP ("Easier to Ask Forgiveness than Permission") over LBYL ("Look Before You Leap"). In Java or C#, you need "interfaces" all over the place; you can't pass something to a function unless it's an instance of a type that implements that interface; in Python, as long as your object has the methods and other attributes that the function needs, no matter what type it is, everything is good.
1

Background

Currently, CPython’s internal bytecode format stores instructions with no args as 1 byte, instructions with small args as 3 bytes, and instructions with large args as 6 bytes (actually, a 3-byte EXTENDED_ARG followed by a 3-byte real instruction). While bytecode is implementation-specific, many other implementations (PyPy, MicroPython, …) use CPython’s bytecode format, or variations on it.

Python exposes as much of this as possible to user code.
6

If you want to skip all the tl;dr and cut to the chase, jump to Concrete Proposal.

Why can’t we write list.len()? Dunder methods C++ Python Locals What raises on failure? Method objects What about set and delete? Data members Namespaces Bytecode details Lookup overrides Introspection C API Concrete proposal CPython Analysis

Why can’t we write list.len()?

Python is an OO language. To reverse a list, you call lst.reverse(); to search a list for an element, you call lst.index().
8

Many people, when they first discover the heapq module, have two questions:

Why does it define a bunch of functions instead of a container type? Why don't those functions take a key or reverse parameter, like all the other sorting-related stuff in Python? Why not a type?

At the abstract level, it's often easier to think of heaps as an algorithm rather than a data structure.
1

Currently, in CPython, if you want to process bytecode, either in C or in Python, it’s pretty complicated.

The built-in peephole optimizer has to do extra work fixing up jump targets and the line-number table, and just punts on many cases because they’re too hard to deal with. PEP 511 proposes a mechanism for registering third-party (or possibly stdlib) optimizers, and they’ll all have to do the same kind of work.
3

One common "advanced question" on places like StackOverflow and python-list is "how do I dynamically create a function/method/class/whatever"? The standard answer is: first, some caveats about why you probably don't want to do that, and then an explanation of the various ways to do it when you really do need to.

But really, creating functions, methods, classes, etc. in Python is always already dynamic.

Some cases of "I need a dynamic function" are just "Yeah? And you've already got one".
1

A few years ago, Cesare di Mauro created a project called WPython, a fork of CPython 2.6.4 that “brings many optimizations and refactorings”. The starting point of the project was replacing the bytecode with “wordcode”. However, there were a number of other changes on top of it.

I believe it’s possible that replacing the bytecode with wordcode would be useful on its own.
1

Many languages have a for-each loop. In some, like Python, it’s the only kind of for loop:

for i in range(10): print(i) In most languages, the loop variable is only in scope within the code controlled by the for loop,[1] except in languages that don’t have granular scopes at all, like Python.[2]

So, is that i a variable that gets updated each time through the loop or is it a new constant that gets defined each time through the loop?

Almost every language treats it as a reused variable.
4
Blog Archive
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.