python memory usage dict and variables large dataset

Question

So, I'm making a game in Python 3.4. In the game I need to keep track of a map. It is a map of joined rooms, starting at (0,0) and continuing in every direction, generated in a filtered-random way(only correct matches for the next position are used for a random list select).

I have several types of rooms, which have a name, and a list of doors:

RoomType = namedtuple('Room','Type,EntranceLst')
typeA = RoomType("A",["Bottom"])
...

For the map at the moment I keep a dict of positions and the type of room:

currentRoomType = typeA
currentRoomPos = (0,0)
navMap = {currentRoomPos: currentRoomType}

I have loop that generates 9.000.000 rooms, to test the memory usage. I get around 600 and 800Mb when I run it. I was wondering if there is a way to optimize that.

I tried with instead of doing

navMap = {currentRoomPos: currentRoomType}

I would do

navMap = {currentRoomPos: "A"}

but this doesn't have a real change in usage.

Now I was wondering if I could - and should - keep a list of all the types, and for every type keep the positions on which it occurs. I do not know however if it will make a difference with the way python manages its variables.

This is pretty much a thought-experiment, but if anything useful comes from it I will probably implement it.

Answer 1

You can use sys.getsizeof(object) to get the size of a Python object. However, you have to be careful when calling sys.getsizeof on containers: it only gives the size of the container, not the content -- see this recipe for an explanation of how to get the total size of a container, including contents. In this case, we don't need to go quite so deep: we can just manually add up the size of the container and the size of its contents.

The sizes of the types in question are:

# room type size
>>> sys.getsizeof(RoomType("A",["Bottom"])) + sys.getsizeof("A") + sys.getsizeof(["Bottom"]) + sys.getsizeof("Bottom")
233

# position size
>>> sys.getsizeof((0,0)) +  2*sys.getsizeof(0)
120

# One character size
>>> sys.getsizeof("A")
38

Let's look at the different options, assuming you have N rooms:

1. Dictionary from position -> room_type. This involves keeping N*(size(position) + size(room_type)) = 353 N bytes in memory.
2. Dictionary from position -> 1-character string. This involves keeping N*158 bytes in memory.
3. Dictionary from type -> set of positions. This involves keeping N*120 bytes plus a tiny overhead with storing dictionary keys.

In terms of memory usage, the third option is clearly better. However, as is often the case, you have a CPU memory tradeoff. It's worth thinking briefly about the computational complexity of the queries you are likely to do. To find the type of a room given its position, with each of the three choices above you have to:

1. Look up the position in a dictionary. This is an O(1) lookup, so you'll always have the same run time (approximately), independent of the number of rooms (for a large number of rooms).
2. Same
3. Look at each type, and for each type, ask if that position is in the set of positions for that type. This is an O(ntypes) lookup, that is, the time it takes is proportional to the number of types that you have. Note that, if you had gone for list instead of a set to store the rooms of a given type, this would grow to O(nrooms * ntypes), which would kill your performance.

As always, when optimising, it is important to consider the effect of an optimisation on both memory usage and CPU time. The two are often at odds.

As an alternative, you could consider keeping the types in a 2-dimensional numpy array of characters, if your map is sufficiently rectangular. I believe this would be far more efficient. Each character in a numpy array is a single byte, so the memory usage would be much less, and the CPU time would still be O(1) lookup from room position to type:

# Generate random 20 x 10 rectangular map
>>> map = np.repeat('a', 100).reshape(20, 10)
>>> map.nbytes
200 # ie. 1 byte per character.

---

Some additionally small scale optimisations:

Encode the room type as an int rather than a string. Ints have size 24 bytes, while one-character strings have size 38.

Encode the position as a single integer, rather than a tuple. For instance:

# Random position
xpos = 5
ypos = 92

# Encode the position as a single int, using high-order bits for x and low-order bits for y
pos = 5*1000 + ypos

# Recover the x and y values of the position.     
xpos = pos / 1000
ypos = pos % 1000

Note that this kills readability, so it's only worth doing if you want to squeeze the last bits of performance. In practice, you might want to use a power of 2, rather than a power of 10, as your delimiter (but a power of 10 helps with debugging and readability). Note that this brings your number of bytes per position from 120 to 24. If you do go down this route, consider defining a Position class using __slots__ to tell Python how to allocate memory, and add xpos and ypos properties to the class. You don't want to litter your code with pos / 1000 and pos % 1000 statements.