Re: [PATCH] define auto_vec copy ctor and assignment (PR 90904)

[Richard Biener <richard.guenther@gmail.com>]

On Tue, Jun 8, 2021 at 5:26 AM Trevor Saunders <tbsaunde@tbsaunde.org> wrote:
>
> On Mon, Jun 07, 2021 at 02:34:26PM -0600, Martin Sebor wrote:
> > On 6/7/21 2:51 AM, Richard Biener wrote:
> > > On Thu, Jun 3, 2021 at 10:29 AM Trevor Saunders <tbsaunde@tbsaunde.org> wrote:
> > > >
> > > > On Wed, Jun 02, 2021 at 10:04:03AM -0600, Martin Sebor via Gcc-patches wrote:
> > > > > On 6/2/21 12:55 AM, Richard Biener wrote:
> > > > > > On Tue, Jun 1, 2021 at 9:56 PM Martin Sebor <msebor@gmail.com> wrote:
> > > > > > >
> > > > > > > On 5/27/21 2:53 PM, Jason Merrill wrote:
> > > > > > > > On 4/27/21 11:52 AM, Martin Sebor via Gcc-patches wrote:
> > > > > > > > > On 4/27/21 8:04 AM, Richard Biener wrote:
> > > > > > > > > > On Tue, Apr 27, 2021 at 3:59 PM Martin Sebor <msebor@gmail.com> wrote:
> > > > > > > > > > >
> > > > > > > > > > > On 4/27/21 1:58 AM, Richard Biener wrote:
> > > > > > > > > > > > On Tue, Apr 27, 2021 at 2:46 AM Martin Sebor via Gcc-patches
> > > > > > > > > > > > <gcc-patches@gcc.gnu.org> wrote:
> > > > > > > > > > > > >
> > > > > > > > > > > > > PR 90904 notes that auto_vec is unsafe to copy and assign because
> > > > > > > > > > > > > the class manages its own memory but doesn't define (or delete)
> > > > > > > > > > > > > either special function.  Since I first ran into the problem,
> > > > > > > > > > > > > auto_vec has grown a move ctor and move assignment from
> > > > > > > > > > > > > a dynamically-allocated vec but still no copy ctor or copy
> > > > > > > > > > > > > assignment operator.
> > > > > > > > > > > > >
> > > > > > > > > > > > > The attached patch adds the two special functions to auto_vec along
> > > > > > > > > > > > > with a few simple tests.  It makes auto_vec safe to use in containers
> > > > > > > > > > > > > that expect copyable and assignable element types and passes
> > > > > > > > > > > > > bootstrap
> > > > > > > > > > > > > and regression testing on x86_64-linux.
> > > > > > > > > > > >
> > > > > > > > > > > > The question is whether we want such uses to appear since those
> > > > > > > > > > > > can be quite inefficient?  Thus the option is to delete those
> > > > > > > > > > > > operators?
> > > > > > > > > > >
> > > > > > > > > > > I would strongly prefer the generic vector class to have the properties
> > > > > > > > > > > expected of any other generic container: copyable and assignable.  If
> > > > > > > > > > > we also want another vector type with this restriction I suggest to add
> > > > > > > > > > > another "noncopyable" type and make that property explicit in its name.
> > > > > > > > > > > I can submit one in a followup patch if you think we need one.
> > > > > > > > > >
> > > > > > > > > > I'm not sure (and not strictly against the copy and assign).  Looking
> > > > > > > > > > around
> > > > > > > > > > I see that vec<> does not do deep copying.  Making auto_vec<> do it
> > > > > > > > > > might be surprising (I added the move capability to match how vec<>
> > > > > > > > > > is used - as "reference" to a vector)
> > > > > > > > >
> > > > > > > > > The vec base classes are special: they have no ctors at all (because
> > > > > > > > > of their use in unions).  That's something we might have to live with
> > > > > > > > > but it's not a model to follow in ordinary containers.
> > > > > > > >
> > > > > > > > I don't think we have to live with it anymore, now that we're writing
> > > > > > > > C++11.
> > > > > > > >
> > > > > > > > > The auto_vec class was introduced to fill the need for a conventional
> > > > > > > > > sequence container with a ctor and dtor.  The missing copy ctor and
> > > > > > > > > assignment operators were an oversight, not a deliberate feature.
> > > > > > > > > This change fixes that oversight.
> > > >
> > > > I've been away a while, but trying to get back into this, sorry.  It was
> > > > definitely an oversight to leave these undefined for the compiler to
> > > > provide a default definition of, but I agree with Richi, the better
> > > > thing to have done, or do now would be to mark them as deleted and make
> > > > auto_vec move only (with copy() for when you really need a deep copy.
> > > > > > > > >
> > > > > > > > > The revised patch also adds a copy ctor/assignment to the auto_vec
> > > > > > > > > primary template (that's also missing it).  In addition, it adds
> > > > > > > > > a new class called auto_vec_ncopy that disables copying and
> > > > > > > > > assignment as you prefer.
> > > > > > > >
> > > > > > > > Hmm, adding another class doesn't really help with the confusion richi
> > > > > > > > mentions.  And many uses of auto_vec will pass them as vec, which will
> > > > > > > > still do a shallow copy.  I think it's probably better to disable the
> > > > > > > > copy special members for auto_vec until we fix vec<>.
> > > > > > >
> > > > > > > There are at least a couple of problems that get in the way of fixing
> > > > > > > all of vec to act like a well-behaved C++ container:
> > > > > > >
> > > > > > > 1) The embedded vec has a trailing "flexible" array member with its
> > > > > > > instances having different size.  They're initialized by memset and
> > > > > > > copied by memcpy.  The class can't have copy ctors or assignments
> > > > > > > but it should disable/delete them instead.
> > > > > > >
> > > > > > > 2) The heap-based vec is used throughout GCC with the assumption of
> > > > > > > shallow copy semantics (not just as function arguments but also as
> > > > > > > members of other such POD classes).  This can be changed by providing
> > > > > > > copy and move ctors and assignment operators for it, and also for
> > > > > > > some of the classes in which it's a member and that are used with
> > > > > > > the same assumption.
> > > > > > >
> > > > > > > 3) The heap-based vec::block_remove() assumes its elements are PODs.
> > > > > > > That breaks in VEC_ORDERED_REMOVE_IF (used in gcc/dwarf2cfi.c:2862
> > > > > > > and tree-vect-patterns.c).
> > > > > > >
> > > > > > > I took a stab at both and while (1) is easy, (2) is shaping up to
> > > > > > > be a big and tricky project.  Tricky because it involves using
> > > > > > > std::move in places where what's moved is subsequently still used.
> > > > > > > I can keep plugging away at it but it won't change the fact that
> > > > > > > the embedded and heap-based vecs have different requirements.
> > > > > >
> > > > > > So you figured that neither vec<> nor auto_vec<> are a container like
> > > > > > std::vector.
> > > > >
> > > > > That's obvious from glancing at their definitions.  I didn't go
> > > > > through the exercise to figure that out.
> > > > >
> > > > > >
> > > > > > I'm not sure it makes sense to try to make it so since obviously vec<>
> > > > > > was designed to match the actual needs of GCC.  auto_vec<> was added
> > > > > > to make a RAII (like auto_bitmap, etc.) wrapper, plus it got the ability
> > > > > > to provide initial stack storage.
> > > > >
> > > > > The goal was to see if the two vec instances could be made safer
> > > > > to use but taking advantage of C++ 11 features.  As I mentioned
> > > > > recently, creating a copy of a vec and modifying it changes it as
> > > > > well as the original (e.g., by changing a vec argument passed to
> > > > > it by value a function changes the actual argument in the caller).
> > > > > That's surprising to most C++ programmers.
> > > >
> > > > It can probably be improved now with c++11, but while very unfortunate
> > > > There is hard requirements on how vec works from existing code using it.
> > > >
> > > > > My conclusion from the exercise is that although some of the problems
> > > > > with vec can, and IMO should, be solved, making the heap-based one
> > > > > a well-behaved C++ 11 container will take considerable effort and
> > > > > is impossible for the embedded vec.
> > > >
> > > > Yes, fortunately things using embedded vec do not at all expect a c++
> > > > container, and so don't really mismatch it.  You probably should not be
> > > > creating them yourself unless you are creating a new object with an
> > > > embedded vector, and you probably don't want to do that.
> > > >
> > > > > >
> > > > > > > It doesn't seem to me that having a safely copyable auto_vec needs
> > > > > > > to be put on hold until the rats nest above is untangled.  It won't
> > > > > > > make anything worse than it is.  (I have a project that depends on
> > > > > > > a sane auto_vec working).
> > > > > >
> > > > > > So how does your usage look like?  I can't really figure who'd need
> > > > > > deep copying of a container - note there's vec<>::copy at your
> > > > > > discretion.
> > > > > >
> > > > > > > A couple of alternatives to solving this are to use std::vector or
> > > > > > > write an equivalent vector class just for GCC.
> > > >
> > > > imho one of the significant advantages to having our own datastructures
> > > > rather than using the standard library is the ability to have a
> > > > different API that is less constrained by history, and can make better
> > > > choices than standard containers like deleting operators that would
> > > > otherwise require deep coppies.  Though certainly they don't always live
> > > > up to that like the oversight here of not defining the copy / assignment
> > > > operators at all.  Perhaps there's an argument to be made for the
> > > > standard containers doing deep coppies that it makes the language easier
> > > > to use, but its not all that much easier than .copy(), if that's your
> > > > priority c++ probably isn't the right tool for the job, and I doubt it
> > > > makes sense for gcc in particular.
> > > >
> > > > > > As said, can you show the usage that's impossible to do with
> > > > > > the current vec<>/auto_vec<>?
> > > > >
> > > > > The test case in PR 90904 shows a trivial example.  More generally,
> > > > > using an auto_vec that depends on it being assignable (e.g., storing
> > > > > an auto_vec in another container like hash_map or auto_vec itself)
> > > > > is impossible.  Using a plain vec requires manual memory management
> > > > > and so is error-prone.
> > >
> > > Btw, I remember once trying to make hash_map<int, auto_vec<int, 1> >
> > > work which pre-dated C++11 allowance (but I found a much nicer,
> > > albeit non-"C++" solution using obstacks and linked lists .. heh).  That
> > > might work nowadays if we fix hash_map re-allocation to use
> > > std::move and add move CTORs to the auto_vec<int, N> template
> > > (I refrained from that when I added them to the , 0 specialization
> > > since even moving would mean moving quite some storage).
> >
> > hash_map relies on its elements being copy-assignable.  To avoid that
> > it needs to overload its put() member to take an rvalue reference and
> > forward the argument to the move ctor.  Those would be good changes
> > to make but they alone wouldn't make using a hash_map easy to use
> > with a move-only type because the move overload is only viable in
> > limited contexts.  E.g., it wouldn't make this common use case valid:
> >
> >   void f (hash_map<int, Moveable> &m, const Moveable &x)
> >   {
> >     m.put (1, x);
> >   }
> >
> > Sequences like vec (and auto_vec) rely on their elements having a copy
> > ctor and copy assignment to grow by inserting elements in the middle.
> > But similar to hash_map, using them also depends on being able to copy
> > the elements (e.g., call v.push_back(x) in the above).
>
> There's certainly work to do to make these types more than kinda sorta
> work with move only types, or for that matter copyiable types.  I think
> I've looked at a fair percentage of the vec consumers in gcc, and my
> sense is most of them probably could move the object into the vector,
> but most of the current ones are also storing trivially copiable data,
> so that may not be fair.  That said I also reguard it as a good thing
> that if you find yourself in a case like your f function above you need
> to consider if you should make a copy or if there is a better way to
> take ownership of the object and pass it to the vector, this is really
> just forcing you to make an explicit decision about what should happen,
> rather than leaving it to the compiler to decide.
>
> > In general, move semantics are a special case, an optimization, of copy
> > semantics.  There are use cases for moveable-only types but they're not
> > the default and they limit the usability of those types.
>
> While I suppose it in some sense is trivially true that a move is just a
> copy and destruction of the original object, I think there's a real
> semantic difference between copying the object and transfering ownership
> of it to something else.  Consider Rust's choices in this area with
> objects being default move only, and types with destructors only
> implementing the clone trait not copy.  Certainly Rust and C++ are
> different languages, but I think it works reasonably well for Rust, and
> its generally a good way to think about C++ too, but then I think a lot
> of the C++ that has any business being C++ should eventually become Rust
> so milage may vary.

