Jump to content
  • Advertisement
Sign in to follow this  
Gumgo

Allocation algorithm

This topic is 3081 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm storing multiple objects in OpenGL vertex buffers. To do this, I allocate a large vertex buffer and on the CPU keep track of which portions are in use.

Currently, to manage objects, I maintain a list of free and used "blocks" (not sure if that's the right term). Initially, there is a single free block. When a new object is added, I linearly scan the list of blocks and split the first free one that is big enough. To delete objects, I merge the block used with any surrounding free blocks.

Of course, this is definitely not an optimal solution and has many problems such as fragmentation.

Specifically, since the data represents vertices, each object is not likely to be the same size (I read on this page about QuickFit which takes advantage of the fact that blocks of the same size would often be allocated, but I can't use that one). I will be adding/deleting objects at various times, so I can't do something like mark-and-release.

Can anyone suggest an allocation algorithm for me to research/implement that might work well for this purpose?

Share this post


Link to post
Share on other sites
Advertisement
My last encounter with real theoretical computer science is unfortunately a bit behind and I currently don't have access to my notes from back then. However, as far as I remember the strategy you are currently utilizing (First Fit) is in the same theoretical efficiency class as many other algorithms and I don't believe you can get any better for the general case (in practical applications strategies like Best Fit even perform worse because they have a tendency to cause miniature fragments which are next to impossible to recycle).
You might be able to get better performance with stochastic strategies but unfortunately this is where my memory really starts to go a bit fuzzy.

However, the main point here is "general case". If you can better define what kind of allocations you have to deal with, things could be improved upon.

Share this post


Link to post
Share on other sites
One option you have with a vertex buffer is to keep track of how fragmented it is, and occasionally defragment it by creating a new buffer of the same size and copying everything to that eliminating the gaps then throw away the original. This could either be done when an allocation fails, or at level load time.

Another trick is that you can try and put short lived allocations at one end of the buffer, and long lived ones at the other. That way they don't fragment each other so much.

Share this post


Link to post
Share on other sites
Quote:
Original post by Adam_42
One option you have with a vertex buffer is to keep track of how fragmented it is, and occasionally defragment it by creating a new buffer of the same size and copying everything to that eliminating the gaps then throw away the original.


Depending on latency/jitter (microsecond scale), this is likely the simplest by far. As it happens, copying data in this way is so cheap, it can probably be done every frame.


But since this is about VBOs, it might be perhaps be worth minimizing the data transferred to GPU, if possible.

Quote:
Specifically, since the data represents vertices, each object is not likely to be the same size

What exactly do these buffers hold and what are the approximate sizes? How is geometry indexed, are they triangles only and there is a separate array holding indices?

Share this post


Link to post
Share on other sites
Dang, I thought posted yesterday but I guess it didn't get submitted.

Anyway, my vertex data can be fairly large, up to 96 bytes per vertex in some cases. The vertex data is stored in a VBO and an IBO is used to index it to form triangles. Unfortunately I'm not sure how big each mesh will be, but they probably will be fairly low poly.

The idea about occasionally defragmenting seems interesting. In fact, I wouldn't even need a new buffer necessarily if I move forward through the data and push blocks "back" to fill holes when I defragment. One issue with this is that right now I'm simply returning the offset into the buffer upon allocation, but if I move data around, I'd need to index objects and return an index so the actual offsets could be altered without needing to update everything pointing to that object in the buffer (when the offsets were needed I'd just pass the index to the object managing the buffer). This actually seems like a cleaner way to do things, so I'd have the object that manages the buffer also manage all the offsets of data in the buffer, rather than having those offsets floating around in various other objects.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!