Storing objects in a list



  • On 21/05/2013 at 08:10, xxxxxxxx wrote:

    Sorry to hear that BaseArray => R14 
    In any case, it is right up my alley, exactly what I need. And it works just great.



  • On 21/05/2013 at 08:20, xxxxxxxx wrote:

    It would now be interesting to see how this performs against a std::list Jack



  • On 21/05/2013 at 09:23, xxxxxxxx wrote:

    I must say that I am impressed. :-)
    Didn't expect the AtomArray to be fairly fast! And the std library to be so slow.. And the
    GeDynamicArray is really slow compared to all of those! Must be some very rusty piece of
    list implementation? 🙂

    Benchmarks in the next post, the previous results were from a debug build.

    Code:

    #include <c4d.h>
      
    #include <ge_dynamicarray.h>
    #include <list>
    #include <vector>
      
    String* g_mode;
      
    void StartTest(String mode) {
        GePrint("Starting Test: " + mode);
        if (!g_mode) g_mode = new String;
        *g_mode = mode;
    }
      
    void AddStats(String type, LONG delta) {
        LONG l = type.GetLength();
        for (LONG i=l; l <= 20; l++) {
            type += " ";
        }
      
        if (!g_mode) g_mode = new String("FOO");
      
        GePrint(type + " " + *g_mode + ": " + LongToString(delta) + "ms");
    }
      
    void Bench(LONG x) {
        AutoAlloc<AtomArray> atomarr;
        GeDynamicArray<BaseObject*> gda;
        c4d_misc::BaseArray<BaseObject*> ba;
        std::list<BaseObject*> list;
        std::vector<BaseObject*> vector;
        LONG i, tstart, delta;
      
        BaseObject* test = BaseObject::Alloc(Onull);
        if (!test) {
            GeDebugOut("No object could be allocated.");
            return;
        }
        AutoFree<BaseObject> test_free(test);
      
        GePrint("Benchmark started with " + LongToString(x) + " elements.");
        GePrint("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
      
        StartTest("Adding Elements");
      
        // Atom Array
        tstart = GeGetTimer();
        for (i=0; i < x; i++) {
            atomarr->Append(test);
        }
        delta = GeGetTimer() - tstart;
        AddStats("AtomArray", delta);
      
        // GeDynamicArray
        tstart = GeGetTimer();
        for (i=0; i < x; i++) {
            gda.Push(test);
        }
        delta = GeGetTimer() - tstart;
        AddStats("GeDynamicArray", delta);
      
        // BaseArray
        tstart = GeGetTimer();
        for (i=0; i < x; i++) {
            ba.Append(test);
        }
        delta = GeGetTimer() - tstart;
        AddStats("BaseArray", delta);
      
        // std::list
        tstart = GeGetTimer();
        for (i=0; i < x; i++) {
            list.push_back(test);
        }
        delta = GeGetTimer() - tstart;
        AddStats("std::list", delta);
      
        // std::vector
        tstart = GeGetTimer();
        for (i=0; i < x; i++) {
            vector.push_back(test);
        }
        delta = GeGetTimer() - tstart;
        AddStats("std::vector", delta);
      
        StartTest("Iteration");
      
        // AtomArray
        tstart = GeGetTimer();
        for (i=0; i < x; i++) {
            (void) atomarr->GetIndex(i);
        }
        delta = GeGetTimer() - tstart;
        AddStats("AtomArray", delta);
      
        // GeDynamicArray
        tstart = GeGetTimer();
        for (i=0; i < x; i++) {
            (void) gda[i];
        }
        delta = GeGetTimer() - tstart;
        AddStats("GeDynamicArray", delta);
      
        // BaseArray
        tstart = GeGetTimer();
        for (i=0; i < x; i++) {
            (void) ba[i];
        }
        delta = GeGetTimer() - tstart;
        AddStats("BaseArray", delta);
      
        // std::list
        tstart = GeGetTimer();
        std::list<BaseObject*>::iterator list_it = list.begin();
        for (; list_it != list.end(); list_it++) {
            (void) *list_it;
        }
        delta = GeGetTimer() - tstart;
        AddStats("std::list", delta);
      
        // std::vector
        tstart = GeGetTimer();
        std::vector<BaseObject*>::iterator vector_it = vector.begin();
        for (; vector_it != vector.end(); vector_it++) {
            (void) *vector_it;
        }
        delta = GeGetTimer() - tstart;
        AddStats("std::vector", delta);
    }
      
    class Test : public CommandData {
      
    public:
      
        Bool Execute(BaseDocument* doc) {
            Bench(10000);
            Bench(100000);
            Bench(1000000);  
            Bench(10000000);
            return TRUE;
        }
      
    };
      
      
    Bool PluginStart() {
        return RegisterCommandPlugin(1000023, "Benchmark", PLUGINFLAG_COMMAND_HOTKEY, NULL,
                                     "Benchmark for List Types", gNew Test);
        return TRUE;
    }
      
    Bool PluginMessage(LONG type, void* pData) {
        return TRUE;
    }
      
    void PluginEnd() {
    }
    


  • On 21/05/2013 at 09:41, xxxxxxxx wrote:

    Here it is, the new benchmark:

    Benchmark started with 10000 elements.
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Starting Test: Adding Elements
    AtomArray             Adding Elements: 0ms
    GeDynamicArray        Adding Elements: 0ms
    BaseArray             Adding Elements: 0ms
    std::list             Adding Elements: 1ms
    std::vector           Adding Elements: 0ms
    Starting Test: Iteration
    AtomArray             Iteration: 0ms
    GeDynamicArray        Iteration: 0ms
    BaseArray             Iteration: 0ms
    std::list             Iteration: 1ms
    std::vector           Iteration: 0ms
      
    Benchmark started with 100000 elements.
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Starting Test: Adding Elements
    AtomArray             Adding Elements: 2ms
    GeDynamicArray        Adding Elements: 10ms
    BaseArray             Adding Elements: 1ms
    std::list             Adding Elements: 6ms
    std::vector           Adding Elements: 2ms
    Starting Test: Iteration
    AtomArray             Iteration: 0ms
    GeDynamicArray        Iteration: 0ms
    BaseArray             Iteration: 0ms
    std::list             Iteration: 1ms
    std::vector           Iteration: 0ms
      
    Benchmark started with 1000000 elements.
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Starting Test: Adding Elements
    AtomArray             Adding Elements: 20ms
    GeDynamicArray        Adding Elements: 5060ms
    BaseArray             Adding Elements: 18ms
    std::list             Adding Elements: 43ms
    std::vector           Adding Elements: 15ms
    Starting Test: Iteration
    AtomArray             Iteration: 3ms
    GeDynamicArray        Iteration: 0ms
    BaseArray             Iteration: 0ms
    std::list             Iteration: 7ms
    std::vector           Iteration: 0ms
      
    Benchmark started with 10000000 elements.
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Starting Test: Adding Elements
     **AtomArray             Adding Elements: 180ms**
     **GeDynamicArray        Adding Elements: 550471ms**
     **BaseArray             Adding Elements: 170ms**
     **std::list             Adding Elements: 454ms**
     **std::vector           Adding Elements: 236ms**
    Starting Test: Iteration
     **AtomArray             Iteration: 34ms**
     **GeDynamicArray        Iteration: 0ms**
     **BaseArray             Iteration: 0ms**
     **std::list             Iteration: 70ms**
     **std::vector           Iteration: 0ms**
    

    Now that I have compiled in release mode, the differences between the std library and the
    Cinema 4D API or not that huge anymore, but still signifficant!

    -Niklas



  • On 21/05/2013 at 09:58, xxxxxxxx wrote:

    Thanks first of all Niklas! but of course you have to call .reserve() before iterating the vector container when doing push_backs to give a fair comparison (and resize for lists...).

    dereferencing is slower than direct access which is not suprising but good to know!



  • On 21/05/2013 at 10:26, xxxxxxxx wrote:

    Hi Katachi,

    öhm, do I? Why should I reverse the list? All the methods I have used add the new element to
    the end of the list.


    technically equal to *(arr + x) when operating on an array (or better, pointer).

    -Nik



  • On 21/05/2013 at 10:38, xxxxxxxx wrote:

    Originally posted by xxxxxxxx

    Hi Katachi,

    öhm, do I? Why should I reverse the list? All the methods I have used add the new element to
    the end of the list.

    Not reverse, re s er v e! (the vector. resize the list as there is no reserve for lists).
    Btw. for performance purposes you may try the forward_list container as it uses single-linked list (so there should be no overhead over a c-style implementation).

    Originally posted by xxxxxxxx

    And what do you mean with "direct access is faster than dereferencing"? using the [ x ] operator is
    technically equal to *(arr + x) when operating on an array (or better, pointer).

    The iterator in the std containers, you dereference it, i.e. (*iter), for access to the actual data. With [s] you directly access the c-style array (you could do the same with the std containers btw if you'd iterate over the data).



  • On 21/05/2013 at 11:01, xxxxxxxx wrote:

    Oh I'm sorry, misread it. :)
    Well, usually when you use a list, you don't know how many elements it will have after storing
    elements is done. This is why I think not calling reserve() is appropriate in this test.

    I don't think there is a big difference in speed regarding the dereferencing. As you can see from
    the results above, the BaseArray as well as the std::vector iteration take almost no time even
    with 10.000k elements.

    Best,
    -Niklas



  • On 21/05/2013 at 11:43, xxxxxxxx wrote:

    Originally posted by xxxxxxxx

    Oh I'm sorry, misread it. :)
    Well, usually when you use a list, you don't know how many elements it will have after storing
    elements is done. This is why I think not calling reserve() is appropriate in this test.

    That's why you don't use resize for the vector but you definetly use reserve if you are about to push largely. It has a huge performance impact on the following push operations. Even if you don't know the exact size a good guess will increase performance.

    Originally posted by xxxxxxxx

    I don't think there is a big difference in speed regarding the dereferencing. As you can see from
    the results above, the BaseArray as well as the stdvector iteration take almost no time even
    with 10.000k elements.

    Maybe it is the double-linked list structure of the list container that makes the difference. Would be well worth exploring (at least I'll do) to see what exactly is causing the slow down (and how the forward_list performance is in contrast).

    Edit: Don't know why but your quoted text is out of screen for me Anyway, thanks for the tests so far.



  • On 21/05/2013 at 12:15, xxxxxxxx wrote:

    Originally posted by xxxxxxxx

    I must say that I am impressed. :-)
    Didn't expect the AtomArray to be fairly fast! And the std library to be so slow.. And the
    GeDynamicArray is really slow compared to all of those! Must be some very rusty piece of
    list implementation?

    [...]

    The AtomArray is that fast because in R14 it internally uses the BaseArray. As you can see, there is some overhead involved as there 's some work needed to make in compatible to the old behaviour, but compared to the old implementation there are measurable benefits.

    On a side note: There are also several additional types available (since R14) :

    - BlockArray; this one has big benefits when doing a lot of inserts/deletes and dealing with complex objects (Classes) - which is esp. useful (and faster than anything a BaseArray or std::vector can deliver) if you can't resize the the array once to a max. possible size.

    - PointerArray; this one isn't moving the memory of the elements which is beneficial if you've to make sure the location of something you're referencing with a pointer doesn't change

    - BaseList; not an array, but it uses the same methods as arrays and can easiliy interchanged; note, that here the subscript operator will be massively slower than an iterator

    Best regards,

    Wilfried



  • On 21/05/2013 at 12:36, xxxxxxxx wrote:

    Thanks for the info. BlockArray seems indeed quite interesting for certain circumstances.


Log in to reply