Programming is a huge pile of layered abstractions that we can often (but not always) ignore.
Whether we like it or not, abstractions leak.
An incomplete list of those abstractions:
I want to talk more about the programming language → instructions abstraction that is provided by a combination of language design and compilers.
Of course we have seen
A lot of what we have said about assembly and
Notable differences: most other languages don't have the concept of raw pointers (i.e. where you can add to the pointer and explore elsewhere in memory), or manual free/delete because they're too hard to get right.
Overall interactions with the processor should be similar to C/C++: same machine instructions, pipelines, branch predictor, etc.
This is particularly true when your code is ahead-of-time compiled to machine code. Typical in Rust, Fortran, Go. Sometimes in Julia. The details of the language and the compiler's optimizer are going to affect performance, but the processor is fundamentally the same.
Many languges are typically compiled to bytecode, a low-level representation of your logic, but not machine code that runs on any actual processor.
e.g. Java to JVM bytecode ; Scala to JVM bytecode ; Python to Python bytecode ; but possibly also C to LLVM bytecode .
That bytecode is then executed (≈interpreted) by a virtual machine that can run that bytecode quickly.
VMs typically have some performance penalty over native machine code, but it can be surprisingly little. Often because…
A VM can also just-in-time (JIT) compile the bytecode to machine code at runtime. If all goes well, a JIT can get basically the same performance as ahead-of-time compiled machine code.
e.g. JavaScript in your web browser, Python in PyPy or Cinder, Java and the common JVMs, PHP and HHVM, the .NET CLR.
One language I want to say a few things about: Rust. Rust is designed to be fast and compiled to machine code.
We'd expect performance similar to C compiled under clang: both use the LLVM (Low-Level Virtual Machine) compiler framework. Both first compile to LLVM IR (Intermediate Representation, a bytecode), which is then optimized and compiled to machine code.
These are idiomatic ways to sum a vector in Rust:
pub fn vec_sum_method(values: &Vec<f32>) -> f32 {
values.iter().sum()
}
pub fn vec_sum_fold(values: &Vec<f32>) -> f32 {
values.iter().fold(0.0, |a, b| a + b)
}
The
is an anonymous function: a function that takes two arguments (|a, b| a + ba, b) and returns a+b.fold() method expresses use this function to combine values in an accumulator
.
Those get the same performance as (non-vectorized) C or C++. The compiler is capable of transforming these into the same loop we wrote by hand in assembly or the compiler wrote from our C for loop.
Every time I write
in C, I die a little inside. I don't care about loop counters or indexing arrays: I want to combine my array values with addition. That's exactly what this expresses.for(i=0; i<len; i++)
values.iter().fold(0.0, |a, b| a + b)
If we don't care about the order of the additions, Rust can express addition but assume it's associative and commutative
with the (not yet stabilized) algebraic_add method:
pub fn vec_sum_algebraic(values: &Vec<f32>) -> f32 {
values.iter().fold(0.0, |a, &b| a.algebraic_add(b))
}
Or we can give explicit SIMD operations with the (not yet stabilized) std::simd module.
pub fn vec_sum_simd(values: &Vec<f32>) -> f32 {
let chunks = values.iter().copied().array_chunks();
let v: f32x8 = chunks.clone().map(f32x8::from_array).sum();
let tail: f32 = chunks.into_remainder().sum();
v.as_array().iter().sum::<f32>() + tail
}
Or with the fearless_simd crate (which should work on any architecture):
#[inline(always)]
fn fearless_sum<S: Simd>(simd: S, values: &Vec<f32>) -> f32 {
let chunks = values.chunks_exact(S::f32s::N);
let tail: f32 = chunks.remainder().iter().sum();
let partials = chunks
.into_iter()
.map(|c| S::f32s::from_slice(simd, c))
.fold(S::f32s::splat(simd, 0.0), |a, b| a + b);
partials.as_slice().iter().sum::<f32>() + tail
}
pub fn vec_sum_fearless(values: &Vec<f32>) -> f32 {
let level = Level::new();
dispatch!(level, simd => fearless_sum(simd, values))
}
If we convince Rust to auto-vectorize, we get the same performance as hand-written SIMD assembly, or vectorclass, or C with -funsafe-math-optimizations.
RUSTFLAGS='-C target-cpu=haswell' cargo run --release
Looking at the way they're compiled , we'd expect the same performance as C or assembly.
Or do it in multiple threads with Rayon's ParallelIterator:
pub fn vec_sum_parallel(values: &Vec<f32>) -> f32 {
values
.par_iter()
.copied()
.reduce(|| 0.0, |a, b| a.algebraic_add(b))
}
Or run some benchmarks with Criterion.
RUSTFLAGS='-C target-cpu=haswell' cargo bench
It runs your code several times to check for variability in runtime and produces an HTML report.
for LoopCompare the simplest way to do the vector sum in Rust with the equivalent to what I'd write in C
version:
pub fn vec_sum_fold(values: &Vec<f32>) -> f32 {
values.iter().fold(0.0, |a, b| a + b)
}
pub fn vec_sum_indexed_loop(values: &Vec<f32>) -> f32 {
let mut total = 0.0;
for i in 0..values.len() {
total += values[i];
}
total
}
I don't care about almost all of the code in the for loop version.
for LoopI'm not actually interested in accumulators or loop counters or the order of the additions. I only really care about using + to combine values, starting at zero.
let mut total = 0.0;
for i in 0..values.len() {
total += values[i];
}
Everything else in that code is noise. I hate it so much.
for LoopWe now know that it's worse than that: the for loop forces us to specify the order of the additions. Even if we don't care, which I don't in most for loops.
To access SIMD instructions, the compiler must unwind our meaning, transform our code into a different loop (if it's allowed), then implement that with SIMD operations. On simple code it might, on more complex code it might not.
for LoopSo why are we writing code we don't want to write to specify details that are work actively against good compilation of our code?
My conclusion: the for loop we have been writing forever is the wrong abstraction.
for LoopThe care to don't care
ratio is much better in the iterator version:
values.iter().fold(0.0, |a, b| a + b)
The Rust iter().fold() does specify the order of the additions (combines elements in a left-associative fashion
) but Rayon's does not: I should be careful about what I'm asking for.
My second conclusion: the right abstraction for almost every for loop I have ever written was some kind of do this to each element
abstraction. An iterator or similar.
C doesn't provide one. Most textbooks don't introduce them (early) in languages where they do exist. Many programmers don't know to look for them.
A more complex list processing task: sum the squares of only positive elements. The for-loop version, at least using a foreach style, not a counter:
pub fn sum_positive_squares_for(values: &Vec<f32>) -> f32 {
let mut total = 0.0;
for v in values {
if *v > 0.0 {
total += v * v;
}
}
total
}
With the Rust iterator style, take your pick:
pub fn sum_positive_squares_iter(values: &Vec<f32>) -> f32 {
values
.iter()
.filter(|&&v| v > 0.0)
.map(|v| v * v)
.sum()
}
pub fn sum_positive_squares_iter2(values: &Vec<f32>) -> f32 {
values
.iter()
.filter_map(|&v| if v > 0.0 { Some(v * v) } else { None })
.fold(0.0, |a, b| a + b)
}
Or as a Python programmer, I could choose between:
total = 0.0
for v in values:
if v > 0.0:
total += v*v
total = sum(v*v for v in values if v > 0.0)
I would expect the second to be significantly faster.
Also: Java Streams; std::algorithm, std::accumulate, std::ranges.
Nobody writing SQL worries that they haven't specified the exact order of additions.
SELECT SUM(value*value) FROM data WHERE value > 0;
I could make a similar statement for Pandas, Spark, CUDA kernels, functional languages, … .
Why should I be forced to give so much unnecessary detail and fight the compiler?
We have been trained to think of the for loop as a concept so core to programming that we can't imagine programming without it.
But it doesn't allow us to express our thoughts in a way that map to the most efficient instructions on modern processors. One-at-a-time processing is rarely what we want from definite iteration.
Look for a higher-level and more clear way to express yourself.