ACP: add bool::select

[orlp]

Proposal

Problem statement

It is a common theme in performance-oriented programming to want to select between two outcomes, but without changing which code runs as this invokes branch prediction. Branch prediction is great when it works but has two downsides:

1. It can be significantly slower than branchless code if the branch is unpredictable, like in sorting random data.
2. It can have inconsistent performance (even if faster on average), which can be a deal-breaker in latency-sensitive applications.

Currently in Rust if you want to have a good chance of something being branchless you have to write your code in a particular way, and even then it regularly fails to compile to branchless instructions, depending on the mood of the compiler.

Motivating examples or use cases

There are tons of examples, I don't think I have to convince anyone familiar with performance-sensitive code of its use. Binary searches, sorting, filtering of data based on a condition, the applications are nearly endless. In performance-sensitive code, if you write an if where both sides of the if are cheap to evaluate and the condition is not 99%+ consistent there's a good chance a branchless select statement would be faster.

And of course there is the consistency argument even if the branch is 99%+ consistent in most cases, for example audio DSP code might want to ensure a kernel is always consistent in its speed to prevent audio crackling when a rare sequence of unpredictable samples come along, or high-frequency trading code may want to ensure it always has a response in a certain amount of nanoseconds.

Solution sketch

I propose we add the following method to the bool primitive type:

/// Selects one of two values based on the value of self.
///
/// Unlike an `if` statement both arguments are always evaluated. The compiler
/// will try to emit machine code that avoids control flow for this selection,
/// taking the same amount of time regardless of whether self is true or false.
const fn select<T>(self, true_val: T, false_val: T) -> T;

This interface is similar to the std::simd::Mask::select API, just for one value.

Alternatives

There is the select_unpredictable intrinsic. However, it is an intrinsic so it should not really be used. There is no viable alternative, even writing things such as [false_val, true_val][cond as usize] can and do get rewritten by the compiler to branches, or just generate plain terrible code. One can reach for inline assembly but this pessimizes surrounding code and is not portable.

As for bikeshedding about the name, I considered the following alternatives, in order of preference:

• select_predicated (see predication)
• select_eager
• select_branchless
• select_unpredictable (as the intrinsic was named)

However, I prefer just the simple select. I think the fact it always eagerly evaluates both arguments (as functions do) is already self-documenting enough to readers to show it is not a control flow structure, but rather a selection operator between two pre-computed values. I think it is fairly natural that this then in turn compiles to a branchless select, even when simply reading cond.select(a, b).

My reason for not favoring the current name of the intrinsic select_unpredictable is that (in my opinion) it confuses a problem with the solution. This can lead to confusing scenarios where the solution is applicable but the problem is not, e.g. someone could make an informed choice to use select_unpredictable while the boolean condition is in fact predictable - they just wanted consistency or avoid conditional jumps for other reasons.

Links and related work

• select_unpredictable

[the8472]

This shouldn't go on the bool type itself. It's more something fit for the std::hint module

[orlp]

@the8472 It's not a hint, it's an actual computation - selecting between two values. In fact if you read my ACP a bit more carefully you'll notice I'm trying to move away from the concept of 'unpredictability' in the API completely, which is the only thing that could be hinted about in the first place.

[workingjubilee]

std::hint is not std::intrinsics by a different name, and this is not quite proposing to expose the LLVMIR metadata that select_unpredictable emits directly.

[chorman0773]

I'd assume this would be allowed to generate a branch if no other codegen option exists.

[ChrisDenton]

It does seem a bit weird to have this as a method on bool. Maybe some code examples would change my mind but it feels too niche to not be a separate function or a wrapper type.

[orlp]

I'd assume this would be allowed to generate a branch if no other codegen option exists.

Yes, the description should probably be expanded to explicitly mention this isn't a hard guarantee (even if compiling on a platform that has, e.g. cmov) and that it should not be relied upon for e.g. constant-time cryptography code.

