algo pred copies

[Jonathan Wakely]

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.

But making each caller pass it to the next algo using std::move(pred)
should have no negative impact, only positive.

For empty and trivially copyable predicates, it makes no difference
(we'll do a trivial copy anyway).
For heavyweight objects, a move should be cheaper than a copy, e.g.
moving std::function is cheap whereas copying might allocate
(depending on the size of the target callable it holds).
For reference counted objects, a move is cheap, there are no ref count
increments and decrements.



>
> 1. Empty predicate
>
> Here, it doesn't much matter how it is passed. Passing by
> reference, we pass around a pointer in a register, but
> never dereference it. Either way, it takes up an argument
> slot.
>
> 2. Small predicate
>
> The predicate fits in a register, and is rule-of-zero so
> it can live in registers. Passing by reference might seem
> slow because you need to dereference it, but all instances
> fit in the same word in cache, and a copy in a register
> may be used many times. Inlining means it doesn't need to
> be loaded again across those call transitions.
>
> It will tend not to be evicted. The main cost might be
> register pressure hanging onto the pointer, too, so it can
> be passed along, but the real work tends to happen in leaf
> functions where that can be recognized as dead if the
> referent doesn't spill.
>
> 3. "Big" predicate
>
> At some point it is more expensive to copy than to
> dereference a pointer to a common object. Moving it is as
> expensive as copying. More important, each copy burns
> precious cache. You want to pass those by reference. Users
> have been motivated to avoid making them.
>
> 4. Refcounted
>
> One way they do that is to refcount-pimpl them. When the
> predicate is a pimpl passed by value, algorithms may spend
> much of their time incrementing and decrementing refcounts.
> ABI means such objects must be passed via a pointer on the
> stack, regardless of size. So those want to go by reference,
> too.
>
> 5. Move-mostly
>
> In principle they could pass predicates that can be moved
> cheaply. They still have to be copied once. Passing by move
> burns the source object, so the helper would have to return
> the value for further use, another move. They still get
> passed by pointer because ABI. So, you want to pass those
> by reference no matter how cheap moving them ought to be.

For the large number of algos where we implement std::foo in terms of
some std::_foo or std::__foo_aux, the predicate is used exactly once,
to pass to the next "layer" of the implementation. There's no concern
about use-after-move, and no need to return the predicate back to the
caller.

There are some algos where the predicate is used more than once, e.g.
it calls the a std::__foo_impl in a loop. In that case, the predicate
shouldn't be moved. Maybe those ones would benefit from passing by
reference, or maybe we just shouldn't change those ones.

> 6. reference_wrapper
>
> Smarter users pass a std::ref. If we pass that by reference,
> using it involves an awkward double dereference. I could
> see having a line at the top of each public function to
> unwrap some known types like reference_wrapper<T> or the
> unfortunate optional<T&>, so we can pass naked T& instead.
>
> Concluding, it seems like the only place where passing by
> value wins is with empty and small rule-of-zero objects,
> and there the difference is small. It is hard to describe
> a case where passing by reference really loses.

Passing by value and using std::move might not be 100% optimal in all
cases, but it should never be *worse* than what we do now. It will be
a strict improvement.