C++ Logo


Advanced search

Re: Questions + bikeshed for reorderase

From: Patrice Roy <patricer_at_[hidden]>
Date: Wed, 20 Sep 2023 17:49:58 -0400
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 21:50:11