I doubt he'll bother, but I would love to know Knuth's reaction to this article.
"TAOCP is written for MIX and MIX is not FreeBSD."
You're Doing It Wrong: CS in the real world
31–40 of 60 posts
Re: You're Doing It Wrong: CS in the real world
#32To be honest. I think it's a misconception that CS is about algorithms. The science should be modeling the relationships between the environment, the desired functionality and the resulting trade-offs. There's actually a lot of this to go around, but it's not recognized enough. The electrical engineering establishment, which is more concerned with buildings specific systems and algorithms, is far more influential. We…
This is very general. What would you recommend, more specifically?
Re: You're Doing It Wrong: CS in the real world
#33Earlier quoted context omitted.
> When I said "a heap big enough to require multiple pages", I actually meant it. Did you? Your math that follows seems to indicate otherwise. > Hence, I was referring to the size of the heap he used for his test: 8MB (1M records, 512 elements per page, 1954 pages allocated in memory). I don't understand. I demonstrated that a heap with only 2048 records requires multiple 4 KB pages. Are you perhaps confusing KB with…
You guys are totally talking past each other. Varnish makes the assumption that the OS cache replacement policy is awesome. You should let it do its thing and write your data structures accordingly. Considering that the author is intimately familiar with that policy, it's a valid approach. You could alternately say that you don't want to depend on the OS policy, which you don't control. You could say that using a dif…
> You guys are totally talking past each other.
That doesn't change the fact that, as best I can discern, the OP has made some factual errors which demand (" rel="nofollow">http://xkcd.com/386/>) response.
Re: You're Doing It Wrong: CS in the real world
#34Earlier quoted context omitted.
You guys are totally talking past each other. Varnish makes the assumption that the OS cache replacement policy is awesome. You should let it do its thing and write your data structures accordingly. Considering that the author is intimately familiar with that policy, it's a valid approach. You could alternately say that you don't want to depend on the OS policy, which you don't control. You could say that using a dif…
You guys are totally talking past each other. Not totally, it started with "the article is dumb", to which someone replied "nuh uh! you're dumb", to which the OP replied, "oh no i'm not", to which another reply said "oh yes you are". Very focused. (The rest of the posts were good reading, but getting the emotion involved just makes everyone mad. Neither of the commenters cared anymore about their argument, they only…
> The rest of the posts were good reading, but getting the emotion involved just makes everyone mad.
For my part, there was no emotion involved. That's why I didn't bother replying to the emotional aspects of timr's second post.
> Neither of the commenters cared anymore about their argument, they only cared about winning.
I care a lot about the argument; I think Poul's article was interesting and relevant, and should not be dismissed by people who (it seems clearly to be the case) did not understand it, but think they did.
Re: You're Doing It Wrong: CS in the real world
#35Earlier quoted context omitted.
One problem is that the article seems to incorrectly assume that "theory" always ignores memory hierarchies. That was true in, say, 1975, but the past 20 years of algorithms theory pays a lot of attention to memory hierarchies. You can even get all sorts of off-the-shelf algorithms designed to perform well on typical modern memory configurations. I mean, he's basically arguing that CS hasn't revisited heaps since 196…
Undergraduate CS education certainly hasn't.
Hmm, my undergrad algorithms class at least mentioned the existence of cache effects, though it didn't really go into any detail. It had a bit of disclaimer along the lines of: for simplicity, we don't take into account caches in this class, but more modern models of computation do, and for real-world applications you might want to look up cache-aware algorithms.
Re: You're Doing It Wrong: CS in the real world
#36Well this certainly sparks my interest. Could I ask for some recommendations for any books and articles on algorithms which take the current computer/memory architecture into account?
I'm currently reading "Mastering algorithms with C", and I had some other books in queue. But I'm always looking for some fresh content.
Re: You're Doing It Wrong: CS in the real world
#37Earlier quoted context omitted.
"I could be wrong, but it sounds to me like you may not have the base of knowledge necessary to accurately evaluate Poul's writing." Touché. I'm not Knuth or anything, but I try. "Pages are 4KB on most systems; I don't know where you're getting your 8MB number from." When I said "a heap big enough to require multiple pages" , I actually meant it. Hence, I was referring to the size of the heap he used for his test: 8M…
> When I said "a heap big enough to require multiple pages", I actually meant it. Did you? Your math that follows seems to indicate otherwise. > Hence, I was referring to the size of the heap he used for his test: 8MB (1M records, 512 elements per page, 1954 pages allocated in memory). I don't understand. I demonstrated that a heap with only 2048 records requires multiple 4 KB pages. Are you perhaps confusing KB with…
"Your math that follows seems to indicate otherwise....I demonstrated that a heap with only 2048 records requires multiple 4 KB pages. Are you perhaps confusing KB with MB?"
No. There are 1M records, 512 per page. This is directly from the article. From this, we can deduce that each record is 4096 / 512 = 8 bytes. Eight bytes multiplied by 1M records: 8MB.
Don't believe my math? OK. The article explicitly said that there were 1954 pages in the heap. If we have a 4k page size, that's (4096 * 1954) bytes == 7.63 MB. Even better.
Re: You're Doing It Wrong: CS in the real world
#38Earlier quoted context omitted.
> When I said "a heap big enough to require multiple pages", I actually meant it. Did you? Your math that follows seems to indicate otherwise. > Hence, I was referring to the size of the heap he used for his test: 8MB (1M records, 512 elements per page, 1954 pages allocated in memory). I don't understand. I demonstrated that a heap with only 2048 records requires multiple 4 KB pages. Are you perhaps confusing KB with…
You guys are totally talking past each other. Varnish makes the assumption that the OS cache replacement policy is awesome. You should let it do its thing and write your data structures accordingly. Considering that the author is intimately familiar with that policy, it's a valid approach. You could alternately say that you don't want to depend on the OS policy, which you don't control. You could say that using a dif…
I'm not talking past anyone -- I'm just choosing to ignore the silly aspersions to my intelligence. It's possible to make an argument without calling the other guy stupid.
What you're seeing here is really just the usual battle between ideology and reason that seems to pop up on HN on the weekends. We've got a fundamentally silly article that wants to take all of computer science to task, based on a corner-case analysis of worst-case performance of a single algorithm, in a single, exaggerated context.
You're right that the author wants to rely entirely upon the OS cache replacement policy for Varnish and that's fine, as far as it goes. But this ideology leads directly to the problem observed (namely: some rarely used things that really should stay in memory are evicted, because the OS has no ability to discern the semantics of memory use by the application). Rather than acknowledging this limitation, the author has decided instead that the algorithms are all wrong, and that the Stoopid Computer Scientists are all a bunch of short-sighted eggheads.
Again, it's not a question of who's right, and who's wrong -- it's a matter of philosophy. You can assume that the OS memory manager is the all-knowing, all-powerful Wizard of RAM, or you can give it some guidance. In this case, locking an 8MB heap into RAM is hardly a trade-off, when you're talking about a system that is actively managing several orders of magnitude more memory on a regular basis. Spending days of coding time optimizing a basic data structures for worst-case memory access patterns is short-sighted, when the alternative is an mlock() call.
Re: You're Doing It Wrong: CS in the real world
#39Earlier quoted context omitted.
Undergraduate CS education certainly hasn't.
Hmm, my undergrad algorithms class at least mentioned the existence of cache effects, though it didn't really go into any detail. It had a bit of disclaimer along the lines of: for simplicity, we don't take into account caches in this class, but more modern models of computation do, and for real-world applications you might want to look up cache-aware algorithms.
Hmm, my undergrad algorithms class at least mentioned the existence of cache effects, though it didn't really go into any detail.
There should at least be exposure on the level of a walkthrough of the optimization of a real-world server. There was a concurrency optimization video posted to HN a couple of weeks ago.
Re: You're Doing It Wrong: CS in the real world
#40This article is stealing from a whole science of Cache Oblivous Algorithms. The author is trying to say he invented this idea, what a load of BS. If he did invent this then he is just misinformed/miseducated :(