10 ms·

Fancy algorithms lose; dumb C code wins

84 points by begriffs 15y ago

lukesandberg 15y ago
This doesn't strike me as particularly interesting. CL is just a programming language, a functional assembly so iit seems intuitive that it would be infeasible to cache all computations. Even just caching all programs up to a given size is a big issue because the number grows exponentially with the size of the program, so even if you could cache all programs of a given size it wouldn't neccesarily help to solve (reduce) larger programs very much. It would be like trying to write a compiler with a peephole optimization for every form of the language, you just end up with a large, slow compiler. Still it makes me want to write an SKI interpreter.
- p4bl0 15y ago
  > Still it makes me want to write an SKI interpreter. See unlambda at http://en.wikipedia.org/wiki/Unlambda http://en.wikipedia.org/wiki/Unlambda.
  - Sniffnoy 15y ago
    Bah, Unlambda is clearly artificial. You want something that is ridiculous in a natural way, you use Iota: http://en.wikipedia.org/wiki/Iota_and_Jot http://en.wikipedia.org/wiki/Iota_and_Jot
- JadeNB 15y ago
  > Still it makes me want to write an SKI interpreter. How about in Perl-style regexes? http://www.perlmonks.org/?node_id=809842 http://www.perlmonks.org/?node_id=809842
stuhood 15y ago
The first solution that didn't involve disk or network IO was the fast one?
- Mesmoria 15y ago
  My thoughts exactly. It has nothing to do with language at all.
  - archangel_one 15y ago
    Potentially it still might have done; since C is more efficient with memory, it may not have been practical to take that approach with PHP.
- sambeau 15y ago
  It also doesn't free anything.
