Re: [Algorithms] memory pool algorithms

[Tom P. <ga...@fa...>]

>> then clearly moving things around shouldn't be too terrible.  I believe
>> keeping a parallel bitfield would be more straight forward than an
>> unsorted array of free elements.
>
> So with the parallel bit-field, each bit indicates whether the element has
> been allocated, and when you iterate over all elements you skip elements
> without a set bit?

That was my thinking, with the 30 seconds I spent on the problem.  ;)

I'm not sure if it's ideal, and I'm sure its power would show off
differently in sparse vs. not allocation patterns, but compared to an
array of integers that would require traversing the allocations in
arbitrary order I think it would considerably outperform this.  However,
I'm also aware that setting bits in bitfields is horrifically slow on some
platforms, so you'd probably want to write whatever your solution was in
assembler so that you could optimally schedule memory reads and writes. 
(I did battle with a certain compiler this week on just this front, but my
solution was to remove the need for the set bits at all.)

-tom!

--