7 ms·

Here are a couple of reasons why I think it's not so clear cut: 1. If garbage collection was that damaging to the cache, Haskell wouldn't be nearly as fast as

Here are a couple of reasons why I think it's not so clear cut: 1. If garbage collection was that damaging to the cache, Haskell wouldn't be nearly as fast as C. 2. Copy-on-write data structures are nice because the immutability allows for concurrent access without locking. Granted, this was from 2002 and Linus may no longer feel so strongly about the topic.

jedbrown 16y ago
Show me a memory-intensive kernel in which Haskell runs close to the performance model. Sparse and dense matrix kernels would be a good place to start. Our C code for sparse matrix-vector products and sparse triangular solves gets better than 90% of STREAM bandwidth (based on an assumption of optimal cache reuse, STREAM is about 85% of hardware peak). Dense matrix kernels should get better than 90% of FPU peak. Unlike sparse kernels, dense kernels are no longer bandwidth limited, but cache reuse in both L1 and L2, as well as friendly TLB behavior is important to good performance. It would be interesting to see any Haskell implementations that are competitive. I suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad.
- joshhart 16y ago
  Let's be fair here. Numerical processing is not representative of most applications, but I concede the point. It's an interesting question though. I'm a Haskell beginner, but I'm pretty experienced with Scala. Let me try to see how using sliding compares with a tight Java loop on statically allocated data for convolutions/filters.
- marshray 16y ago
  I suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad. Of course not every problem is going to fit well into an imperative model either. E.g. a problem with a large variety of pointer-y data structures and interit-y objects, like say, a compiler.
- dons 16y ago
  > It would be interesting to see any Haskell implementations that are competitive. I suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad. Or teach the compiler about the algebra of arrays and matrices, so it can do the things to the code, that we'd write by hand. E.g. * http://www.cse.unsw.edu.au/~benl/papers/stencil/stencil-icfp2011-sub.pdf http://www.cse.unsw.edu.au/~benl/papers/stencil/stencil-icfp... * http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.pdf http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.p... * http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf * http://www.cse.unsw.edu.au/~chak/papers/acc-cuda.pdf http://www.cse.unsw.edu.au/~chak/papers/acc-cuda.pdf In all these cases arrays codes are written in a function style, accompanied with special purpose optimizations and/or code generators (in the case of GPU code), layered over an imperative arrays primitive layer, using a memory effects monad.
  - jedbrown 16y ago
    This is a worthwhile research topic, but it doesn't really answer my question. From the first paper you cite: The single threaded Handwritten C version is about 45% faster than our best Haskell result, which is achieved with 3 threads. Meanwhile, there is no performance model so we don't know how good the C version is. The paper doesn't even report a simple fraction of FPU or bandwidth peak. It is not using SSE instructions so it cannot possibly be better than 50% of FPU peak (the limit is actually lower because this kernel is/should be bandwidth limited). As for parallelism, I'll quote Bill Gropp [1] The easiest way to make software scalable is to make it sequentially inefficient. [1] http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&ots=TJCM7dzUgl&dq=gropp%20exploiting%20existing%20software%20in%20libraries&lr&pg=PA21#v=onepage&q=gropp%20exploiting%20existing%20software%20in%20libraries&f=false http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&#...
    - dons 16y ago
      Oh, I'm certainly not arguing that you're going to beat hand tuned straightline code. I'm just pointing out that dropping into assembly isn't the only possibly path.
- rayiner 16y ago
  You just described an ideal use-case for GC. You allocate a bunch of arrays at the outset, then sit there pounding on them with little to no allocation. A good GC won't cost you anything in this case, since it'll allocate large pointer-free arrays in a separate pool that doesn't get traced. Haskell isn't a good example, since it's a lazy functional language, but if something like Java isn't just as fast for your case it isn't the GC, it's the code generation. Much harder to do all those fancy loop optimizations in 100 ms in a JIT than in 10s in an offline compiler.
  - jedbrown 16y ago
    I concede that my arguments were directed primarily at Haskell and actually more about data structure reuse than about GC. The threading model and task affinity is also relevant: if a compacting GC moves a hot data structure to a different memory bank, performance can be much slower. In principle, a runtime (with kernel support, libnuma may be sufficient on Linux) could set thread affinity, trace the page table for each (core,thread) pairs, and then have the compacting GC migrate threads and memory so that threads tended to use local memory. In principle, this could give better performance than most static distribution schemes, but this tracing costs something and to my knowledge, this sort of NUMA-aware GC is still a research topic.
scott_meyer 16y ago
Read your own words "immutability allows for concurrent access" Most GCs mutate (mark bits, semi-space copy, etc.) The immutability of Haskell data structures is an illusion, and from the standpoint of real concurrent access, an expensive one.
- ww520 16y ago
  For mutating GCs, they stop the world when making changes so there's no erosion of the immutability contract in concurrent access. There are parallel GC systems that works quite well with multiple-core systems.
  - scott_meyer 16y ago
    You write "stop the world" and "concurrent access" in the same sentence. What is up with that? When we manage to go for 10 years without getting 5 or 6 papers claiming to "solve the concurrent/pauseless GC problem" then, perhaps, it might be reasonable to present the problem as "solved."
    - marshray 16y ago
      It's an interesting problem that will probably never be solved, only optimized and amortized. That makes it good for papers! The most efficient scheme probably is a "stop the world" system. The regular program might mutate concurrently and the GC could indeed be concurrent, but making them run at the same time is a real challenge. Of course, people don't like it when their app pauses. I think it's noteworthy that there never was a big office suite or even a web browser written primarily in a GC system, despite many years of promises.
      - rayiner 16y ago
        Re: office suites, the code bases of the major office suites pre-date the rise of Java, which brought GC into the mainstream. Lot's of apps bigger and more complex than an office suite have been written in Java. As for web browsers... every web browser has a GC...

