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

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

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

Show all headers | View raw

And this is an extension to unordered_set:

#include <iostream>
#include <set>
#include <unordered_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 N      = 10'000'000,
	             ROUNDS = 10'000'000;
	set<int> si;
	for( int i = N; 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;
	unordered_set<int> usi;
	usi.max_load_factor( 2.0f );
	usi.reserve( N );
	for( int i = N; i--; )
		usi.insert( i );
	bool volatile found;
	start = high_resolution_clock::now();
	for( size_t r = ROUNDS; r--; )
		pvi = &*usi.find( uid( mt ) );
	ns = (int64_t)duration_cast<nanoseconds>( high_resolution_clock::now() 
- start ).count() / (double)ROUNDS;
	cout << "uset: " << ns << endl;
	vector<int> vi( N );
	for( size_t i = N; i--; vi[i] = (int)i );
	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;
}

So with unordered_set the lookup is 15.1ns. I think that's
also while  the lookups get OoO-parallelized because the
bucket-chains aren't so deep.

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