I suppose some of the "confusion" around auto_vec and friends  (auto_vec
in particular) could have been avoided if we'd done auto<vec<..> > instead
and thus added a smart instance (not pointer) wrapper template that
deals with the RAII we wanted to add.  We definitely didn't want to make
vec<> a [lib]C++ style container - at least that was my understanding.

And yes, a large part of why we have custom data structures in GCC is
memory and time complexity of algorithms we use - what's usually
inefficient should simply be not available (without pain).

So at this point I'd support sprinkling the missing = deleted; copy/assign
methods around our containers.

Richard.

> Trev
>
>
>
> >
> > Martin
> >
> > >
> > > > Certainly deleting the copy constructor and assignment operator means
> > > > that you can't use them,  but can you show real code where it is a
> > > > significant imposition to have to call .copy() rather than using them?
> > > > Certainly its a little longer, but deep copies are a bit of a
> > > > performance footgun, especially when you have vectors linear in the size
> > > > of the function all over, and your goal is to be no worse than
> > > > O(N log(N)), meaning you can copy the vector at most log(N) times at
> > > > worst.
> > > >
> > > > I would think storing move only objects in auto_vec and hash_* should
> > > > work, and if it doesn't should be fixable without introducing overly
> > > > easy ways to make deep coppies.
> > > >
> > > > > But more important, as a C++ code base, GCC should follow the best
> > > > > practices for the language.  Among the essential ones are using RAII
> > > > > to manage resources and the Rule of Three (or Five in C++ 11): a class
> > > > > that defines a dtor should also define a copy ctor and copy assignment
> > > > > (and move ctor and move assignment in C++).
> > > >
> > > > When discussing the rule of 3/5 at least
> > > > https://en.cppreference.com/w/cpp/language/rule_of_three considers
> > > > deleting the member to be a form of definition, see the part about non
> > > > copiable members and deleting both copy constructor and assignment, in
> > > > this case to make the class move only.  Strictly speaking, I suppose its
> > > > true that an array of 10k items is copiable, but its also very likely
> > > > something to be avoided if at all possible, and doesn't need to be made
> > > > easy.
> > > >
> > > > Trev
> > > >
> > > > >
> > > > > Martin
> >