Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #79934

Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)"

Show all headers | View raw

28.05.2021 20:54 Bonita Montero kirjutas:
>>> Problem is that if binary tree is not reorganizing internaly to be cache
>>> friendly for every insert (balancing and making close nodes close to
>>> each other) traversing set is awfully slow.
> 
>> A vector isn't cache-friendly either when you do a binary search.
>> Random-access memory-accesses are always slow.
> 
> I just wrote a little test:
> 
> #include <iostream>
> #include <set>
> #include <vector>
> #include <algorithm>
> #include <random>
> #include <chrono>
> 
> using namespace std;
> using namespace chrono;
> 
> int main()
> {
>      using hrc_tp = time_point<high_resolution_clock>;
>      size_t const ROUNDS = 10'000'000;
>      set<int> si;
>      for( int i = 1000; --i; )
>          si.insert( i );
>      mt19937_64 mt( (default_random_engine())() );
>      uniform_int_distribution<int> uid( 0, 999 );
>      int const *volatile pvi;
>      hrc_tp start = high_resolution_clock::now();
>      for( size_t r = ROUNDS; r--; )
>          pvi = &*si.find( uid( mt ) );
>      double ns = (int64_t)duration_cast<nanoseconds>( 
> high_resolution_clock::now() - start ).count() / (double)ROUNDS;
>      cout << "set: " << ns << endl;
>      vector<int> vi( 1'000 );
>      for( size_t i = 1'000; i--; vi[i] = (int)i );
>      bool volatile found;
>      start = high_resolution_clock::now();
>      for( size_t r = ROUNDS; r--; )
>          found = binary_search( vi.begin(), vi.end(), uid( mt ) );
>      ns = (int64_t)duration_cast<nanoseconds>( 
> high_resolution_clock::now() - start ).count() / (double)ROUNDS;
>      cout << "vec: " << ns << endl;
> }
> 
> On my Ryzen Threadripper 3990X the times for set are 52.2 and forvec
> they are 48.3. I expected the difference to be somewhat larger, but
> as the set and map trees are usually red-black-trees there's some
> kind of binary-lookup inside the nodes (up to 4 descendants), so the
> memory access-patterns become not so random.

Are you kidding? Making big-O tests with N=1000? This is an insult for 
big-O!

Here are timings of your program with a bit more meaningful N. I also 
added unordered_set for curiosity, in the last column.

N             ROUNDS       Set time /ns/  Vec time /ns/  hash_set /ns/
1'000         10'000'000      52.3           50.0          4.88
100'000       100'000        208            115           14.6
10'000'000    1000          1322            340           53
100'000'000   100           2242            690          122
1'000'000'000 10            5320           1380          420

So, std::set is the clear loser here. std::unordered_set lookup is 
fastest, but OTOH its memory consumption, construction and destruction 
time are the worst (not shown in the table, but building and destroying 
the last hash set with 1G elements took ages and it ate up almost 64GB 
RAM!). A (sorted) vector takes *much* less memory, is *much* faster to 
construct and destruct, and binary lookup in it is better than std::set, 
regardless of size.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Juha Nieminen <nospam@thanks.invalid> - 2021-05-28 06:45 +0000
  Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-05-28 17:05 +0000
    Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-28 19:31 +0200
      Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-28 19:54 +0200
        Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" scott@slp53.sl.home (Scott Lurndal) - 2021-05-28 20:20 +0000
          Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-29 05:18 +0200
        Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-05-28 21:50 +0000
          Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-29 05:25 +0200
            Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-29 05:42 +0200
            Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-05-29 10:44 +0000
              Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-29 13:00 +0200
        Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Paavo Helde <myfirstname@osa.pri.ee> - 2021-05-29 02:24 +0300
      Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-05-28 21:31 +0000
      Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Juha Nieminen <nospam@thanks.invalid> - 2021-05-30 06:40 +0000

csiph-web