On Tue, Apr 26, 2011 at 10:09:23AM -0400, Ted Unangst wrote:
> On Tue, Apr 26, 2011 at 9:33 AM, Otto Moerbeek <[email protected]> wrote:
> > This diff implements a tradeoff to gain speed at the cost of reducing
> > the randomness of chunk allocation in malloc slightly.
> >
> > The idea is only to randomize the first half of chunks in a page. The
> > second half of chunks will fill in the gaps in-order. The
> > effectiveness of the current randomization decreases already with the
> > number of free slots diminishing in a page.
> >
> > In one test case, this diff reduced the runtime from 31s to 25s. I'm
> > not completely sure if the reduced randomness is acceptable. But if
>
> Perhaps a quarter? We want to prevent adjacent consecutive
> allocations, which is still very likely at the half way point, but
> diminishes after that.
Yes, that might be better, though you some of the performance gain is
lost because you are scanning a lot of bits: i free bits + all bits in
between that are not free. If a chunk page is pretty full, that's a
lot of bits before you find the i'th free chunk.
Originally I though most of the time was lost getting the random bits,
but now it seems the scanning of the bits is to blame. Unless I'm
misinterpreting my data....
-Otto
