[SDL] glSDL Texture sizes

David Olofson david at olofson.net
Tue Nov 11 13:28:00 PST 2003

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.

> > 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.

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. :-)

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...?

//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 ---

More information about the SDL mailing list