4 ms·

That's the essence of Clojure's transducers http://clojure.org/transducers http://clojure.org/transducers ...they give you the declarative syntax of filter/red

by drcode 12y ago

That's the essence of Clojure's transducers http://clojure.org/transducers http://clojure.org/transducers ...they give you the declarative syntax of filter/reduce/etc but can have the same evaluation strategy as for loops, with comparable performance.

adrusi 12y ago
That's not why clojure has transducers. You can use a mapping transducer to express map, but it's actually going to have slightly worse performance than regular map. There's nothing inherently slow about higher order collection functions, rust has them and they compile to the same machine code as the equivalent loop construct. Its just that most languages implement them on the wrong data structures. Functional languages implement them on lazy lists, which is good, but has overhead. A lot of languages implement them on arrays, which is bad because then it needs to process the whole array at once, and allocate all the memory, even though the next transformation in the pipeline doesn't need all that memory. Rust implements them on iterators, which have all the sane benefits as lazy lists, but fit better into a performance-focused imperative language.
- bunderbunder 12y ago
  .NET implements them on iterators, too, but that's not an inherently fast approach. .NET iterators are objects that implement a specific interface, and iterating over them involves two function calls per element - one to move to the next item, and one to retrieve the current item. Those two function calls introduce an overhead that may be significant in a "tight loop", and that may not exist in a hand-coded for loop. Perhaps .NET's optimizer is smart enough to get things down to a for loop equivalent in some cases, but in general I haven't seen much evidence of that happening.
  - pcwalton 12y ago
    > .NET iterators are objects that implement a specific interface, and iterating over them involves two function calls per element - one to move to the next item, and one to retrieve the current item. Any optimizing compiler will inline those functions. "Avoid function calls for performance" hasn't been relevant optimization advice for at least a decade.
    - inglor 12y ago
      In particular - the Microsoft .NET JIT will gladly make them as fast as loops in most cases - there might be overhead involving closures but that's mostly taken care of.
    - bunderbunder 12y ago
      A good optimizer can inline those functions, but that doesn't necessarily mean it will. .NET JIT is conservative in what it decides to inline. There's even a special hint you can use to ask it to be more aggressive about inlining a method. You can't necessarily apply that hint to every function, though. Anonymous ones, for example.
      - pcwalton 12y ago
        > A good optimizer can inline those functions, but that doesn't necessarily mean it will. If the optimizer isn't choosing to inline where it is a performance win, it's not a good optimizer. Especially for trivial functions like Current() and MoveNext(), which are pretty much the textbook example of functions where inlining really helps (not so much because of the function call overhead, but because it enables so many intraprocedural loop optimizations).
- drcode 12y ago
  > You can use a mapping transducer to express map, but it's actually going to have slightly worse performance than regular map. That's a strawman argument- Neither OP nor my comment made any mention of "map". This is a discussion about reduction and filtering. Yes, using transducers in a way that is silly like you suggest will produce disappointing results.
  - adrusi 12y ago
    Bad example, but my point holds. Transducers aren't performance improvers, they're an abstraction over the process of iteration. They actually degrade performance in the absence of a particularly smart inlining compiler.
    - drcode 12y ago
      > They actually degrade performance in the absence of a particularly smart inlining compiler. So it sounds like you're saying that iterators in Rust are faster than transducer-based filter/reduce. I think it's clear that my original point was that transducer-based filter/reduce is faster than lazy-list based filter/reduce, and comparable in performance to a for loop. (in that lazy-list operations are MUCH MUCH slower in most cases for filter reduce operations than the latter two approaches)

by drcode 12y ago

adrusi 12y ago

That's not why clojure has transducers. You can use a mapping transducer to express map, but it's actually going to have slightly worse performance than regular map. There's nothing inherently slow about higher order collection functions, rust has them and they compile to the same machine code as the equivalent loop construct. Its just that most languages implement them on the wrong data structures. Functional languages implement them on lazy lists, which is good, but has overhead. A lot of languages implement them on arrays, which is bad because then it needs to process the whole array at once, and allocate all the memory, even though the next transformation in the pipeline doesn't need all that memory. Rust implements them on iterators, which have all the sane benefits as lazy lists, but fit better into a performance-focused imperative language.

bunderbunder 12y ago
.NET implements them on iterators, too, but that's not an inherently fast approach. .NET iterators are objects that implement a specific interface, and iterating over them involves two function calls per element - one to move to the next item, and one to retrieve the current item. Those two function calls introduce an overhead that may be significant in a "tight loop", and that may not exist in a hand-coded for loop. Perhaps .NET's optimizer is smart enough to get things down to a for loop equivalent in some cases, but in general I haven't seen much evidence of that happening.
- pcwalton 12y ago
  > .NET iterators are objects that implement a specific interface, and iterating over them involves two function calls per element - one to move to the next item, and one to retrieve the current item. Any optimizing compiler will inline those functions. "Avoid function calls for performance" hasn't been relevant optimization advice for at least a decade.
  - inglor 12y ago
    In particular - the Microsoft .NET JIT will gladly make them as fast as loops in most cases - there might be overhead involving closures but that's mostly taken care of.
  - bunderbunder 12y ago
    A good optimizer can inline those functions, but that doesn't necessarily mean it will. .NET JIT is conservative in what it decides to inline. There's even a special hint you can use to ask it to be more aggressive about inlining a method. You can't necessarily apply that hint to every function, though. Anonymous ones, for example.
    - pcwalton 12y ago
      > A good optimizer can inline those functions, but that doesn't necessarily mean it will. If the optimizer isn't choosing to inline where it is a performance win, it's not a good optimizer. Especially for trivial functions like Current() and MoveNext(), which are pretty much the textbook example of functions where inlining really helps (not so much because of the function call overhead, but because it enables so many intraprocedural loop optimizations).
drcode 12y ago
> You can use a mapping transducer to express map, but it's actually going to have slightly worse performance than regular map. That's a strawman argument- Neither OP nor my comment made any mention of "map". This is a discussion about reduction and filtering. Yes, using transducers in a way that is silly like you suggest will produce disappointing results.
- adrusi 12y ago
  Bad example, but my point holds. Transducers aren't performance improvers, they're an abstraction over the process of iteration. They actually degrade performance in the absence of a particularly smart inlining compiler.
  - drcode 12y ago
    > They actually degrade performance in the absence of a particularly smart inlining compiler. So it sounds like you're saying that iterators in Rust are faster than transducer-based filter/reduce. I think it's clear that my original point was that transducer-based filter/reduce is faster than lazy-list based filter/reduce, and comparable in performance to a for loop. (in that lazy-list operations are MUCH MUCH slower in most cases for filter reduce operations than the latter two approaches)