4 ms·
HN, you really need to stop dismissing out-of-hand anything you read that doesn't match your expectations. It's embarrassing. 1. The author is Tim Deegan, who'
by thaumaturgy 12y ago
HN, you really need to stop dismissing out-of-hand anything you read that doesn't match your expectations. It's embarrassing.
1. The author is Tim Deegan, who's a former Xen maintainer and currently does low-level work in a data storage startup. He holds a PhD from a reputable university (Cambridge...) and has published several papers (http://www.tjd.phlegethon.org/ http://www.tjd.phlegethon.org/). This doesn't immediately make him right of course, but it does mean he's probably not an idiot and his statements merit a little consideration.
2. The bottom paragraph of the article explains his reasoning behind hoping for a recursive version in interviews: "When I actually implemented this in C, the iterative version was not only messier, but also nearly four times slower than the recursive one. ... a modern CPU will predict all the return addresses correctly. And the work of figuring out which of the two candidate disks to move next and where to is quite a bit more than just finding the spare peg. Since any Towers of Hanoi problem that will complete in less than a day should fit entirely in L1 cache, the extra instructions and (potentially mispredicted) branches to find the next move are worse than the extra memory operations for the recursion." It's not clear from some of the comments in this thread that many people read all the way down to that paragraph.
3. His test case is here: http://tjd.phlegethon.org/blog/hanoi.c http://tjd.phlegethon.org/blog/hanoi.c ... if he has done something wrong, this would be the place to go looking for it. I don't see anything obviously wrong with his iterative version, although I'm getting a double-free error after compiling and running his code.
I've believed for years that iterative approaches gave better performance than recursive versions. This probably goes all the way back to working in 68k assembly. I'm pretty sure there's a chapter in Beautiful Code that suggests iterative is better than recursive, performance-wise. But if Tim's right, then I've learned something valuable today.
edit: I'm busy today and my C is suuuuper rusty; I think there might be something in that for loop in finish() that's screwing up the pegs[2] that's being passed to free() a couple of lines later, but I don't really have the time to debug it. Hopefully someone else is willing to try, I'd like to see what the actual results turn out to be in different environments.
- anindyabd 12y agoThank you. It seems that people read the title of the post, skimmed through half of it, then rushed to post their opinion. Reminds me of an Ars Technica experiment I read about in Jeff Atwood's blog [1]: "Ars Technica ran a little experiment in 2011. When they posted Guns at home more likely to be used stupidly than in self defense, embedded in the last sentence of the seventh paragraph of the article was this text: If you have read this far, please mention Bananas in your comment below. We're pretty sure 90% of the respondants to this story won't even read it first. The first person to do this is on page 3 of the resulting discussion, comment number 93." [1] http://blog.codinghorror.com/because-reading-is-fundamental-2/ http://blog.codinghorror.com/because-reading-is-fundamental-...
- jnbiche 12y agoNice try discounting our opinions about interviewing by citing a completely unrelated forum and article. I'm sure you know the name of that particular logical fallacy. Despite my frustration with the attitude displayed toward interviewers, I actually did read to the end because I'm in the middle of reading Concrete Mathematics[1], which starts with the Tower of Hanoi. So I was interested in his solution. 1. Concrete Mathematics: A Foundation for Computer Science. Graham, Knuth, Patashnik.
- anindyabd 12y agoI'm not sure how citing the article discounts your opinion about interviewing. All it does is say that it's common for people to make comments without reading through entire articles. I'm sure there are plenty of people who do read through articles, but I'm also sure there are plenty of others who don't, and the experiment proves it.
- jnbiche 12y agoIt's not the blog post content that people are reacting to (which I agree was edifying), it's the attitude toward interviews. No one is complaining about or criticising his code or his discussion of the Towers of Hanoi solution (although some skepticism has been expressed about the exact speedup he's getting). I'm quite sure the man has forgotten more about embedded programming than I know.
- thaumaturgy 12y agoLet's agree that the tone of his article could use a little work. What about the substance of it? I read his article as, "too many candidates don't realize that recursive solutions are better than iterative ones now." If that's true, it seems like a big deal. He's not really arguing for knowledge of some arcane language feature or framework widget; this would be a fundamental aspect of programming methodology, something that might be broadly applicable. edit: sorry, I just realized we're talking at cross-purposes. Yeah, his approach to interviews could maybe use some work. I just didn't read that as what the article was about, so I was ignoring that as a conversational topic.
- jnbiche 12y agoNo, I agree with you 100% that the blog is very interesting. I'll probably check out his code in greater detail. But developers are really getting tired of these types of interviews and interviewers. I can just feel the anger and frustration in others I know rising. It's morally and ethically wrong to make formal complaints to Congress about developer shortages and then turn around and exclude well-qualified candidates because hiring devs are clinging to some deprecated model of interviewing that has a mediocre true positive rate but an awfully, awfully high false negative rate.
- peterwwillis 12y ago1. I learned years ago that just because someone has a PhD, does not mean they're not also an idiot. Work with enough PhDs and you'd agree. 2. The comments are a reaction to the story, not a reflection on the character of the author. Most comments are about interviewers that make the same mistake the author did before the author realized their erroneous assumption. They're engaging in group validation of an immediate opinion or feeling without thorough analysis, or what is also known as "commenting on the internet". 3. Remember one of the cardinal rules of HN about meta-commenting? Yeah, it doesn't really help.