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

Groups > comp.lang.c++ > #79805 > 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)" Vir Campestris <vir.campestris@invalid.invalid> - 2021-05-27 21:38 +0100
    Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Louis Krupp <lkrupp@invalid.pssw.com.invalid> - 2021-05-27 19:03 -0600
      Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Paavo Helde <myfirstname@osa.pri.ee> - 2021-05-28 08:59 +0300
        Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" scott@slp53.sl.home (Scott Lurndal) - 2021-05-28 14:44 +0000
          Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" James Kuyper <jameskuyper@alumni.caltech.edu> - 2021-05-28 11:25 -0400
            Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" scott@slp53.sl.home (Scott Lurndal) - 2021-05-28 17:23 +0000
          Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Juha Nieminen <nospam@thanks.invalid> - 2021-05-28 16: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:13 +0000
            Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" scott@slp53.sl.home (Scott Lurndal) - 2021-05-28 17:50 +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 21:41 +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 18:46 +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 17:02 +0000

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

On 26/05/2021 21:44, Scott Lurndal wrote:
> Lynn McGuire <lynnmcguire5@gmail.com> writes:
>> "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.
> 
> Isn't that computer science 101?   O(N) vs. [O(1) .. O(Log N)] for
> vector  vs std::map (red-black tree).
> 
It's funny, I usually say "Use vector. No really, use vector. Oh, 
perhaps if you have a special case..."

But having glanced through that code It's not clear to me _why_ set 
works so much better for that case. Most likely lots of insertions or 
searches.

Andy

[toc] | [next] | [standalone]

#79817

On 5/27/2021 2:38 PM, Vir Campestris wrote:
> On 26/05/2021 21:44, Scott Lurndal wrote:
>> Lynn McGuire <lynnmcguire5@gmail.com> writes:
>>> "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.
>>
>> Isn't that computer science 101?   O(N) vs. [O(1) .. O(Log N)] for
>> vector  vs std::map (red-black tree).
>>
> It's funny, I usually say "Use vector. No really, use vector. Oh, 
> perhaps if you have a special case..."
>
> But having glanced through that code It's not clear to me _why_ set 
> works so much better for that case. Most likely lots of insertions or 
> searches.
>

The update code for vectors loops through elements until it finds a 
match. In the Code Project page:

             for  (auto  it = _aPixelActionsVec.begin(); it != _aPixelActionsVec.end(); it++)
             {
                 if  (it->ManipulationType == PIXEL_MANIPULATION &&
                     it->ColumnOrPalIdx == lCol &&
                     it->Row == lRow)
                 {
                     it->NewColIdxOrRef = dwNewColIdxOrRef;
                     it->NewMask = bNewMask;
                     return  true;
                 }
             }

The update code for sets calls the set's "find" method:

             IMAGMANIPULATION im;
             SetPixelManipulation(im, lCol, lRow, dwOldColIdxOrRef, dwNewColIdxOrRef,
                                  bOldMask, bNewMask);
  
             auto  it = _aPixelActionsSet.find(im);
             if  (it != _aPixelActionsSet.end())
             {
                 if  (it->NewColIdxOrRef != dwNewColIdxOrRef ||
                     it->NewMask        != bNewMask            )
                 {
                     _aPixelActionsSet.erase(it);
                     _aPixelActionsSet.insert(im);
                 }
                 return  true;
             }

A set *could* be implemented as a vector, but it's almost certainly not; 
as Scott said, it uses a self-balancing binary search tree. The set's 
"find" method would take advantage of this to find matches quickly; 
think of how you would code a binary search to find something in a 
sorted array.

If there's no need to cycle through all the elements of a set in a 
particular sequence, an unordered set might be even faster than a set; 
from what I've read, it uses a hash table instead of a binary search tree.

If there's a need to cycle through the elements in their order of 
insertion, it might be possible to maintain both a vector and a set, 
adding a vector element pointer to the set element. The code could find 
matches quickly using the set while still being able to cycle through 
the elements of the vector. The bookkeeping required to keep the vector 
and the set in sync might or might not be worth the time and trouble.

Louis

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

#79846

