Ping-pong buffer (swap 1-frame allocator) suitable for games?

Started by
4 comments, last by hyyou 6 years, 8 months ago

I am considering to allocate most persistent data of my ECS framework on a one-frame allocator.

To extend their life to exist on > 1 frame, I will need to copy it to another buffer.

Initialization  I create Buffer X and Y.  Each has 50-300MB.

  • 1st timestep : every Entity / Components will use buffer X to allocate.
  • 1st-end : copy every Entity/Component that are not marked as deleted to buffer Y, clear X.
  • 2st timestep : every Entity / Components will use buffer Y to allocate.
  • 2st-end : copy every Entity/Component that are not marked as deleted to buffer X, clear Y.  ...

Advantage

  • almost 0 fragmentation cost, pool is not needed anymore
  • very low cache miss in game-logic

Disadvantage

  • high cost of memory swapping (X<-->Y 50-300 MB every timestep)
  • Reason : computer can read or write memory at 10 GB/s = 170 MB/timestep
  • (reference : https://stackoverflow.com/questions/25827416/ )
  • (minor) pointer become invalidated, I must use ID instead

Note: Luckily, every components are POD (plain old data = no pointer as field).

After some draft, it strongly believe it is possible to implement.

Question

  • Does it sound bad?  Is it a good practice / technique?
  • Is "ping-pong buffer" a correct name of this technique?  What are other names?

 

 

Advertisement

Congratulations, you have reinvented the copying garbage collector. It's going to be ridiculously expensive to run it every frame as you propose - you've already burnt your entire memory bandwidth just of garbage collection, leaving nothing for the actual game.

This might make sense if the number of deleted objects every frame vastly outnumbered the living objects, but I'm hard put to imagine a scenario where that would be true. How many objects in your game *actually* are created/deleted in a single frame?

Many simulations are designed such that zero allocations/deallocations take place on a frame-by-frame basis. i.e. by preallocating pools of objects when the level loads, you can potentially avoid ever performing an allocation during the level.

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

I tried doing something similar to this 10-12 years ago when I was trying my hand at a Liero clone, but with N stages/copies/whatever (ie 5). The idea was basically to store a complete copy of the game state up to N frames back. This way I thought I could back up and re-run the simulation when an old network packet arrived. The reason I wanted to do it that way is that it (Liero that is) is a rather fast paced action game, with thousands if not millions of objects and destructible terrain, where butterfly effects can potentially be a giant problem, while back then we also had much crappier connections than we do now.

Anyway, my conclusion was basically what swiftcoder said, memory bandwidth sucks. Back then we had something like 1-2gb/s, which I thought would give me something like 20MB/frame, but I didn't initially realize that it was 20MB spread across the entire frame, not a quick action at the beginning of the frame. In short, the copying alone ate every last slice of juice my high end P4 system had to offer at the time.

Temporary allocation strategies have their place in games, yes. The trick is to use them very selectively, i.e. only for data you know will be short-lived (in this case).

If you need allocation and you know you won't preserve the results for more than a tick, you can definitely use strategies that throw away the memory and restart at the beginning of the next frame. I've done this to great effect in past games.

More generally, if you know the lifetime patterns of a piece of data, you can find a custom allocator that will suit your specific use cases. It is not uncommon for games to have several custom allocation strategies for different sorts of data.

As has been noted already, doing poor-man's copying GC is risky at best and probably prohibitively expensive. But you can still get great mileage out of custom allocators if you're more deliberate in how you deploy them.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

Thank a lot, swiftcoder, DvDmanDT and ApochPiQ. 

Your valuable knowledge save me several working days.   :D

This topic is closed to new replies.

Advertisement