"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

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

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;
}
}

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

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.

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 );
}

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.

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 );
}

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?

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.

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.

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.

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.

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.