C++ Logo


Advanced search

Re: Questions + bikeshed for reorderase

From: Matthew Bentley <mattreecebentley_at_[hidden]>
Date: Thu, 21 Sep 2023 10:37:13 +1200
Cheers - but, to be clear there's nothing special to the
destructive_partition method, it's just whatever partitioning method you
choose (stable or unstable) with the swap removed and a move in it's place.
Whether or not it's really useful to anyone is unclear to me - since you're
left with moved-from elements at the end of your range, so I'm not clear
what you would do with them other than erasing them - in which case would
you not just use erase_if (stable or unstable variant)?
erase_if is just a reversed-predicate destructive_partition followed by
range erasure.

Certainly open to opinions there.

In terms of my partition code, it's really QoI stuff. So that much would
not be useful in a paper, but maybe destructive_partition, if people have a
use for it outside of erase_if.

On Thu, 21 Sept 2023 at 09:50, Patrice Roy <patricer_at_[hidden]> wrote:

> We'll put that in the paper if you're Ok with it. This sort of behavior
> makes it interesting to offer tool that has been optimized for the user's
> platform (client code stays stable). It seems to me to be an argument for
> standardizing the function.
> Le mer. 20 sept. 2023 à 17:39, Matt Bentley <mattreecebentley_at_[hidden]>
> a écrit :
>> Just as a follow-up,
>> I refined my benchmarks, and while my partition code works better on some
>> platforms, it's not consistent.
>> However, the destructive partitioning (move instead of swap) results are
>> good vs non-destructive, at (on average across different numbers of
>> elements up to 1000000) 2% faster for int, 8% faster for double and 40-byte
>> structs, 40% faster for 490-byte structs, ie. scales with type sizeof
>> and/or non-trivially-copyable status.
>> On 6/09/2023 11:43 am, Patrice Roy wrote:
>> These remarks make SG14 a fun place to be :) Thanks!
>> Le mar. 5 sept. 2023 à 19:03, Matt Bentley via SG14 <
>> sg14_at_[hidden]> a écrit :
>>> Thanks for that-
>>> it led me down a rabbithole where I realised I can improve upon the
>>> existing strategies used in std::partition across all of the 3 major
>>> vendors.
>>> Cheers-
>>> On 4/09/2023 2:17 pm, Edward Catmur via SG14 wrote:
>>> This is a pretty vague thought, but have you noticed the correspondence
>>> to the partition / stable_partition algorithms? partition is essentially a
>>> way to accomplish the swap part of a swap-and-pop, and stable_partition is
>>> more or less identical to remove_if, so it feels like maybe there should be
>>> an equivalent using move instead of swap that operates on iterators/ranges
>>> instead of containers, leaving two consecutive ranges where the first part
>>> contains the desired elements and the second is moved-from.
>>> Anyway, great work and thanks.
>>> On Sun, Sep 3, 2023, 18:06 Matt Bentley via SG14 <sg14_at_[hidden]>
>>> wrote:
>>>> Yeah there's a few issues, such as whether to support deques, but I
>>>> figured one thing at a time. Given lack of response, might be best to
>>>> discuss at next meeting.
>>>> Can't use swap in the name as mentioned - as no swaps occur.
>>>> Cheers for getting back to me.
>>>> On 4/09/2023 10:16 am, Patrice Roy wrote:
>>>> In PXXX, I put « Move-With-Last-Swap / Reorderase » for the moment and
>>>> we'll find a better name if needed (it's a bit early for that). I'd focus
>>>> on the technical issues initially, and feel LEWG's mood for the name.
>>>> Thanks!
>>>> Le jeu. 24 août 2023 à 20:07, Matt Bentley via SG14 <
>>>> sg14_at_[hidden]> a écrit :
>>>>> Hi all-
>>>>> as per the last meeting there was some support for putting forward a
>>>>> proposal for what I call reorderase (plflib.org/reorderase.htm) but
>>>>> is really just an iteration of the swap-and-pop idiom, optimized (no swap,
>>>>> just move) and extended to range-erase and std::erase_if/std::erase. See
>>>>> the page for more information.
>>>>> There was some discussion of this back in 2015 by Brent Freidman but
>>>>> he was focused on the erase_if equivalents - which're the worse-performing
>>>>> of the set.
>>>>> I have a few questions before putting a paper together, the first of
>>>>> which is bikeshedding. I'm pretty settled on the name 'move_pop', for
>>>>> reasons which will become clear, but I am open to suggestions. Please let
>>>>> me know what you think:
>>>>> Names which aren't appropriate:
>>>>> - I like portmanteau's but the standard doesn't, so I'm guessing
>>>>> 'reorderase' is out of the question; possibly unfair on non-english
>>>>> speakers.
>>>>> - Anything with 'swap' in it. Implies operations which do not
>>>>> occur, also implies allocation.
>>>>> - Anything with 'unstable' in it - in the case of the standard
>>>>> library the term 'unstable' is not defined or used, only the term 'stable'
>>>>> is defined. In addition the word has a bad connotation in terms of
>>>>> programs, and algorithms are assumed to be unstable by-default where
>>>>> 'stable' is not used in functions.
>>>>> - Anything long like 'unstable', 'disordered', 'unordered',
>>>>> 'reordering', etc; at least for the singular/range reorderase equivalents.
>>>>> They are expected to be commonly-used functions, so long is Bad. I don't
>>>>> mind a longer title on the erase_if/remove_if equivalent as this is
>>>>> expected to be less-frequently used.
>>>>> - Anything involving 'back' or 'front'. A deque would want to pop
>>>>> from the front if location == begin() or first == begin() (in
>>>>> reorderase(first, last)), and we would want the name to be
>>>>> consistent between deques and vectors/inplace_vectors (if we want to
>>>>> support deques).
>>>>> Potential names:
>>>>> - move_pop/move_and_pop (the standard currently has about 1 other
>>>>> function which uses _and_ but it seems an unnecessary elongation) - this is
>>>>> good enough, and short, and brings in the 'pop' association with being
>>>>> quick/O(1).
>>>>> - ...? Suggestions?
>>>>> - For an std::erase_if/std::erase equivalent, using the 'pop'
>>>>> thing won't work, as erase_if already does this (moves the stuff to the
>>>>> back, erases it). If we go with a remove_if-equivalent implementation
>>>>> instead of erase_if, pop also doesn't work because remove_if doesn't
>>>>> erase/pop anything. I'm leaning towards (assuming a remove_if equivalent
>>>>> member function instead of erase_if)
>>>>> 'unordered_remove_if'/'unordered_remove', or
>>>>> 'disordered_remove_if'/'disordered_remove'. I prefer the latter is it
>>>>> clearly implies that there *will be* a disruption of order in the
>>>>> use of this function.
>>>>> M@
>>>>> _______________________________________________
>>>>> SG14 mailing list
>>>>> SG14_at_[hidden]
>>>>> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>>>> _______________________________________________
>>>> SG14 mailing list
>>>> SG14_at_[hidden]
>>>> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>>> _______________________________________________
>>> SG14 mailing listSG14_at_[hidden]://lists.isocpp.org/mailman/listinfo.cgi/sg14
>>> _______________________________________________
>>> SG14 mailing list
>>> SG14_at_[hidden]
>>> https://lists.isocpp.org/mailman/listinfo.cgi/sg14

Received on 2023-09-20 22:37:55