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

21–30 of 60 posts

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

#21

Post by slioslat »

Qz wrote: post #6
slioslat wrote: post #4

this article is ridiculous. He makes blanket claims based on the performance of a very specialized application. For many / most applications, memory is so cheap that you CAN effectively ignore VM. Where some thought about the relative latency of memory is useful though is in parallel applications on NUMA hardware.

That depends whether, when you're talking about 'most applications', you mean most by sheer number , or most by processing time used . Because yes, there are a zillion tiny applications that don't care about VM space. But the ones that do are used far more often (running nonstop on servers, etc) than that random iBoobs app on your iPhone.

Even for most applications "running non-stop on servers", VM is almost moot these days. For anything computational, swap is the kiss of death. For many applications where the working set is larger than available memory, the work is typically done inside a DBMS which usually has it's own systems for managing paging. Algos in DBMS are certainly aware of non-uniform access time: http://en.wikipedia.org/wiki/B-tree

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

#22

Post by kmavm »

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 N cache misses to find something in a tree (the pointers all point somewhere random, and you should expect them to miss) is much more expensive than hashing reasonable-length keys and taking a single cache miss in a hash table, for almost any value of N > 1.

The author has made a nice contribution; as Colivas probably was trying to hint to him, there is a long history of converting linked data structures to block-friendly form by an analogous transformation. A straight write-up of his work, without all the chest-pounding over his rediscovery of the fact that block devices operate on blocks, would have been a pleasure to read. Pity.

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

#23

Post by jemfinch »

timr wrote: post #19
jemfinch wrote: post #15

Earlier 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. > So, maybe I'm reading this wrong, but it sure sounds like he's going out of his way to find a scenario that results in an "order of magnitude" difference, simply so that he can write an article with a big claim. What he's saying is that this order of magnitude difference is where his so…

"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 MB?

> Indeed. If you fixed your 8MB heap in memory, you would lose that 8MB of pages for other uses. I guess it's a trade-off then...is it better to use 8MB of RAM on a system with gigabytes of main memory, or to re-write fundamental data structures for worst-case timing of operations that occur once per minute?

The knowledge you seem especially to lack here is that Poul's software, Varnish, is designed to operate in conditions where swap is being used. It's irrelevant how many gigabytes of main memory are available: Varnish will use it all, and let the operating system decide which VM pages should be evicted to disk and which should remain resident in memory. His software lives at high VM pressure by design, so every page his index/heap requires in memory is a page of cached content that Varnish will not be able to deliver quickly. He doesn't just pay that cost when the heap runs once per minute, but also when the heap's pages are paged out again, and pages which would otherwise have remained resident in memory are brought back into memory.

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

#24

Post by jemfinch »

_delirium wrote: post #16
stcredzero wrote: post #7

Earlier quoted context omitted.

this article is great. He gives a specific example based on real-world performance, showing that you can't always rely on theory assuming a general case. For many intensive applications, memory is so precious, you CAN'T effectively ignore VM. Some thought about the relative latency of memory is useful in more than just parallel applications on NUMA hardware. (Git and Mercurial are designed with an eye towards optimiz…

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…

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

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

#25

Post by tybris »

To 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're currently craftsmen. We have very little knowledge about building systems, except our experience and some arcane beliefs. It's time to start digging ourselves out of the stone age.

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

#26

Post by gaius »

_delirium wrote: post #16
stcredzero wrote: post #7

Earlier quoted context omitted.

this article is great. He gives a specific example based on real-world performance, showing that you can't always rely on theory assuming a general case. For many intensive applications, memory is so precious, you CAN'T effectively ignore VM. Some thought about the relative latency of memory is useful in more than just parallel applications on NUMA hardware. (Git and Mercurial are designed with an eye towards optimiz…

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.

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

#27

Post by _delirium »

jemfinch wrote: post #24
_delirium wrote: post #16

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

> 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 describes a different variety of block-aggregated heaps, "d-heaps", aimed mainly at cache-aware performance: http://lamarca.org/anthony/pubs/heaps.pdf

It's quite possible that no existing heap layouts solve his specific problem, but he could've at least acknowledged that there exist heaps newer than Knuth's, and that many of them specifically look at the influence of the memory hierarchy on performance.

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

#28

Post by wrs »

jemfinch wrote: post #23
timr wrote: post #19

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

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 differently-packed heap layout is more important than retaining 8MB more page content in the cache. (Maybe you have a nice fully-debugged heap library handy and you don't want to throw it away to get that 8MB back.) In that case, wiring that 8MB into physical memory is a valid approach.

Databases (and, indeed, OS kernels) override generic cache replacement policies like this all the time.

What is not a valid approach ("doing it wrong") is not thinking through issues like this at all, ignoring the dominating runtime cost of the memory hierarchy.

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

#29

Post by kvs »

Good article but a little resarch into recent publications in systems conferences could have helped put it in a better direction. Althogh lot of programmers use text-book algorithm there exist a large body of work (in CS) that focus on the engineering aspects of algorithms. Look into compression/decompression algorithms like PPM for example and you will see O(n^2) algos are proposed as improvements over O(lg n). (run time vs. execution time).

Design and analysis of algorithm is only one area in CS. Author is correct in pointing out CS programs lack engineering focus, at least in undergrad education.

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

#30

Post by jrockway »

wrs wrote: post #28
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…

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 cared about winning.)

At least on 4chan we get pictures of cats with this stuff ;)

Post reply on HN