Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

AssocVector speed

Developers
2008-04-15
2013-04-08
  • Thomas Jarosch
    Thomas Jarosch
    2008-04-15

    Hello together,

    I've just discovered Loki and must say I'm really impressed by it's beauty.

    I was showing it to a coworker and was raving about the speed gain of AssocVector
    compared to a map. We benchmarked it against a std::map by filling an AssocVector<std::string,std::string>
    with 100.000 elements and then accessed an element at the beginning, in the middle
    and almost at the end of the corresponding container.

    Using gcc 4.1 on linux (kernel 2.6.24), the lookup using the std::map was always faster than AssocVector.
    We retried the same test with only 10.000 elemenets, the map was still faster.
    Enabling/disabling the compiler optimizer made no difference.

    Here are the results for 25.000 elements:
    [std::map] Init: 0.116, Lookups: 0.152
    [Loki::AssocVector] Init: 38.791, Lookups: 0.187

    Is there still a need for AssocVector using a modern STL?

    Cheers,
    Thomas

    --------------------------------------------
    #include <loki/AssocVector.h>

    #include <string>
    #include <map>
    #include <sstream>
    #include <iostream>
    #include <time.h>
    #include <sys/timeb.h>
    #include <sys/types.h>

    using namespace std;
    using namespace Loki;

    double prec_time(void)
    {
        struct timeb tb;
        double ret;

        ftime(&tb);

        ret=tb.time+(static_cast<float>(tb.millitm)/1000);

        return ret;
    }

    template<class container> class tester
    {
    private:
        void init()
        {
            ostringstream out;
            cerr << "Init";

            double before = prec_time();
            for (int i = 0; i < Count; i++)
            {
                out.str("");
                out << i;
                MapImpl[out.str()] = "1";

                if ((i % 100) == 0)
                    cerr << ".";
            }
            double after = prec_time();

            cerr << "DONE\n";
            cerr << "Init time: " << after-before << endl;
        }

        std::string format(int number)
        {
            ostringstream out;
            out << number;
            return out.str();
        }

        void lookup()
        {
            string s1, s2, s3, s4;
            s1 = format(Count/4);
            s2 = format(Count/3);
            s3 = format(Count/2);
            s4 = format(Count-1);

            double before = prec_time();
            for (int i = 0; i < Count; i++)
            {
                MapImpl["1"];
                MapImpl[s1];
                MapImpl[s2];
                MapImpl[s3];
                MapImpl[s4];
            }
            double after = prec_time();
            cout << "Lookup time: " << after-before << endl;
            cout << endl;
        }
        container MapImpl;
        int Count;

    public:
        tester(int count)
        { Count = count; }

        void run()
        {
            init();
            lookup();
        }
    };

    int main(void)
    {
        int count = 25000;
        tester<map<string,string> > test1(count);
        tester<AssocVector<string,string> > test2(count);

        test1.run();
        test2.run();

        return 0;
    }
    --------------------------------------------

     
    • hmm I always said that if you have something in STL that does something good, you can't make it better.
      But most of the big libraries (wxWidgets, Irrlicht) disagree for some reason.
      Actually, can someone explain what is the purpose of this class?

      broken blade (lazy to log in)

       
    • Malcolm
      Malcolm
      2008-07-12

      That's due to the differences in Big-Oh notation. Though it may seem as though you're inserting every string at the end, you're actually not. Strings sort lexicographically and the means that it goes like this for 1 to 20 say: 1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9
      As you can see 20 comes between 2 and 3 etc.
      This means you are hitting the O(n*n) case for insertion. That's why the init is so slow. If you were to try inserting numbers between 100000 and 350000 for example, which are all 6 characters long, then it should be as fast as a std::map.

      It's not just about speed either. This container is about memory usage, fragmentation, and cache coherency as well. A vector of items uses one contiguous block of memory - No fragmentation and no per-item overhead. std::map is a different story.
      If the objects in the map are small, e.g. ints, then this container can come in at under half the memory usage!

       
    • Malcolm
      Malcolm
      2008-07-12

      Actually while I'm here, I have a suggestion:
      At the moment the two-iterator form of insert runs in O(n*n) time. Worst case when the items between first and last are in reverse order. This is much poorer than can be achieved with this container.

      My suggestion would be to first insert all the new items between first and last at the end of the vector, then obtain an iterator to the first newly inserted item (called middle). Next use std::sort to sort from this middle iterator to end(), sorting only those items. Then finish up by using std::inplace_merge with begin(), middle, end().
      That's O(n*log(n)) for the sort and O(n + m) for the merge, making it O(n*log(n)) overall, where m is the number of existing items and n is the number of items being inserted.

      I'm considering joining the dev team and submitting this change myself.

       
    • Alber Kami
      Alber Kami
      2008-07-24

      Hello,

      For my knowledge AssocVector is not about insertion!, on the contrary, it willing to give up some speed at insertion but to gain back the speed at fetching!
      It does a binary search in an array its suppose to be for case where there is one time insertion and a lot of fetching - like statics maps (e.g. name --> function) all insertion is done on one time initialization.

      Shaul