I pushed the first half of the block_alloc.h replacement. The new block allocator improves the worst case search time when freeing blocks. The old one kept pages in a linked list and had to search linearly to find the right page on free.
Also, unlike the old one it is not using macros to inline the block size, which decreases code size considerably.
The old block allocator behaved very badly, when freeing blocks in a somewhat random fashion. Consider this example:
class Node { object left, right; }
int rec1(object node, int depth) { if (depth < 20) { rec1(node->left = Node(), depth+1); rec1(node->right = Node(), depth+1); } }
int main() { object n = Node(); rec1(n, 0); n = 0; return 0; }
Bad things happen, when freeing the tree. This particular example is about seven times faster using the new allocator.
There is some places where the old one is still in use. Furthermore, since it clashes with cc0851de980d46e85e514657d8d9a484fe8be2eb, its in a seperate branch right now (arne/new_block_alloc). Using malloc/free as in cc0851de980d46e85e514657d8d9a484fe8be2eb is certainly much faster than the old worst case behavior. I would guess the new block allocator is faster than malloc/free, so I propose to overwrite cc0851de980d46e85e514657d8d9a484fe8be2eb by this. Any objections?
arne