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

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

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

Show all headers | View raw

>> 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.

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