28.05.2021 04:03 Louis Krupp kirjutas:
> On 5/27/2021 2:38 PM, Vir Campestris wrote:
>> On 26/05/2021 21:44, Scott Lurndal wrote:
>>> Lynn McGuire <lynnmcguire5@gmail.com> writes:
>>>> "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.
>>>
>>> Isn't that computer science 101?   O(N) vs. [O(1) .. O(Log N)] for
>>> vector  vs std::map (red-black tree).
>>>
>> It's funny, I usually say "Use vector. No really, use vector. Oh, 
>> perhaps if you have a special case..."
>>
>> But having glanced through that code It's not clear to me _why_ set 
>> works so much better for that case. Most likely lots of insertions or 
>> searches.
>>
> 
> The update code for vectors loops through elements until it finds a 
> match. In the Code Project page:
> 
>              for  (auto  it = _aPixelActionsVec.begin(); it != 
> _aPixelActionsVec.end(); it++)

One can have efficient search in vectors, beating std::set. But for that 
the vector must be sorted and one must use std::lower_bound(), not 
linear search.

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

#79882

Paavo Helde <myfirstname@osa.pri.ee> writes:
>28.05.2021 04:03 Louis Krupp kirjutas:
>> On 5/27/2021 2:38 PM, Vir Campestris wrote:
>>> On 26/05/2021 21:44, Scott Lurndal wrote:
>>>> Lynn McGuire <lynnmcguire5@gmail.com> writes:
>>>>> "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.
>>>>
>>>> Isn't that computer science 101?   O(N) vs. [O(1) .. O(Log N)] for
>>>> vector  vs std::map (red-black tree).
>>>>
>>> It's funny, I usually say "Use vector. No really, use vector. Oh, 
>>> perhaps if you have a special case..."
>>>
>>> But having glanced through that code It's not clear to me _why_ set 
>>> works so much better for that case. Most likely lots of insertions or 
>>> searches.
>>>
>> 
>> The update code for vectors loops through elements until it finds a 
>> match. In the Code Project page:
>> 
>>              for  (auto  it = _aPixelActionsVec.begin(); it != 
>> _aPixelActionsVec.end(); it++)
>
>One can have efficient search in vectors, beating std::set. But for that 
>the vector must be sorted and one must use std::lower_bound(), not 
>linear search.

A vector miss will always be O(N).  The average hit will be O(N/2).  From a big-O
perspective, they're identical complexities.

And either the sort needs to be done after every insert or the insert
complexity becomes high (due to the need to move all the higher
elements up one in the vector).

A miss on a balanced tree structure will always be O(LOG N), with
some complexity on insert due to balancing.

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

#79893

On 5/28/21 10:44 AM, Scott Lurndal wrote:
> Paavo Helde <myfirstname@osa.pri.ee> writes:
...
>> One can have efficient search in vectors, beating std::set. But for that 
>> the vector must be sorted and one must use std::lower_bound(), not 
>> linear search.
> 
> A vector miss will always be O(N).  The average hit will be O(N/2).  From a big-O
> perspective, they're identical complexities.

The description for std::lower_bound<T>() says "They are especially
appropriate for random access iterators, because these algorithms do a
logarithmic number of steps through the data structure." (25.8.3p1). For
types other than bool, std::vector<T> is a contiguous container
(22.3.11.1), and therefore has "member types iterator and const_iterator
[that] meet the Cpp17 RandomAccessIterator requirements (23.3.5.6)"
(22.2.1p13). Therefore lower_bound should be O(ln(N)), not O(N/2),
regardless of whether there's a hit or a miss.


> And either the sort needs to be done after every insert or the insert

If lower_bound() fails to find an exact match, the value it does return
will indicate precisely where the new item should be inserted to keep
the vector in order, so there's no need to sort. On the other hand, it
is true that:

> complexity becomes high (due to the need to move all the higher
> elements up one in the vector).

That's true, but it's importance depends upon how frequently the sorted
vector will be searched compared with how frequently it will need to be
modified. The comment you were responding to was only about searching.

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

#79908

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>On 5/28/21 10:44 AM, Scott Lurndal wrote:
>> Paavo Helde <myfirstname@osa.pri.ee> writes:
>...
>>> One can have efficient search in vectors, beating std::set. But for that 
>>> the vector must be sorted and one must use std::lower_bound(), not 
>>> linear search.
>> 
>> A vector miss will always be O(N).  The average hit will be O(N/2).  From a big-O
>> perspective, they're identical complexities.
>
>The description for std::lower_bound<T>() says 

I missed the reference to lower_bound (i.e. binary search).  It's true that
using a binary search on a sorted vector will be O(log N).

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

#79899

Scott Lurndal <scott@slp53.sl.home> wrote:
>>One can have efficient search in vectors, beating std::set. But for that 
>>the vector must be sorted and one must use std::lower_bound(), not 
>>linear search.
> 
> A vector miss will always be O(N).  The average hit will be O(N/2).  From a big-O
> perspective, they're identical complexities.

