After using my trusty friend the Binary Chop algorithm to successfully track down some of Those Fscking C Pointers Gone Awry Again, I decided to have a quick look at the Wikipedia article on binary search, and its use outside of programming (if there was any). What greeted me was this.
Jon Bentley [...] found that an astounding ninety percent failed to code a binary search correctly after several hours…
Not only that, the article mentions “professional programmers”; i.e. people who do this for a living.
I know Knuth said that “the details can be surprisingly tricky”, but if you’re coding for a living, and you can’t do the most basic search algorithm out there in code…well, wow. That was one of the first things I learnt when I learnt C at thirteen years old. This is a forty year old language, with no bounds safety whatsoever (unlike modern VM-based languages), and I managed to learn bin-search, taking school into account, in a week. This was when I’d known C for not more than a month.
And you’re telling me modern professional programmers, who get paid 3-4 times what I do, can’t do a binary search… god, I think I’m in the wrong career sometimes. Bloody hell – pick up a copy of TAOCP; it won’t kill you.
This also goes some way to explaining why much code output by companies in this day and age is full of bugs and issues; it also explains to me why many programmers bitch and moan about how hard it is to split programs across processor cores when a five year old could use CreateThread() or clone().
Rant over, although the fact I even needed to rant about what I just have worries me.
One Comment
I agree with you up to a point, but that only applies as far as inherently parallel programming is concerned – with realtime stuff, race conditions abound. And perforance scaling – the lowest common denominator (ie the minimum spec on the back of the box, for a game) has to be able to run, say, ragdoll physics code at a bare minimum of 25 loops per second (ie, the minimum acceptable frame rate for the game – ever see a CPU-limited game chug? Not pretty). These people have to balance the performance of their code on that lowest common denominator (which is still likely to be single-core) against what they’d like to achieve from their engine. And anytime realtime code has to be threaded, there’s an overhead in seeing that the output synchronises, which in a lot of cases leads to more work than just running it single-threaded.
The move to mostly threaded code across the industry is a paradigm shift, and it’s going to take a while to sink in. Meanwhile, some shops are finding it more feasible to stop halfway with coarse-grained multithreading.