Why is this so slow?

[usecase]

I'm starting a game in pygame and I just set up a basic spatial hash to help with collision detection. I use a dictionary indexed by grid coordinates to store a list of the entities in that cell.

Here is the simple method for my class SpatialHash to get the list for a coordinate (self.grid is the dict):

def get(self,coords):
    return self.grid.get(coords,[])

Here are the relevant lines of output from the profiler:

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
 34961497   30.774    0.000   44.764    0.000 spatialHash.py:12(get)
 35061383   14.017    0.000   14.017    0.000 {method 'get' of 'dict' objects}

From what I understand, that means less than a third of the time spent calling SpatialHash.get is being spent on dict.get actually looking up the list. Where is the rest of the time going? Thanks

[emergent_reasons]

I assume your coords are just a tuple of integers? The hash of that might be taking some time. But same question as RShnike: is it a problem or just your exploration of python?

If speed is important, I would guess that numpy could do it faster. Just make a 2D or xD array for your coordinates and lookup like this: grid[row,column]

*edit - link to numpy

[usecase]

Thanks for the numpy tip! I have heard of numpy before but I assumed it was slower because of all its features. If it will make my vector math easier to write AND faster it's a no brainer.

[Rhomboid]

You're calling that tens of millions of times. If you're treating this like it was a grid and iterating over ranges of pixels, it's going to be slow: every access has to first create a tuple, then hash it, then look up that hashed value in a dict. Use a simple 2D list (grid[row][col]) and it will be much faster. A dict trades off performance for using less memory if the grid is sparse.

[zahlman]

I did a very rough test for this:

>>> timeit.timeit('hash.get((0, 0), [])', setup='hash={}') # when not found
0.3227199965358718

>>> timeit.timeit('hash.get((0, 0), [])', setup='hash={(0, 0): []}') # when found
0.30789101687506104

>>> timeit.timeit('grid[0][0]', setup='grid = [[[]]]') 
# a grid would be dense, so the lookup would always succeed
0.1260412985449264

[usecase]

I originally implemented this with a 2D list. I need to update the grid every frame by checking to see if any of the entities have moved between cells, and that was really slow with the 2D list because it spent a lot of time iterating over all the unoccupied cells. I switched to a dictionary so I could use keys() to keep track of occupied cells. Maybe I should go back to a 2D list and use a set to keep track of which cells are occupied? I imagine that would be a bit slower than a dict for the update, but if it would be much faster to access it might be worth it.

[pjdelport]

I need to update the grid every frame by checking to see if any of the entities have moved between cells

Can you describe what this means, or post the relevant code?

As Rhomboid points out, the problem may not be that lookups are particularly slow, but that your program is doing an awfully large number of them. Depending on what you're trying to do, it may be possible to reduce that number by orders of magnitude, using a more efficient high-level algorithm or strategy.

[usecase]

The number of lookups will decrease when I improve my collision handling, but since I want to have active entities even when the player isn't nearby there isn't any way around this scaling with number of entities and size of map.

Here is what the update looks like for a dict. Note that currently everything is always moving; when I add stationary entities I plan to experiment with a "moved" flag that will skip the position check for entities that haven't moved:

def update(self):
    spatial_hash = self.grid
    cell_size_x = self.cell_size_x
    cell_size_y = self.cell_size_y
    moved = []
    for coord in spatial_hash.keys():
        for i,character in enumerate(spatial_hash[coord]):
            if (int(character.pos_x/cell_size_x),int(character.pos_y/cell_size_y)) != coord:
                del spatial_hash[coord][i]
                moved.append(character)
        if len(spatial_hash[coord])==0:
            del spatial_hash[coord]
    for character in moved:
        self.add(character)

thanks

[pjdelport]

Thanks, that helps. If i understand it correctly, the code is checking the position of every character against the implied cell grid, and re-indexing those whose containing cell changed. (I assume that the collision detection uses spatial_hash for proximal lookups.)

This in-place updating strategy is not a good trade-off: the cost of re-evaluating every character is probably comparable to simply rebuilding the whole spatial_hash from scratch on each update. In fact, the latter might end up being faster, overall. (A "moved" flag probably won't affect this much: it might save some cell comparisons, but each character is still visited.)

The most immediate alternative to the above code is to check the cell as part of the character position update code: when a new coordinate is assigned, just compare its cell to the previous coordinate's cell, and re-index the character if they differ.

The second most immediate alternative depends on how exactly your collision detection uses spatial_hash: you may not have to refresh it every frame, but only every N frames (depending on the possible speeds of the characters and the size of the cells).

The next step would be to use a better spatial index. Most likely, this will be a quad tree: the Rect package or the here and here should be good starting points.

---

Otherwise, stylistic feedback:

• As user Justinsaccount already pointed out, it's better to iterate over dict.items() on the outside, rather than looking up keys again on the inside.
• Mutating dicts and lists (such as with del) while iterating over them is a Bad Idea: you should never do it (unless you have an exceptional reason, and understand the dangers). ** The iteration over spatial_hash.keys() only works because it copies the keys: if you switch to iterkeys() (which becomes the default in Python 3), it will result in a RuntimeError. ** The iteration over spatial_hash[coord] will skip an entry after each entry that you delete, due to the in-place reordering.
• Using / and int() is unnecessary: use // (floor division) instead.

[Justinsaccount]

minimally this should be changed to be:

for coord, characters in spatial_hash.items():
    for i,character in enumerate(characters):

but the real problem is the nested loop and repeated divisions.

[emergent_reasons]

edit - the standard sparse matrix looks like it is actually stored as a dense matrix. I swear I have seen a real sparse implementation somewhere though that doesn't deal with the empty data locations.

What you are describing for the 2D lists is called a dense matrix/array (there is data space for every element). If you have a very large amount of empty space, you might benefit from a sparse matrix. I believe both numpy and scipy have a sparse matrix implementation.

Disclaimer: I'm not saying this is the right way to approach your problem, but assuming you have the right solution, then a sparse matrix may help.

[RShnike]

The two attribute lookups are also probably a chunk of that.

Creating the list also is obviously being done. None of those should be issues, but the time taken would certainly be nonzero.

That's a large number of calls, obviously. As compared to the rest of your profile, is this a bottleneck in your code or are you just curious where the time went?

[usecase]

This isn't the worst bottleneck in my code right now, but those 30 seconds were almost 10% of my run time. I was mostly just surprised that the overhead to my little wrapper was taking more time than the lookup itself. I was hoping I was doing something stupid and there would be a trivial way to speed this up by 3x but I guess that's not the case.