sg14

From: Pedro Oliveira <ei06125_at_[hidden]> · Date: Wed, 16 Mar 2022 09:11:34 +0000

---
Pedro Oliveira
t: +351 916 175 642
m: pedro.andre.oliveira_at_[hidden]
Mestrado Integrado em Engenharia Informática e Computação (MIEIC)
Faculdade de Engenharia da Universidade do Porto (FEUP)
On Tue, Mar 15, 2022 at 11:25 PM <sg14-request_at_[hidden]> wrote:
> Send SG14 mailing list submissions to
>         sg14_at_[hidden]
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         https://lists.isocpp.org/mailman/listinfo.cgi/sg14
> or, via email, send a message with subject or body 'help' to
>         sg14-request_at_[hidden]
>
> You can reach the person managing the list at
>         sg14-owner_at_[hidden]
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of SG14 digest..."
>
>
> Today's Topics:
>
>    1. Re: Colony/hive & unordered vs ordered == operator
>       (Jake Arkinstall)
>    2. Re: Colony/hive & unordered vs ordered == operator (Henry Miller)
>    3. Re: Colony/hive & unordered vs ordered == operator
>       (Ville Voutilainen)
>    4. Re: Colony/hive & unordered vs ordered == operator (Matt Bentley)
>    5. Re: Colony/hive & unordered vs ordered == operator (Matt Bentley)
>    6. Re: Colony/hive & unordered vs ordered == operator (Nevin Liber)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Tue, 15 Mar 2022 09:23:49 +0000
> From: Jake Arkinstall <jake.arkinstall_at_[hidden]>
> To: sg14_at_[hidden]
> Subject: Re: [SG14] Colony/hive & unordered vs ordered == operator
> Message-ID:
>         <CAC+0CCPL_c8zmcEGj-+P_0pF5win=
> vt6_NDWsyvLfL5WAp_tiw_at_[hidden]>
> Content-Type: text/plain; charset="utf-8"
>
> On Tue, 15 Mar 2022, 03:59 Matt Bentley via SG14, <sg14_at_[hidden]>
> wrote:
>
> if anyone
> here has any opinions about whether ==/!=/<=> is useful on the container
> level (ordered or unordered), please chime in.
>
>
> I cannot think of any use I'd have of such comparisons, except for niche
> cases where I'd happily just iterate (e.g. tests).
>
> Based on that, and that alone, I'd go for the no built-in comparison route
> for now, with the option of adding one later if a solid use case comes
> along.
>
> That is, unless a plan involves storing some composable hash in each block
> (customising by template args might give the user choice of
> ordered/unordered comparisons? Not sure on that one, just spitballing), in
> which case ABI prevents the later change.
> -------------- next part --------------
> HTML attachment scrubbed and removed
>
> ------------------------------
>
> Message: 2
> Date: Tue, 15 Mar 2022 08:45:14 -0500
> From: "Henry Miller" <hank_at_[hidden]>
> To: "Ben Craig via SG14" <sg14_at_[hidden]>
> Subject: Re: [SG14] Colony/hive & unordered vs ordered == operator
> Message-ID: <52f958bc-0054-4d3d-bc58-2c0e694f79df_at_[hidden]>
> Content-Type: text/plain
>
> The  more I think about this the more convinced I become that hive should
> not have operator== at all.
>
> First of all: put on your "I just got my CS degree and have been doing C++
> for 2 weeks" hat:  intuitively I expect operator== is O(n).  That it is
> instead O(n lg n) is an unpleasant surprise.  Sure we can say it is in the
> documentation, but I hate documenting something unexpected without good
> reason. I also think SG20 (education) needs to approve such documentation
> as they need to teach it. C++ has enough surprises. (for completeness I'll
> say that only allowing == when O(n) sort applies seems obviously
> unacceptable)
>
> If there is an operator == it must be ordered! Nothing in the standard
> guarantees that hive<int> {1,2, 3} == hive<int> {1,2, 3}  if == is
> unordered.  While that is an unlikely case, if you assume two hives with
> exactly the same operations performed on them, but in different
> translations units, then it is possible the implementation has changed
> between them while still being ABI compatible, and because of inlining
> different algorithms were used to add/remove/shrink_to_fit... I think we
> want to preserve the freedom of implementors to change their algorithm and
> thus unordered operator== cannot exist lest changing algorithms break
> existing code, or force on our vendors ABI break style upgrades for
> internal algorithm changes.
>
> Ordered operator==  is a lot more complex. Is operator== const, non-const,
> or both?
>
> Const means that it is allocating memory someplace for the sort and thus
> has weird memory behavior. operator== that can throw an out_of_memory
> exception is surprising.  Worse, the sorted result - which may be useful is
> thrown away.  It seems to me that someone who wants == is probably going to
> do a number of them in nearby code places often without any other
> operations.  Thus we should encourage the explicate copy of the container
> (possibly to a vector): the memory is going to be allocated anyway, so
> making it clear that a copy happens seems better to me and the only cost is
> one extra line of code.
>
> non-const is weird.  It invalidates iterators: I think many who were on
> the "whatever" side of this debate will be firmly against this one for that
> reason.  SG20 needs to be consulted on this one as well.  There are other
> surprise related to operator== mutating the container as well, I think they
> are all places where you could have used an iterator but didn't.
>
> non-const also means you cannot compare const hives - this is another
> place where C++ would be surprising and bring out  more blog posts about
> how C++ is a bad language.
>
> Both means you have you get different behavior in different situations -
> and this seems bug prone.  In C++98 getting a const_iterator from a
> non-const container was ugly and rarely done correctly - we will get
> similar complaints about it being hard to get the correct == from a
> non-const hive.
>
> If someone makes a good argument that they want to compare hive, then it
> should be with functions that make the behavior clear.
> Sort_and_compare_hives, Compare_sorted_hives (with a contract that it is
> sorted), and maybe others.  You can bike shed those names, but they make it
> clear what is happening and thus reviewers can debate if the right choice
> was made, while == will be something reviewers will skip over without
> realizing it is important (unless they have been burned).
>
> We probably should clean up the above arguments and put them directly into
> the paper (an appendix) so that they are easy to find in 10 years when this
> comes up again.
>
> --
>   Henry Miller
>   hank_at_[hidden]
>
> On Mon, Mar 14, 2022, at 19:20, Matt Bentley via SG14 wrote:
> > Hi Everyone,
> > quick question:
> > colony/hive is unordered in terms of insertion position (but sortable),
> > should the ==/!= operator also be unordered ie.
> > should hive<int> {1,2, 3} == hive<int> {3, 1, 2}?
> >
> > My main interest is not which is more 'correct' but which is more useful
> > in practice?
> > I don't use == operator for containers a lot so I don't know.
> > Be aware this will affect >= < etc also.
> >
> > The unordered version of the operator is trivial, but slower -
> > it allocates pointers to each of the elements in each of the containers,
> > then sorts the pointers via the values they point to, then does a
> > standard == left-hand/right-hand compare via the pointers.
> > This means (a) == allocates, (b) == is slower due to jumping around in
> > memory and not necessarily following element sequence.
> >
> > Opinions?
> >
> > BTW lewg hive discussion next week, for those who are a part of lewg
> > already.
> > m@
> > _______________________________________________
> > SG14 mailing list
> > SG14_at_[hidden]
> > https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>
>
> ------------------------------
>
> Message: 3
> Date: Tue, 15 Mar 2022 16:41:45 +0200
> From: Ville Voutilainen <ville.voutilainen_at_[hidden]>
> To: sg14_at_[hidden]
> Subject: Re: [SG14] Colony/hive & unordered vs ordered == operator
> Message-ID:
>         <
> CAFk2RUbSPAAsfA0kof_5ZbjHcorLDyN8-1q3hBC+mwQ64f1LBQ_at_[hidden]>
> Content-Type: text/plain; charset="UTF-8"
>
> On Tue, 15 Mar 2022 at 15:45, Henry Miller via SG14
> <sg14_at_[hidden]> wrote:
> >
> > The  more I think about this the more convinced I become that hive
> should not have operator== at all.
>
> Agreed. My rationale is thus:
>
> - I would think two hives are equal if they contain the same bees
> - that's an unordered operation, because hive is unordered
> - yeah, sure, a hive is ordered if you don't remove and re-add bees,
> because their positions-once-inserted-but-not-removed in the hive
> are stable, but that's a stretch of the semantics, if you ask me; all
> use cases of hive, as far as I understand
> them, are geared for scenarios where the user must not care about the
> order of the hive, just that it either
> does or does not contain a particular bee.
>
> Then we get to the semantics and cost of the unordered equality
> comparison, and we come to the conclusion
> that it's perhaps something that shouldn't be provided as an equality
> operator at all. The need to allocate memory
> instantly calls for domain-specific customizations, and to cater for
> those we need a function anyway, and we should
> perhaps standardize such functions only if we find really really
> common ones that many users need.
>
> I'm quite at loss what ordering comparisons on a hive would mean,
> again because the high-level operational semantics
> of a hive are unordered, so they don't make sense as something that
> should be provided via a spaceship, either.
>
> Summa summarum: just drop the comparison operators.
>
>
> ------------------------------
>
> Message: 4
> Date: Wed, 16 Mar 2022 11:54:36 +1300
> From: Matt Bentley <mattreecebentley_at_[hidden]>
> To: sg14_at_[hidden]
> Subject: Re: [SG14] Colony/hive & unordered vs ordered == operator
> Message-ID: <22055e0c-4fd0-3a6d-c4f6-9f13e21a446f_at_[hidden]>
> Content-Type: text/plain; charset=UTF-8; format=flowed
>
>
>
> On 15/03/2022 10:23 pm, Jake Arkinstall via SG14 wrote:
> > I cannot think of any use I'd have of such comparisons, except for niche
> > cases where I'd happily just iterate (e.g. tests).
>
> But in that case, there is a use for a comparison operator. Perhaps not
> a <=> operator, but certainly a comparison operator - and keeping ==
> prevents people from having to roll their own code.
>
>
> > Based on that, and that alone, I'd go for the no built-in comparison
> > route for now, with the option of adding one later if a solid use case
> > comes along.
> >
> > That is, unless a plan involves storing some composable hash in each
> > block (customising by template args might give the user choice of
> > ordered/unordered comparisons? Not sure on that one, just spitballing),
> > in which case ABI prevents the later change.
>
> That wouldn't really help with comparing across the entire container.
>
>
> ------------------------------
>
> Message: 5
> Date: Wed, 16 Mar 2022 12:05:24 +1300
> From: Matt Bentley <mattreecebentley_at_[hidden]>
> To: sg14_at_[hidden]
> Subject: Re: [SG14] Colony/hive & unordered vs ordered == operator
> Message-ID: <8ceac8e8-324c-bce6-8d8d-0c6f07a03e40_at_[hidden]>
> Content-Type: text/plain; charset=UTF-8; format=flowed
>
>
>
> On 16/03/2022 2:45 am, Henry Miller via SG14 wrote:
> > If there is an operator == it must be ordered! Nothing in the standard
> guarantees that hive<int> {1,2, 3} == hive<int> {1,2, 3}  if == is
> unordered.  While that is an
>
> Maybe I'm misunderstanding you, but as Arthur already mentioned,
> std::unordered_set has an unordered == operator. Which Does guarantee
> that hive<int> {1,2, 3} == hive<int> {1,2, 3}, as well as hive<int>
> {1,2, 3} == hive<int> {3,1, 2}.
>
>
> > Ordered operator==  is a lot more complex. Is operator== const,
> non-const, or both?
>
> It's not more complex, it's less complex. And unordered is only
> trivially more-complex than ordered. As mentioned, there is no sorting
> of container elements.
> It is still O(n), despite what some people have written here - it's just
> that there are 2 passes over n, rather than 1.
> Again I am more swayed by practical arguments than non-practical. So if
> anyone has any strong experience of using == comparisons in containers
> in general, please say your piece.
> Only insertion position is unordered in hive/colony - otherwise
> sequences don't change, and the container can be sorted as mentioned.
>
>
> > We probably should clean up the above arguments and put them directly
> into the paper (an appendix) so that they are easy to find in 10 years when
> this comes up again.
> >
>
> Probably a Good idea - but this will probably happen after LEWG (11am
> pacific time, 22nd).
>
>
> ------------------------------
>
> Message: 6
> Date: Tue, 15 Mar 2022 18:24:05 -0500
> From: Nevin Liber <nevin_at_[hidden]>
> To: sg14_at_[hidden]
> Subject: Re: [SG14] Colony/hive & unordered vs ordered == operator
> Message-ID:
>         <
> CAGg_6+NKUi1Pxau6KDGYqqAkPdbtXwh9VGEkPt-+W3Bn86guEw_at_[hidden]>
> Content-Type: text/plain; charset="utf-8"
>
> On Mon, Mar 14, 2022 at 7:20 PM Matt Bentley via SG14 <
> sg14_at_[hidden]>
> wrote:
>
> > The unordered version of the operator is trivial, but slower -
> > it allocates pointers to each of the elements in each of the containers,
> > then sorts the pointers via the values they point to, then does a
> > standard == left-hand/right-hand compare via the pointers.
> > This means (a) == allocates, (b) == is slower due to jumping around in
> > memory and not necessarily following element sequence.
> >
>
> My opinion is that it should have one, and if it does, the expectation is
> that it is unordered.
>
> For most containers (other than string), I rarely use its comparison
> operators, but when I need them, they are very handy.
>
> We are supposed to be designing a coherent standard library, and all the
> containers in the standard library are equality comparable.  This should
> not be a snowflake.
>
> How does the complexity compare with the complexity of
> unordered_multiset::operator==?
> --
>  Nevin ":-)" Liber  <mailto:nevin_at_[hidden] <nevin_at_[hidden]
> >>
> +1-847-691-1404
> -------------- next part --------------
> HTML attachment scrubbed and removed
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> SG14 mailing list
> SG14_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>
>
> ------------------------------
>
> End of SG14 Digest, Vol 39, Issue 8
> ***********************************
>