Faster than STL

• Download source - 2.7 MB
• Clone: http://github.com/gigasopht/iplusplus - specify drive:\iplusplus as the destination.

Introduction

Programmers tend to be satisfied with a standard like STL until it is proven that there is something better. I++ provides the same classes: list, set, map, etc. except they are much, much faster. Once we have got some figures, we will discuss the reasons for the performance difference.

Background

I++ is a C++ class library that has been around for more than 20 years. Its documentation may be found at http://gigasopht.net.

Using the Code

We will look at a single, simple program that allocates 10 million items into various containers. i++ and STL containers will be compared for performance. Here is the code:

import std.core;
import iplusplus;
using namespace core;

int main()
{
    {
        std::list<int> sm;
        systime stl_build_start;
        for (int i = 0; i < 10000000; i++) sm.push_back(i);
        systime build_end;
        std::cout << "stl list build time is: " << 
                      stl_build_end - stl_build_start << "\n";
        systime stl_sort_start;
        sm.sort();
        systime stl_sort_end;
        std::cout << "stl list sort time is: " << 
                      stl_sort_end - stl_sort_start << "\n";

        std::forward_list<int> stlfl;
        systime stlfl_build_start;
        for (int i = 0; i < 10000000; i++) stlfl.push_front(i);
        systime stlfl_build_end;
        std::cout << "stl forward_list build time is: " << 
                      stlfl_build_end - stlfl_build_start << "\n";
        systime stlfl_sort_start;
        stlfl.sort();
        systime stlfl_build_sort_end;
        std::cout << "stl forward_list sort time is: " << 
                      stlfl_sort_end - stlfl_sort_start << "\n";

        list<int> fl;
        systime fl_build_start;
        for (int i = 0; i < 10000000; i++) fl << i;
        systime fl_build_end;
        std::cout << "core::list build time is: " << 
                      fl_build_end - fl_build_start << "\n";
        systime fl_sort_start;
        fl.sort();
        systime fl_sort_end;
        std::cout << "core::list sort time is: " << 
                      fl_sort_end - fl_sort_start << "\n";

        linked_list<int> s;
        systime ipp_build_start;
        for (int i = 0; i < 10000000; i++) s << i;
        systime ipp_build_end;
        std::cout << "core::linked_list build time is: " << 
                      ipp_build_end - ipp_build_start << "\n";
        systime ipp_sort_start;
        s.sort();
        systime ipp_sort_end;
        std::cout << "core::linked_list sort time is: " << 
                      ipp_sort_end - ipp_sort_start << "\n";

        std::set<int> ss;
        systime stl_ss_build_start;
        for (int i = 0; i < 10000000; i++) ss.insert(i);
        systime stl_ss_build_end;
        std::cout << "stl set build time is: " << 
                      stl_ss_build_end - stl_ss_build_start << "\n";
        systime stl_ssearch_start;
        for (int i = 0; i < 10000000; i++) ss.find(i);
        systime stl_ssearch_end;
        std::cout << "stl set search time is: " << 
                      stl_ssearch_end - stl_ssearch_start << "\n";

        set<int> sts;
        systime stl_sts_build_start;
        for (int i = 0; i < 10000000; i++) sts << i;
        systime stl_sts_build_end;
        std::cout << "I++ set build time is: " << 
                      stl_sts_build_end - stl_sts_build_start << "\n";
        systime sts_ssearch_start;
        for (int i = 0; i < 10000000; i++) sts.find(i);
        systime sts_ssearch_end;
        std::cout << "I++ set search time is: " << 
                      sts_ssearch_end - sts_ssearch_start << "\n";

        std::unordered_set<int> us;
        systime stl_us_build_start;
        for (int i = 0; i < 10000000; i++) us.insert(i);
        systime stl_us_build_end;
        std::cout << "stl unordered_set build time is: " << 
                      stl_us_build_end - stl_us_build_start << "\n";
        systime stl_ussearch_start;
        for (int i = 0; i < 10000000; i++) us.find(i);
        systime stl_ussearch_end;
        std::cout << "stl unordered_set search time is: " << 
                      stl_ussearch_end - stl_ussearch_start << "\n";

        std::map<int, int> stlm;
        systime stl_map_build_start;
        for (int i = 0; i < 10000000; i++) stlm[i] = i;
        systime stl_map_build_end;
        std::cout << "stl map build time is: " << 
                      stl_map_build_end - stl_map_build_start << "\n";
        systime map_search_start;
        for (int i = 0; i < 10000000; i++) { int j = stlm[i]; }
        systime map_search_end;
        std::cout << "stl map search time is: " << 
                      map_search_end - map_search_start << "\n";

        std::unordered_map<int, int> stlum;
        systime stl_umap_build_start;
        for (int i = 0; i < 10000000; i++) stlum[i] = i;
        systime stl_umap_build_end;
        std::cout << "stl unordered map build time is: " << 
                      stl_umap_build_end - stl_umap_build_start << "\n";
        systime umap_search_start;
        for (int i = 0; i < 10000000; i++) { int j = stlum[i]; }
        systime umap_search_end;
        std::cout << "stl unordered map search time is: " << 
                      umap_search_end - umap_search_start << "\n";

        map<int, int> dic;
        systime dic_build_start;
        for (int i = 0; i < 10000000; i++) dic[i] = i;
        systime dic_build_end;
        std::cout << "I++ map build time is: " << 
                      dic_build_end - dic_build_start << "\n";
        systime dic_search_start;
        for (int i = 0; i < 10000000; i++) { int j = dic[i]; }
        systime dic_search_end;
        std::cout << "I++ map search time is: " << 
                      dic_search_end - dic_search_start << "\n";

        multimap<int, int> mm;
        systime mm_build_start;
        for (int i = 0; i < 10000000; i++) mm.insert(i,i);
        systime mm_build_end;
        std::cout << "I++ multimap build time is: " << 
                      mm_build_end - mm_build_start << "\n";
        systime mm_search_start;
        for (int i = 0; i < 10000000; i++) { list<int> j = mm[i]; }
        systime mm_search_end;
        std::cout << "I++ multimap search time is: " << 
                      mm_search_end - mm_search_start << "\n";

        systime ipp_copy_start;
        oarchive oa;
        oa << s;
        void* data = oa.allocate(); // data points to the serialized list.
        iarchive ia(data);
        list<int> t;
        ia >> t;
        oa.free(data);              // you should free the data 
                                    // once you are done with it.
        systime ipp_copy_end;
        std::cout << "I++ serialization/deserialization time is: 
                     " << ipp_copy_end - ipp_copy_start << "\n";

        array<int> l;
        systime array_build_start;
        for (int i = 0; i < 10000000; i++) l.push(i);
        systime array_build_end;
        std::cout << "array build time is: " << array_build_end - 
                           array_build_start << "\n";

        std::vector<int> stlv;
        systime stl_vector_build_start;
        for (int i = 0; i < 10000000; i++) stlv.push_back(10000000 - i);
        systime stl_vector_build_end;
        std::cout << "stl vector build time is: " << 
                      stl_vector_build_end - stl_vector_build_start << "\n";
        systime stlv_sort_start;
        sort(stlv.begin(), stlv.end());
        systime stlv_sort_end;
        std::cout << "stl vector sort time is: " << 
                      stlv_sort_end - stlv_sort_start << "\n";

        int* ai = new int[10000000];
        for (int i = 0; i < 10000000; i++) ai[i] = 10000000 - i;
        systime qsort_start;
        quick_sort(ai, 1000000);
        systime qsort_end;
        std::cout << "Quick Sort time is: " << qsort_end - qsort_start << "\n";
        delete[] ai;

        database::set<int> st("Speed Test");
        st.clear();
        systime db_start;
        for (int i = 0; i < 1000; i++) st << i;
        systime db_end;
        systime db_search_start;
        for (int i = 0; i < 25000; i++) bool present = st.contains(i%1000);
        systime db_search_end;
        std::cout << "Database search for: 25000 entries is: " << 
                      db_search_end - db_search_start << "\n";

        std::cout << "heap allocations: " << get_heap_units() << "\n";
    }
    std::cout << "heap allocations: " << get_heap_units() << "\n";

    return 0;
}

