Interest in a "breadth first" algorithm?
A while ago I needed to serialize and de-serialize a std::map and I realized that the only interface was begin(), end() which of course meant that re-creating this same map was the least efficient way possible, as all the elements were added in sorted order. Because I wrote them out using begin() -> end() So I wrote a breadth first template which takes a container, a template to use as the core of a queue, a template for the allocator, the container and a function to apply to the elements. It doesn't quite do a true breadth first traversal because I don't look at the inner data structure of the map, (works with sets as well) but instead does a middle, then right, left push until it's hit all of the nodes. And it doesn't copy the elements, it pushes the iterators, and calls the function on that iterator when the length is 1. It ended up speeding up my map recreation by about 20% (because I start with a center enough node that it should never have to be rebalanced) at a cost of about 5% to write it this way (It's more expensive to create the queue, and traverse the map from center on out), for a roughly 15% gain in speed. Is there any interest this for boost? I've got working code but not any documentation. And rather than spend a huge amount of time on that I'm looking to see if anyone else has an interest in this. -Gary- -- ------------------ powellg@gmail.com "Come gather 'round people wherever you roam. And admit that the waters around you have grown. And accept it that soon you'll be drenched to the bone. If your time to you is worth savin'. Ahh you better start swimmin' or you'll sink like a stone. For the times they are a-changin'" Bob Dylan
On 2012-06-19 00:47, Gary Powell wrote:
A while ago I needed to serialize and de-serialize a std::map and I realized that the only interface was begin(), end() which of course meant that re-creating this same map was the least efficient way possible, as all the elements were added in sorted order. Because I wrote them out using begin() -> end() So I wrote a breadth first template which takes a container, a template to use as the core of a queue, a template for the allocator, the container and a function to apply to the elements.
It doesn't quite do a true breadth first traversal because I don't look at the inner data structure of the map, (works with sets as well) but instead does a middle, then right, left push until it's hit all of the nodes. And it doesn't copy the elements, it pushes the iterators, and calls the function on that iterator when the length is 1.
It ended up speeding up my map recreation by about 20% (because I start with a center enough node that it should never have to be rebalanced) at a cost of about 5% to write it this way (It's more expensive to create the queue, and traverse the map from center on out), for a roughly 15% gain in speed.
Is there any interest this for boost? I've got working code but not any documentation. And rather than spend a huge amount of time on that I'm looking to see if anyone else has an interest in this.
-Gary-
Maybe a an obvious question, but is this speedup relative to the positional insertion overload of std::map? iterator insert ( iterator position, const value_type& x ); Regards, Rutger
Maybe a an obvious question, but is this speedup relative to the positional insertion overload of std::map?
iterator insert ( iterator position, const value_type& x );
Regards,
Rutger
Hits self on head... no. It was relative to map::operator[]()
Just testing operator[] vs iterator insert(...) is about 68% faster to use insert. breadthfirst ordering vs insert() is about 48% using insert. I think I didn't use insert because of folklore that it didn't help, and clearly that was wrong and should have been tested. Well all the time spent was not totally lost as I figured out how to use meta programming to turn on and off member functions in a templated class... use inheritence. But that's another story. Thanks, -Gary- -- ------------------ powellg@gmail.com "Come gather 'round people wherever you roam. And admit that the waters around you have grown. And accept it that soon you'll be drenched to the bone. If your time to you is worth savin'. Ahh you better start swimmin' or you'll sink like a stone. For the times they are a-changin'" Bob Dylan
Insert a big sorted sequence in a std::set is more faster than insert an unordered sequence, due to the cache performance. The potencial benefits in an small sequence disappear when the sequence grows. In a std::set <uin64_t> , inserting 30.000.000 elements, sorted elements : 29.98 secs unordered elements : 53.57 secs Regards Francisco Tapia
This thread needed the tag in the subject line. on Mon Jun 18 2012, Gary Powell <gwpowell-AT-gmail.com> wrote:
A while ago I needed to serialize and de-serialize a std::map and I realized that the only interface was begin(), end() which of course meant that re-creating this same map was the least efficient way possible, as all the elements were added in sorted order. Because I wrote them out using begin() -> end() So I wrote a breadth first template which takes a container, a template to use as the core of a queue, a template for the allocator, the container and a function to apply to the elements.
It doesn't quite do a true breadth first traversal because I don't look at the inner data structure of the map, (works with sets as well) but instead does a middle, then right, left push until it's hit all of the nodes. And it doesn't copy the elements, it pushes the iterators, and calls the function on that iterator when the length is 1.
It ended up speeding up my map recreation by about 20% (because I start with a center enough node that it should never have to be rebalanced) at a cost of about 5% to write it this way (It's more expensive to create the queue, and traverse the map from center on out), for a roughly 15% gain in speed.
Is there any interest this for boost? I've got working code but not any documentation. And rather than spend a huge amount of time on that I'm looking to see if anyone else has an interest in this.
-Gary-
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
participants (4)
-
Dave Abrahams -
Francisco José Tapia -
Gary Powell -
Rutger ter Borg