jedbrown 16y ago

Show me a memory-intensive kernel in which Haskell runs close to the performance model. Sparse and dense matrix kernels would be a good place to start. Our C code for sparse matrix-vector products and sparse triangular solves gets better than 90% of STREAM bandwidth (based on an assumption of optimal cache reuse, STREAM is about 85% of hardware peak). Dense matrix kernels should get better than 90% of FPU peak. Unlike sparse kernels, dense kernels are no longer bandwidth limited, but cache reuse in both L1 and L2, as well as friendly TLB behavior is important to good performance. It would be interesting to see any Haskell implementations that are competitive. I suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad.

joshhart 16y ago
Let's be fair here. Numerical processing is not representative of most applications, but I concede the point. It's an interesting question though. I'm a Haskell beginner, but I'm pretty experienced with Scala. Let me try to see how using sliding compares with a tight Java loop on statically allocated data for convolutions/filters.
marshray 16y ago
I suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad. Of course not every problem is going to fit well into an imperative model either. E.g. a problem with a large variety of pointer-y data structures and interit-y objects, like say, a compiler.
dons 16y ago
> It would be interesting to see any Haskell implementations that are competitive. I suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad. Or teach the compiler about the algebra of arrays and matrices, so it can do the things to the code, that we'd write by hand. E.g. * http://www.cse.unsw.edu.au/~benl/papers/stencil/stencil-icfp2011-sub.pdf http://www.cse.unsw.edu.au/~benl/papers/stencil/stencil-icfp... * http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.pdf http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.p... * http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf * http://www.cse.unsw.edu.au/~chak/papers/acc-cuda.pdf http://www.cse.unsw.edu.au/~chak/papers/acc-cuda.pdf In all these cases arrays codes are written in a function style, accompanied with special purpose optimizations and/or code generators (in the case of GPU code), layered over an imperative arrays primitive layer, using a memory effects monad.
- jedbrown 16y ago
  This is a worthwhile research topic, but it doesn't really answer my question. From the first paper you cite: The single threaded Handwritten C version is about 45% faster than our best Haskell result, which is achieved with 3 threads. Meanwhile, there is no performance model so we don't know how good the C version is. The paper doesn't even report a simple fraction of FPU or bandwidth peak. It is not using SSE instructions so it cannot possibly be better than 50% of FPU peak (the limit is actually lower because this kernel is/should be bandwidth limited). As for parallelism, I'll quote Bill Gropp [1] The easiest way to make software scalable is to make it sequentially inefficient. [1] http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&ots=TJCM7dzUgl&dq=gropp%20exploiting%20existing%20software%20in%20libraries&lr&pg=PA21#v=onepage&q=gropp%20exploiting%20existing%20software%20in%20libraries&f=false http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&#...
  - dons 16y ago
    Oh, I'm certainly not arguing that you're going to beat hand tuned straightline code. I'm just pointing out that dropping into assembly isn't the only possibly path.
rayiner 16y ago
You just described an ideal use-case for GC. You allocate a bunch of arrays at the outset, then sit there pounding on them with little to no allocation. A good GC won't cost you anything in this case, since it'll allocate large pointer-free arrays in a separate pool that doesn't get traced. Haskell isn't a good example, since it's a lazy functional language, but if something like Java isn't just as fast for your case it isn't the GC, it's the code generation. Much harder to do all those fancy loop optimizations in 100 ms in a JIT than in 10s in an offline compiler.
- jedbrown 16y ago
  I concede that my arguments were directed primarily at Haskell and actually more about data structure reuse than about GC. The threading model and task affinity is also relevant: if a compacting GC moves a hot data structure to a different memory bank, performance can be much slower. In principle, a runtime (with kernel support, libnuma may be sufficient on Linux) could set thread affinity, trace the page table for each (core,thread) pairs, and then have the compacting GC migrate threads and memory so that threads tended to use local memory. In principle, this could give better performance than most static distribution schemes, but this tracing costs something and to my knowledge, this sort of NUMA-aware GC is still a research topic.

scott_meyer 16y ago

Read your own words "immutability allows for concurrent access" Most GCs mutate (mark bits, semi-space copy, etc.) The immutability of Haskell data structures is an illusion, and from the standpoint of real concurrent access, an expensive one.

ww520 16y ago
For mutating GCs, they stop the world when making changes so there's no erosion of the immutability contract in concurrent access. There are parallel GC systems that works quite well with multiple-core systems.
- scott_meyer 16y ago
  You write "stop the world" and "concurrent access" in the same sentence. What is up with that? When we manage to go for 10 years without getting 5 or 6 papers claiming to "solve the concurrent/pauseless GC problem" then, perhaps, it might be reasonable to present the problem as "solved."
  - marshray 16y ago
    It's an interesting problem that will probably never be solved, only optimized and amortized. That makes it good for papers! The most efficient scheme probably is a "stop the world" system. The regular program might mutate concurrently and the GC could indeed be concurrent, but making them run at the same time is a real challenge. Of course, people don't like it when their app pauses. I think it's noteworthy that there never was a big office suite or even a web browser written primarily in a GC system, despite many years of promises.
    - rayiner 16y ago
      Re: office suites, the code bases of the major office suites pre-date the rise of Java, which brought GC into the mainstream. Lot's of apps bigger and more complex than an office suite have been written in Java. As for web browsers... every web browser has a GC...