Message6493

Author malte
Recipients jendrik, malte
Date 2017-09-01.15:52:24
Content
> The new test code should already be pushed.

Thanks! With larger hash sets (10M entries), I get a much larger effect, and it
is again larger if after insertions we do 10 rounds of lookups for every key.
For the read-then-lookup test, the old hash table is more than 10 times faster
on my machine:

Running nothing 1 times: 1e-06s

Running insert sequential int with BoostHash 1 times: 0.885316s
Running insert sequential int with BurtleFeed 1 times: 5.48213s

Running insert scrambled int with BoostHash 1 times: 6.22216s
Running insert scrambled int with BurtleFeed 1 times: 6.28391s

Running insert, then read sequential int with BoostHash 1 times: 3.14857s
Running insert, then read sequential int with BurtleFeed 1 times: 34.718s

Running insert, then read scrambled int with BoostHash 1 times: 20.511s
Running insert, then read scrambled int with BurtleFeed 1 times: 25.3854s

Running nothing 1 times: 0s

Running insert sequential int with BoostHash 1 times: 1.85816s
Running insert sequential int with BurtleFeed 1 times: 5.49561s

Running insert scrambled int with BoostHash 1 times: 6.29328s
Running insert scrambled int with BurtleFeed 1 times: 6.40746s

Running insert, then read sequential int with BoostHash 1 times: 3.15231s
Running insert, then read sequential int with BurtleFeed 1 times: 35.194s

Running insert, then read scrambled int with BoostHash 1 times: 20.461s
Running insert, then read scrambled int with BurtleFeed 1 times: 25.3585s


For reference, here is the experiment code I used (no changes outside main):

int main(int, char **) {
    const int REPETITIONS = 2;
    const int NUM_CALLS = 1;
    const int NUM_INSERTIONS = 10000000;
    const int NUM_READ_PASSES = 10;

    for (int i = 0; i < REPETITIONS; ++i) {
        benchmark("nothing", NUM_CALLS, [] () {});
        cout << endl;

        benchmark("insert sequential int with BoostHash", NUM_CALLS,
                  [&]() {
            unordered_set<int> s;
            for (int i = 0; i < NUM_INSERTIONS; ++i) {
                s.insert(i);
            }
        });
        benchmark("insert sequential int with BurtleFeed", NUM_CALLS,
                  [&]() {
            utils::HashSet<int> s;
            for (int i = 0; i < NUM_INSERTIONS; ++i) {
                s.insert(i);
            }
        });
        cout << endl;

        benchmark("insert scrambled int with BoostHash", NUM_CALLS,
                  [&]() {
            unordered_set<int> s;
            for (int i = 0; i < NUM_INSERTIONS; ++i) {
                s.insert(scramble(i));
            }
        });
        benchmark("insert scrambled int with BurtleFeed", NUM_CALLS,
                  [&]() {
            utils::HashSet<int> s;
            for (int i = 0; i < NUM_INSERTIONS; ++i) {
                s.insert(scramble(i));
            }
        });
        cout << endl;

            benchmark("insert, then read sequential int with BoostHash", NUM_CALLS,
                  [&]() {
            unordered_set<int> s;
            for (int i = 0; i < NUM_INSERTIONS; ++i) {
                s.insert(i);
            }
            for (int j = 0; j < NUM_READ_PASSES; ++j) {
                for (int i = 0; i < NUM_INSERTIONS; ++i) {
                    s.count(i);
                }
            }
        });
        benchmark("insert, then read sequential int with BurtleFeed", NUM_CALLS,
                  [&]() {
            utils::HashSet<int> s;
            for (int i = 0; i < NUM_INSERTIONS; ++i) {
                s.insert(i);
            }
            for (int j = 0; j < NUM_READ_PASSES; ++j) {
                for (int i = 0; i < NUM_INSERTIONS; ++i) {
                    s.count(i);
                }
            }
        });
        cout << endl;

        benchmark("insert, then read scrambled int with BoostHash", NUM_CALLS,
                  [&]() {
            unordered_set<int> s;
            for (int i = 0; i < NUM_INSERTIONS; ++i) {
                s.insert(scramble(i));
            }
            for (int j = 0; j < NUM_READ_PASSES; ++j) {
                for (int i = 0; i < NUM_INSERTIONS; ++i) {
                    s.count(i);
                }
            }
        });
        benchmark("insert, then read scrambled int with BurtleFeed", NUM_CALLS,
                  [&]() {
            utils::HashSet<int> s;
            for (int i = 0; i < NUM_INSERTIONS; ++i) {
                s.insert(scramble(i));
            }
            for (int j = 0; j < NUM_READ_PASSES; ++j) {
                for (int i = 0; i < NUM_INSERTIONS; ++i) {
                    s.count(i);
                }
            }
        });
        cout << endl;
    }

    return 0;
}
History
Date User Action Args
2017-09-01 15:52:24maltesetmessageid: <1504273944.81.0.709490106987.issue731@unibas.ch>
2017-09-01 15:52:24maltesetrecipients: + malte, jendrik
2017-09-01 15:52:24maltelinkissue731 messages
2017-09-01 15:52:24maltecreate