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

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

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

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

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

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

Lynn McGuire <lynnmcguire5@gmail.com> wrote:
> "STL: Amazing Speed Differences between std::vector and std::set 
> (Observed with an UndoRedoAction)"
> 
> https://www.codeproject.com/Tips/5303529/STL-Amazing-Speed-Differences-between-std-vector-a
> 
> I have seen this myself.   We used a std::map for a very large set 
> (>10,000 members) just because it is much faster than std::vector.

If you are programming something for efficiency, you should know the theory
behind algorithms and data containers. You should unerstand the difference
between linear-time operations and logarithmic-time operations. You should
know how data containers behave internally and what their computational
complexity is.

It's quite obvious that a binary search on a sorted data container (which
is essentially waht std::set does) is going to be exponentially faster
than a linear search on an unsorted data container (the larger the amount
of elements, the exponentially larger the difference in speed).

To a competent programmer something like std::set shouldn't merely be a
black box that does some strange magic inside. The competent programmer
knows what it's doing behind the scenes, and what its strengths and
weaknesses are.

In the same way as std::vector is not good for everything, likewise
std::set is not good for everything. There are many situations where
std::vector (even with a very large number of elements) is actually much
more efficient than std::set. It depends on what exactly you are doing.
(And, of course, std::vector and std::set are not fully interchangeable
in all situations, because std::set is an ordered data container. It does
not preserve the order of insertion, like std::vector does, but always
keeps the elements sorted. That's what allows the logarithmic search,
insertion and deletion of elements.)

When the logarithmic-time insertion, deletion and searching for a large
data container are not needed, std::set can be detrimental to performance
compared to an implementation that uses std::vector efficiently. That's
because std::set allocates memory dynamically for every single element
(and each element has quite some overhead in the form of several pointers
and other data members). This not only means that std::set consumes more
memory, but it's also slower to create new elements and, in some cases,
to traverse the container because the elements are not placed in
contiguous memory locations (and, even if they happened to be, they
would be spaced out a lot more, causing more cache misses).

Depending on the task at hand, std::vector can be as fast as, if not faster
than std::set even when requiring fast searching. This is if you can keep
the vector sorted and use binary searching (std::lower_bound). Of course
this applies mostly if you can generate the entire vector in one go and
then you just need to search but don't need to insert or remove elements.

[toc] | [next] | [standalone]

#79903

On 2021-05-28, Juha Nieminen <nospam@thanks.invalid> wrote:
> Lynn McGuire <lynnmcguire5@gmail.com> wrote:
>> "STL: Amazing Speed Differences between std::vector and std::set 
>> (Observed with an UndoRedoAction)"
>> 
>> https://www.codeproject.com/Tips/5303529/STL-Amazing-Speed-Differences-between-std-vector-a
>> 
>> I have seen this myself.   We used a std::map for a very large set 
>> (>10,000 members) just because it is much faster than std::vector.
>
> If you are programming something for efficiency, you should know the theory
> behind algorithms and data containers. You should unerstand the difference
> between linear-time operations and logarithmic-time operations. You should
> know how data containers behave internally and what their computational
> complexity is.
>
> It's quite obvious that a binary search on a sorted data container (which
> is essentially waht std::set does) is going to be exponentially faster
> than a linear search on an unsorted data container (the larger the amount
> of elements, the exponentially larger the difference in speed).
>
> To a competent programmer something like std::set shouldn't merely be a
> black box that does some strange magic inside. The competent programmer
> knows what it's doing behind the scenes, and what its strengths and
> weaknesses are.
>
> In the same way as std::vector is not good for everything, likewise
> std::set is not good for everything. There are many situations where
> std::vector (even with a very large number of elements) is actually much
> more efficient than std::set. It depends on what exactly you are doing.
> (And, of course, std::vector and std::set are not fully interchangeable
> in all situations, because std::set is an ordered data container. It does
> not preserve the order of insertion, like std::vector does, but always
> keeps the elements sorted. That's what allows the logarithmic search,
> insertion and deletion of elements.)
>
> When the logarithmic-time insertion, deletion and searching for a large
> data container are not needed, std::set can be detrimental to performance
> compared to an implementation that uses std::vector efficiently. That's
> because std::set allocates memory dynamically for every single element
> (and each element has quite some overhead in the form of several pointers
> and other data members). This not only means that std::set consumes more
> memory, but it's also slower to create new elements and, in some cases,
> to traverse the container because the elements are not placed in
> contiguous memory locations (and, even if they happened to be, they
> would be spaced out a lot more, causing more cache misses).
>
> Depending on the task at hand, std::vector can be as fast as, if not faster
> than std::set even when requiring fast searching. This is if you can keep
> the vector sorted and use binary searching (std::lower_bound). Of course
> this applies mostly if you can generate the entire vector in one go and
> then you just need to search but don't need to insert or remove elements.
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.

