Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

Complexity of push_back()

Bartlomiej
New Contributor I
594 Views
Hello,

I wasn't able to find this information neither in the Reference Manual, nor by Google - what is the time complexity of the push_back() method of parallel_vector ? According to the Wikipedia article for std::vector this operation has an amortized complexity O(1). How is it for the parallel relative ?

Thank you in advance and best regards
0 Kudos
1 Solution
Anton_M_Intel
Employee
594 Views
Quoting - bartlomiej
what is the time complexity of the push_back() method of parallel_vector ? According to the Wikipedia article for std::vector this operation has an amortized complexity O(1). How is it for the parallel relative ?

tbb::concurrent_vector has the same average complexity of push_back() method.
Most of the time, it just increases the size counter and stores an item. However, when capacity is not enough to store the item, push_back() extends the vector by adding one more segment. It is similar to resizing of std::vector but actually requires even less effort because it doesn't have to move existing items. Anyway, less initial capacity --> more resize operations --> more overhead. See also my blog for more information.

View solution in original post

0 Kudos
2 Replies
Anton_M_Intel
Employee
595 Views
Quoting - bartlomiej
what is the time complexity of the push_back() method of parallel_vector ? According to the Wikipedia article for std::vector this operation has an amortized complexity O(1). How is it for the parallel relative ?

tbb::concurrent_vector has the same average complexity of push_back() method.
Most of the time, it just increases the size counter and stores an item. However, when capacity is not enough to store the item, push_back() extends the vector by adding one more segment. It is similar to resizing of std::vector but actually requires even less effort because it doesn't have to move existing items. Anyway, less initial capacity --> more resize operations --> more overhead. See also my blog for more information.
0 Kudos
Bartlomiej
New Contributor I
594 Views
Thanks a lot ! A very interesting blog entry.
I'm so ashamed - if I googled concurrent vector, instead of "parallel vector", oops... I'm so sorry.
And thanks once more !

0 Kudos
Reply