MALLOC_ORDER_LARGE_FREELIST

[Simon Lundmark]

Hi,

I'm currently looking a bit at performance for the driver. I noticed that we spend a lot of time in add_to_free_list.

I did a comparison with/without the MALLOC_ORDER_LARGE_FREELIST define and the implications were astounding. Without the define saving and loading files takes about 25% of the time than with the define. 

The design implicitly assumes same-size lists are short (diverse sizes -> the AVL tree spreads blocks across many nodes, each with a few list entries). A mud breaks that assumption in the worst way: it churns identical structures constantly - savefile pointer-table mempool chunks, same-shaped mappings and arrays - so a single size class accumulates thousands of free blocks, and the sorted insert becomes an O(n) pointer-chase over a cold, scattered list. The benefit (slightly better packing) is probabilistic and modest; the cost became 30% of our CPU time at the point of measurement.

We'll be turning this off in the future but I suggest that it will be switched to default off in the future. 

I could likely implement some sort of middle-ground with a tail pointer or maybe make the list unsorted with a low-address bias at the head. 

Please let me know what you guys think.

Thanks,

Simon