-- 
current job title: senior software engineer
skills: x86 aasembler,c++,c,rust,go,nim,haskell...

press any key to continue or any other to quit...

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

#79909

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

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

#79912

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

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

#79922

Bonita Montero <Bonita.Montero@gmail.com> writes:
>>> 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 );

A thousand integers will fit in the L1 cache.  Try
it with a hundred million.

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

#79938

> A thousand integers will fit in the L1 cache.
> Try it with a hundred million.

It will be slower - but the relationship will be the same.

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

#79930

On 2021-05-28, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> 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.
>
Your test is wrong. Too much iterations while data fits in cache:
look when data fits in cache:
~/.../bmaxa_data/examples >>> ./vecvsset
set: 45.2584
vec: 48.2688
so in this case set is even faster then vec, but this is iluusion.
Look how things look like when data does not fits in cache:
/.../bmaxa_data/examples >>> g++ -O2 vecvsset.cpp -march=native -o vecvsset                                                                                                                                             [147]
~/.../bmaxa_data/examples >>> ./vecvsset
set: 226.181
vec: 56.9002
Holy moly vec is 4 times faster then set ;)
Do you understand now what I am talking about ?

-- 
current job title: senior software engineer
skills: x86 aasembler,c++,c,rust,go,nim,haskell...

press any key to continue or any other to quit...

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

#79937

> Your test is wrong. Too much iterations while data fits in cache:
> ...

When I do this:

#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 N      = 1'000'000,
	             ROUNDS = 100'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;
	vector<int> vi( N );
	for( size_t i = N; 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;
}

set is about 78,2 and vector is about 53,8.
Not a big difference ...

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

#79939

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.

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

#79945

On 2021-05-29, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> Your test is wrong. Too much iterations while data fits in cache:
>> ...
>
> When I do this:
>
> #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 N      = 1'000'000,
> 	             ROUNDS = 100'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;
> 	vector<int> vi( N );
> 	for( size_t i = N; 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;
> }
>
> set is about 78,2 and vector is about 53,8.
> Not a big difference ...

That still fits in cache. Try with 8-16 million depending on your cache
size.

>


-- 
current job title: senior software engineer
skills: x86 aasembler,c++,c,rust,go,nim,haskell...

press any key to continue or any other to quit...

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

#79946

> That still fits in cache. Try with 8-16 million depending on your cache
> size.

10E6 ints are 40MB with the vector-version. I've got only 4MB L2-cache,
but 256MB (8 * 32MB) L3-cache. But a cacheline in a L3-cache of a CPU
-die of my multi-die CPU is only populated by one of the cores of the
same die; other dies can't populate it.

That are the number from memory:

set: 1872.5
uset: 188.302
vec: 695.665

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

#79934

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.

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

#79927

On 2021-05-28, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> 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.

Look, caches are pretty large these days. Rarely you will have vector
larger then L3 ;)
for example take a look at this bench:
[code]
~/.../examples/sort >>> ./list_sort 1000000
seed: 1622237019
N: 1000000
unsorted

     0x102515e70 299531
     0x102515e50 398346
     0x102515e30 273381
     0x102515e10 875323
     0x102515df0 289978
     0x102515dd0 399336
     0x102515db0 21582
     0x102515d90 874270
     0x102515d70 114179
     0x102515d50 778108
     0x102515d30 451177
     0x102515d10 570319
     0x102515cf0 621189
     0x102515cd0 138605
     0x102515cb0 908552
     0x102515c90 267934
