[haiku-development] Re: heap freelist problem?
- From: "Michael Lotz" <mmlr@xxxxxxxx>
- To: haiku-development@xxxxxxxxxxxxx
- Date: Mon, 04 Feb 2008 23:31:08 +0100
Hi Marcus
> > I am going to take a look at simply sorting the freelists which
> > should
> > have no real performance impact and speed up the lookup
> > considerably.
> > That will probably be a good enough fix for the current situation.
> Can't we just use an additonal hash where we put the pointers when
> they
> have been freed, and remove them when they get assigned again?
> That should speed things up as well, and could be implemented without
> touching the basic allocator. just for debugging, of cause.
I eventually came to that conclusion too, but from an implementation
standpoint of view it is not really parctical. To not change the base
allocator it would be required to have some structure to hold the
address and the next pointer to work as an element of the hash table.
The problem is that you can't simply allocate and free this entry, as
exactly allocating and freeing would in turn cause another loop of
entering/removing from the hash which would result in another alloc/
free and so forth... It could be done with seperatly allocated blocks/
areas, but then you'd have to implement another pseudo allocator just
to support the to-be-replaced allocator, which doesn't strike me as
very beneficial. In the end a hash table would just devide the amount
of entries to search through on each free (in the best case), but since
the freelists can get _very_ large, this does not really scale.
Another idea I had while looking through the code: When using
PARANOID_KFREE we are marking everything with 0xdeadbeef anyway. So we
could simply check for 0xdeadbeef and only walk the free list if we
find that. I know that this is not safe for usages like free(pointer);
memset(pointer, 0, x); but honestly, since we put the freelist link
into the first four bytes of every freed block of memory, doing that
would cause the freelist to go corrupt anyway. So is this an acceptable
solution? I would really like to do away with this constant freelist
walking as disabling this gives a considerable performance boost.
Regards
Michael
Other related posts:
