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