[SDL] glSDL Texture sizes

Bob Pendleton bob at pendleton.com
Wed Nov 12 11:32:01 PST 2003

On Tue, 2003-11-11 at 15:27, David Olofson wrote:
> On Tuesday 11 November 2003 20.52, Bob Pendleton wrote:
> [...]
> > > Sounds like a 2D version of a commonly used real time memory
> > > manager design. :-)
> >
> > That is exactly what it was but with all chunks being 2^n in size.
> > So, we indexed the list of lists by n.
> Actually, most RT memory managers also use 2^n chunk sizes, since that 
> keeps the calculations fast and simple.

Yeah, the allocator we used was based on a mixture of experience. On one
side we had a group of people who had experience with RT image
generators used in flight simulators and on the other side we had a
group of people with experience implementing LISP and other programming
languages with dynamic memory allocation.

> > > Did you merge small squares back together when possible, and if
> > > so, how did you go about finding them in the free pool?
> >
> > We tried. The thing is you have to get all four sub-squares
> > together before you can merge them. Which is nearly impossible. We
> > tried inserting them in the free list in address order. Then you
> > can do a simple scan looking at sequential headers and look at the
> > addresses to see if any sequence of four items are all part of the
> > same larger square. (You can do that while you are inserting
> > squares in the free list.) This was actually for use in the X
> > server on the old ESV workstations so it worked pretty well. But,
> > there was always some amount of unrecoverable fragmentation.
> It seems to me that it should be theoretically possible to merge back 
> any groups of squares that used to belong together, although there 
> are no simple and obvious ways of finding out when to merge.

Yes, of course. IIRC, If you use the trick of computing an index for the
start of each block you can always count on certain patterns in the bits
of the index. Depending on the size of the parent block the starting
index of sub-blocks will follow the pattern x00y x01y x10y x11y when x
and y are bit strings of various lengths. 

The smallest sized blocks will have addresses of the form:
x00, x01, x10, x11, the next largest block size will be:
x00bb, x01bb, x10bb, x11bb, the next will look like
x00bbbb, x01bbbb, x10bbbb, x11bbbb

and so on. So, if you now the block size you know the bits to check and
it becomes very easy to scan a sorted list of free blocks and merge then
into the next largest size.

> How about this:
> When allocating a rect for splitting, mark it as ALLOCATED and keep 
> the structure. Add the resulting child rects to the free list for 
> their size. Also store child referenses in a table or list in the 
> parent rect. Put a parent reference in each resulting rectangle.
> Now, whenever a rect is freed, it's removed from the free list, as 
> well as from it's paren't table/list of children. When a rect has no 
> more children, it is marked as free, and returned to the free list.
> (Beware of holes; I just dreamed this up as I wrote it. :-)

This, or something like it, works fine so long as their are a fixed
number of child blocks. I've used it in other memory allocators.

> Of course, this cannot eliminate fragmentation caused by long lived 
> objects, but that's expected. The only sane (*) way to deal with that 
> is to move things around to physically defragment the texture space.
> (*) If you *really* don't want to move things around, you're
>     out of texture RAM, and you can't DMA from system RAM, you
>     could resort to using smaller tiles to make use of the areas
>     around those long lived tiles. Actually, maybe this *is*
>     sane in the case of glSDL, considering that it already does
>     tiling for other reasons...?

Personally I'm starting to like the idea of a bit map based allocator
like the one described earlier. If you use two layers of bit maps you
can solve your problem pretty well. The top layer is used to allocate
max texture sized textures out of the available space and unused space
withing those blocks can be kept track of and allocated using another
bit map for each block. 

			Bob Pendleton

> //David Olofson - Programmer, Composer, Open Source Advocate
> .- Audiality -----------------------------------------------.
> |  Free/Open Source audio engine for games and multimedia.  |
> | MIDI, modular synthesis, real time effects, scripting,... |
> `-----------------------------------> http://audiality.org -'
>    --- http://olofson.net --- http://www.reologica.se ---
> _______________________________________________
> SDL mailing list
> SDL at libsdl.org
> http://www.libsdl.org/mailman/listinfo/sdl
+ Bob Pendleton: writer and programmer. +
+ email: Bob at Pendleton.com              +
+ web:   www.GameProgrammer.com         +

More information about the SDL mailing list