Re: [boost] Re: Boost Array: read/write access to entire data

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2002-11-06 14:21:34

----- Original Message -----
From: "Gennaro Prota" <gennaro_prota_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Wednesday, November 06, 2002 2:36 PM
Subject: [boost] Re: Boost Array: read/write access to entire data

> On Wed, 6 Nov 2002 11:52:21 -0300, "Fernando Cacciola"
> <fernando_cacciola_at_[hidden]> wrote:
>
> >
> >----- Original Message -----
> >From: "Gennaro Prota" <gennaro_prota_at_[hidden]>
> >To: <boost_at_[hidden]>
> >Sent: Wednesday, November 06, 2002 8:13 AM
> >Subject: [boost] Re: Boost Array: read/write access to entire data
> >
> >
> >> On Tue, 5 Nov 2002 18:22:22 -0300, "Fernando Cacciola"
> >> <fernando_cacciola_at_[hidden]> wrote:
> >>
> >> >I also think it is useful for the case when you have more than one
object
> >> >and you don't know how to perform a (no throw) move/swap of those
> >objects.
> >> >That is, if you have:
> >> >
> >> >T[0]
> >> >T[1]
> >> >...
> >> >
> >> >How do you implement no-throw swapping without a transacted approach
(so
> >> >that you can rollback state in case of an exception)?
> >> >
> >> >The double buffer would allow you to have no-throw swap in the array
even
> >> >if you don't have it in the objects themselves.
> >>
> >>
> >> Well, I'm not sure what you are trying to say. BTW I couldn't find the
> >> details of construct_as. Are you saying that it doesn't use the copy
> >> constructor? Otherwise I don't see how the tecnique achieves a
> >> *no-throw* swap: either the copy constructor is nothrow itself and
> >> thus the tecnique is not needed, or it throws and the tecnique only
> >> gives you the strong guarantee. Or am I missing something?
> >>
> >> Genny.
> >>
> >OK. I'll try to explain it better.
>
> It's better that I explain it better too :-) I was commenting on your
> phrase "would allow you to have a _no-throw_ swap". The original code
> I've seen is:
>
>   [code snipped]
>
OK, my fault.
I wasn't thinking of directly using  StrongStorage<T>...
I was thinking of borrowing its idea, so I meant that using some variation
of the double-buffer technique, you could achieve no-throw. Though I should
have said so explicitely, sorry.

>
> Now, as I said, I DO NOT have the code of construct_as () because I
> haven't found it in any place, but if it uses copy construction (as I
> suppose) and if the copy may throw then that swap cannot provide the
> nothrow guarantee. We agree on that, I think. Now let us see other
> points:
>
You are right here, construct_as(), which is in "aligned_storage.hpp" in the
sandbox, uses the copy ctor, so StrongStorage<T>::swap is not designed as
no-throw.

> >The double buffer technique allows you to skip the expensive save/restore
> >mechanism required for the rollback of a 'traditional'
> >no-throw/strong-guarantee implementation. That is:
> >In our case, we have an array of fixed size which is not allocated in the
> >heap, so we can't use the address of the memory block used by the array
> >itself for swapping.
> >Schematically, this would be something like the following (showing only
the
> >relevant parts):
> >
> >// [UNTESTED CODE BELOW]
> >template<class T, size_t N>
> >struct FixedArray
> >{
> >  FixedArray() : p_(storage_.address()) {}
> >
> >  void swap(FixedArray&);
> >
> >  typedef aligned_storage<sizeof(T)*N> storage_t ;
> >  storage_t storage_ ;
> >  T* p_ ;
> >} ;
> >
> >Now, let's consider a swap() with strong guarantee (not a no-throw swap,
> >yet)
> >
> >template<class T, size_t N>
> >FixedArray<T,N>::swap ( FixedArray<T,N>& rhs )
> >{
> >   save_a_copy_of_the_current_state_without_throwing();
>
> How do you do that? Do you use memcpy? If so you are in UB land
> (though it will usually work)
>
Precisely... I don't know how to do that :-)
That's why I put the pseudo-code, because what know is *what* to do :-)
(anyway, this part would be expensive but possible: use the copy ctor upon
uninitialized temporary storage, in a protected code block. If this copy
fails, then the rest of the swap must be aborted, either throwing or not
depending on the guarantees we want for our swap. In any event, this far the
state is preserved since we only tried to copy into a temporary storage)

> >   try
> >   {
> >     using std::swap ;
> >     for ( size_t i = 0 ; i < N ; ++ i )
> >       swap(p_[i],rhs.p_[i]); // THIS MAY THROW
>
> This must be just an oversight. Weren't you thinking to p_ as the
> pointer to the array in the free store case?
>
No. It was intended to be the pointer to the stack allocated array. It
shouldn't have been a member, though.

>
> >   }
> >   catch(...)
> >   {
> >      restore_previous_state_without_throwing();
>
> Same note, of course.
>
OK. Since I've actually cheated by showing what should be done instead of
how to do it, I've noticed that this couldn't possible work AFAICT. This
restore, unlike the save, not only should not throw but also succeed: i.e:
copy back all elements without failure.

> >      throw;
> >   }
> >}
> >
> >A no-throw swap would be essentially the same except that exception
possibly
> >thrown by the T's swap are eaten.
> >
> >Do we agree that the above is the minimun 'traditional' implementation?
>
> It depends. Don't make me say that :-) Once you are in the catch and
> you have swapped N/2 objects...
>
Before we get into the details of the double buffer, let me try to put my
thoughts into perspective.
We have an Array class which has two internal arrays: one dynamically
allocated and another automatically allocated.
If I am understanding the design correctly, at any time, only one of these
internal arrays represents the state of the Array.
If it is the dynamic array, then swap is not a problem since we just swaps
pointers. That's easy.
But what if the automatic array is the one currently active?
How would you implement swap() and which exceptions guarantees would you
achieve?
-- please answer here --

