Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site













SourceForge.net Logo

U++ Core vs standard C++ library

 

Ultimate++ can be easily accused of reinventing the wheel. While the main reason of not using standard C++ library is not quite performance related, the interface definition of U++ containers allows very effective implementation. Matched with U++ heap allocator which overloads global new and delete operators, U++ is able to boost the speed of applications a bit.

 

In the benchmark example, we are comparing "out-of-box" performance of standard library implementations coming with widely used compilers with performance of U++ Core with the same compilers in simple example. The purpose of code is to scan through file, find all identifiers (by C lexical definition) and print them sorted by the name, with list of lines where they occur.

 

Implementation use std::map, std::tr1::unordered_map (or equivalent stdext::hash_map with microsoft compiler) with std::string and standard library streams and U++ container VectorMap with UPP::String and U++ streams, tested with both U++ and standard library heap allocator.

 

ratio U++/std column shows how many times is U++ Core VectorMap container based solution faster then the standard solution with the library that comes with the compiler (best of map/hash_map times is considered).

 

ratio U++/STL column shows how many times is U++ Core based solution faster then the STL solution when using U++ allocator, because STL containers also benefit from it (best of map/hash_map times is considered).

 

Perhaps if the reinvented wheel spins about 4 times faster, reinventing is not that bad idea...

 

 

Results

 

Test with 3.93 KB .cpp file:

 

allocator

standard

U++

ratio

U++/std

ratio

U++/STL

code

map

unordered_map

map

unordered_map

U++

GCC32

5.3 s

4.9 s

4.4 s

3.9 s

1.1 s

4.5

3.5

GCC64

4.2 s

3.7 s

3.2 s

3.0 s

0.8 s

4.6

3.8

 

 

Test with 58 KB .cpp file:

 

allocator

standard

U++

ratio

U++/std

ratio

U++/STL

code

map

unordered_map

map

unordered_map

U++

GCC32

70 s

56 s

58 s

45 s

11 s

5.1

4.1

GCC64

55 s

43 s

45 s

34 s

8.8 s

4.9

3.9

 

 

Platforms

 

GCC64

Ubuntu 7.10 AMD64

(GCC) 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)

compiler options: -O3

GCC32

Ubuntu 7.10 i386

(GCC) 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)

compiler options: -O3

 

Hardware: Core 2 Duo, 2.7 Ghz, 2GB RAM

 

 

Benchmark code

 

#define  NDEBUG

#define  _SECURE_SCL 0

 

#include <Core/Core.h>

 

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <time.h>

#include <vector>

#include <algorithm>

#include <map>

#include <deque>

#include <string>

 

#define TEST_HASHMAP

 

#ifdef TEST_HASHMAP

 

#ifdef COMPILER_GCC

#include <tr1/unordered_map>

#else

#include <hash_map>

#endif

 

#endif

 

using namespace std;

using namespace Upp;

 

#define NO_OUTPUT // for benchmark purposes, output is omitted

 

void BenchNTL(const char *file) {

    FileIn in(file);

    if (!in) {

        std::cout << "Cannot open input file.\n";

        return;

    }

 

    VectorMap<String, Vector<int> > map;

    int line = 1;

 

    for(;;) {

        int c = in.Get();

        if(c < 0) break;

        if(isalpha(c) || c == '_') {

            String id;

            id.Cat(c);

            c = in.Get();

            while(c >= 0 && (isalnum(c) || c == '_')) {

                id.Cat(c);

                c = in.Get();

            }

            map.GetAdd(id).Add(line);

        }

        else

        if(isdigit(c))

            do c = in.Get();

            while(c >= 0 && (isalnum(c) || c == '.'));

        if(c == '\n')

            ++line;

    }

 

    Vector<int> order = GetSortOrder(map.GetKeys());

#ifndef NO_OUTPUT

    for(int i = 0; i < order.GetCount(); i++) {

        std::cout << ~map.GetKey(order[i]) << ": ";

        const Vector<int>& l = map[order[i]];

        for(int i = 0; i < l.GetCount(); i++) {

            if(i) std::cout << ", ";

            std::cout << l[i];

        }

        std::cout << '\n';

    }

#endif

}

 

