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

Groups > comp.lang.c++ > #91216 > unrolled thread

"Inside STL: The map, set, multimap, and multiset" by Raymond Chen

Back to article view | Back to comp.lang.c++

Contents

  "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Lynn McGuire <lynnmcguire5@gmail.com> - 2023-08-08 16:23 -0500
    Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen wij <wyniijj5@gmail.com> - 2023-08-08 17:53 -0700
      Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Paavo Helde <eesnimi@osa.pri.ee> - 2023-08-09 09:26 +0300
        Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Öö Tiib <ootiib@hot.ee> - 2023-08-09 03:08 -0700
          Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-09 13:22 +0200
          Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-09 13:52 +0200
            Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Öö Tiib <ootiib@hot.ee> - 2023-08-09 05:10 -0700
              Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-09 14:52 +0200
            Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen wij <wyniijj5@gmail.com> - 2023-08-09 07:32 -0700
              Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-09 16:36 +0200
        Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen wij <wyniijj5@gmail.com> - 2023-08-09 07:20 -0700
          Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Paavo Helde <eesnimi@osa.pri.ee> - 2023-08-09 20:29 +0300
            Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Öö Tiib <ootiib@hot.ee> - 2023-08-09 21:09 -0700
    Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-15 08:37 -0700

#91216 — "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

"Inside STL: The map, set, multimap, and multiset" by Raymond Chen
    https://devblogs.microsoft.com/oldnewthing/20230807-00/

"The complexity requirements of the C+ standard library map, set, 
multimap, and multiset basically narrow the possible implementation 
options to AVL trees and red-black trees."

"In practice, everybody seems to choose a red-black tree, with an 
explicit sentinel node. The sentinel node also doubles as a header."

Lynn

[toc] | [next] | [standalone]

#91217

On Wednesday, August 9, 2023 at 5:23:23 AM UTC+8, Lynn McGuire wrote:
> "Inside STL: The map, set, multimap, and multiset" by Raymond Chen 
> https://devblogs.microsoft.com/oldnewthing/20230807-00/ 
> 
> "The complexity requirements of the C+ standard library map, set, 
> multimap, and multiset basically narrow the possible implementation 
> options to AVL trees and red-black trees." 
> 
> "In practice, everybody seems to choose a red-black tree, with an 
> explicit sentinel node. The sentinel node also doubles as a header." 
> 
> Lynn

/*
  Compare speed of Wy::Subset and std::set
*/
#include <Wy.stdlib.h>
#include <Wy.stdio.h>
#include <Wy.time.h>
#include <CSCall/Subset.h>
#include <set>

using namespace Wy;

void test() {
 typedef int ElemType;
 const size_t Cnt=1000000;
 Rand48 rnd;
 Timespec tm0,tm1;


 Subset<ElemType> aa;
 tm0=now(CLOCK_THREAD_CPUTIME_ID);
 for(size_t i=0; i<Cnt; ++i) {
   aa.insert(rnd.i32()%(Cnt/2));
  }
 cout << "Subset: " << (now(CLOCK_THREAD_CPUTIME_ID)-tm0) << WY_ENDL;

 std::set<ElemType> bb;
 tm0=now(CLOCK_THREAD_CPUTIME_ID);
 for(size_t i=0; i<Cnt; ++i) {
   bb.insert(rnd.i32()%(Cnt/2));
  }
 cout << "std::set: " << (now(CLOCK_THREAD_CPUTIME_ID)-tm0) << WY_ENDL;
};

int main(int argc, const char* argv[])
try {
 test();
 return 0;
}
catch(const Errno& e) {
 cerr << wrd(e) << WY_ENDL;
 return -1;
}
catch(...) {
 cerr << "main() caught(...)" WY_ENDL;
 throw;
};

-----------
[]$ ./sp_set                  
Subset: 0.562357101
std::set: 0.826916740

