Attempt to optimize `SpriteList.remove()`

[einarf]

Removing a sprite is O(N) worst case. It's because we can't track what index a sprite is in a spritelist or performance will tank. If there was some magical ordered set that solved the problem, that would be great.

One idea is to store sprites using the slot index instead of the rendering order and resolve the actual index during spritelist iteration. This means that removing sprite by reference it fast but the drawback is that removing by index will be slow. There might also be some overhead when iterating a spritelist due to native->python integer conversion when reading from the index buffer.

In addition we could add

• __del__(self, index: int)
• remove_at_index(self, index: int)
• popleft(self)
• swap(self, sprite_a, sprite_b)

In addition the index buffer is resized for every call to remove((). This is an array.array that could potentially be batch updated once before draw()

• Is there a way in python we can remove N indices from this structure without re-allocating it N times?
• A possible way could be using a transform feedback to prune the index buffer but this might put additional stress on the rendering if only one thing is removed per frame
• Keeping dead entries in the index buffer marked with a sentinel value and purge periodically could also be a solution but this also adds more complexity for custom shaders
• Worst case see how converting the array to a list, remove items and create a new array from that

[DragonMoffon]

Could we maybe use a pool instead?

When you add a sprite the active index shifts up by one.
then when a sprite is removed we swap the data from the last active sprite with the removed sprite and decrement the active index. It doesn't preserve order of data, but we could still preserve idx order with some finangling

[einarf]

The removal process looks like this

• list.remove(sprite) - O(N) - scans the list and removes the first occurrence
• Remove the spritelist reference from the sprite
  • This can probably be removed in the collision revamp when we can have spaces for sprites instead
• Delete the sprite in the slot dict and add mark the slot as free
• array.remove(slot) - O(N) - scans the array looking for the first occurrence of the slot integer
• Appends a 0 at the end of the array. This and the above operation likely leads to an internal re-allocation
• Remove sprite from spatial hash if present

Assuming the index buffer is always the same order as the spritelist we can reuse the first index when removing the element from the array.

[einarf]

I found two really nice optimizations #2624

[einarf]

Closing this for now. We already got a pretty nice boost.

@DragonMoffon you can look over #2624 if you want.