5 ms·

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 (possi

by dhosek 2y ago

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 2y ago
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.
- varikin 2y ago
  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.
  - kstrauser 2y ago
    Huh, interesting. Thanks for that! Today, I learned.
    - deleted 2y ago
      [deleted]
  - Measter 2y ago
    > 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. 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.
  - ynik 2y ago
    The big differences are: 1. Rust closures are by-value structs; whereas Java closures are heap objects. 2. Rust generics are monomorphized; whereas Java type-erases them -> lots of virtual call overhead when passing a closure to a generic function. 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.
  - dhosek 2y ago
    The other problem with the parallel streams is that it’s badly implemented. Threads for parallel streams are pulled from a single thread pool shared across the whole application so if you have multiple parallel streams in an application that’s already inherently multithreaded (e.g. a web service), you end up with severe resource contention that makes the parallelism work poorly if at all and can end up causing your app to deadlock because all the threads are in use somewhere else. There’s a workaround for it, but it ends up requiring some ugly boilerplate code to work.
- recursive 2y ago
  > `.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.
  - kstrauser 2y ago
    Then that may not be an appropriate optimization for those languages.
    - recursive 2y ago
      That's what I'm saying. In fact, I think that's most languages.
  - chabska 2y ago
    What languages would that be?
    - recursive 2y ago
      Probably most that has imperative stuff or closures. Here's the spec from ECMAscript. https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.map https://tc39.es/ecma262/multipage/indexed-collections.html#s... C# and Javascript are the ones that I know of for sure.
  - dhosek 2y ago
    The author is confusing .map(…) with the Map interface for collections.
  - sunshowers 2y ago
    It's interesting -- so, logically, `map` in Rust does imply an ordering. The closure is a `FnMut`, i.e. a callback which mutably captures values, causing external side effects. And it is guaranteed that if externally visible, mutations will be done in 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 https://doc.rust-lang.org/std/cell/struct.UnsafeCell.html [2] https://doc.rust-lang.org/std/macro.print.html https://doc.rust-lang.org/std/macro.print.html

by dhosek 2y ago

kstrauser 2y ago

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.

varikin 2y ago
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.
- kstrauser 2y ago
  Huh, interesting. Thanks for that! Today, I learned.
  - deleted 2y ago
    [deleted]
- Measter 2y ago
  > 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. 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.
- ynik 2y ago
  The big differences are: 1. Rust closures are by-value structs; whereas Java closures are heap objects. 2. Rust generics are monomorphized; whereas Java type-erases them -> lots of virtual call overhead when passing a closure to a generic function. 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.
- dhosek 2y ago
  The other problem with the parallel streams is that it’s badly implemented. Threads for parallel streams are pulled from a single thread pool shared across the whole application so if you have multiple parallel streams in an application that’s already inherently multithreaded (e.g. a web service), you end up with severe resource contention that makes the parallelism work poorly if at all and can end up causing your app to deadlock because all the threads are in use somewhere else. There’s a workaround for it, but it ends up requiring some ugly boilerplate code to work.
recursive 2y ago
> `.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.
- kstrauser 2y ago
  Then that may not be an appropriate optimization for those languages.
  - recursive 2y ago
    That's what I'm saying. In fact, I think that's most languages.
- chabska 2y ago
  What languages would that be?
  - recursive 2y ago
    Probably most that has imperative stuff or closures. Here's the spec from ECMAscript. https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.map https://tc39.es/ecma262/multipage/indexed-collections.html#s... C# and Javascript are the ones that I know of for sure.
- dhosek 2y ago
  The author is confusing .map(…) with the Map interface for collections.
- sunshowers 2y ago
  It's interesting -- so, logically, `map` in Rust does imply an ordering. The closure is a `FnMut`, i.e. a callback which mutably captures values, causing external side effects. And it is guaranteed that if externally visible, mutations will be done in 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 https://doc.rust-lang.org/std/cell/struct.UnsafeCell.html [2] https://doc.rust-lang.org/std/macro.print.html https://doc.rust-lang.org/std/macro.print.html