[]$ make sp_set CFLAGS=-O2
[]$ ./sp_set 
Subset: 0.388614721
std::set: 0.413042782

[toc] | [prev] | [next] | [standalone]

#91220

09.08.2023 03:53 wij kirjutas:
> /*
>    Compare speed of Wy::Subset and std::set
> */
> 
> []$ make sp_set CFLAGS=-O2
> []$ ./sp_set
> Subset: 0.388614721
> std::set: 0.413042782

I guess this shows that it is not really worth of effort to reinvent 
one's own std::set.

If the point is that one can fine-tune something to beat a single 
performance test, then I can do better. My my_set below beats std::set 
100x for this insertion test ;-)

my_set: 0.006683
std::set: 0.597735

#include <set>
#include <chrono>
#include <random>
#include <iostream>
#include <vector>

void test() {
	typedef int ElemType;
	const size_t Cnt = 1000000;

	std::random_device rd;
	std::mt19937 gen(rd());
	std::uniform_int_distribution<> distr(0, Cnt / 2);

	std::vector<unsigned char> my_set(Cnt / 2);
	auto tm0 = std::chrono::high_resolution_clock::now();
	for (size_t i = 0; i < Cnt; ++i) {
		my_set[distr(gen)] = 1;
	}
	auto tm1 = std::chrono::high_resolution_clock::now();
	double duration = 
std::chrono::duration_cast<std::chrono::duration<double>>(tm1 - 
tm0).count();
	std::cout << "my_set: " << duration << "\n";

	std::set<ElemType> bb;
	tm0 = std::chrono::high_resolution_clock::now();
	for (size_t i = 0; i < Cnt; ++i) {
		bb.insert(distr(gen));
	}
	tm1 = std::chrono::high_resolution_clock::now();
	duration = 
std::chrono::duration_cast<std::chrono::duration<double>>(tm1 - 
tm0).count();
	std::cout << "std::set: " << duration << "\n";
};

int main(int argc, const char* argv[]) {
	try {
		test();
	} catch (const std::exception& e) {
		std::cerr << "Exception: " << e.what() << "\n";
		return EXIT_FAILURE;
	} catch (...) {
		std::cerr << "Exception\n";
		return EXIT_FAILURE;
	}
}

[toc] | [prev] | [next] | [standalone]

#91222

On Wednesday, 9 August 2023 at 09:26:32 UTC+3, Paavo Helde wrote:
> 09.08.2023 03:53 wij kirjutas: 
> > /* 
> > Compare speed of Wy::Subset and std::set 
> > */ 
> >
> > []$ make sp_set CFLAGS=-O2 
> > []$ ./sp_set 
> > Subset: 0.388614721 
> > std::set: 0.413042782
> I guess this shows that it is not really worth of effort to reinvent 
> one's own std::set. 
> 
> If the point is that one can fine-tune something to beat a single 
> performance test, then I can do better. My my_set below beats std::set 
> 100x for this insertion test ;-) 
> 
> my_set: 0.006683 
> std::set: 0.597735 
> 
Great example, intersting how std::bitset<500000> and 
std::vector<bool>(500000) perform compared to that "my_set".

[toc] | [prev] | [next] | [standalone]

#91223

Am 09.08.2023 um 12:08 schrieb Öö Tiib:

> Great example, intersting how std::bitset<500000> and
> std::vector<bool>(500000) perform compared to that "my_set".

I think both are as fast and yours is at best as fast.

[toc] | [prev] | [next] | [standalone]

#91225

Am 09.08.2023 um 12:08 schrieb Öö Tiib:

> Great example, intersting how std::bitset<500000> and
> std::vector<bool>(500000) perform compared to that "my_set".

With this code bitset and vector<bool> have the same performance
under Windows (MSVC) and Linux (g++ / clang++).

#include <iostream>
#include <bitset>
#include <vector>
#include <random>
#include <chrono>
#include <atomic>

using namespace std;
using namespace chrono;

