Locality and Custom Allocations

[Sean Kelly]

John Demme wrote:
> 
> The bulk of my surpise came when only one read loop was done, so the
> allocation part of the test program has far more weight.  The LinkedList
> without block allocations does better by an order of magnitude!!!  This
> blew me away.  I figured that in terms of allocations, the block
> allocations would do no harm, and probably do better.  In fact, I expected
> them to beat out the ArrayList-- the whole point of a LinkedList!  Here is
> what I surmise from this result:
> 
> Custom Allocators are Slow.
> 
> Is my reasoning faulty, or am I right?  If I'm right, here's my question to
> Walter:  why?  Are calls to these allocators not inlined?  If not, can they
> be?  In addition, to what extent can virtual function calls be sped up via
> optimization?  Under what circumstances can calls to virtual methods be
> inlined?

This was the conclusion in some research papers I've read as well, the 
most relevant being "Reconsidering Custom Memory Allocation":

http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf

I'll leave the paper to outline why.


Sean