Locality and Custom Allocations

John Demme me at teqdruid.com
Sun May 14 00:38:41 PDT 2006


Walter (and other compiler geniuses)- I've got two questions for you at the
bottom of the post, if you want to skip the bulk of it.

-------

In order to decrease page faults (and thus increase performance) of my
LinkedList, I implemented a block allocate scheme using the below snippet
in a node struct:
struct Node
{
        static void[] block;
        /*
          If we allocate large blocks in advance for the nodes, then
          we increase our locality and thus cut down on page-faults
          and increase our cache-hit percentage
         */
        new (size_t sz, int length)
        {
                if (block.length < sz)
                        block = new void[sz*(length+1)];   
                        
                void* p = block.ptr;
                block = block[sz..$];
                return p;
        }
...
}

Then, I used some variants of the following benchmark code to test
ArrayList, LinkedList with block allocation and LinkedList without block
allocations.  You can find ArrayList and LinkedList (w/o block allocations)
in the mango.containers SVN.  ArrayList is backed by a D dynamic array, and
LinkedList uses struct nodes.

void main()
{
        MutableList!(int) list = new LinkedList!(int)();

        for (int i=0; i<1_000_000; i++)
        {
                list ~= i;
        }

        for (int j=0; j<1; j++)
        {
                foreach (int index, int i; list)
                {
                        if (i != index)
                                Stdout("Error: "c)(i)(" != "c)(index)(CR);
                }
        }
}

I found the results quite puzzling.  I used the "time" command in unix to
get the results. Here they are:

LinkedList, block allocations, compiler optimizations
(-O -release -inline) , 1_000_000 elements, 1_000 read loops
real    0m35.673s
user    0m34.274s
sys     0m0.240s

LinkedList, no block allocations, compiler optimizations
(-O -release -inline) , 1_000_000 elements, 1_000 read loops
real    1m2.546s
user    0m57.824s
sys     0m0.412s

ArrayList, compiler optimizations (-O -release -inline) , 1_000_000
elements, 1_000 read loops
real    0m48.569s
user    0m46.559s
sys     0m0.288s

LinkedList, block allocations, compiler optimizations
(-O -release -inline) , 1_000_000 elements, 1 read loop
real    0m2.597s
user    0m2.500s
sys     0m0.016s

LinkedList, no block allocations, compiler optimizations
(-O -release -inline) , 1_000_000 elements, 1 read loop
real    0m0.988s
user    0m0.944s
sys     0m0.028s

ArrayList, compiler optimizations (-O -release -inline) , 1_000_000
elements, 1 read loop
real    0m0.203s
user    0m0.148s
sys     0m0.028s


Interpretation:
Clearly, the block allocations are very helpful in the reads.  And surprise:
the LinkedList performs better than the ArrayList!!!  How?  I suspect that
it has to do with the method of iteration.  mango.container Containers are
iterated through using Iterator objects (the opApplys use them as well) and
the generic ListIterator calls .get(index) on the array in addition to
the .next() call to the iterator.  The LinkedListIterator, however, is
specific to LinkedList and uses a reference to the current node to avoid
the obvious inefficiency of .get(index) on a LinkedList.  Assuming that the
extra call to .get(index) on the ArrayList was causing some strain, I built
an ArrayListIterator to avoid it, and came up with the following results:

ArrayList, compiler optimizations (-O -release -inline) , 1_000_000
elements, 1_000 read loops, using ArrayListIterator
real    0m30.966s
user    0m29.774s
sys     0m0.180s

OK, looks like I was right.  What does this tell us?  That virtual function
calls suck, but we knew this.  The LinkedList with block allocations only
runs about 15% longer than the ArrayList- that's not too shabby.

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?

Sorry for the long post.... I may just be compensating for not posting much
lately.

~John Demme



More information about the Digitalmars-d mailing list