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