Hi, I patched nommu.c because free()'ing often was quite slow in case that I allocated many memory blocks with malloc() and then wanted to free them. Please, try the attached patch. Background: From time to time my user program switches the used data. My data consists of many dynamically allocated memory blocks (e.g. a big tree of nodes with strings as leaves). Switching those data means to free() all the nodes recursively, and then to malloc() all the new nodes. It turned out deallocating such big tree object takes several seconds (O((n^2)/2)) due the sequential search in a simple-linked list when searching the next candidate to delete. My patch stores the last position to start there again on the next free() in that list. First, it searches 8 predecessors, that's why the change to a double-linked list. Second, on negative result, it checks if the search along the successors can start from the stored position. The patch speeds up here a lot, about 3 times faster than before. With my added logging on you can see how the search is done. Often, the next one to free() is in the near neighbourhood of the previously deleted one. Without the adding of a 'prev' pointer to the struct you can't search the predecessors, but nevertheless the second lookup in 'next' direction should often help anyway. Any comments about the patch are appreciated. CU, Falk
Attachment:
fastFreePatch.diff
Description: fastFreePatch.diff