Now, without the double buffer, my only answer to the question above *would*
be the 'traditional' implementation I've shown. However, even that doesn't
work because the restore cannot be made to succeed, AFAICT, in the presence
of throwing copy ctor.

So, since *I* do not have a clue about how to implement a swap with at least
strong guarantees without the double buffer, I propose it.
However, you or someone else might know how to do the same without this
complicated scheme (and without relying on the presence of a no-throw T's
swap). In that case, though, I will love to hear about it.

> >
> >Now, let's see how the double buffer could be used:
> >
> >// [UNTESTED CODE BELOW]
> >
> >template<class T, size_t N>
> >struct FixedArray
> >{
> >  FixedArray() : idx_(0) {
> >storage_initialized_[0]=storage_initialized_[1]=false;}
> >
> >  void swap(FixedArray&);
> >
> >  T* data() const { return storage_[idx_].address() ; }
> >
> >  typedef aligned_storage<sizeof(T)*N> storage_t ;
> >  storage_t storage_[2] ;
> >  bool storage_initialized_[2];
> >  int idx_ ;
> >} ;
> >
> >
> >template<class T, size_t N>
> >FixedArray<T,N>::swap ( FixedArray<T,N>& rhs )
> >{
> >   // NO NEED FOR SAVING STATE BEFORE.
> >   try
> >   {
> >     // (1) Copy active storage in rhs to mirror storage here
> >     int mirror_idx = (idx_+1)%2;
>
> Yep :-) I commented that you could have written
>
>       int mirror_idx = 1 - idx;
>
> but then I saw your pre-increments below and I understood.
>
> >     T* lhs_mirror  = storage_[mirror_idx].address() ;
> >     T* rhs_source = rhs.storage_[rhs.idx_].address() ;
> >     for ( size_t i = 0 ; i < N ; ++ i )
> >     {
> >       if ( storage_initialized_[mirror_idx] )
> >         lhs_mirror->~T();
>
> Who says you that you can invoke the destructor on all the N elements?

This code is destructing the element which has been previously stored in the
'mirror' storage. That is, this is not the element which is currently
contained in the Array. IOWs, this element will exist only if there was a
swap being made before. (*anyway, more on this later, because this confused
you since it's actually plain wrong!)

> I think the destruction must be done at the moment you know you have
> constructed, say, i elements and the construction of the (i+1)-th
> failed. In that case you call the destructor on the first i.
>
Without a double buffer, destructing the 'contained' elements would achieve
*some* result: the Array would be reset to 'empty' upon an exception.
As a user, I would prefer if the swap could leave Array unchanged if failed.

> [snipped]
>
> I understand that. But, as you showed, if
>
>   new(lhs_mirror++) T(*rhs_source++);
>
> does throw then swap throws too. Which was my point.
>
But you can contain this throw from the copy-ctor and try to do something
with the state of the previously swaped  elements.
AFAICT, you can't completely restore the state of the previously swapped
elements using a single buffer, so your best bet is to destroy them so as to
at least leave the Array in some consistent state.

(*1)
I've noticed that the code I've posted, which was out of my head, had a
peculiar behaviour:

In the first swaps, new elements (from rhs) where copied into the 'second'
storage, BUT the previous elements were kept in the first storage alive.
Silly!!
That's why during the swap, it first destroys the elements before copy them
into the will-be-active storage. Even more silly!!
The correct code would just destroy all objects from the first storage (not
active anymore) after all the elements were copied into the second storage.
(for both Arrays)

Fernando Cacciola

>
> Genny.
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>
>