Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The humble for loop in Rust

blog.startifact.com

Post reply on HN
Print view View original

31–40 of 60 posts

Re: The humble for loop in Rust

#31

Post by Lvl999Noob »

aidos wrote: post #6
nemo1618 wrote: post #4

> Why is map so much faster? I am not sure. I suspect with the map() option the Rust compiler figures out it can avoid allocations altogether by simply writing over the original vector, while with the loop it can't. Or maybe it's using SIMD? I tried to look in the compiler explorer but I'm not competent enough yet to figure it out. Maybe someone else can explain! Yep, it's due to SIMD -- in the assembly for `using_ma…

Ah thanks! I was going to ask in here to see if anyone knew because the explanation about overwriting the same vector seemed pretty off base. 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.

If I recall correctly, there was actually some unstable specialisation in the std library that allowed reusing the backing storage if you do an `into_iter()` and then a `collect()`.

Re: The humble for loop in Rust

#32

Post by orf »

CrendKing wrote: post #27

Maybe I'm dumb, but I can't see how the code in the "Errors and map" section can compile. "transform_list" returns a Result , yet "result" is just a Vec. I thought you always need to wrap it with Ok()? Is that a new nightly feature?

No, it seems like an oversight in the code sample. It should be wrapped in Ok()

Re: The humble for loop in Rust

#33

Post by kstrauser »

dhosek wrote: post #20

It’s interesting to note that performance of a for loop versus the functional-style mechanism varies by language. On Java, there is a performance penalty (possibly shrunken since Java 8) for using the FP idioms while in Rust, they end up much faster.

That surprises me, and I'd expect the FP version to be at least as fast, with the option to be much faster. With the for loop, you're saying "run against this value, then run against the next one, then run against the next one, then...". If the compiler isn't certain that the iterations aren't free of side effects, then it would have to run each one in order before moving on to the next.

`.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.

Re: The humble for loop in Rust

#34

Post by mijoharas »

IshKebab wrote: post #17

Yeah I kind of wish there was a way to still use `?` inside map/filter/etc. lambdas. Error handling with that functional style is generally way more awkward than for loops, but also it's often more elegant in other ways (e.g. Rayon). 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?

What's the ruby feature you're referring to?

Re: The humble for loop in Rust

#35

Post by skitter »

ridiculous_fish wrote: post #19
nemo1618 wrote: post #4

> Why is map so much faster? I am not sure. I suspect with the map() option the Rust compiler figures out it can avoid allocations altogether by simply writing over the original vector, while with the loop it can't. Or maybe it's using SIMD? I tried to look in the compiler explorer but I'm not competent enough yet to figure it out. Maybe someone else can explain! Yep, it's due to SIMD -- in the assembly for `using_ma…

SIMD is true, but the original guess is correct, and that effect is bigger! 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 ) -> Vec { v.iter_mut().for_each(|c| *c += 1); v } This is a particularly fancy optimization that Rust can perform.

This can even turn the following code into a no-op:

    vec_of_u32.into_iter().map(f32::from_bits).collect()

Re: The humble for loop in Rust

#36

Post by neonsunset »

zamalek wrote: post #21
nemo1618 wrote: post #4

> Why is map so much faster? I am not sure. I suspect with the map() option the Rust compiler figures out it can avoid allocations altogether by simply writing over the original vector, while with the loop it can't. Or maybe it's using SIMD? I tried to look in the compiler explorer but I'm not competent enough yet to figure it out. Maybe someone else can explain! Yep, it's due to SIMD -- in the assembly for `using_ma…

It's not only because of SIMD. Contrasted to many other languages (though not all) the compiler is working with code here, not an arbitrary function pointer. In essence, JS and the like are operating with this: let result: Vec = list.into_iter().map:: >(Box::new(transform)).collect() Rust is able to inline the transform code right into the loop, which then becomes available for SIMD etc. Rust further brings really ni…

JS, Java and C# have vastly different implementation details each.

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 - 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 `[]`-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.

Re: The humble for loop in Rust

#37

Post by varikin »

kstrauser wrote: post #33
dhosek wrote: post #20

It’s interesting to note that performance of a for loop versus the functional-style mechanism varies by language. On Java, there is a performance penalty (possibly shrunken since Java 8) for using the FP idioms while in Rust, they end up much faster.

That surprises me, and I'd expect the FP version to be at least as fast, with the option to be much faster. With the for loop, you're saying "run against this value, then run against the next one, then run against the next one, then...". If the compiler isn't certain that the iterations aren't free of side effects, then it would have to run each one in order before moving on to the next. `.map(...)` implies "I don't…

Streams (FP in java) is slower than for loops for a couple reasons. A big one is java doesn't natively support real closures or lambdas. It does have syntax for them, but that is just syntactic sugar for an class with a single method under the hood. So streams end up doing lot of object allocation and garbage for the fake closures.

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.

Re: The humble for loop in Rust

#38

Post by kstrauser »

varikin wrote: post #37
kstrauser wrote: post #33

Earlier quoted context omitted.

That surprises me, and I'd expect the FP version to be at least as fast, with the option to be much faster. With the for loop, you're saying "run against this value, then run against the next one, then run against the next one, then...". If the compiler isn't certain that the iterations aren't free of side effects, then it would have to run each one in order before moving on to the next. `.map(...)` implies "I don't…

Streams (FP in java) is slower than for loops for a couple reasons. A big one is java doesn't natively support real closures or lambdas. It does have syntax for them, but that is just syntactic sugar for an class with a single method under the hood. So streams end up doing lot of object allocation and garbage for the fake closures. Also, streams operate on objects, so they have to be on the heap. You can't use them w…

Huh, interesting. Thanks for that! Today, I learned.

Re: The humble for loop in Rust

#39

Post by recursive »

kstrauser wrote: post #33
dhosek wrote: post #20

It’s interesting to note that performance of a for loop versus the functional-style mechanism varies by language. On Java, there is a performance penalty (possibly shrunken since Java 8) for using the FP idioms while in Rust, they end up much faster.

That surprises me, and I'd expect the FP version to be at least as fast, with the option to be much faster. With the for loop, you're saying "run against this value, then run against the next one, then run against the next one, then...". If the compiler isn't certain that the iterations aren't free of side effects, then it would have to run each one in order before moving on to the next. `.map(...)` implies "I don't…

> `.map(...)` implies "I don't care about ordering, and therefore you don't need to, either"

In plenty of languages, no such implication exist. `map` can be specified to run in a certain order.

Re: The humble for loop in Rust

#40

Post by tialaramex »

c0balt wrote: post #13
ironhaven wrote: post #12

Earlier quoted context omitted.

Yep that can be used for pre allocating the Vec like in the `with_capacity` example

That's not accurate, it can be used while consuming an Iterator and, depending on the implementation, be used to guide the consumer during runtime. The stdlib likely is not doing this but the API very much allows advanced behavior. We, e. G., used this for some part of a query engine in a course in uni to guide algorithm choice for operators.

> The stdlib likely is not doing this

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();
... will just give you a Vec with the 23456 values from zero to 23455 inclusive, it won't waste time growing that Vec because it knows from the outset that there are going to be exactly 23456 items in the Vec.
Post reply on HN