4 ms·

Emphatic agreement. I wind up helping folks a lot with writing high performance software, and it's very easy to get to the point where the time to run a model i

Emphatic agreement. I wind up helping folks a lot with writing high performance software, and it's very easy to get to the point where the time to run a model is totally determined by how fast the CPU and IO are. I'm talking problems where naively written C would take an hour, but if I'm careful and use some blend of very clever c or Haskell, the computation is done in 2-5 minutes

awef 13y ago
What kind of problems are those? I would love to find problems, ultimately examples, where smart Haskell and c blends are superior to pure c.
- dikei 13y ago
  It's not neccesarily which language is faster, but the which algorithm is faster. He said naively written C, which mean the algorithm may be entirely different and run in O(n2) and much slower than a Haskell version which use a different algorithm and run in O(nlogn).
  - awef 13y ago
    Right, I read 'naively' as 'natively'. Carry on!
    - carterschonwald 13y ago
      to answer your question just plain ole mathematical modeling / machine learning, and associated duct taping the tubes. I am also going to be releasing the start of a "Numerical Haskell" tool chain sometime (hopefully this fall, but life happens and all that jazz)
  - carterschonwald 13y ago
    actually in the specific example I'm thinking about, i'm talking about memory locality being the performance difference (and in this case, array layout for matrix multiplication). The naive obvious "dot product" matrix mult of two Row Major matrices is 100-1000x slower than somewhat fancier layouts, or even simply transposing the right hand matrix can make a significant difference, let alone more fancy things. Often the biggest throughput bottleneck for CPU bound algorithms in a numerical setting is the quality of the memory locality (because the CPU can chew through data faster than you can feed it). Its actually really really hard to get C / C++ to help you write code with suitably fancy layouts that are easy to use. Amusingly, I also think most auto vectorization approaches to SIMD actually miss the best way to use SIMD registers! I've actually some cute small matrix kernels where by using the AVX SIMD registers as a "L0" cache, I get a 1.5x perf boost!
    - dikei 13y ago
      This is like replacing the compiler optimizer algorithm with your own, similar to the method of writing critical function in Assembly, right? Still I don't see the connection to Haskell, can you elaborate ?
      - carterschonwald 13y ago
        oh, thats just me rambling about why i don't trust compiler autovectorization :) well: 1) i've been slowly working on a numerical computing / data analysis substrate for haskell for over a year now. 2) the haskell c ffi is probably the nicest c ffi you'll ever see. Also pretty fast, basically just a known jump/funcall! And no marshaling overhead too! 3) theres a lot of current and pending over the next year work to make it easy to write HPC grade code using haskell. Some approaches involve interesting libs for runtime code gen (the llvm-general lib for haskell is AMAZING). Theres also a number of ways where ghc haskell will likely get some great performance improvements for numerical code over the next 1-2 years! (i've a few ideas for improving the native code gen / SIMD support over the next year that I hope to experiment with as time permits)
shocks 13y ago
Your problems sound interesting. Could you elaborate?
- carterschonwald 13y ago
  just plain ole mathematical modeling / machine learning, and associated duct taping the tubes. I am also going to be releasing the start of a "Numerical Haskell" tool chain sometime (hopefully this fall, but life happens and all that jazz)
x0x0 13y ago
in machine learning, as soon as you stop using linear models which are normally quite fast to compute, models will be as slow as you can tolerate. for example: random forest, gradient boosting, gam, etc -- you will typically do parameter searches and the models you get are as good as your willingness to wait. Good software will run at a significant fraction of memory bus speed and the faster that bus goes the better your models will be.
- carterschonwald 13y ago
  exactly! This winds up being a memory locality / layout problem often times! eg: most CPU memory traffic is in "cachelines" size chunks so you're best off trying to organize information so you can use all bandwidth! I've a few ideas on this i'm trying to bake into an array/matrix library i hope to release soon. :)

awef 13y ago

What kind of problems are those? I would love to find problems, ultimately examples, where smart Haskell and c blends are superior to pure c.

dikei 13y ago
It's not neccesarily which language is faster, but the which algorithm is faster. He said naively written C, which mean the algorithm may be entirely different and run in O(n2) and much slower than a Haskell version which use a different algorithm and run in O(nlogn).
- awef 13y ago
  Right, I read 'naively' as 'natively'. Carry on!
  - carterschonwald 13y ago
    to answer your question just plain ole mathematical modeling / machine learning, and associated duct taping the tubes. I am also going to be releasing the start of a "Numerical Haskell" tool chain sometime (hopefully this fall, but life happens and all that jazz)
- carterschonwald 13y ago
  actually in the specific example I'm thinking about, i'm talking about memory locality being the performance difference (and in this case, array layout for matrix multiplication). The naive obvious "dot product" matrix mult of two Row Major matrices is 100-1000x slower than somewhat fancier layouts, or even simply transposing the right hand matrix can make a significant difference, let alone more fancy things. Often the biggest throughput bottleneck for CPU bound algorithms in a numerical setting is the quality of the memory locality (because the CPU can chew through data faster than you can feed it). Its actually really really hard to get C / C++ to help you write code with suitably fancy layouts that are easy to use. Amusingly, I also think most auto vectorization approaches to SIMD actually miss the best way to use SIMD registers! I've actually some cute small matrix kernels where by using the AVX SIMD registers as a "L0" cache, I get a 1.5x perf boost!
  - dikei 13y ago
    This is like replacing the compiler optimizer algorithm with your own, similar to the method of writing critical function in Assembly, right? Still I don't see the connection to Haskell, can you elaborate ?
    - carterschonwald 13y ago
      oh, thats just me rambling about why i don't trust compiler autovectorization :) well: 1) i've been slowly working on a numerical computing / data analysis substrate for haskell for over a year now. 2) the haskell c ffi is probably the nicest c ffi you'll ever see. Also pretty fast, basically just a known jump/funcall! And no marshaling overhead too! 3) theres a lot of current and pending over the next year work to make it easy to write HPC grade code using haskell. Some approaches involve interesting libs for runtime code gen (the llvm-general lib for haskell is AMAZING). Theres also a number of ways where ghc haskell will likely get some great performance improvements for numerical code over the next 1-2 years! (i've a few ideas for improving the native code gen / SIMD support over the next year that I hope to experiment with as time permits)

shocks 13y ago

Your problems sound interesting. Could you elaborate?

carterschonwald 13y ago
just plain ole mathematical modeling / machine learning, and associated duct taping the tubes. I am also going to be releasing the start of a "Numerical Haskell" tool chain sometime (hopefully this fall, but life happens and all that jazz)

x0x0 13y ago

in machine learning, as soon as you stop using linear models which are normally quite fast to compute, models will be as slow as you can tolerate. for example: random forest, gradient boosting, gam, etc -- you will typically do parameter searches and the models you get are as good as your willingness to wait. Good software will run at a significant fraction of memory bus speed and the faster that bus goes the better your models will be.

carterschonwald 13y ago
exactly! This winds up being a memory locality / layout problem often times! eg: most CPU memory traffic is in "cachelines" size chunks so you're best off trying to organize information so you can use all bandwidth! I've a few ideas on this i'm trying to bake into an array/matrix library i hope to release soon. :)