atomic<size_t> aSum;

int main()
{
	constexpr size_t BITS = 0x10000;
	bitset<BITS> bs;
	vector<bool> vb( BITS );
	mt19937_64 mt;
	uniform_int_distribution<size_t> iBit( 0, BITS - 1 );
	auto fill = []( auto &container )
	{
		bool bit = false;
		for( size_t i = 0; i != BITS; ++i )
			container[i] = bit,
			bit = !bit;
	};
	fill( bs );
	fill( vb );
	constexpr size_t ROUNDS = 1'000;
	auto linearBench = []( char const *what, auto const &container )
	{
		auto start = high_resolution_clock::now();
		size_t sum = 0;
		for( size_t r = ROUNDS; r--; )
			for( size_t i = 0; i != BITS; ++i )
				sum += container[i];
		double ns = duration_cast<nanoseconds>( high_resolution_clock::now() - 
start ).count() / ((double)BITS * ROUNDS);
		::aSum = sum;
		cout << what << ns << endl;
	};
	linearBench( "linear bitset: ", bs );
	linearBench( "linear vector: ", vb );
	auto gappedBench = []( char const *what, auto const &container )
	{
		auto start = high_resolution_clock::now();
		size_t sum = 0;
		for( size_t r = ROUNDS; r--; )
			for( size_t g = 0, i = 0; g != BITS; ++g, i += 7, i = i < BITS ? i : 0 )
				sum += container[i];
		double ns = duration_cast<nanoseconds>( high_resolution_clock::now() - 
start ).count() / ((double)BITS * ROUNDS);
		::aSum = sum;
		cout << what << ns << endl;
	};
	gappedBench( "gapped bitset: ", bs );
	gappedBench( "gapped vector: ", vb );
}

[toc] | [prev] | [next] | [standalone]

#91226

On Wednesday, 9 August 2023 at 14:53:14 UTC+3, Bonita Montero wrote:
> Am 09.08.2023 um 12:08 schrieb Öö Tiib:
> > Great example, intersting how std::bitset<500000> and 
> > std::vector<bool>(500000) perform compared to that "my_set".
> With this code bitset and vector<bool> have the same performance 
> under Windows (MSVC) and Linux (g++ / clang++). 
> 
> uniform_int_distribution<size_t> iBit( 0, BITS - 1 ); 

Unused variable "iBit", must be your test tests some other test case
as "distr" of Paavo was used in his tests.

[toc] | [prev] | [next] | [standalone]

#91227

Am 09.08.2023 um 14:10 schrieb Öö Tiib:
> On Wednesday, 9 August 2023 at 14:53:14 UTC+3, Bonita Montero wrote:
>> Am 09.08.2023 um 12:08 schrieb Öö Tiib:
>>> Great example, intersting how std::bitset<500000> and
>>> std::vector<bool>(500000) perform compared to that "my_set".
>> With this code bitset and vector<bool> have the same performance
>> under Windows (MSVC) and Linux (g++ / clang++).
>>
>> uniform_int_distribution<size_t> iBit( 0, BITS - 1 );
> 
> Unused variable "iBit", must be your test tests some other test case
> as "distr" of Paavo was used in his tests.

I made it even shorter:

#include <iostream>
#include <bitset>
#include <vector>
#include <random>
#include <chrono>
#include <atomic>

using namespace std;
using namespace chrono;

atomic<size_t> aSum;