array radix elapsed 0.029208 seconds
list radix elapsed 1.070269 seconds
list merge elapsed 0.329870 seconds
equal

equal

sorted

     0x100d80710 0
     0x101931470 1
     0x101bb1dd0 4
     0x10198ef10 6
     0x101b8a350 6
     0x102453390 7
     0x1008aa4b0 10
     0x101938ab0 10
     0x100d8a650 11
     0x102093f30 12
     0x101a94eb0 13
     0x10086a5f0 13
     0x101538210 15
     0x100876930 16
     0x10079f010 16
     0x100e9faf0 17
size of node 12, length 1000000
[/code]
Fits in cache (L3)
Now look list sort vs array sort with 8 mil elements.
Goes out of cache size ;)
[code]
~/.../examples/sort >>> ./list_sort 8000000
seed: 1622237118
N: 8000000
unsorted

     0x1112ff670 5357700
     0x1112ff650 5227237
     0x1112ff630 6764785
     0x1112ff610 2977649
     0x1112ff5f0 5339439
     0x1112ff5d0 3588837
     0x1112ff5b0 6605927
     0x1112ff590 1268989
     0x1112ff570 5989679
     0x1112ff550 492070
     0x1112ff530 4063176
     0x1112ff510 2130048
     0x1112ff4f0 2334049
     0x1112ff4d0 5751483
     0x1112ff4b0 1179952
     0x1112ff490 973123
array radix elapsed 0.239062 seconds
list radix elapsed 10.192995 seconds
list merge elapsed 4.259887 seconds
equal

equal

sorted

     0x10ffe8410 0
     0x10e433430 0
     0x107ba73b0 1
     0x11021d0b0 2
     0x10b008290 3
     0x1034351f0 4
     0x10f710f90 5
     0x10b8be5b0 6
     0x10395b170 9
     0x102da6fd0 9
     0x10e729ef0 10
     0x110a91990 11
     0x103f86a90 12
     0x10853c310 13
     0x1065f8890 16
     0x104453390 16
size of node 12, length 8000000
[/code]
While array does not fits in cache as well, it is more cache friendly
then list. Same is for binary tree. That is why btree is so much faster
then plain ordinary binary tree on modern hardware ;)
But C++ because of iterators can't use btrees :(
Also merge sort is much faster on list then radix sort? Can you beleive
that?
Look now trees benchamr. Binary trees vs btree.
[code]
~/.../rust/trees >>> ./target/release/binary_trees                                                                                                                                                                ±[●][master]
└── (0,0):(c:BLACK)
    ├── nil
    └── nil
└── (0,0):(data)
    ├── nil
    └── nil
└── (0,0):(c:BLACK)
    ├── nil
    └── (1,1):(c:RED)
        ├── nil
        └── nil
└── (0,0):(data)
    ├── nil
    └── (1,1):(data)
        ├── nil
        └── nil
└── (1,1):(c:BLACK)
    ├── (0,0):(c:RED)
    │   ├── nil
    │   └── nil
    └── (2,2):(c:RED)
        ├── nil
        └── nil
└── (0,0):(data)
    ├── nil
    └── (1,1):(data)
        ├── nil
        └── (2,2):(data)
            ├── nil
            └── nil
└── (1,1):(c:BLACK)
    ├── (0,0):(c:BLACK)
    │   ├── nil
    │   └── nil
    └── (2,2):(c:BLACK)
        ├── nil
        └── (3,3):(c:RED)
            ├── nil
            └── nil
└── (2,2):(data)
    ├── (1,1):(data)
    │   ├── (0,0):(data)
    │   │   ├── nil
    │   │   └── nil
    │   └── nil
    └── (3,3):(data)
        ├── nil
        └── nil
└── (1,1):(c:BLACK)
    ├── (0,0):(c:BLACK)
    │   ├── nil
    │   └── nil
    └── (3,3):(c:BLACK)
        ├── (2,2):(c:RED)
        │   ├── nil
        │   └── nil
        └── (4,4):(c:RED)
            ├── nil
            └── nil