What do you mean by "vector miss"?

> And either the sort needs to be done after every insert or the insert
> complexity becomes high (due to the need to move all the higher
> elements up one in the vector).

I think the idea was that if you already have a sorted vector (for example
a dataset that you read eg. from a file and sorted once), making repeated
searches for different values will be as fast as, if not even slightly
faster than with std::set (not asymptotically faster, but faster in
terms of wallclock time).

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

#79907

On 2021-05-28, Scott Lurndal <scott@slp53.sl.home> wrote:
> Paavo Helde <myfirstname@osa.pri.ee> writes:
>>28.05.2021 04:03 Louis Krupp kirjutas:
>>> On 5/27/2021 2:38 PM, Vir Campestris wrote:
>>>> On 26/05/2021 21:44, Scott Lurndal wrote:
>>>>> Lynn McGuire <lynnmcguire5@gmail.com> writes:
>>>>>> "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.
>>>>>
>>>>> Isn't that computer science 101?   O(N) vs. [O(1) .. O(Log N)] for
>>>>> vector  vs std::map (red-black tree).
>>>>>
>>>> It's funny, I usually say "Use vector. No really, use vector. Oh, 
>>>> perhaps if you have a special case..."
>>>>
>>>> But having glanced through that code It's not clear to me _why_ set 
>>>> works so much better for that case. Most likely lots of insertions or 
>>>> searches.
>>>>
>>> 
>>> The update code for vectors loops through elements until it finds a 
>>> match. In the Code Project page:
>>> 
>>>              for  (auto  it = _aPixelActionsVec.begin(); it != 
>>> _aPixelActionsVec.end(); it++)
>>
>>One can have efficient search in vectors, beating std::set. But for that 
>>the vector must be sorted and one must use std::lower_bound(), not 
>>linear search.
>
> A vector miss will always be O(N).  The average hit will be O(N/2).  From a big-O
> perspective, they're identical complexities.
>
> And either the sort needs to be done after every insert or the insert
> complexity becomes high (due to the need to move all the higher
> elements up one in the vector).
>
> A miss on a balanced tree structure will always be O(LOG N), with
> some complexity on insert due to balancing.
While this is theorectically OK, sorting list in place lineraly
with sequential quirt sort is faster then sorting it by relinking nodes.
And after that traversal is much faster as in place sort doesn't change
memory order. Chasing pointers is unforgivin on modern hardware.
You get less then instruction per cycle ...



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

#79913

Branimir Maksimovic <branimir.maksimovic@gmail.com> writes:
>On 2021-05-28, Scott Lurndal <scott@slp53.sl.home> wrote:
>> Paavo Helde <myfirstname@osa.pri.ee> writes:
>>>28.05.2021 04:03 Louis Krupp kirjutas:
>>>> On 5/27/2021 2:38 PM, Vir Campestris wrote:
>>>>> On 26/05/2021 21:44, Scott Lurndal wrote:
>>>>>> Lynn McGuire <lynnmcguire5@gmail.com> writes:
>>>>>>> "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.
>>>>>>
>>>>>> Isn't that computer science 101?   O(N) vs. [O(1) .. O(Log N)] for
>>>>>> vector  vs std::map (red-black tree).
>>>>>>
>>>>> It's funny, I usually say "Use vector. No really, use vector. Oh, 
>>>>> perhaps if you have a special case..."
>>>>>
>>>>> But having glanced through that code It's not clear to me _why_ set 
>>>>> works so much better for that case. Most likely lots of insertions or 
>>>>> searches.
>>>>>
>>>> 
>>>> The update code for vectors loops through elements until it finds a 
>>>> match. In the Code Project page:
>>>> 
>>>>              for  (auto  it = _aPixelActionsVec.begin(); it != 
>>>> _aPixelActionsVec.end(); it++)
>>>
>>>One can have efficient search in vectors, beating std::set. But for that 
>>>the vector must be sorted and one must use std::lower_bound(), not 
>>>linear search.
>>
>> A vector miss will always be O(N).  The average hit will be O(N/2).  From a big-O
>> perspective, they're identical complexities.
>>
>> And either the sort needs to be done after every insert or the insert
>> complexity becomes high (due to the need to move all the higher
>> elements up one in the vector).
>>
>> A miss on a balanced tree structure will always be O(LOG N), with
>> some complexity on insert due to balancing.
>While this is theorectically OK, sorting list in place lineraly
>with sequential quirt sort is faster then sorting it by relinking nodes.
>And after that traversal is much faster as in place sort doesn't change
>memory order. Chasing pointers is unforgivin on modern hardware.
>You get less then instruction per cycle ...