int main()
{
	constexpr size_t BITS = 0x10000;
	bitset<BITS> bs;
	vector<bool> vb( BITS );
	mt19937_64 mt;
	auto fill = []( auto &container )
	{
		bool bit = false;
		for( size_t i = 0; i != BITS; ++i )
			container[i] = bit,
			bit = !bit;
	};
	fill( bs );
	fill( vb );
	constexpr size_t ROUNDS = 10'000;
	auto bench = []( char const *what, auto const &container, auto next )
	{
		auto start = high_resolution_clock::now();
		size_t sum = 0;
		for( size_t r = ROUNDS; r--; )
			for( size_t g = 0, i = 0; g != BITS; ++g, i = next( i ) )
				sum += container[i];
		double ns = duration_cast<nanoseconds>( high_resolution_clock::now() - 
start ).count() / ((double)BITS * ROUNDS);
		::aSum = sum;
		cout << what << ns << endl;
	};
	auto linear = []( size_t i ) { return i + 1; };
	bench( "linear bitset: ", bs, linear );
	bench( "linear vector: ", vb, linear );
	auto gapped = []( size_t i ) { return i + 7 < BITS ? i + 7 : 0; };
	bench( "gapped bitset: ", bs, gapped );
	bench( "gapped vector: ", vb, gapped );
}

[toc] | [prev] | [next] | [standalone]

#91231

On Wednesday, August 9, 2023 at 7:53:14 PM UTC+8, Bonita Montero wrote:
> Am 09.08.2023 um 12:08 schrieb Öö Tiib:
> > Great example, intersting how std::bitset<500000> and 
> > std::vector<bool>(500000) perform compared to that "my_set".
> With this code bitset and vector<bool> have the same performance 
> under Windows (MSVC) and Linux (g++ / clang++). 
> 
> #include <iostream> 
> #include <bitset> 
> #include <vector> 
> #include <random> 
> #include <chrono> 
> #include <atomic> 
> 
> using namespace std; 
> using namespace chrono; 
> 
> atomic<size_t> aSum; 
> 
> int main() 
> { 
> constexpr size_t BITS = 0x10000; 
> bitset<BITS> bs; 
> vector<bool> vb( BITS ); 
> mt19937_64 mt; 
> uniform_int_distribution<size_t> iBit( 0, BITS - 1 ); 
> auto fill = []( auto &container ) 
> { 
> bool bit = false; 
> for( size_t i = 0; i != BITS; ++i ) 
> container[i] = bit, 
> bit = !bit; 
> }; 
> fill( bs ); 
> fill( vb ); 
> constexpr size_t ROUNDS = 1'000; 
> auto linearBench = []( char const *what, auto const &container ) 
> { 
> auto start = high_resolution_clock::now(); 
> size_t sum = 0; 
> for( size_t r = ROUNDS; r--; ) 
> for( size_t i = 0; i != BITS; ++i ) 
> sum += container[i]; 
> double ns = duration_cast<nanoseconds>( high_resolution_clock::now() - 
> start ).count() / ((double)BITS * ROUNDS); 
> ::aSum = sum; 
> cout << what << ns << endl; 
> }; 
> linearBench( "linear bitset: ", bs ); 
> linearBench( "linear vector: ", vb ); 
> auto gappedBench = []( char const *what, auto const &container ) 
> { 
> auto start = high_resolution_clock::now(); 
> size_t sum = 0; 
> for( size_t r = ROUNDS; r--; ) 
> for( size_t g = 0, i = 0; g != BITS; ++g, i += 7, i = i < BITS ? i : 0 ) 
> sum += container[i]; 
> double ns = duration_cast<nanoseconds>( high_resolution_clock::now() - 
> start ).count() / ((double)BITS * ROUNDS); 
> ::aSum = sum; 
> cout << what << ns << endl; 
> }; 
> gappedBench( "gapped bitset: ", bs ); 
> gappedBench( "gapped vector: ", vb ); 
> }

I can't read these new C++ syntax. In case of 'vector<bool>', I would use
Wy::VLInt<unsigned int> (Very Large Integer), two access members bit(size_t)
and set_bit(size_t,bool). As you can see, every thing is 'concrete' and
direct. But such classes are not the purpose of libwy.

[toc] | [prev] | [next] | [standalone]

#91232

