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@gmail.com> 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@lists.isocpp.org> 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@lists.isocpp.org> 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@lists.isocpp.org> 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@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/sg14
_______________________________________________
SG14 mailing list
SG14@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/sg14

_______________________________________________
SG14 mailing list
SG14@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/sg14
_______________________________________________
SG14 mailing list
SG14@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/sg14