Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

You're Doing It Wrong: CS in the real world

queue.acm.org

Post reply on HN
Print view View original

41–50 of 60 posts

Re: You're Doing It Wrong: CS in the real world

#41

Post by nostrademons »

kmavm wrote: post #22

Knuth was writing for MIX. This machine, like all its contemporaries, had a flat memory hierarchy. If you've ever wondered why the CS literature seems full of trees, but in 2010 practice, sets, associative memories, etc., are often implemented with hashing, consider that a cache miss on much modern hardware is 300 cycles. The equivalent of for (register int i = 0; i can pay for itself by saving a cache miss. The log…

This is a big problem for functional languages, and there've been a bunch of efforts to solve it. For example, Clojure's default dictionary type uses a hash array-mapped trie, with each level sized so that a typical block can fit in a single cache line. It's very common for the youngest generation in a generational garbage collector to be sized to fit entirely into L2 cache, so that you know that every write or read of a recently-allocated value will at least be an L2 cache hit. (Unfortunately, it's usually not practical to make it a L1 hit, lest you be stuck thrashing in the GC, so you're still looking at ~12 cycles.) Deforestation optimizes out allocation entirely, instead performing the next computation immediately on values that are already in registers. Many GCs will also try to copy nearby pointers next to their parents, so that the pointers aren't quite random.

Re: You're Doing It Wrong: CS in the real world

#42

Post by jemfinch »

timr wrote: post #38
wrs wrote: post #28

Earlier 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…

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 analy…

> I'm not talking past anyone -- I'm just choosing to ignore the silly aspersions to my intelligence.

There haven't been any "silly aspersions" to your intelligence. You just didn't exhibit a sufficient knowledge of the problem to dismiss the article like you did. Computer science is a large field, and it doesn't say anything at all about your intelligence if you're unaware of one particular implementation of one particular type of software by one particular author. You're the one who's cast this whole conversation into a competition, not me.

> It's possible to make an argument without calling the other guy stupid.

Exactly, which is why I responded like I did, and gave you an opportunity to explain whether I misunderstood you. You, on the other hand, responded with sarcasm and rhetoric, and clarified nothing.

Re: You're Doing It Wrong: CS in the real world

#43

Post by jemfinch »

timr wrote: post #37
jemfinch wrote: post #23

Earlier 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…

"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 t…

Why are you still arguing about this? Your original claim was, "if you build a binary heap...and make that heap big enough to require multiple pages (about 8 MB". It does not take 8 MB to make a heap "big enough to require multiple pages." It takes 4 KB. PHK's example was a middling-sized heap, not the minimum heap necessary to require multiple pages, as you implied with your original statement.

Re: You're Doing It Wrong: CS in the real world

#44

Post by blahedo »

It's good of him to remind us not to live in the clouds, I guess, but I think he's hitting a bit of a straw man here. I just finished teaching a CS2 course where a recurring theme is that big-O complexity isn't and can't be the only thing you consider when choosing an algorithm. My understanding is that this is typical---that this idea is usually covered somewhere in the first couple terms of a standard CS major. Admittedly, I didn't talk specifically about memory paging (since they won't really hit that until their OS/Networking class next year), but it's a fairly natural extension of the tradeoffs I did train them to consider.

Put another way, if presented with this article, I'd expect my students not to say "ZOMG what have I been doing??" but rather "Ah, another thing to look out for!" And I suspect this is typical of modern CS2 courses, not to mention more advanced algorithms courses.

Re: You're Doing It Wrong: CS in the real world

#45

Post by jemfinch »

_delirium wrote: post #27
jemfinch wrote: post #24

Earlier quoted context omitted.

> I mean, he's basically arguing that CS hasn't revisited heaps since 1961...But that's of course not the case. Then kindly link me to the paper which describes his B-heaps; I'd love to read it.

His specific B-heaps might indeed be novel; I'm not claiming he makes no contribution. I'm just objecting to the portion of his paper that claims that nobody in CS has ever thought of the idea of optimizing heaps for the properties of a modern computer's memory hierarchy. He seems to really believe Knuth's 1961 paper is the last word on the subject, or at least says so. Fwiw, here's a widely cited 1996 paper that des…

That's a great paper, thanks for the reference.