Am 09.08.2023 um 16:32 schrieb wij:
> On Wednesday, August 9, 2023 at 7:53:14 PM UTC+8, Bonita Montero wrote:
>> Am 09.08.2023 um 12:08 schrieb Öö Tiib:
>>> Great example, intersting how std::bitset<500000> and
>>> std::vector<bool>(500000) perform compared to that "my_set".
>> With this code bitset and vector<bool> have the same performance
>> under Windows (MSVC) and Linux (g++ / clang++).
>>
>> #include <iostream>
>> #include <bitset>
>> #include <vector>
>> #include <random>
>> #include <chrono>
>> #include <atomic>
>>
>> using namespace std;
>> using namespace chrono;
>>
>> atomic<size_t> aSum;
>>
>> int main()
>> {
>> constexpr size_t BITS = 0x10000;
>> bitset<BITS> bs;
>> vector<bool> vb( BITS );
>> mt19937_64 mt;
>> uniform_int_distribution<size_t> iBit( 0, BITS - 1 );
>> auto fill = []( auto &container )
>> {
>> bool bit = false;
>> for( size_t i = 0; i != BITS; ++i )
>> container[i] = bit,
>> bit = !bit;
>> };
>> fill( bs );
>> fill( vb );
>> constexpr size_t ROUNDS = 1'000;
>> auto linearBench = []( char const *what, auto const &container )
>> {
>> auto start = high_resolution_clock::now();
>> size_t sum = 0;
>> for( size_t r = ROUNDS; r--; )
>> for( size_t i = 0; i != BITS; ++i )
>> sum += container[i];
>> double ns = duration_cast<nanoseconds>( high_resolution_clock::now() -
>> start ).count() / ((double)BITS * ROUNDS);
>> ::aSum = sum;
>> cout << what << ns << endl;
>> };
>> linearBench( "linear bitset: ", bs );
>> linearBench( "linear vector: ", vb );
>> auto gappedBench = []( char const *what, auto const &container )
>> {
>> auto start = high_resolution_clock::now();
>> size_t sum = 0;
>> for( size_t r = ROUNDS; r--; )
>> for( size_t g = 0, i = 0; g != BITS; ++g, i += 7, i = i < BITS ? i : 0 )
>> sum += container[i];
>> double ns = duration_cast<nanoseconds>( high_resolution_clock::now() -
>> start ).count() / ((double)BITS * ROUNDS);
>> ::aSum = sum;
>> cout << what << ns << endl;
>> };
>> gappedBench( "gapped bitset: ", bs );
>> gappedBench( "gapped vector: ", vb );
>> }
> 
> I can't read these new C++ syntax. In case of 'vector<bool>', I would use
> Wy::VLInt<unsigned int> (Very Large Integer), two access members bit(size_t)
> and set_bit(size_t,bool). As you can see, every thing is 'concrete' and
> direct. But such classes are not the purpose of libwy.

For me a vector<bool> or a bitset<N> is much more concrete.

[toc] | [prev] | [next] | [standalone]

#91230

On Wednesday, August 9, 2023 at 2:26:32 PM UTC+8, Paavo Helde wrote:
> 09.08.2023 03:53 wij kirjutas: 
> > /* 
> > Compare speed of Wy::Subset and std::set 
> > */ 
> >
> > []$ make sp_set CFLAGS=-O2 
> > []$ ./sp_set 
> > Subset: 0.388614721 
> > std::set: 0.413042782
> I guess this shows that it is not really worth of effort to reinvent 
> one's own std::set. 

About the 'reinventing' things, I think C++ programmer should be able to
reinvent things. Otherwise why learning C++ (lots in stdc++ lib are about
implement things)? Isn't Python or others better?

One of the feature of Wy::Subset is that Subset has a member objimag(), allowing
the instance be saved to hard disk and read back (fast). I normally need Subset
for analysis of large data (10 Gbytes), many of them, e.g. generating 10
instances and read back as needed, this is because of the limits of RAM.

