Update: STL vs Gnulib Performance

Following up on a previous post about the relative performance of STL vs gnulib, this post extends and completes the analysis to include the stl::vector and stl::deque containers. These containers provide a more direct comparison against the Gnulib array-list and carray-list implementations. The results are shown below. Please refer to the previous post on this subject for details on how the results were collected including source code.

DISCLAIMER: Please note that the intent of the post is not to suggest that gnulib should be used instead of STL in C++ programs, but rather to point out that although not part of the C language specification, gnulib offers C programmers a set of containers whose performance is comparable to the STL container performance available to C++ programmers.

Push back (insert at end) performance

Push back (insert at end) performance

Search Performance

Search (unsorted) Performance

Note that the vertical axis represents seconds and the lower the bar for each algorithm, the better.

Based on the above results, it can be seen that the performance of the stl::list is comparable to the gnulib linked_list for both insertions (at the end) and unsorted searching. Gnulib array_list is comparable in implementation to the stl::vector but proves to be almost 2x faster for insertions and ~1.5x slower for searching for this test. The stl::deque is also comparable to the gnulib array_list and proves to be slightly faster for insertions and just under 3x slower for searching.

As a final note, this analysis only performed comparisons based on two tests – push back and unsorted find. This is just an indication of performance and far from complete. The results may well be different if different tests were chosen.

Tags: ,

6 Responses to “Update: STL vs Gnulib Performance”

  1. Nice work.

    It would be interesting to see what the cause for the speed difference is, i.e. to compare the implementations.

  2. Mad says:

    Hi,

    I’m having a hard time getting around those graphs. What does the insert graph mean ? I can’t really imagine that inserting one element into a list ( not at the end or beginning but somewhere in the middle ) should be that much slower than doing the same op on a vector.

    Greets,
    Mad

    P.S.: Now that I read the previous post, I guess having named the “insert” graph “push_back” graph would quickly resolve those questions :)

  3. ADL says:

    The numbers are still a little suspicious. “insert” is ambiguous; std::vector is optimized for push_back (append operations), std::deque is optimized for constant time push_back and push_front. If another container is able to do better than the STL implementation you’re using, then it’s a bug in your STL implementation.

    The search chart is more troubling. How exactly are you searching? Both std::vector and std::deque have random access iterators, so you should be able to get log(n) search time – the best possible. std::list only has bi-directional iterators, so by definition it only offers O(n) search time. I suspect you have an unsorted container and are just doing std::find, which just does a linear walk. This is suboptimal, typically when searching a container is an important operation, you ensure the container is sorted and do binary searches.

    I suspect the differences in your chart are due to the methodology you used, but since you haven’t posted the source code I can’t be of any help here. But generally:

    * When inserting, you should be comparing std::vectors push_back to the equivalent in array_list
    * When inserting, you should be comparing std::deque push_front to the equivalent
    * When searching, you should be using the member function search/find etc on the stl containers if present, otherwise use std::binary_search (to test t/f) or std::lower/upper_bound (to actually get the element). And the container, obviously, should be presorted.

    It’d also be helpful if you posted source code when you make such claims.

  4. Stephen Doyle says:

    Hi ADL – See the reference to the previous post for details on methodology and source code. Insert is more correctly named push_back. Searching is using the stl::find algorithm for STL and its an unsorted search. A sorted search is another test.

  5. yoco says:

    What’s your compiler and compile option? Debug version or optimized release version? The result is dramatically different.

  6. Stephen Doyle says:

    yoco – compiler is gcc v4.0.1 and -O2 optimization