> Investigating further, from one stop, I used gdb to follow the chain > of pointers in the nextarena and prevarena directions. There were > 5449 and 112765 links, respectively. maxarenas is 131072.
To reduce the time for keeping sorted lists of arenas, I was first thinking of a binheap. I had formulated it all, and don't want to waste that effort, so I attach it below in case my second idea (right below) is flawed. It then occurred that there are only 64 different values for nfreepools, as ARENA_SIZE is 256kiB, and POOL_SIZE is 4kiB. So rather than keeping the list sorted, I now propose to maintain 64 lists, accessible in an array double-linked lists indexed by nfreepools. Whenever nfreepools changes, the arena_object is unlinked from its current list, and linked into the new list. This should reduce the overhead for keeping the lists sorted down from O(n) to O(1), with a moderate overhead of 64 pointers (512 Bytes in your case). Allocation of a new pool would have to do a linear search in these pointers (finding the arena with the least number of pools); this could be sped up with a finger pointing to the last index where a pool was found (-1, since that pool will have moved). Regards, Martin a) usable_arenas becomes an arena_object**, pointing to an array of maxarenas+1 arena*. A second variable max_usable_arenas is added. arena_object loses the prevarena pointer, and gains a usable_index value of type size_t (which is 0 for unused or completely allocated arena_objects). usable_arenas should stay heap-sorted, with the arena_object with the smallest nfreepools at index 1. b) sink and swim operations are added, which keep usable_index intact whenever arena_object pointers get swapped. c) whenever a pool is allocated in an arena, nfreepools decreases, and swim is called for the arena. whenever a pool becomes free, sink is called. d) when the last pool was allocated in an arena, it is removed from the heap. likewise, when all pools are freed in an arena, it is removed from the heap and returned to the system. e) when the first pool gets freed in an arena, it is added to the heap. On each pool allocation/deallocation, this should get the O(n) complexity of keeping the arena list sorted down to O(log n). _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