Not really unforgiving, we spend significant resources on tuning
the cache replacement algorithms and cache prefetchers to detect
and support pointer chasing applications.

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

#79929

On 2021-05-28, Scott Lurndal <scott@slp53.sl.home> wrote:
> Branimir Maksimovic <branimir.maksimovic@gmail.com> writes:
>>On 2021-05-28, Scott Lurndal <scott@slp53.sl.home> wrote:
>>> Paavo Helde <myfirstname@osa.pri.ee> writes:
>>>>28.05.2021 04:03 Louis Krupp kirjutas:
>>>>> On 5/27/2021 2:38 PM, Vir Campestris wrote:
>>>>>> On 26/05/2021 21:44, Scott Lurndal wrote:
>>>>>>> Lynn McGuire <lynnmcguire5@gmail.com> writes:
>>>>>>>> "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.
>>>>>>>
>>>>>>> Isn't that computer science 101?   O(N) vs. [O(1) .. O(Log N)] for
>>>>>>> vector  vs std::map (red-black tree).
>>>>>>>
>>>>>> It's funny, I usually say "Use vector. No really, use vector. Oh, 
>>>>>> perhaps if you have a special case..."
>>>>>>
>>>>>> But having glanced through that code It's not clear to me _why_ set 
>>>>>> works so much better for that case. Most likely lots of insertions or 
>>>>>> searches.
>>>>>>
>>>>> 
>>>>> The update code for vectors loops through elements until it finds a 
>>>>> match. In the Code Project page:
>>>>> 
>>>>>              for  (auto  it = _aPixelActionsVec.begin(); it != 
>>>>> _aPixelActionsVec.end(); it++)
>>>>
>>>>One can have efficient search in vectors, beating std::set. But for that 
>>>>the vector must be sorted and one must use std::lower_bound(), not 
>>>>linear search.
>>>
>>> A vector miss will always be O(N).  The average hit will be O(N/2).  From a big-O
>>> perspective, they're identical complexities.
>>>
>>> And either the sort needs to be done after every insert or the insert
>>> complexity becomes high (due to the need to move all the higher
>>> elements up one in the vector).
>>>
>>> A miss on a balanced tree structure will always be O(LOG N), with
>>> some complexity on insert due to balancing.
>>While this is theorectically OK, sorting list in place lineraly
>>with sequential quirt sort is faster then sorting it by relinking nodes.
>>And after that traversal is much faster as in place sort doesn't change
>>memory order. Chasing pointers is unforgivin on modern hardware.
>>You get less then instruction per cycle ...
>
> Not really unforgiving, we spend significant resources on tuning
> the cache replacement algorithms and cache prefetchers to detect
> and support pointer chasing applications.
+1


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

#79897

> One can have efficient search in vectors, beating std::set. ...

Use unordered_set if you don't need sorted iteration.
When the load-factor is set correctly that will be faster.

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

#79902

On 2021-05-28, Paavo Helde <myfirstname@osa.pri.ee> wrote:
> 28.05.2021 04:03 Louis Krupp kirjutas:
>> On 5/27/2021 2:38 PM, Vir Campestris wrote:
>>> On 26/05/2021 21:44, Scott Lurndal wrote:
>>>> Lynn McGuire <lynnmcguire5@gmail.com> writes:
>>>>> "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.
>>>>
>>>> Isn't that computer science 101?   O(N) vs. [O(1) .. O(Log N)] for
>>>> vector  vs std::map (red-black tree).
>>>>
>>> It's funny, I usually say "Use vector. No really, use vector. Oh, 
>>> perhaps if you have a special case..."
>>>
>>> But having glanced through that code It's not clear to me _why_ set 
>>> works so much better for that case. Most likely lots of insertions or 
>>> searches.
>>>
>> 
>> The update code for vectors loops through elements until it finds a 
>> match. In the Code Project page:
>> 
>>              for  (auto  it = _aPixelActionsVec.begin(); it != 
>> _aPixelActionsVec.end(); it++)
>
> One can have efficient search in vectors, beating std::set. But for that 
> the vector must be sorted and one must use std::lower_bound(), not 
> linear search.

well that is because vector is more cache friendly ;)
>


-- 
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] | [standalone]

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

csiph-web