└── (2,2):(data)
    ├── (1,1):(data)
    │   ├── (0,0):(data)
    │   │   ├── nil
    │   │   └── nil
    │   └── nil
    └── (3,3):(data)
        ├── nil
        └── (4,4):(data)
            ├── nil
            └── nil
└── (1,1):(c:BLACK)
    ├── (0,0):(c:BLACK)
    │   ├── nil
    │   └── nil
    └── (3,3):(c:RED)
        ├── (2,2):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (4,4):(c:BLACK)
            ├── nil
            └── (5,5):(c:RED)
                ├── nil
                └── nil
└── (2,2):(data)
    ├── (1,1):(data)
    │   ├── (0,0):(data)
    │   │   ├── nil
    │   │   └── nil
    │   └── nil
    └── (3,3):(data)
        ├── nil
        └── (4,4):(data)
            ├── nil
            └── (5,5):(data)
                ├── nil
                └── nil
└── (1,1):(c:BLACK)
    ├── (0,0):(c:BLACK)
    │   ├── nil
    │   └── nil
    └── (3,3):(c:RED)
        ├── (2,2):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (5,5):(c:BLACK)
            ├── (4,4):(c:RED)
            │   ├── nil
            │   └── nil
            └── (6,6):(c:RED)
                ├── nil
                └── nil
└── (2,2):(data)
    ├── (1,1):(data)
    │   ├── (0,0):(data)
    │   │   ├── nil
    │   │   └── nil
    │   └── nil
    └── (5,5):(data)
        ├── (4,4):(data)
        │   ├── (3,3):(data)
        │   │   ├── nil
        │   │   └── nil
        │   └── nil
        └── (6,6):(data)
            ├── nil
            └── nil
└── (3,3):(c:BLACK)
    ├── (1,1):(c:RED)
    │   ├── (0,0):(c:BLACK)
    │   │   ├── nil
    │   │   └── nil
    │   └── (2,2):(c:BLACK)
    │       ├── nil
    │       └── nil
    └── (5,5):(c:RED)
        ├── (4,4):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (6,6):(c:BLACK)
            ├── nil
            └── (7,7):(c:RED)
                ├── nil
                └── nil
└── (2,2):(data)
    ├── (1,1):(data)
    │   ├── (0,0):(data)
    │   │   ├── nil
    │   │   └── nil
    │   └── nil
    └── (5,5):(data)
        ├── (4,4):(data)
        │   ├── (3,3):(data)
        │   │   ├── nil
        │   │   └── nil
        │   └── nil
        └── (6,6):(data)
            ├── nil
            └── (7,7):(data)
                ├── nil
                └── nil
└── (3,3):(c:BLACK)
    ├── (1,1):(c:RED)
    │   ├── (0,0):(c:BLACK)
    │   │   ├── nil
    │   │   └── nil
    │   └── (2,2):(c:BLACK)
    │       ├── nil
    │       └── nil
    └── (5,5):(c:RED)
        ├── (4,4):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (7,7):(c:BLACK)
            ├── (6,6):(c:RED)
            │   ├── nil
            │   └── nil
            └── (8,8):(c:RED)
                ├── nil
                └── nil
└── (2,2):(data)
    ├── (1,1):(data)
    │   ├── (0,0):(data)
    │   │   ├── nil
    │   │   └── nil
    │   └── nil
    └── (5,5):(data)
        ├── (4,4):(data)
        │   ├── (3,3):(data)
        │   │   ├── nil
        │   │   └── nil
        │   └── nil
        └── (6,6):(data)
            ├── nil
            └── (7,7):(data)
                ├── nil
                └── (8,8):(data)
                    ├── nil
                    └── nil
└── (3,3):(c:BLACK)
    ├── (1,1):(c:BLACK)
    │   ├── (0,0):(c:BLACK)
    │   │   ├── nil
    │   │   └── nil
    │   └── (2,2):(c:BLACK)
    │       ├── nil
    │       └── nil
    └── (5,5):(c:BLACK)
        ├── (4,4):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (7,7):(c:RED)
            ├── (6,6):(c:BLACK)
            │   ├── nil
            │   └── nil
            └── (8,8):(c:BLACK)
                ├── nil
                └── (9,9):(c:RED)
                    ├── nil
                    └── nil
