Fancy algorithms lose; dumb C code wins
blog.begriffsschrift.com
blog.begriffsschrift.com
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.
See unlambda at http://en.wikipedia.org/wiki/Unlambda.
How about in Perl-style regexes? http://www.perlmonks.org/?node_id=809842
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).
This is a tradeoff that people in computing have been happily taking for years -- e.g. using a higher level language is a similar kind of tradeoff (use Python instead of C - pay x10 in performance, get x10 shorter development time).
But this tradeoff only makes sense if the x10 thing you get is cheaper than the x10 thing you pay for. With hadoop, you pay x10 for hardware/computing time and more for administration (unless you have some kind of EC2 elastic mapreduce, at which point you pay x20 for hardware/computing but no administration cost), and you save some development time.
Two hadoop projects I was consulting on (or rather, consulting _off_ hadoop) were paying ~$10K/month each to Amazon for a while, when <$20K in programmer time for each reduced it to working on one beefy machine that was already located in the office, with ~$100/month cost (power, cooling).
If your problem is IO constrained, for example processing 10 TB of log data, hadoop will get all your disks to 100% utilization just as well as anything else will. It will leave your processors horribly underutilized, but that's just the nature of IO constrained problems. If you could get 10 TB of ram dedicated to your dataset then you could easily get a massive speedup over the hadoop solution but that's just not realistic.
A related specific example would be molecular dynamics on GPUs versus CPUs. Not only are GPUs faster, they're faster than CPUs can be at this time because of communication issues. As in you can throw as many CPUs and servers as you want at the problem and they'll never beat a single $600 consumer GPU with its 120+ GB/s internal bus (note the absence of hyperbolic claims of 100x to 1000x faster, just faster).
Or in other words, strong-scaling tasks don't work out so well on a weak-scaling architecture.
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.
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.
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?
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.
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 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