secure 15y ago
So not putting stuff into a transactional database and using a compiled language instead of an interpreted one is better for computationally intensive tasks? Big surprise.
codex 15y ago
This story reminds me of the (apocryphal?) claim that C++ running on a single machine can often beat a cluster of Hadoop machines. Scalability is another matter.
- bpodgursky 15y ago
  That's a totally problem/domain specific assertion. A single machine with 8 or so cores simply isn't going to make it through a hundred terabytes of data, and many (most?) hadoop jobs are IO-bound anyway. If you find that micro-optimization greatly increases your performance, you probably shouldn't be using hadoop anyway...
  - rbranson 15y ago
    Have you any useful examples of non-trivial Hadoop MapReduce jobs that can process input data at hundreds of megabytes per second?
    - jeffffff 15y ago
      building sharded inverted indexes
  - beagle3 15y ago
    > If you find that micro-optimization greatly increases your performance, you probably shouldn't be using hadoop anyway... It's all a matter of what you optimize for. In a recent project, a C++ version, using memory mapped files with a fixed-length record, was about 20 times faster than the hadoop version, and that's just the CPU. The C++ version had: no deserializing needed, everything random access, multiple runs on same data had NO I/O requirements (mmap was cached between runs). It was about as hard to write. So, instead of running a 100-core strong Hadoop install (which is small, but far from trivial), I was able to do with one hefty 8-core machine. Scaling up is "easier" with Hadoop, in the sense that you can just throw money at it and get more EC@/rackspace nodes when needed. But it is a lot of money. Hadoop makes sense if you've got lots of money to waste, and actually need thousands of cores (cause you'll only need a few tens if you effectively use your hardware).
cageface 15y ago
Must be a slow news day when this hits the front page.
StavrosK 15y ago
Ah, nothing like a false dichotomy to start the weekend.
mjbellantoni 15y ago
Anyone wanting to do experimentation of pre-computing logical expressions should take a look at Binary Decision Diagrams. http://en.wikipedia.org/wiki/Binary_decision_diagram http://en.wikipedia.org/wiki/Binary_decision_diagram
listrophy 15y ago
Hey begriffs, next time we're hanging at CE or a tech social, let's talk about this kinda stuff. I may be able to shed some light on making "fancy" stuff work faster/better... though a straight-up C implementation without I/O is gonna win (though it perhaps won't be as persistent as, say, anything with actual persistence)
3pt14159 15y ago
Once you get good enough at Python or Ruby knowing C is so very, very important. It releases whole swaths of problems up to you and binding it to Ruby or Python is easy.
hmottestad 15y ago
From the post: "This post is about sucking it up and just writing low-level code" So I'm quite sure that C is a high level language. Assembly is low level. It allows you to control the cpu directly by telling it what instructions to run and which registers should be used for what. In C the closest thing you have is specifying if a register should be used at all. Or inline assembly, which again...is just assembly. And yes....php is even higher level. Caching to drive is only useful if your operation takes longer than reading from drive. In this case reading from drive was slower than doing the calculation. What he should have considered is an in-memory-cache.
- slowpoke 15y ago
  >So I'm quite sure that C is a high level language. Except it isn't. At least not anymore. This statement was true a few decades back, when C was the highest level available. Today, C is barely a level above Assembly on the abstraction scale of programming languages. Mind you, I'm not saying that's bad (and most other people don't mean it as an insult, either). C is a powerful language that will probably be needed by generations to come. But calling it "high level" today is being stuck in the 1970s.
- bonch 15y ago
  Obviously, he's speaking in relative terms. C is low-level compared to PHP, but it's high-level compared to assembly.
chuinard 15y ago
You complain about App Engine expiring requests, but I think the new 'backend instances' concept allows you to have really long requests running.
viraptor 15y ago
I think this might be much faster with caching, but the mistake was to put caching in some external database, rather than local process memory. There are only 4 characters possible: `,i,k,s - that means on a 64b machine you can have 29 elements fitting into a native integer (5 bits for length + 29 2-bit elements). Use that as a key for a hash in a cache and compute the longer terms in a standard way to avoid smaller mallocs, preallocate large chunks of memory which can be filled linear way... I'd hope for 1.5-2x speedup over the original "dumb C". Sigh... now I'm tempted to actually try that. Does anyone know of a good library of SKI fragments for testing?
- begriffs 15y ago
  I'd love to see what you come up with! Here are lots of CL terms you can use: http://share.begriffsschrift.com/joe/bank-17.txt.bz2 http://share.begriffsschrift.com/joe/bank-17.txt.bz2 It is a tab delimited file. The first column is all CL terms of length 17 which reduce to a normal form. The second column is what they reduce to, and the last column is the number of reduction steps it took in a leftmost-outermost evaluation order.
  - viraptor 15y ago
    I'm not sure how comparable it is to your program since I cannot run it in batch mode (memory leaking...), but I'm able to process the first 340k rows of that file in under 7 seconds with cache limited to 15 characters. That makes 20 microseconds per row (with checking the result). Or another way - 7 microseconds per reduction step on average. Without cache, it takes minutes, so I didn't want to wait for the actual time. See http://imgur.com/FL2Eg http://imgur.com/FL2Eg for seconds per row -vs- cache limit. Ah... written in python without using the bit-packing tricks. I guess the 100+ times speedup is enough anyways... https://bitbucket.org/viraptor/ski/src https://bitbucket.org/viraptor/ski/src
    - begriffs 15y ago
      Nicely done, and good analysis. It's a fascinating problem, isn't it? Simple rules, but an opportunity to approach it several ways and refine the solution.

84 points by begriffs 15y ago

This doesn't strike me as particularly interesting. CL is just a programming language, a functional assembly so iit seems intuitive that it would be infeasible to cache all computations. Even just caching all programs up to a given size is a big issue because the number grows exponentially with the size of the program, so even if you could cache all programs of a given size it wouldn't neccesarily help to solve (reduce) larger programs very much. It would be like trying to write a compiler with a peephole optimization for every form of the language, you just end up with a large, slow compiler. Still it makes me want to write an SKI interpreter.

p4bl0 15y ago
> Still it makes me want to write an SKI interpreter. See unlambda at http://en.wikipedia.org/wiki/Unlambda http://en.wikipedia.org/wiki/Unlambda.
- Sniffnoy 15y ago
  Bah, Unlambda is clearly artificial. You want something that is ridiculous in a natural way, you use Iota: http://en.wikipedia.org/wiki/Iota_and_Jot http://en.wikipedia.org/wiki/Iota_and_Jot
JadeNB 15y ago
> Still it makes me want to write an SKI interpreter. How about in Perl-style regexes? http://www.perlmonks.org/?node_id=809842 http://www.perlmonks.org/?node_id=809842

stuhood 15y ago

The first solution that didn't involve disk or network IO was the fast one?

Mesmoria 15y ago
My thoughts exactly. It has nothing to do with language at all.
- archangel_one 15y ago
  Potentially it still might have done; since C is more efficient with memory, it may not have been practical to take that approach with PHP.
sambeau 15y ago
It also doesn't free anything.

secure 15y ago

So not putting stuff into a transactional database and using a compiled language instead of an interpreted one is better for computationally intensive tasks? Big surprise.

codex 15y ago

This story reminds me of the (apocryphal?) claim that C++ running on a single machine can often beat a cluster of Hadoop machines. Scalability is another matter.

bpodgursky 15y ago
That's a totally problem/domain specific assertion. A single machine with 8 or so cores simply isn't going to make it through a hundred terabytes of data, and many (most?) hadoop jobs are IO-bound anyway. If you find that micro-optimization greatly increases your performance, you probably shouldn't be using hadoop anyway...
- rbranson 15y ago
  Have you any useful examples of non-trivial Hadoop MapReduce jobs that can process input data at hundreds of megabytes per second?
  - jeffffff 15y ago
    building sharded inverted indexes
- beagle3 15y ago
  > If you find that micro-optimization greatly increases your performance, you probably shouldn't be using hadoop anyway... It's all a matter of what you optimize for. In a recent project, a C++ version, using memory mapped files with a fixed-length record, was about 20 times faster than the hadoop version, and that's just the CPU. The C++ version had: no deserializing needed, everything random access, multiple runs on same data had NO I/O requirements (mmap was cached between runs). It was about as hard to write. So, instead of running a 100-core strong Hadoop install (which is small, but far from trivial), I was able to do with one hefty 8-core machine. Scaling up is "easier" with Hadoop, in the sense that you can just throw money at it and get more EC@/rackspace nodes when needed. But it is a lot of money. Hadoop makes sense if you've got lots of money to waste, and actually need thousands of cores (cause you'll only need a few tens if you effectively use your hardware).

cageface 15y ago

Must be a slow news day when this hits the front page.

StavrosK 15y ago

Ah, nothing like a false dichotomy to start the weekend.

mjbellantoni 15y ago

Anyone wanting to do experimentation of pre-computing logical expressions should take a look at Binary Decision Diagrams. http://en.wikipedia.org/wiki/Binary_decision_diagram http://en.wikipedia.org/wiki/Binary_decision_diagram

listrophy 15y ago

Hey begriffs, next time we're hanging at CE or a tech social, let's talk about this kinda stuff. I may be able to shed some light on making "fancy" stuff work faster/better... though a straight-up C implementation without I/O is gonna win (though it perhaps won't be as persistent as, say, anything with actual persistence)

3pt14159 15y ago

Once you get good enough at Python or Ruby knowing C is so very, very important. It releases whole swaths of problems up to you and binding it to Ruby or Python is easy.

hmottestad 15y ago

From the post: "This post is about sucking it up and just writing low-level code" So I'm quite sure that C is a high level language. Assembly is low level. It allows you to control the cpu directly by telling it what instructions to run and which registers should be used for what. In C the closest thing you have is specifying if a register should be used at all. Or inline assembly, which again...is just assembly. And yes....php is even higher level. Caching to drive is only useful if your operation takes longer than reading from drive. In this case reading from drive was slower than doing the calculation. What he should have considered is an in-memory-cache.

slowpoke 15y ago
>So I'm quite sure that C is a high level language. Except it isn't. At least not anymore. This statement was true a few decades back, when C was the highest level available. Today, C is barely a level above Assembly on the abstraction scale of programming languages. Mind you, I'm not saying that's bad (and most other people don't mean it as an insult, either). C is a powerful language that will probably be needed by generations to come. But calling it "high level" today is being stuck in the 1970s.
bonch 15y ago
Obviously, he's speaking in relative terms. C is low-level compared to PHP, but it's high-level compared to assembly.

chuinard 15y ago

You complain about App Engine expiring requests, but I think the new 'backend instances' concept allows you to have really long requests running.

viraptor 15y ago

I think this might be much faster with caching, but the mistake was to put caching in some external database, rather than local process memory. There are only 4 characters possible: `,i,k,s - that means on a 64b machine you can have 29 elements fitting into a native integer (5 bits for length + 29 2-bit elements). Use that as a key for a hash in a cache and compute the longer terms in a standard way to avoid smaller mallocs, preallocate large chunks of memory which can be filled linear way... I'd hope for 1.5-2x speedup over the original "dumb C". Sigh... now I'm tempted to actually try that. Does anyone know of a good library of SKI fragments for testing?

begriffs 15y ago
I'd love to see what you come up with! Here are lots of CL terms you can use: http://share.begriffsschrift.com/joe/bank-17.txt.bz2 http://share.begriffsschrift.com/joe/bank-17.txt.bz2 It is a tab delimited file. The first column is all CL terms of length 17 which reduce to a normal form. The second column is what they reduce to, and the last column is the number of reduction steps it took in a leftmost-outermost evaluation order.
- viraptor 15y ago
  I'm not sure how comparable it is to your program since I cannot run it in batch mode (memory leaking...), but I'm able to process the first 340k rows of that file in under 7 seconds with cache limited to 15 characters. That makes 20 microseconds per row (with checking the result). Or another way - 7 microseconds per reduction step on average. Without cache, it takes minutes, so I didn't want to wait for the actual time. See http://imgur.com/FL2Eg http://imgur.com/FL2Eg for seconds per row -vs- cache limit. Ah... written in python without using the bit-packing tricks. I guess the 100+ times speedup is enough anyways... https://bitbucket.org/viraptor/ski/src https://bitbucket.org/viraptor/ski/src
  - begriffs 15y ago
    Nicely done, and good analysis. It's a fascinating problem, isn't it? Simple rules, but an opportunity to approach it several ways and refine the solution.