> If the point is that one can fine-tune something to beat a single 
> performance test, then I can do better. My my_set below beats std::set 
> 100x for this insertion test ;-) 
> 
> my_set: 0.006683 
> std::set: 0.597735 
> 
> #include <set> 
> #include <chrono> 
> #include <random> 
> #include <iostream> 
> #include <vector>
> void test() { 
> typedef int ElemType; 
> const size_t Cnt = 1000000;
> std::random_device rd; 
> std::mt19937 gen(rd()); 
> std::uniform_int_distribution<> distr(0, Cnt / 2); 
> 
> std::vector<unsigned char> my_set(Cnt / 2); 
> auto tm0 = std::chrono::high_resolution_clock::now(); 
> for (size_t i = 0; i < Cnt; ++i) { 
> my_set[distr(gen)] = 1; 
> } 
> auto tm1 = std::chrono::high_resolution_clock::now(); 
> double duration = 
> std::chrono::duration_cast<std::chrono::duration<double>>(tm1 - 
> tm0).count(); 
> std::cout << "my_set: " << duration << "\n"; 
> 
> std::set<ElemType> bb; 
> tm0 = std::chrono::high_resolution_clock::now(); 
> for (size_t i = 0; i < Cnt; ++i) { 
> bb.insert(distr(gen)); 
> } 
> tm1 = std::chrono::high_resolution_clock::now(); 
> duration = 
> std::chrono::duration_cast<std::chrono::duration<double>>(tm1 - 
> tm0).count(); 
> std::cout << "std::set: " << duration << "\n";
> }; 
> 
> int main(int argc, const char* argv[]) { 
> try { 
> test();
> } catch (const std::exception& e) { 
> std::cerr << "Exception: " << e.what() << "\n"; 
> return EXIT_FAILURE; 
> } catch (...) { 
> std::cerr << "Exception\n"; 
> return EXIT_FAILURE; 
> } 
> }

Why you show the comparison of std::vector's random access and std::set's insert?

[toc] | [prev] | [next] | [standalone]

#91234

09.08.2023 17:20 wij kirjutas:

> Why you show the comparison of std::vector's random access and std::set's insert?

Because a linear array can be used as a set, if set elements are 
reasonably small integers, with a potentially huge expense on memory. 
And sometimes this approach is used in production, of course only if it 
makes sense.

[toc] | [prev] | [next] | [standalone]

#91236

On Wednesday, 9 August 2023 at 20:29:39 UTC+3, Paavo Helde wrote:
> 09.08.2023 17:20 wij kirjutas: 
> 
> > Why you show the comparison of std::vector's random access and std::set's insert?
> Because a linear array can be used as a set, if set elements are 
> reasonably small integers, with a potentially huge expense on memory. 
> And sometimes this approach is used in production, of course only if it 
> makes sense.

Such vector is typically used in counting sort algorithm. Sorting 
million (N) items  of half million (K) possible states with counting
sort O(N+K) time complexity is about 13 times better than with 
O(N*log N) sort. But of course misuse of std::set for such sorting 
adds another order of magnitude to loss in performance.

[toc] | [prev] | [next] | [standalone]

#91258

Lynn McGuire <lynnmcguire5@gmail.com> writes:

> "Inside STL:  The map, set, multimap, and multiset" by Raymond Chen
>    https://devblogs.microsoft.com/oldnewthing/20230807-00/
>
> "The complexity requirements of the C+ standard library map, set,
> multimap, and multiset basically narrow the possible implementation
> options to AVL trees and red-black trees."

I find this claim hard to believe.  There are other kinds of
balanced trees that offer the same kinds of performance
guarantees that AVL and red-black trees do.  Is there some sort
of unexpected requirement in the C++ standard that would rule out
other balanced tree data structures?  I confess I have not tried
to read the C++ standard looking for such a requirement, but I'm
willing to take a look if someone provides a specific reference.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web