└── (2,2):(data)
    ├── (1,1):(data)
    │   ├── (0,0):(data)
    │   │   ├── nil
    │   │   └── nil
    │   └── nil
    └── (5,5):(data)
        ├── (4,4):(data)
        │   ├── (3,3):(data)
        │   │   ├── nil
        │   │   └── nil
        │   └── nil
        └── (8,8):(data)
            ├── (7,7):(data)
            │   ├── (6,6):(data)
            │   │   ├── nil
            │   │   └── nil
            │   └── nil
            └── (9,9):(data)
                ├── nil
                └── nil
└── (3,3):(c:BLACK)
    ├── (1,1):(c:BLACK)
    │   ├── (0,0):(c:BLACK)
    │   │   ├── nil
    │   │   └── nil
    │   └── (2,2):(c:BLACK)
    │       ├── nil
    │       └── nil
    └── (5,5):(c:BLACK)
        ├── (4,4):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (7,7):(c:RED)
            ├── (6,6):(c:BLACK)
            │   ├── nil
            │   └── nil
            └── (8,8):(c:BLACK)
                ├── nil
                └── (9,9):(c:RED)
                    ├── nil
                    └── nil
true
0 1
1 2
2 3
3 4
4 5
0 1
1 2
2 3
3 4
4 5
0 1
1 2
2 3
3 4
4 5
valid true 9
valid true 8
valid true 7
valid true 6
valid true 5
valid true 4
valid true 3
valid true 2
valid true 1
valid true 0
valid true 9
valid true 8
valid true 7
valid true 6
valid true 5
valid true 4
valid true 3
valid true 2
valid true 1
valid true 0
valid true 9
└── (5,5):(c:BLACK)
    ├── (3,3):(c:BLACK)
    │   ├── (1,1):(c:BLACK)
    │   │   ├── nil
    │   │   └── (2,2):(c:RED)
    │   │       ├── nil
    │   │       └── nil
    │   └── (4,4):(c:BLACK)
    │       ├── nil
    │       └── nil
    └── (7,7):(c:BLACK)
        ├── (6,6):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (8,8):(c:BLACK)
            ├── nil
            └── (9,9):(c:RED)
                ├── nil
                └── nil
valid true 8
└── (5,5):(c:BLACK)
    ├── (3,3):(c:BLACK)
    │   ├── (2,2):(c:BLACK)
    │   │   ├── nil
    │   │   └── nil
    │   └── (4,4):(c:BLACK)
    │       ├── nil
    │       └── nil
    └── (7,7):(c:BLACK)
        ├── (6,6):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (8,8):(c:BLACK)
            ├── nil
            └── (9,9):(c:RED)
                ├── nil
                └── nil
valid true 7
└── (5,5):(c:BLACK)
    ├── (3,3):(c:BLACK)
    │   ├── nil
    │   └── (4,4):(c:RED)
    │       ├── nil
    │       └── nil
    └── (7,7):(c:RED)
        ├── (6,6):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (8,8):(c:BLACK)
            ├── nil
            └── (9,9):(c:RED)
                ├── nil
                └── nil
valid true 6
└── (5,5):(c:BLACK)
    ├── (4,4):(c:BLACK)
    │   ├── nil
    │   └── nil
    └── (7,7):(c:RED)
        ├── (6,6):(c:BLACK)
        │   ├── nil
        │   └── nil
        └── (8,8):(c:BLACK)
            ├── nil
            └── (9,9):(c:RED)
                ├── nil
                └── nil
valid true 5
└── (7,7):(c:BLACK)
    ├── (5,5):(c:BLACK)
    │   ├── nil
    │   └── (6,6):(c:RED)
    │       ├── nil
    │       └── nil
    └── (8,8):(c:BLACK)
        ├── nil
        └── (9,9):(c:RED)
            ├── nil
            └── nil
valid true 4
└── (7,7):(c:BLACK)
    ├── (6,6):(c:BLACK)
    │   ├── nil
    │   └── nil
    └── (8,8):(c:BLACK)
        ├── nil
        └── (9,9):(c:RED)
            ├── nil
            └── nil