Note that 10 million entries are added to list, forward_list, set, map, etc. I++'s time class is used to gather timings. Both STL containers and the equivalent i++ containers are used. The results of running this program are shown below:

stl list build time is: 0:0:0:0:474
stl list sort time is: 0:0:0:0:404
stl forward_list build time is: 0:0:0:0:370
stl forward_list sort time is: 0:0:0:0:461
core::list build time is: 0:0:0:0:164
core::list sort time is: 0:0:0:0:274
core::linked_list build time is: 0:0:0:0:181
core::linked_list sort time is: 0:0:0:0:327
stl set build time is: 0:0:0:1:315
stl set search time is: 0:0:0:0:594
I++ set build time is: 0:0:0:0:599
I++ set search time is: 0:0:0:0:510
stl unordered_set build time is: 0:0:0:3:23
stl unordered_set search time is: 0:0:0:0:584
stl map build time is: 0:0:0:1:435
stl map search time is: 0:0:0:0:547
stl unordered map build time is: 0:0:0:3:3
stl unordered map search time is: 0:0:0:0:600
I++ map build time is: 0:0:0:0:609
I++ map search time is: 0:0:0:0:507
I++ multimap build time is: 0:0:0:0:576
I++ multimap search time is: 0:0:0:2:561
I++ serialization/deserialization time is: 0:0:0:1:537
array build time is: 0:0:0:0:188
stl vector build time is: 0:0:0:0:40
stl vector sort time is: 0:0:0:0:135
Quick Sort time is: 0:0:0:0:10
Database search for: 25000 entries is: 0:0:0:1:655
heap allocations: 70000028
heap allocations: 0

