...

Would it be okay to you if we would add support for array types to the Boost.Swap utility that is located in the sandbox?

David Abrahams wrote:

Whether or not this is a good idea depends on whether you think swap is fundamentally an O(1) and/or nonthrowing operation.

The array support I would like to add to boost::swap is non-throwing, as long as the array element type has a non-throwing swap. Because it would do an elementwise swap of its two (array) arguments. The addition is needed to implement swap functions for wrappers like value_initialized. Suppose you have two value_initialized arrays of vectors: value_initialized<std::vector<int>[42]> v1, v2; Swapping such value_initialized objects is currently quite expensive (and throwing), doing three std::vector copy operations for each of the 42 array elements, even when using boost::swap (from the sandbox). Basically that's just because value_initialized doesn't yet have a custom swap function. Which could typically be implemented as follows: namespace boost { template <typename T> void swap( value_initialized<T>& lhs, value_initialized<T>& rhs) { // Assuming that sandbox/swap is available: boost::swap( get(lhs), get(rhs) ); } } But such an overload would need boost::swap to support arrays! Otherwise it simply wouldn't compile, when trying to swap value_initialized<std::vector<int>[42]> objects. What do you think? See also www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#809 (now having status Ready). Kind regards, Niels

...

Would it be okay to you if we would add support for array types to the Boost.Swap utility that is located in the sandbox?

Whether or not this is a good idea depends on whether you think swap is fundamentally an O(1) and/or nonthrowing operation.

...

The array support I would like to add to boost::swap is non-throwing, as long as the array element type has a non-throwing swap.

David Abrahams wrote:

Sure, but it is not O(1) no matter what the element type does.

For a particular template instantiation of boost::swap, for a particular type of arrays, the number of element swaps would be constant. Doesn't that make it O(1)? :-) Maybe I just don't understand the definition of O(1) well enough. Do you consider the following swap_pod<T> function O(1)? Or is it O(n), having n = sizeof(T)? It would support swapping arrays, as long as their element type is POD. template<typename T> void swap_pod(T & lhs, T & rhs) { unsigned char tmp[sizeof(T)]; std::memcpy(tmp, lhs, sizeof(T)); std::memcpy(lhs, rhs, sizeof(T)); std::memcpy(rhs, tmp, sizeof(T)); } (BTW, my proposal wasn't to use std::memcpy, but instead, to do the swap elementwise, using the custom swap function of the element type, whenever found by ADL.) So do you think that adding array support to boost::swap is /not/ a good idea? Note that boost::array<T,N> /does/ have a swap function, even though it is documented to have no constant complexity. www.boost.org/doc/libs/1_35_0/doc/html/array.html Do you think that boost::array<T,N> should not have one? Kind regards, Niels

On Jun 23, 2008, at 3:54 PM, David Abrahams wrote:

I haven't formed an opinion yet, but the fact remains that swapping a boost::array would have very different efficiency characteristics from swapping the analogous std::vector, so we ought to think it through carefully.

If it helps, here is a test program using gcc 4.0.1: #include <iostream> #include <vector> #include <tr1/array> #include <ctime> template <class T, std::size_t N> void swap1(std::tr1::array<T, N>& a, std::tr1::array<T, N>& b) { std::tr1::array<T, N> temp(a); a = b; b = temp; } template <class T, std::size_t N> void swap2(std::tr1::array<T, N>& a, std::tr1::array<T, N>& b) { std::swap_ranges(a.begin(), a.end(), b.begin()); } int main() { std::tr1::array<std::vector<int>, 1000> a; for (unsigned i = 0; i < a.size(); ++i) a[i] = std::vector<int>(10000); std::tr1::array<std::vector<int>, 1000> b(a); std::clock_t t1 = std::clock(); swap1(a, b); std::clock_t t2 = std::clock(); std::cout << "swap1 time is " << double(t2 - t1) / CLOCKS_PER_SEC << " seconds\n"; t1 = std::clock(); swap2(a, b); t2 = std::clock(); std::cout << "swap2 time is " << double(t2 - t1) / CLOCKS_PER_SEC << " seconds\n"; } On my machine: $ g++ -O3 test.cpp $ ./a.out swap1 time is 0.172796 seconds swap2 time is 1.3e-05 seconds I also note that swap1 can throw exceptions and swap2 can't. I also note that move semantics will greatly speed swap1, and make it nothrow, but I still expect swap1 with move semantics to be about twice as slow as swap2. -Howard

On Jun 24, 2008, at 12:20 PM, Niels Dekker - mail address until 2008-12-31 wrote:

David Abrahams wrote:

...

I haven't formed an opinion yet, but the fact remains that swapping a boost::array would have very different efficiency characteristics from swapping the analogous std::vector, so we ought to think it through carefully.

Howard Hinnant wrote:

...

If it helps, here is a test program using gcc 4.0.1: ... template <class T, std::size_t N> void swap1(std::tr1::array<T, N>& a, std::tr1::array<T, N>& b) { std::tr1::array<T, N> temp(a); a = b; b = temp; }

template <class T, std::size_t N> void swap2(std::tr1::array<T, N>& a, std::tr1::array<T, N>& b) { std::swap_ranges(a.begin(), a.end(), b.begin()); } ... On my machine:

$ g++ -O3 test.cpp $ ./a.out swap1 time is 0.172796 seconds swap2 time is 1.3e-05 seconds

Cool! Thanks, Howard. The swap member function of boost::array also calls std::swap_ranges, like your swap2:

// swap (note: linear complexity) void swap (array<T,N>& y) { std::swap_ranges(begin(),end(),y.begin()); }

Unfortunately std::swap_ranges doesn't always pick the custom swap function of T. At least, the STL implementation that comes with MSVC 2008 has swap_ranges calling std::iter_swap, which calls std::swap, without doing argument-dependent lookup. :-( Luckily, once boost::swap would be in the trunk, boost::array::swap could be implemented simply by swapping its one and only data member, elems (a built-in array of T):

void swap (array<T,N>& y) { // Assuming that boost::swap supports built-in arrays: boost::swap(this->elems, y.elems); }

Having boost::array::swap call boost::swap would have two advantages: it would support a boost::array containing built-in arrays as elements (boost::array<T[M],N>), and it would use ADL to pick the custom swap function of T.

What do you think?

That sounds like a good solution for the boost lib. Fwiw, I am trying to ensure that std::iter_swap does nothing but call swap (unqualified) in C++0X. -Howard

Howard Hinnant wrote: swap1 time is 0.172796 seconds swap2 time is 1.3e-05 seconds

David Abrahams wrote:

Your program gives about the results I'd have expected for the case you tested, but it doesn't address what I was concerned about.

Howard's example shows that a swap overload for std::tr1::array effectively reduces the complexity of swapping a tr1::array<vector<int>,N> from O(M*N) to O(N), when the array has N vectors, each having size M. And it provides no-throw. Aren't those the issues you were concerned about? Any type that is both CopyConstructible and Assignable is Swappable, by definition. Within generic code, people typically use the well-known idiom to swap a pair of Swappable objects: // Allow argument-dependent lookup to find a custom swap. using std::swap; swap(lhs, rhs); As long as boost::swap hasn't come out of the sandbox, of course (hint)! Don't you think it /always/ makes sense to provide a custom swap overload for a Swappable type, as long as it outperforms the default std::swap, in one way or the other? Kind regards, Niels

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Thursday 26 June 2008 10:51 am, David Abrahams wrote:

...

Don't you think it /always/ makes sense to provide a custom swap overload for a Swappable type, as long as it outperforms the default std::swap, in one way or the other?

That's the whole question. I'm not 100% sure.

I'd say if the default std::swap compiles for the type, then there is no reason not to provide a more efficient swap specialization. The only question for me would be in a case where the type is not assignable/copy constructible. Then you might want to have a compile error instead of a non O(1) swap. But given that the default std::swap can in reality already have arbitrary complexity, depending on the complexity of a type's assignment/copy constructor, I don't see much value in producing a compile error. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFIY7Xf5vihyNWuA4URArlXAKDFqOtlL14dwWbVODm2cKHv8N+KGACdGkKR a3I9hVHxt2AEl6iLLffROfE= =HMY+ -----END PGP SIGNATURE-----

On Thu, Jun 26, 2008 at 10:51 AM, David Abrahams <dave@boostpro.com> wrote:

But the efficiency is a different issue. It's like the same reason we don't provide random access for list iterators: operator++ on an iterator is supposed to be fundamentally O(1) (notwithstanding filter_iterator -- how do you measure /that/?!)

I am inclined to agree that a fast swap for array is useful and thus should be provided, but I still have a nagging doubt about whether it's "the right thing to do." Maybe I've been brainwashed by a certain disciple of Alex Stepanov's, because nobody else seems to share that doubt... so feel free to ignore me if you're unconvinced.

I think the problem here is that you are talking about a swap operation being a strictly O(1) operation and therefore there shouldn't be an array swap because it would have to be O(n), but the actual underlying problem is that in the context of a generic swap, at least in the sense of std::swap, there simply _is_no_ "n" to even be talking about in a meaningful sense. When working with the STL, we get into the habit of assuming that "n" is always the size of a range we are dealing with and the reason we can do that is because those algorithms are required to be working over a range. In that context, "n" is the size of the range. Again, we are able to do this because being passed a range is a requirement of these algorithms and a range must always have a size. However, in the context of std::swap, this is not the case. std::swap has no requirement that what you pass is some type of container or range. As Neils pointed out earlier: "For a particular template instantiation of boost::swap, for a particular type of arrays, the number of element swaps would be constant. Doesn't that make it O(1)?" What he is saying is perfectly fine because "n" was never appropriately defined before it was decided that swap must be an O(1) operation as opposed to an O(n) operation. So in the general sense, how do you define "n" here? Remember that std::swap may be used with types other than containers (ints, floats, pods, etc.). If you want to state the complexity of a general algorithm, then any variables you refer to (i.e. "n") have to be expressible in terms of the concept requirements of that algorithm. In the context of most STL algorithms we use "n" to mean the size of the range we are operating over, but we can only do that because it is required that a range is passed to those algorithms. With respect to the general concept of a swap, there is no such requirement and so it doesn't make sense to define "n" in that manner. A quick example -- what is the complexity of the swap operation here: _________________________________________________ struct complex_type { /**/ }; struct a { complex_type b, c, d; } left, right; swap( left, right ); _________________________________________________ You would probably say O(1), but then what is the complexity of the same swap done here (assume the above definition of a): _________________________________________________ BOOST_FUSION_ADAPT_STRUCT( a, (complex_type,b)(complex_type,c)(complex_type,d) ) swap( left, right ); _________________________________________________ Did the complexity of the general swap operation now change to O(n) simply because we adapted the struct to be a fusion sequence of size n? No. The fact that it is a sequence is meaningless with respect to the general idea of the swap operation. It's true that because we are using a fusion sequence we can now say "the swap operation in this context is O(n) where n is equal to the size of the fusion sequence being passed," but that doesn't mean that it's an O(n) swap in the general sense of the swap operation because "n" simply has no meaning in the general sense of std::swap. Because of this, I see absolutely no reason why std::swap should not be defined for arrays and boost::array, at least with respect to complexity. -- -Matt Calabrese

on Sun Jun 29 2008, David Abrahams <dave-AT-boostpro.com> wrote:

Matt Calabrese wrote:

...

I think the problem here is that you are talking about a swap operation being a strictly O(1) operation and therefore there shouldn't be an array swap because it would have to be O(n), but the actual underlying problem is that in the context of a generic swap, at least in the sense of std::swap, there simply _is_no_ "n" to even be talking about in a meaningful sense. When working with the STL, we get into the habit of assuming that "n" is always the size of a range we are dealing with and the reason we can do that is because those algorithms are required to be working over a range. In that context, "n" is the size of the range. Again, we are able to do this because being passed a range is a requirement of these algorithms and a range must always have a size.

However, in the context of std::swap, this is not the case. std::swap has no requirement that what you pass is some type of container or range. As Neils pointed out earlier:

"For a particular template instantiation of boost::swap, for a particular type of arrays, the number of element swaps would be constant. Doesn't that make it O(1)?"

What he is saying is perfectly fine because "n" was never appropriately defined before it was decided that swap must be an O(1) operation as opposed to an O(n) operation. So in the general sense, how do you define "n" here?

It's proportional to the memory footprint of the data values that, after the swap is complete, must to be accessible as part of the opposite argument from the one from which they were accessible befpre the swap. You might look for swap in Stepanov's March 1995 Dr. Dobb's interview if that helps.

Oh, and see http://www.stepanovpapers.com/DeSt98.pdf Cheers, -- Dave Abrahams BoostPro Computing http://www.boostpro.com

Joseph Gauterin wrote:

I've now moved utility/swap to the trunk.

Thank you, Joe! Hopefully it will be included with Boost release version 1.37 (before the end of the year, I guess). Your boost::swap function is essentially needed to get boost::array::swap fixed, and to implement a swap function for wrapper classes like boost::value_initialized. I'll make tickets on those issues. BTW, its test-suite isn't yet included with the regression page, http://www.boost.org/development/tests/trunk/developer/index.html While we added the test-suite to trunk/status/Jamfile.v2 (as suggested by David): utility/swap/test # test-suite utility/swap Is there anything else to do, to get utility/swap onto the regression page? Kind regards, Niels

Thanks for all your feedback, David, Frank, Steven, Howard, and Matt. I think it's safe to conclude that we agree by now that it's acceptable for boost::array to have a custom swap function, and that it would be acceptable for boost::swap to support built-in arrays. So I'll create a ticket, requesting built-in array support for boost::swap, referring to our discussion, and including a patch. It may be slightly unusual to create a ticket for an item that's still in the sandbox, but I guess it's the best I can do right now. I'll create two more tickets, for boost::array and boost::value_initialized: boost::array<T,N>::swap doesn't always use the custom swap of T, if there is one. And value_initialized<T> should have a custom swap overload as well. Both of these two issues can be solved very elegantly when boost::swap is patched, and moved from the sandbox to the trunk.

...

Within generic code, people typically use the well-known idiom to swap a pair of Swappable objects:

// Allow argument-dependent lookup to find a custom swap. using std::swap; swap(lhs, rhs);

As long as boost::swap hasn't come out of the sandbox, of course (hint)!

??

Once boost::swap is out, the "using std::swap" idiom doesn't need to be used anymore. My "hint" was just an attempt to draw the attention of anyone involved, hoping to get boost::swap out of the sandbox... It very much looks like it's ready for review, having documentation and tests included: http://svn.boost.org/svn/boost/sandbox/swap/ But I guess it very much depends on when Joseph Gauterin, the first author, has found the time... Kind regards, Niels

...

My "hint" was just an attempt to draw the attention of anyone involved, hoping to get boost::swap out of the sandbox. [...] But I guess it very much depends on when Joseph Gauterin, the first author, has found the time...

David Abrahams wrote:

If he hasn't, I'd be more than happy to stick it in the utility library.

I would very much appreciate if you'd do so. :-)

This facility, while perhaps more important, can't be much bigger than next and prior.

The current sandbox/swap/boost/utility/swap.hpp has only 38 lines of code! :-) Of course, adding array support would take a few more lines: Ticket 2056 - https://svn.boost.org/trac/boost/ticket/2056 Fortunately, when applying the patch that I attached to the ticket, swap.hpp would still have only 51 lines, just like next_prior.hpp :-) BTW, once boost::swap would be in the trunk, I'd probably have another feature request: Given the fact that current implementations of std::iter_swap and std::swap_ranges don't always call the custom swap function of the iterator's value_type, it would be helpful to have boost::iter_swap and boost::swap_ranges calling boost::swap. Moreover, such boost::iter_swap and boost::swap_ranges functions would support array types as value_type. :-) I think that <boost/utility/swap.hpp> would be an appropriate place for Boost versions of iter_swap and swap_ranges. Don't you think? Kind regards, Niels

Joseph Gauterin wrote:

Niels, I've taken a look at your patch, and it looks good.

Thanks :-)

There's an exception safety issue that I think is worth mentioning in the documentation: If the underlying swap function used is no-throw then boost::swap is no-throw, but if the underlying swap function provides the strong guarantee, then boost::swap only provides the basic guarantee for arrays of size > 1.

Good point! I'll add your note: https://svn.boost.org/trac/boost/attachment/ticket/2056/array_support_for_sa...

As for putting it on the trunk - it completely slipped my mind. I'm happy for boost::swap to move to the trunk - what kind of review process does it need to go through? Given that the new version is only 51 lines, a full review seems like overkill.

David already tried to move it to the trunk, as you may have read at <https://svn.boost.org/trac/boost/ticket/2056>: "I tried to move the sandbox and apply these patches, but the sandbox is at least missing something to link the documentation into the rest of the Boost docs, a Jamfile for testing, and an editorial pass over the docs (at least one glaringly incomplete sentence)." I guess Dave has overlooked https://svn.boost.org/svn/boost/sandbox/swap/libs/utility/swap/test/Jamfile.... (Right?) Certainly I did, because I haven't yet put my "swap_array.cpp" test in there. An editorial pass wouldn't harm: I spotted a few typo's at http://svn.boost.org/svn/boost/sandbox/swap/libs/utility/swap.html ("constuction", "guarentee"). I still think it would be nice to add a literature reference to the doc. I would suggest adding a reference to Scott Meyers, Effective C++ Third Edition, Item 25: "Consider support for a non-throwing swap". Do you know how to link the documentation into the rest of the Boost docs? Kind regards, Niels

On Jun 22, 2008, at 9:18 PM, David Abrahams wrote:

Niels Dekker - mail address until 2008-12-31 wrote:

...

...

...

Would it be okay to you if we would add support for array types to the Boost.Swap utility that is located in the sandbox?

David Abrahams wrote:

...

Whether or not this is a good idea depends on whether you think swap is fundamentally an O(1) and/or nonthrowing operation.

The array support I would like to add to boost::swap is non- throwing, as long as the array element type has a non-throwing swap.

Sure, but it is not O(1) no matter what the element type does.

O(1) is not as important as fast. For std::pair, std::tuple, std::array, and now built-in arrays, having a custom swap is considerably faster than using the default std::swap definition (which also is not O(1)). -Howard