template <class Container>

void BenchSTL(Container& imap, const char *file) {

    std::ifstream in(file);

    if (!in) {

        std::cout << "Cannot open input file.\n";

        return;

    }

 

    int line = 1;

 

    for(;;) {

        int c = in.get();

        if(c == EOF) break;

        if(isalpha(c) || c == '_') {

            string id;

            id += c;

            c = in.get();

            while(c != EOF && (isalnum(c) || c == '_')) {

                id += c;

                c = in.get();

            }

            imap[id].push_back(line);

        }

        else

        if(isdigit(c))

            do c = in.get();

            while(c != EOF && (isalnum(c) || c == '.'));

        if(c == '\n')

            ++line;

    }

}

 

void BenchMap(const char *file)

{

    map< string, vector<int> > imap;

    BenchSTL(imap, file);

#ifndef NO_OUTPUT

    map< std::string, vector<int> >::const_iterator e = imap.end();

    for(map< std::string, vector<int> >::const_iterator i = imap.begin(); i != e; i++) {

        std::cout << i->first << ": ";

        vector<int>::const_iterator e = i->second.end();

        vector<int>::const_iterator b = i->second.begin();

        for(vector<int>::const_iterator j = b; j != e; j++) {

            if(j != b) std::cout << ", ";

            std::cout << *j;

        }

        std::cout << '\n';

    }

#endif

}

 

#ifdef TEST_HASHMAP

 

#ifdef COMPILER_GCC

typedef std::tr1::unordered_map< string, vector<int> > HashMap;

#else

typedef stdext::hash_map< string, vector<int> > HashMap;

#endif

 

inline bool h_less(const HashMap::value_type *a, const HashMap::value_type *b)

{

    return a->first < b->first;

}

 

void BenchHashMap(const char *file)

{

    HashMap imap;

    BenchSTL(imap, file);

    vector< const HashMap::value_type * > order;

    for(HashMap::const_iterator i = imap.begin(); i != imap.end(); i++)

        order.push_back(&*i);

    sort(order.begin(), order.end(), h_less);

 

#ifndef NO_OUTPUT

    vector< const HashMap::value_type * >::const_iterator e = order.end();

    for(vector< const HashMap::value_type * >::const_iterator i = order.begin(); i != e; i++) {

        std::cout << (*i)->first << ": ";

        vector<int>::const_iterator e = (*i)->second.end();

        vector<int>::const_iterator b = (*i)->second.begin();

        for(vector<int>::const_iterator j = b; j != e; j++) {

            if(j != b) std::cout << ", ";

            std::cout << *j;

        }

        std::cout << '\n';

    }

#endif

}

 

#endif

 

#define N 10000

 

CONSOLE_APP_MAIN

{

    String fn;

    int argc = CommandLine().GetCount();

    const Vector<String>& argv = CommandLine();

    if(argc < 1)

        fn = GetDataFile("main.cpp");

    else

        fn = argv[0];

 

    BenchNTL(fn); // first run to cache the file

 

#ifdef TEST_HASHMAP

    {

        BenchHashMap(fn);

        TimeStop tm;

        for(int n = 0; n < N; n++)

            BenchHashMap(fn);

        cout << "STL hash_map time: " << tm.Elapsed() << " ms \n";

    }

#endif

 

    {

        BenchMap(fn);

        TimeStop tm;

        for(int n = 0; n < N; n++)

            BenchMap(fn);

        cout << "STL map time: " << tm.Elapsed() << " ms \n";

    }

 

    {

        BenchNTL(fn);

        TimeStop tm;

        for(int n = 0; n < N; n++)

            BenchNTL(fn);

        cout << "NTL time: " << tm.Elapsed() << " ms\n";

    }

}

 

 

Last edit by dolik on 05/12/2010. Do you want to contribute?. T++