9 Nov
2007
9 Nov
'07
9:54 a.m.
On Friday 09 November 2007, Stefano D'Angelo wrote:
[...]
No! You'd pre-allocate (or just not add) the "holes", so those areas
are just ignored.
Well, I'm not even sure it takes any real tricks; it all depends on
the algorithm. I just downloaded TLSF 2.3.2 in order to find out. :-)
Oh, and that version should work on 64 bit platforms as well, so I can
actually use it out of the box on my development system. ;-)
If the pool blocks have the right sizes in relation to the address
range they're in, one could get away with grabbing a few bits of the
pointer and look up the pool in a small table. Tricky and dangerous,
though, as you have no real control over the allocation of new pool
blocks...
Yeah... I prefer nice and clean solutions too, but sometimes you just
have to get the job done, and worry about style in the next
refactoring cycle. :-)
Oh, BTW, I just realized that my "quick hack" approach actually has a
nice bonus: It eliminates the explicit 'mem_pool' arguments from
free_ex() and realloc_ex(), eliminating nasty "Oops, wrong pool!"
bugs. Maybe it's not such a bad idea, after all...
I don't like the idea of an extra pointer per block for small blacks -
but if you deal with large numbers of small blocks (for events and
the like), you should probably use a dedicated manager for that
anyway. For example, in Audiality I use a per-host LIFO stack of
blocks, which means no memory overhead at all, as "free()" doesn't
need to know anything about the block to throw it back on the stack.
Of course... but also a nice challenging task (which could let you
go insane) :-)
Well, I'm crazy enough to design and implement a VM based
scripting/programming language, so it's not like I'm totally unlikely
to dive into stuff like that. :-D
[...]
Yeah. Designing around actual use cases usually results in more
sensible solutions.
//David Olofson - Programmer, Composer, Open Source Advocate
.------- http://olofson.net - Games, SDL examples -------.
| http://zeespace.net - 2.5D rendering engine |
| http://audiality.org - Music/audio engine |
| http://eel.olofson.net - Real time scripting |
'-- http://www.reologica.se - Rheology instrumentation --'
Provided the
allocator actually *works* without a fully populated
pool (I'm not sure about that...), this would allow new memory
blocks to added to the pool later, as long as they're within the
address range defined by the start of the pool and the "maximum
address span" that the allocator was initialized for.
Ah ok, but that would mean being sure that the new pool will be
contiguous to the first one. Then, if TLSF works as I remember, you
would have to either rearrange the bitamp (which could bring to a
big amount of fragmentation too) or have the second bitmap logically
equivalent to the first, and that is in practice what I was
suggesting, except for the contiguity.
Well, my idea was to construct the bitmap based on the maximum pool
size. Suboptimal if you start with a very small pool and/or set the
max very high, but then again, I think you could keep the upper and
lower bounds within a reasonable range in most applications. It
doesn't make sense to start with a pool of just a few kB on a 256+ MB
machine, and the upper bound for any RT memory management is
obviously the amount of physical RAM available for locking.
[...]
Wiring
additional pools to the out-of-memory condition indeed
avoids overhead when dealing with the initial pool, but it
multiplies overhead when you need to deal with additional pools
instead.
Yes, some clever trick should be found. :-)
Maybe one could make use some trick based on the particular geometry
of TLSF pools and relative bitmaps. Also, how do
you know where a free()d block belongs? Checking the
address against each pool isn't exactly efficient, but perhaps no
disaster for small number of pools...
This is a problem as well :-\ [heresy mode on]
Maybe change values passed to/returned from the
allocation/deallocation calls?
[heresy mode off]
Not quite sure what you mean... Sounds dangerous, though. ;-)
[...]
Basically,
without somehow piggy-backing on the existing logic of
TLSF, I have a hard time seeing how you could get away with less
overhead than the "wrapped manager" solution I first suggested.
(That "only" adds one pointer per allocated block, and an extra
level of indirection to use the right manager. Not great, but at
least it's simple, lets you add pools of any size, and scales to
any number of pools.)
It's just that I'm a bit a "purist", however I do agree that maybe
your suggestion could solve the problem, at least until someone goes
deep into TLSF logic. This is just a thought... I never really wrote or
worked on an
allocator :-)
I did, but only enough to realize that coming up with something
really nice and efficient is a lot of work. :-) Yes, that
probably does make sense after all, considering that
it's quite likely that a lot of plugins will deal only with a
small number of different block sizes, and the fact that a "real"
RT allocator (even a really good one) has quite a bit more
overhead than a simple LIFO pool.
Fine :-) However I would like to hear something from some plugin
developer too.