valid true 3
└── (8,8):(c:BLACK)
    ├── (7,7):(c:BLACK)
    │   ├── nil
    │   └── nil
    └── (9,9):(c:BLACK)
        ├── nil
        └── nil
valid true 2
└── (8,8):(c:BLACK)
    ├── nil
    └── (9,9):(c:RED)
        ├── nil
        └── nil
valid true 1
└── (9,9):(c:BLACK)
    ├── nil
    └── nil
valid true 0
empty tree

trees! 64
treest! 64
treesr! 64
average op 5360
t insert time 1.591332069
true
height 20
weight (422175,577824)
average op 5802
t1 insert time 1.722261029
true
height 26
weight (670296,329703)
average op 4334
t2 insert time 1.29017692
true
height 20
weight (422175,577824)
average op 4717
t3 insert time 1.401961993
true
height 23
weight (612266,387733)
counter 31780
average op 3397
bt insert time 1.014782747
true size 1000000
t find time 1.166620321
true
sum 1783293664
t1 find time 1.72787108
true
sum 1783293664
t2 find time 1.192506122
true
sum 1783293664
t3 find time 1.376387028
true
sum 1783293664
bt find time 1.042876439
true
sum 1783293664
average op 375
t iter time 0.110657066
true
sum 1783293664
average op 391
t1 iter time 0.115330211
true
sum 1783293664
average op 376
t2 iter time 0.110930662
true
sum 1783293664
average op 388
t3 iter time 0.114391853
true
sum 1783293664
average op 69
bt iter time 0.020547062
true
sum 1783293664
t delete time 1.806868028
true size 0
empty tree
t1 delete time 1.734909562
true size 0
empty tree
t2 delete time 1.47146888
true size 0
empty tree
t3 delete time 3.051412126
true size 0
counter 19
empty tree
bt delete time 1.052457722
true
[/code]
t,t1,t2,t3 are various binary trees, while bt is btree.
Look how superior btree is, because of cache friendlyness :)



>


-- 
current job title: senior software engineer
skills: x86 aasembler,c++,c,rust,go,nim,haskell...

press any key to continue or any other to quit...

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

#79978

Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> 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.

He was talking about traversing the set, not searching it.
In other words, for(auto& element: theSet).

(This, of course, assuming that the amount of data is so large
that it won't fit entirely even in the L3 cache. Or, if we are
just traversing the set for the first time since all of its contents
have been flushed from the caches.)

Of course even with std::vector it depends on the size of the
element. Traversing a (very large) std::vector linearly from
beginning to end isn't magically going to be very fast either,
if each element is large enough. And "large enough" is actually
quite small. If I remember correctly, cache line sizes are typically
64 bytes or so. This means that if the vector element type is an
object of size 64 bytes or more, and you are accessing just one member
variable of each object, then you'll get no benefit from linear
traversal compared to random access (in the case that the contents of
the vector are not already in the caches).

You only get a speed advantage for (very large) vectors which element
size is very small, like 4 or 8 bytes. For example, if the vector
represents a bitmap image, with each "pixel" element taking eg. 4 bytes,
then a linear traversal will be quite efficient (assuming none of the
vector contents were in any cache to begin with, you'll get an
extremely heavy cache miss only each 16 pixels.)

Of course almost none of this applies if the vector or set is
small enough to fit in L1 cache, and it has already been loaded in
there in its entirety previously. Then none of this matters almost
at all. It starts mattering a bit more if the vector is too large
for L1 but small enough for L2 cache, and furthermore if it's too
large for L2 but small enough for L3 cache.

Modern CPUs tend to have a quite large L3 cache, which mitigates
the problems of cache misses in many instances. For example my CPU
has a L3 cache of 12 MB. Thus if I need to, for example, do some
operations repeatedly to, let's say, an image that fits comfortably
within those 12 MB, then it will be very fast.

It's only when the dataset is much larger than L3 that cache locality
really starts having a very pronounced effect (when performing
operations repeatedly on the entire dataset).

[toc] | [prev] | [standalone]

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

csiph-web