Re: You're Doing It Wrong: CS in the real world

#46

Post by gaius »

_delirium wrote: post #35
gaius wrote: post #26

Earlier 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.

In mine, we learnt about the hardware, the cache hierarchy and so on, completely separately from the algorithms and complexity theory. Two different classes, two professors. Probably they both knew it themselves, but it never occurred to them to cross-pollinate their course materials.

Re: You're Doing It Wrong: CS in the real world

#47

Post by haberman »

kmavm wrote: post #22

Knuth was writing for MIX. This machine, like all its contemporaries, had a flat memory hierarchy. If you've ever wondered why the CS literature seems full of trees, but in 2010 practice, sets, associative memories, etc., are often implemented with hashing, consider that a cache miss on much modern hardware is 300 cycles. The equivalent of for (register int i = 0; i can pay for itself by saving a cache miss. The log…

Note that the article's "improved" data structure is 30% slower than the naive binary heap when there's no VM pressure. And his heap is small compared to the cache itself.

In other words, if he had just used mlock() to make sure his heap wasn't getting swapped out, he would have gotten better performance and avoided the need to invent a "new" data structure. He chose a really bad example to get on a soapbox about.

Re: You're Doing It Wrong: CS in the real world

#48

Post by Confusion »

stcredzero wrote: post #18
acqq wrote: post #14

Earlier quoted context omitted.

The article is really poorly written. The specific example is very specific, the claims that "nobody else gets it" are in fact unsubstantiated. All the effects he mentions are very known among right professionals. And the title text is not about "relative latency" you mention but about the cost of paging, once something gets paged out.

The specific example is very specific Sounds good to me. the claims that "nobody else gets it" are in fact unsubstantiated I'm pretty sure that the entire shop at my last consulting job would all claim it was news to them. Most people don't have to deal with issues like the ones discussed in the article, so it's perfectly understandable that it would be news to them. I don't have to deal with such issues on a daily b…

  I'm pretty sure that the entire shop at my last consulting
  job would all claim it was news to them
On the other hand, I'm pretty sure that the same doesn't hold for the actual target audience of this article.

Re: You're Doing It Wrong: CS in the real world

#49

Post by [deleted] »

haberman wrote: post #47
kmavm wrote: post #22

Knuth was writing for MIX. This machine, like all its contemporaries, had a flat memory hierarchy. If you've ever wondered why the CS literature seems full of trees, but in 2010 practice, sets, associative memories, etc., are often implemented with hashing, consider that a cache miss on much modern hardware is 300 cycles. The equivalent of for (register int i = 0; i can pay for itself by saving a cache miss. The log…

Note that the article's "improved" data structure is 30% slower than the naive binary heap when there's no VM pressure. And his heap is small compared to the cache itself. In other words, if he had just used mlock() to make sure his heap wasn't getting swapped out, he would have gotten better performance and avoided the need to invent a "new" data structure. He chose a really bad example to get on a soapbox about.

[deleted]

Re: You're Doing It Wrong: CS in the real world

#50

Post by sesqu »

jemfinch wrote: post #43
timr wrote: post #37

Earlier quoted context omitted.

"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 t…

Why are you still arguing about this? Your original claim was, "if you build a binary heap...and make that heap big enough to require multiple pages (about 8 MB". It does not take 8 MB to make a heap "big enough to require multiple pages." It takes 4 KB. PHK's example was a middling-sized heap, not the minimum heap necessary to require multiple pages, as you implied with your original statement.

The original was make that heap big enough to require multiple pages (about 8 MB, in this case

You are arguing that it has to be 4 KB. timr is arguing it has to be big enough, and that it is 8 MB. The implication is that it is big enough to qualify, without commenting on how big is big enough.

The wording was misleading, and you made the mistake of focusing on what you saw to be an error in expression and taking it to be error in meaning, even after debate. Sadly, that's a very easy mistake to make, especially if you haven't argued with people very much, and it is only exacerbated by a textual medium with memory that can be referenced. If you ever find yourself in a similar situation again, try to read the whole offending paragraph for context. A lot of people make inaccurate statements that can only be correctly understood by identifying their frame of thought (which can be in error, muddled, or just presuming).

Post reply on HN