[the8472]

Which then sounds like merely a hint to codegen...

[workingjubilee]

in the same sense that unchecked_add is, I suppose?

[the8472]

You have a point. But I'm not convinced yet. Unlike in SIMD llvm does have optimizations that turns cmovs into branches. So there's a difference between computing two values, picking one and then maybe the compiler transforms it depending on what it thinks is profitable and explicitly telling the compiler that you know better.
simd Mask::select doesn't have that because simd generally doesn't do branch prediction (maybe some stuff inside GPUs does?)

[chorman0773]

None of the functions in core::hint have any actual runtime behaviour (unreachable_unchecked and assert_unchecked are either UB or no-ops, black_box is an identity function, and spin_loop is a no-op). bool::select would have actual behaviour, so it definitely doesn't belong in core::hint.

[kennytm]

The proposed API does not fit into std::hint. However one could introduce it actually like a hint as

if std::hint::unpredictable(boolean) {
    true_value
} else {
    false_value
}

This should be "optimized" to core::intrinsics::select_unpredicatable if both true_value and false_value can be inlined and side-effect-free so that evaluating both branches is beneficial¹. This mirrors clang's __builtin_unpredictable intrinsic. Additionally, like __builtin_unpredictable it can be extended to support

match std::hint::unpredictable(integer) {
    0 => a,
    1 => b,
    3 => c,
    9 => d,
    27 => e,
    _ => etc,
}

OTOH in rust-lang/rust#120370 core::intrinsics::{likely, unlikely} are being reimplemented in terms of cold_path() because the intrinsics were broken, departing from hinting the condition and instead hinting the branches.

According to the LLVM docs the !unpredictable metadata are supposed to "be attached to any branch or switch instruction", so it may be better aligned with LLVM to spell it as

#[unpredictable]
if boolean { true_value } else { false_value }

#[unpredictable]
match integer { _ => etc }

Footnotes

1. unfortunately LLVM will lose the !unpredictable metadata if we simply define std::hint::unpredictable(boolean) as core::intrinsics::select_unpredicatable(boolean, true, false), but this may be just an LLVM bug. ↩

[orlp]

@kennytm If true_value or false_value have side-effects such as panics (which could be implicit, e.g. writing v[0]) or have invisible potential side-effects since it contains a non-inlined function call, you'd need to write

let true_value = true_expr;
let false_value = false_expr;
#[unpredictable]
if boolean { true_value } else { false_value }

otherwise the Rust compiler is not allowed to write it using eager evaluation + a cmov/csel.

I'd really much rather just write

boolean.select(true_expr, false_expr)

which much closer matches my intent. The whole point of select and branchless programming in general is that there is no control flow (if possible), and a construct using if is very much the wrong way to express this in my opinion.

The fact that the API bool::select always eagerly evaluates both arguments is by-design, and crucial. That is the fundamental property of control-flow free programming: evaluate both options and use indexing, arithmetic, cmov, csel, etc to select the result you want. It's not just a hint, it's a programming paradigm.

[workingjubilee]

@kennytm

According to the LLVM docs the !unpredictable metadata are supposed to "be attached to any branch or switch instruction", so it may be better aligned with LLVM to spell it as

That documentation is incorrect and outdated. It does in fact work on select. There is considerable code to propagate it and numerous tests to assure it survives the infamous "cmov-to-branch" pass. It is possible the test coverage is not comprehensive enough, but that's compiler bugs for you.

• https://github.com/llvm/llvm-project/blob/main/llvm/lib/CodeGen/CodeGenPrepare.cpp#L7395
• https://github.com/llvm/llvm-project/blob/main/llvm/lib/IR/IRBuilder.cpp#L1056
• https://github.com/llvm/llvm-project/blob/ac5a2010ad35a72de3e75a1883e2495345b92a73/llvm/test/CodeGen/X86/x86-cmov-converter.ll#L359-L430