Optimize vector_indexing_suite set_slice
vector_indexing_suite set_slice does: 1) erase 2) insert Shouldn't this be optimized to simply do copy?
Neal D. Becker wrote:
vector_indexing_suite set_slice does: 1) erase 2) insert
Shouldn't this be optimized to simply do copy?
You mean this: container.erase(container.begin()+from, container.begin()+to); container.insert(container.begin()+from, v); Pardon me for being slow, but how? Could you spell it out for me? Cheers, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Joel de Guzman <joel@boost-consulting.com> writes:
Neal D. Becker wrote:
vector_indexing_suite set_slice does: 1) erase 2) insert Shouldn't this be optimized to simply do copy?
You mean this:
container.erase(container.begin()+from, container.begin()+to); container.insert(container.begin()+from, v);
Pardon me for being slow, but how? Could you spell it out for me?
It's not as simple as "copy", but if you think hard about it you can see how to avoid any redundant moves or copies. The pseudocode is complicated so I'm not writing it out in full here, but: if new_size <= old_size: erase(old_finish + (new_size - old_size), old_finish) if new_size < old_size: copy(new_start, new_finish, old_start) else: # fill in the details here -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
Joel de Guzman <joel@boost-consulting.com> writes:
Neal D. Becker wrote:
vector_indexing_suite set_slice does: 1) erase 2) insert Shouldn't this be optimized to simply do copy?
You mean this:
container.erase(container.begin()+from, container.begin()+to); container.insert(container.begin()+from, v);
Pardon me for being slow, but how? Could you spell it out for me?
It's not as simple as "copy", but if you think hard about it you can see how to avoid any redundant moves or copies. The pseudocode is complicated so I'm not writing it out in full here, but:
if new_size <= old_size: erase(old_finish + (new_size - old_size), old_finish) if new_size < old_size: copy(new_start, new_finish, old_start) else: # fill in the details here
I see. Yeah, same ol' buffer management. Ok, I'll optimize it. But it'll have to be after 1.32. Ok? Cheers, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Joel de Guzman <joel@boost-consulting.com> writes:
David Abrahams wrote:
Joel de Guzman <joel@boost-consulting.com> writes:
Neal D. Becker wrote:
vector_indexing_suite set_slice does: 1) erase 2) insert Shouldn't this be optimized to simply do copy?
You mean this:
container.erase(container.begin()+from, container.begin()+to); container.insert(container.begin()+from, v);
Pardon me for being slow, but how? Could you spell it out for me? It's not as simple as "copy", but if you think hard about it you can see how to avoid any redundant moves or copies. The pseudocode is complicated so I'm not writing it out in full here, but: if new_size <= old_size: erase(old_finish + (new_size - old_size), old_finish) if new_size < old_size: copy(new_start, new_finish, old_start) else: # fill in the details here
I see. Yeah, same ol' buffer management. Ok, I'll optimize it. But it'll have to be after 1.32. Ok?
Sure thing. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
Joel de Guzman <joel@boost-consulting.com> writes:
David Abrahams wrote:
Joel de Guzman <joel@boost-consulting.com> writes:
Neal D. Becker wrote:
vector_indexing_suite set_slice does: 1) erase 2) insert Shouldn't this be optimized to simply do copy?
You mean this:
container.erase(container.begin()+from, container.begin()+to); container.insert(container.begin()+from, v);
Pardon me for being slow, but how? Could you spell it out for me? It's not as simple as "copy", but if you think hard about it you can see how to avoid any redundant moves or copies. The pseudocode is complicated so I'm not writing it out in full here, but: if new_size <= old_size: erase(old_finish + (new_size - old_size), old_finish) if new_size < old_size: copy(new_start, new_finish, old_start) else: # fill in the details here
I see. Yeah, same ol' buffer management. Ok, I'll optimize it. But it'll have to be after 1.32. Ok?
Sure thing.
Just to clarify a little: 1. wrapping std::vector is useful for c++ algorithms intended for efficient processing of relatively large data vectors. 2. This doesn't inherently give any way to directly reference a slice of data. More code has to be written if you want to say from python "compute function F on a slice of vector V". 3. This limitation (lack of optimization to operate directly on slices) may not be very important in many cases, you could just do: Suppose we have a a vector v, and want to modify a slice of v using alg F: w = F (v[2:4]) # compute result from slice v[2:4] = w #splice in result 4. But it's even worse than it looks, because the "splice in result" will actually call erase and insert, instead of just copy.
--- "Neal D. Becker" <ndbecker2@verizon.net> wrote:
3. This limitation (lack of optimization to operate directly on slices) may not be very important in many cases, you could just do: Suppose we have a a vector v, and want to modify a slice of v using alg F:
w = F (v[2:4]) # compute result from slice v[2:4] = w #splice in result
4. But it's even worse than it looks, because the "splice in result" will actually call erase and insert, instead of just copy.
FWIW: I've solved this problem in a different way. I am using two types of "selections" which may be understood as generalization of slices: - type 1: selection array of bools, same size as data array - type 2: selection array of std::size_t Generalized slicing works like this: v.select(selection_array) And now the other way (without using erase and insert): v.set_selected(selection_array, data_array_of_suitable_size) I find that I don't use regular slicing very much, but the generalized slicing is used all over the place in our apps. I am carefully avoiding "slice references" because it is a Pandora's box and can easily backfire performance-wise. If I had an exceptional case where copying a slice is prohibitive I'd code up a specialized C++ function and wrap it with Boost.Python. Ralf __________________________________ Do you Yahoo!? Yahoo! Mail - 50x more storage than other providers! http://promotions.yahoo.com/new_mail
David Abrahams wrote:
Joel de Guzman <joel@boost-consulting.com> writes:
David Abrahams wrote:
Joel de Guzman <joel@boost-consulting.com> writes:
Neal D. Becker wrote:
vector_indexing_suite set_slice does: 1) erase 2) insert Shouldn't this be optimized to simply do copy?
You mean this:
container.erase(container.begin()+from, container.begin()+to); container.insert(container.begin()+from, v);
Pardon me for being slow, but how? Could you spell it out for me? It's not as simple as "copy", but if you think hard about it you can see how to avoid any redundant moves or copies. The pseudocode is complicated so I'm not writing it out in full here, but: if new_size <= old_size: erase(old_finish + (new_size - old_size), old_finish) if new_size < old_size: copy(new_start, new_finish, old_start) else: # fill in the details here
I see. Yeah, same ol' buffer management. Ok, I'll optimize it. But it'll have to be after 1.32. Ok?
Sure thing.
Something wrong with this? Index: vector_indexing_suite.hpp =================================================================== RCS file: /cvsroot/boost/boost/boost/python/suite/indexing/vector_indexing_suite.hpp,v retrieving revision 1.8 diff -c -r1.8 vector_indexing_suite.hpp *** vector_indexing_suite.hpp 25 Jul 2004 17:00:37 -0000 1.8 --- vector_indexing_suite.hpp 16 Aug 2004 14:07:51 -0000 *************** *** 114,121 **** --- 114,126 ---- container.insert(container.begin()+from, first, last); } else { + if (to < container.size()) { + std::copy (first, last, container.begin()+from); + } + else { container.erase(container.begin()+from, container.begin()+to); container.insert(container.begin()+from, first, last); + } } }
How does this patch look? This attempts to optimize for the case in set_slice that the slice being replaced is the same size as the replacement, in which case a simple copy is performed rather than erase/insert.
"Neal D. Becker" <ndbecker2@verizon.net> writes:
How does this patch look?
This attempts to optimize for the case in set_slice that the slice being replaced is the same size as the replacement, in which case a simple copy is performed rather than erase/insert.
Index: vector_indexing_suite.hpp =================================================================== RCS file: /cvsroot/boost/boost/boost/python/suite/indexing/vector_indexing_suite.hpp,v retrieving revision 1.8 diff -c -r1.8 vector_indexing_suite.hpp *** vector_indexing_suite.hpp 25 Jul 2004 17:00:37 -0000 1.8 --- vector_indexing_suite.hpp 19 Aug 2004 19:25:06 -0000 *************** *** 114,121 **** --- 114,126 ---- container.insert(container.begin()+from, first, last); } else { + if (to - from == std::distance (first, last)) { + std::copy (first, last, container.begin()+from); + } + else { container.erase(container.begin()+from, container.begin()+to); container.insert(container.begin()+from, first, last); + } } }
Shouldn't you generalize it? There's no need to do erase + insert. Suppose you're replacing 100 items with 99 or 101 items? If the sizes don't match should either be insert + copy or copy[_backward] + erase (where the erase happens at the end of the container). Some handwaving here, but it should be easy enough to figure out how to make it optimal. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
participants (4)
-
David Abrahams -
Joel de Guzman -
Neal D. Becker -
Ralf W. Grosse-Kunstleve