5 ms·

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 co

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.
    - jedbrown 16y ago
      If you're not within 10% for these kernels, chances are that memory is being used differently. This gets to a further matter which I think is perhaps the greatest failure of current multi/many-core programming paradigms: assuming a flat memory model. Efficient parallel computation has much less to do with computation than with data movement. Recent and future architectures have deeply hierarchical memory systems so any paradigm that does not expose the location of physical pages (within some appropriate abstraction) will have a hard time delivering consistent, understandable performance. Performance should not vary an order of magnitude based on whether memory was faulted (allocation is irrelevant) using a batch of threads with different affinity than those that access it later. But this is the current state of affairs. I would very much like to see a paradigm where a memory distribution (roughly a high-level representation of the mapping to physical memory) was a first-class concept. Suppose that new memory could be allocated or remapped to have certain compatibility relative to the mapping of another block. Then you could associate tasks with certain coupling between two distributions.
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.

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.
  - jedbrown 16y ago
    If you're not within 10% for these kernels, chances are that memory is being used differently. This gets to a further matter which I think is perhaps the greatest failure of current multi/many-core programming paradigms: assuming a flat memory model. Efficient parallel computation has much less to do with computation than with data movement. Recent and future architectures have deeply hierarchical memory systems so any paradigm that does not expose the location of physical pages (within some appropriate abstraction) will have a hard time delivering consistent, understandable performance. Performance should not vary an order of magnitude based on whether memory was faulted (allocation is irrelevant) using a batch of threads with different affinity than those that access it later. But this is the current state of affairs. I would very much like to see a paradigm where a memory distribution (roughly a high-level representation of the mapping to physical memory) was a first-class concept. Suppose that new memory could be allocated or remapped to have certain compatibility relative to the mapping of another block. Then you could associate tasks with certain coupling between two distributions.

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.