[Tim] > I'll note that the approach I very briefly sketched before > (restructure the list of arenas to partition it into multiple lists > partitioned by number of free pools) "should make" obmalloc > competitive with malloc here ...
But it's also intrusive, breaking up a simple linked list into a mutli-headed beast. That affects all code using it, not just the parts mutating it. So instead I suggest leaving `usable_arenas` entirely alone, but add a vector of "search fingers", say, static struct arenaobject* nfp2lasta[MAX_NUMBER_OF_FREE_POOLS_POSSIBLE + 1]; mapping a count of free pools to (a pointer to) the last arena object in usable_arenas with that number of free pools. Then the search loop in py_malloc_free() can be replaced with a single array lookup.: it leaps directly to where the search loop ends now. For example, if we free a pool in an arena that had 23 free pools, then the arena object's count of free pools has to be increased to 24, and the arena object unlinked from its current position in usable_arenas and inserted immediately after nfp2lasta[23]. Note that usable_arenas is a doubly linked list, so there's no _need_ at all to iterate over it. Each node in the list knows what's immediately before and after it. And since a free pool count can only increase by 1, it's always correct to move the arena immediately after the last arena with the same original free pool count. Key invariants: 1. nfp2lasta[n] is NULL if and only if no arena in usable_arenas has nfreepools == n. 2. nfp2lasta[pa->nfreepools] == pa if and only if pa is the only arena in usable_arenas with that many free pools. So, in the example above, nfp2lasta[23] has to be set to NULL if and only if the arena in question was the only one with 23 free pools (which can be determined cheaply via invariant #2). And nfp2lasta[24] has to be set to point to the arena in question if and only if nfp2lasta[24] is NULL. Tricky bit: if the arena in question is the only one with a given original free pool count, no pointers in arena objects need to be changed at all. Following the sketch above literally would leave you trying to insert it after itself, which wouldn't end well ;-) Anyway, this "feels like a right solution" to me, eliminating all searches with simple (albeit delicate) constant-time code, and requiring code changes only where an arena's number of free pools can change. _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