Points of Interest

STL list took 474 milliseconds to build. STL forward_list took 370 milliseconds to build. I++ list (which is a singly-linked list - the equivalent of STL forward list) took 164 milliseconds to build. This is a staggering result, I++ lists build at more than twice the speed of STL. I++'s doubly linked list (linked_list) took 181 milliseconds to build.

Before going any further, an explanation of why I++ is so much faster than STL. To begin with, if you replace the global new and delete operators with i++'s binary heap, you speed up STL containers considerably. If the source code is updated in this manner, we get the following figures:

stl list build time is: 0:0:0:0:265
stl list sort time is: 0:0:0:0:262
stl forward_list build time is: 0:0:0:0:185
stl forward_list sort time is: 0:0:0:0:238
core::list build time is: 0:0:0:0:164
core::list sort time is: 0:0:0:0:241
core::linked_list build time is: 0:0:0:0:181
core::linked_list sort time is: 0:0:0:0:330
stl set build time is: 0:0:0:1:206
stl set search time is: 0:0:0:0:700
I++ set build time is: 0:0:0:0:644
I++ set search time is: 0:0:0:0:534
stl unordered_set build time is: 0:0:0:2:826
stl unordered_set search time is: 0:0:0:0:530
stl map build time is: 0:0:0:1:288
stl map search time is: 0:0:0:0:644
stl unordered map build time is: 0:0:0:2:830
stl unordered map search time is: 0:0:0:0:559
I++ map build time is: 0:0:0:0:590
I++ map search time is: 0:0:0:0:541
I++ multimap build time is: 0:0:0:0:630
I++ multimap search time is: 0:0:0:3:568
I++ serialization/deserialization time is: 0:0:0:1:605
array build time is: 0:0:0:0:186
stl vector build time is: 0:0:0:0:37
stl vector sort time is: 0:0:0:0:136
Quick Sort time is: 0:0:0:0:9
Database search for: 25000 entries is: 0:0:0:1:680
heap allocations: 130000046
heap allocations: 0 

Look at the amazing improvement in STL list. It has dropped from 474 all the way down to 265. So the C++ built in heap is most of the problem - it is very slow. This dramatic performance improvement was obtained merely by adding the following two lines to near the top of the program.

void* operator new(size_t s) {    return allocate_from_heap(s); }
void operator delete(void* p) { free_from_heap(p);} 

allocate_from_heap and free_from_heap are APIs of the i++ binary heap which, clearly, is a very fast heap. So most of STL's woes are more generally woes of C++. Almost any C++ program can be sped up in this way.

So now, we are down to STL forward list time of 185 versus i++ time of 164. STL list build time is now respectable.

Sets

Now let us analyze sets. To be fair to STL set, we will use the second lot of figures where the heap has been switched. STL set is a red/black tree whereas i++ set is an AVL Tree. It is often claimed that red/black sets are faster to build. Well, std::set took 1206 milliseconds to build and i++ set took 534 milliseconds. So much for red/black trees being faster to build - they are more than twice as slow.

Notes

The zip file iplusplus.zip contains a Visual Studio project. In fact, Visual Studio 2022 is required because it uses C++ modules. It runs on Windows 10 or later.

History

• 28^th January, 2023: Initial version