algo pred copies

[Nathan Myers]

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.

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.

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.