[HN Gopher] The humble for loop in Rust
___________________________________________________________________
The humble for loop in Rust
Author : todsacerdoti
Score : 54 points
Date : 2024-12-12 20:10 UTC (2 hours ago)
(HTM) web link (blog.startifact.com)
(TXT) w3m dump (blog.startifact.com)
| mden wrote:
| Anyone have examples where fold leads to easier to read code than
| a for loop in Rust?
| Mond_ wrote:
| I find `foo.iter().map(|x| x.bar()).collect()` almost always
| easier to read and better at expressing intent than a for loop.
|
| The other direction is more interesting to me: Those are the
| awkward cases where people sometimes overdo it with the
| functional iterator heavy style.
| ironhaven wrote:
| I have used fold for converting strings to a bitset in advent
| of code let string = "ewfsan"; let
| bitset = string.bytes().fold(0u32 |acc, ch| acc | 1 << (ch -
| b'a'));
|
| This is a idiom that I have used many times so this being more
| consice than a for loop is a plus
|
| Of course if you have never seen a syntax before it will make
| less sense that anything you have seen before
| bippihippi1 wrote:
| afair I've mostly only used fold when doing maths not covered
| by the standard sum or product. Fold is similar to map reduce
| but it's just one expression.
| kccqzy wrote:
| Readability is subjective. I personally find fold almost always
| more readable than a for loop when the accumulator variable has
| a simple type. This is because merely seeing fold can already
| telling me several things: it will iterate over the entire
| collection without early exits like "break" in a loop; the data
| dependency between each iteration is made clear into a single
| variable.
|
| 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.
| underdeserver wrote:
| Without looking too much at the generated assembly in
| https://godbolt.org/z/fKEPaTdTv, it seems that using_map uses
| SIMD instructions (movdqu and psubd) in the main loop, while
| using_loop doesn't, so that could indeed explain the performance
| difference.
| nemo1618 wrote:
| > 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_map`, you can
| spot pcmpeqd, movdqu, and psubd, while `using_loop` doesn't have
| any of these.
| aidos wrote:
| 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.
| c0balt wrote:
| > 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...)
| hedgehog wrote:
| It seems `map` should have less restrictive semantics
| (specifically ordering) than `for`, does that allow more
| optimization? I don't know much about Rust internals.
| ironhaven wrote:
| Reading the godbolt it looks like for the push loop llvm
| is unable to remove the `grow_one` capacity check after
| every push. Becaue of this the Vec could possibly
| reallocate after every push meaning it can't auto
| vectorize.
| mastax wrote:
| It's a little bit surprising to me that LLVM can't
| eliminate the grow_one check. It looks like there's a
| test ensure it's not needed in the easier case of
| vec.push(vec.pop()) [0]. With the iterator the
| optimization is handled in the standard library using
| specialization and TrustedLen[1].
|
| [0]: https://github.com/rust-
| lang/rust/blob/master/tests/codegen/...
|
| [1]: https://github.com/rust-
| lang/rust/blob/d4025ee454169fbd22f57...
| ironhaven wrote:
| Yep that can be used for pre allocating the Vec like in the
| `with_capacity` example
| c0balt wrote:
| 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.
| aidos wrote:
| Interesting! Thanks.
| Lvl999Noob wrote:
| 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()`.
| ridiculous_fish wrote:
| 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<i32>) -> Vec<i32> {
| v.iter_mut().for_each(|c| *c += 1); v }
|
| This is a particularly fancy optimization that Rust can
| perform.
| zamalek wrote:
| 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<i32> = list.into_iter().map::<_, Box<dyn
| Fn...>>(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 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.
| dmart wrote:
| I would have liked to see a comparison in the fold() section that
| functions the same way as the original for loop:
| list_of_lists.into_iter().fold(Vec::new(), |mut
| accumulator, list| { accumulator.extend(list);
| accumulator } )
| kccqzy wrote:
| The author's fold example is unfair. They could've just called
| accumulator.extend() and then return the accumulator inside the
| fold example for a fair apple to apple comparison. Just mark the
| accumulator as mut.
|
| Furthermore, I'd use with_capacity in both cases:
| Vec::with_capacity(list_of_lists.iter().map(|l| l.len()).sum())
| IshKebab wrote:
| 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?
| zozbot234 wrote:
| "Ad-Hoc Effects in Rust"
| https://capi.hannobraun.com/daily/2024-12-12 discusses the
| issue in detail.
|
| An early attempt at a solution (2022) was provided by
| https://blog.rust-lang.org/inside-rust/2022/07/27/keyword-ge...
| lilyball wrote:
| Why does fallible_flatten_fold have that accumulator.clone() in
| it? You're cloning the in-progress vector only to throw away the
| original, it's extremely wasteful and completely unnecessary.
| Just declare the accumulator as `mut`.
| dhosek wrote:
| 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.
| kstrauser wrote:
| 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.
| worik wrote:
| It is not that hard: If there are side effects, use a for loop
| scotty79 wrote:
| I'm currently doing advent of code in Scala 3 to learn a bit of
| this language.
|
| 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.
| winwang wrote:
| glad to see another Scala fan :)
|
| keep in mind that "for loops" are really "for comprehensions"
| and desugae into flatMap/map
| CrendKing wrote:
| 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?
| orf wrote:
| No, it seems like an oversight in the code sample. It should be
| wrapped in Ok()
___________________________________________________________________
(page generated 2024-12-12 23:00 UTC)