algo pred copies

[Nathan Myers]

On 5/16/26 6:49 AM, Jonathan Wakely wrote:
> On Sat, 16 May 2026 at 11:13, Jonathan Wakely <jwakely@redhat.com> wrote:
>>
>> On Sat, 16 May 2026 at 09:16, Nathan Myers <ncm@cantrip.org> wrote:
>>>
>>> I have been looking over algorithm predicate copying.
>>> We are forced to do one copy on entry, regardless.
>>> We get a choice when passing them along to helper fns.
>>
>> We've discussed this several times over the years, going back and
>> forth over the options. Passing by reference is a pessimization in
>> some cases, so it's not clear that it's a win to make that change.
> 
> One of the key points is that the cost of copying the predicate is
> usually only paid once (per "layer" of the algo), whereas the cost of
> an extra dereference to invoke it happens on every call to the
> predicate. We expect to copy it fewer times than we invoke it.
After it has called the predicate, it doesn't know if the
referent has changed, so it has to reload registers from
L1 cache. If it has a local copy and no pointers to it
have leaked, it doesn't.

Compilers must have got better at distinguishing use
of 'this' from pointers leaking.

> I think we can switch from passing by value via copies to passing by
> value via moves without any concerns. It would only be a
> pessimizations for pathologically dumb objects that have expensive
> moves and cheap copies. But switching to passing by reference would
> need a lot of profiling for different cases, testing each algorithm
> with different predicates and different element types to see what
> benefit passing by reference has.
In my tests, GCC 15 did a bunch of copies and a bunch of
moves. 16 does just the (same number of) copies, but
not the moves. We may hope many of those will turn into
moves.

So to get very specific...

We have to take the top-level argument by value, which might
have been moved into.

The helper functions that actually invoke the predicates
should also take them by value, but they should be passed
there by move.

Any intermediate helper not calling a predicate should
take by lvalue-reference and pass by forwarding.

If a predicate must be passed to more than one helper, we
can either copy to all but the last, or pass to them by
move and get it back again by RVO.

> Libc++ already did some of that analysis (IIRC they currently pass
> predicates around via reference_wrapper):
> https://github.com/llvm/llvm-project/issues/129312
> They found that using reference_wrapper wa hurting them, although
> specifically in the context of an internal "desugars_to" helper, which
> I don't know anything about. It might only hurt in that context
> because they didn't handle that case in their desugars_to helper.
> 
> https://github.com/llvm/llvm-project/pull/133097#issuecomment-2770212647
> "I think we should have a general discussion on whether we want to
> continue forwarding everything instead of just moving the objects
> before making a big refactoring."