The humble for loop in Rust
blog.startifact.com
blog.startifact.com
Yep, it's due to SIMD -- in the assembly for `using_map`, you can spot pcmpeqd, movdqu, and psubd, while `using_loop` doesn't have any of these.
let result: Vec<i32> = list.into_iter().map::<_, Box<dyn Fn...>>(Box::new(transform)).collect()
Rust further brings really nice ergonomics and comprehensive type inference to the equation, which makes it feel like writing C#/JS/whatever. JITted languages could detect and elide creating and immediately using a function pointer, but I don't think that any do.
Edit: these languages may not always allocate (specifically if nothing is captured in a closure), but the core concept remains: they erase the type, which means that they also erase the function body.
Java uses type erasure for generics. .NET uses generic monomorphization for struct-typed generic arguments and method body sharing with virtual/interface dispatch for class-typed generic arguments (the types are never erased).
Moreover, non-capturing lambdas do not allocate, and are also get speculatively inlined by the JIT behind a guard. It's a bit limited but works quite well in production applications. You can also write struct-based iterators in C#. The main limitation is lack of full HM type inference which means having less convenient API where you can't convince the compiler to infer the full type signature.
One of the current limitations of C# is that lambdas are of type Func<T1...Tn, TResult> - calls through them are virtual. So unless JIT emits a guarded devirt path - you cannot specialize over them like over Fns in Rust which are part of the monomorphized generic signature. Various performance-oriented libraries sidestep this by implementing "value delegate" pattern where you constrain an argument over an interface implementation of an invoke-like method. Basically doing the higher order functions via struct implementations.
Java here also deserves a mention because OpenJDK is capable of inlining of shallow streams - Stream API is moderately to significantly slower than LINQ but it's not terribly slow in absolute terms.
With all that, in the recent versions, LINQ has started encroaching on the territory of performance of Rust iterators especially on large sequences where access to faster allocations and heavy pooling of underlying buffers when collecting to an array or a list allow for very efficient hot paths. LINQ also does quite a bit of "flattening" internally so chaining various operators does not necessarily add extra layer of dispatch.
Lastly, F# is capable of lambda inlining together with the function accepting it at IL level at build time and does so for various iterator expressions like Array.map, .iter and similar. You access this via `inline` bindings and `[<InlineIfLambda>]`-annotated parameters. It is also possible to implement your own zero-cost-ish iterators with computation expressions. If JIT/ILC improves at propagating exact types through struct fields in the upcoming release, it will be able to inline F# lambdas even if expansion does not happen at IL level: https://github.com/dotnet/runtime/issues/110290
NB: auto-vectorization is extremely fragile even with LLVM and kicks in only in simple scenarios, the moment you have a side effect a compiler cannot reason about it stops working.
C# lambdas: although non-capturing lambdas do not allocate, capturing lambdas do. "calls through them are virtual" is due to the underlying implementation of delegates in .NET.
For what it's worth - the real issue in C# is not even the virtual calls but the way Roslyn caches lazily allocated non-capturing lambda instances. It does so in a compiler-unfriendly way due to questionable design decisions inside Roslyn.
Luckily, this has a high chance of changing in .NET 10. Ideally, by the time it releases hopefully the compiler will both understand the Roslyn's pattern of caching better and be able to stack-allocate non-escaping lambda closure instances.
Lambdas capturing 'this' inside instance methods of the object they refer to do not allocate either.
using_map is faster because it's not allocating: it's re-using the input array. That is, it is operating on the input `v` value in place, equivalent to this:
pub fn using_map(mut v: Vec<i32>) -> Vec<i32> {
v.iter_mut().for_each(|c| *c += 1);
v
}
vec_of_u32.into_iter().map(f32::from_bits).collect()Never worked in Rust though so wondered if the iterator api had some weird optional notion of size that could be utilised throughout the chain.
Fwiw, this does exist: [Iterator::size_hint] (https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...)
[0]: https://github.com/rust-lang/rust/blob/master/tests/codegen/...
[1]: https://github.com/rust-lang/rust/blob/d4025ee454169fbd22f57...
Um, yes it is, extensively?
SpecFromIterNested is a specialization trait for alloc::vec::Vec's FromIterator which handles both the TrustedLen and ordinary Iterator scenarios
For an ordinary Iterator, it calls next() once to check this Iterator isn't done, if it's done, we can just give back a Vec::new() since that's exactly what was needed. Otherwise, it then consults the hint's low estimate, and it pre-allocates enough capacity on that basis, unless it's lower than Vec's own guess of the minimum worthwhile initial capacity.
For Iterators which impl TrustedLen (ie promise they know exactly how many items they yield) it instead checks the upper end of the hint, to see if it's None, if it is the iterator knows it's too big to store in memory, we should panic. Otherwise though we can Vec::with_capacity
let v: Vec<_> = (0..23456).collect();
Sorry, that was a mistake on my part. I did not see it explicitly in any of the code. Thank you for pointing out in detail where the stdlib uses this.
It looks like the code does exactly the same thing and something the optimizer could catch. Is is because of potential side effects? If not, maybe there is a ticket to open somewhere, if it isn't done already.
FromIterator is the trait that the collect method uses.
Specialization isn’t a stable feature in Rust, but is used extensively in the standard library.
list_of_lists.into_iter().fold(Vec::new(),
|mut accumulator, list| {
accumulator.extend(list);
accumulator
}
)Furthermore, I'd use with_capacity in both cases: Vec::with_capacity(list_of_lists.iter().map(|l| l.len()).sum())
For loop does weird things there. It can be used as a flat map as it can iterate over multiple iterators at once and yield a value for each combination.
What's bitten me so far multiple times is that when you iterate over a Set or a Map the result of for expression is also a Set or a Map.
But since you have access to keys during iteration then some iterations, if they return same map key or same set value, might get silently overwritten by others.
I don't remember having this problem in Rust because there I had to be very intentional about iterators.
The other thing that bit me was that arithmetic on Int overflows silently, but that's apparently a Java thing, which made me wonder how is Java an enterprise language.
Otherwise Scala 3 is superb expeirience. Syntax is ultra-flexible and local extensibility of everything and access to things from the context of where your code is defined and even from the context where it's running is magical.
keep in mind that "for loops" are really "for comprehensions" and desugae into flatMap/map
1. The comparisons, as you've written them up, probably will get stale fast. It would be nice to be able to re-run them.
2. Some of the examples are surprising. Why? Any bugs? Some kind of weirdness? Readers would want to explore.
3. Readers can see how you did the benchmarks. We can put more/less stock in them. Hopefully you used `criterion` or similar, with warm ups, etc.
`.map(...)` implies "I don't care about ordering, and therefore you don't need to, either", freeing the compiler to schedule the loops in a more optimal order, or in parallel or with SIMD, or any other optimization that lets it get the job done as fast as possible. I'm sure someone will come up with an example, but I can't personally think of any way where a for-loop's semantics would let a clever compiler write faster code than the equivalent map.
Also, streams operate on objects, so they have to be on the heap. You can't use them with primitives on the stack. Though with autoboxing, the JVM may play some tricks with a list of Integer objects really being primitives on the stack, but I would never count on it.
As for SIMD, Java isn't going to parallelize anything automatically. You need to tell it you run the steam in parallel which will split it into threads. Java doesn't have lightweight threads like coroutines.
I know lightweight threads are on the roadmap and maybe available in Java 21 or newer. I know real closures have been considered, but I don't if it's gone anywhere. It's hard to do a quick search because we got "closures" in Java 8 so theres a lot of noise.
And as a caveat, I am most familiar with Java 17 (and older). I expect we'll look at moving to Java 21 (current LTS) next year.
Sometimes, if the Java JIT manages to inline absolutely everything, it can optimize away these overheads. But in practice, Rust FP gets optimized a lot more reliably than Java FP.
In Rust a closure is really just a struct that implements up to three closure traits, each of which provide a single function. So from that side of things, what Java is doing for them isn't inherently different from Rust.
In plenty of languages, no such implication exist. `map` can be specified to run in a certain order.
But `FnMut` is the most general possible thing you can pass in. In reality, most callbacks are pure functions that don't alter mutable state at all. With Rust's monomorphization and aggressive inlining, LLVM can figure out that there's no mutation going on and can optimize that.
There is a wrinkle here, which is that capturing variables mutably is one of two ways a function can have side effects in Rust. The other way is via interior mutability, through UnsafeCell [1], or, more commonly, a wrapper around it like Mutex or RefCell. In that case as well, Rust guarantees that function calls to map are done in order. Luckily, because UnsafeCell is the root of all interior mutability, the compiler can simply track whether an UnsafeCell is transitively involved.
If you're wondering where the humble `print!` comes in -- well, it clearly has side effects. But it acquires a global lock on standard output each time it's called [2], so UnsafeCell is involved.
[1] https://doc.rust-lang.org/std/cell/struct.UnsafeCell.html
C# and Javascript are the ones that I know of for sure.
I find it slightly difficult to read when the accumulator variable actually has multiple parts, like a complicated tuple. It's worse when part of the accumulator is a bool indicating whether it's finished; that's just a poor emulation of "break" in a for loop.
let string = "ewfsan";
let bitset = string.bytes().fold(0u32 |acc, ch| acc | 1 << (ch - b'a'));
Of course if you have never seen a syntax before it will make less sense that anything you have seen before
The other direction is more interesting to me: Those are the awkward cases where people sometimes overdo it with the functional iterator heavy style.
I think Ruby has some kind of feature that works like that but IIRC it looked less foot-gun more foot-bazooka. Does anyone know of any languages that solve that problem elegantly?
An early attempt at a solution (2022) was provided by https://blog.rust-lang.org/inside-rust/2022/07/27/keyword-ge...