You're Doing It Wrong: CS in the real world • Hacker News Board

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

#51

Post by albertcardona » Sun, Jun 13, 2010, 7:21 PM UTC

Reads like their server is beyond capacity at the moment. Any cached copies?

EDIT: http://webcache.googleusercontent.com/search?q=cache:Q3SZ-4y...

  500
  
  The request has been canceled by the administrator or by the server.
  
  coldfusion.monitor.event.MonitoringServletFilter$StopThreadException: The request has been canceled by the administrator or by the server.
  	at coldfusion.monitor.event.MonitoringServletFilter.doFilter(MonitoringServletFilter.java:65)
  	at coldfusion.bootstrap.BootstrapFilter.doFilter(BootstrapFilter.java:46)
  	at jrun.servlet.FilterChain.doFilter(FilterChain.java:94)
  	at jrun.servlet.FilterChain.service(FilterChain.java:101)
  	at jrun.servlet.ServletInvoker.invoke(ServletInvoker.java:106)
  	at jrun.servlet.JRunInvokerChain.invokeNext(JRunInvokerChain.java:42)
  	at jrun.servlet.JRunRequestDispatcher.invoke(JRunRequestDispatcher.java:286)
  	at jrun.servlet.ServletEngineService.dispatch(ServletEngineService.java:543)
  	at jrun.servlet.jrpp.JRunProxyService.invokeRunnable(JRunProxyService.java:203)
  	at jrunx.scheduler.ThreadPool$ThreadThrottle.invokeRunnable(ThreadPool.java:428)
  	at jrunx.scheduler.WorkerThread.run(WorkerThread.java:66)

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

#52

Post by wingo » Sun, Jun 13, 2010, 8:35 PM UTC

kenjackson wrote: post #20

ssp wrote: post #10

Earlier quoted context omitted.

Nevertheless, this is a good example as to why performance on real machines often needs to be implemented, rather than speculated, as the the architectural complexity can lead to some interesting peformance characteristics I don't really agree with this. In the old days, to really get an idea of how fast something would run, you had to count cycles and think about pipeline hazards and whatnot. Today, you can simply e…

Actually, even if your goal is to simply count jumps in the memory hierarchy, it can still be tough for several reasons. For example, the set associativity of a given level of the memory hierarchy can make analysis very tricky. Somethings that would ostensibly be efficient w/ respect to the memory hierarchy could actually have a whole bunch of conflict misses. Modeling this is possible, but not easy. Especially for n…

> We used to do all these tricks in 'C' to map data and move it around to get the best locality. This isn't nearly as feasible in C# and Java.

Did we really? With malloc things are just as unpredictable. If you resort to mmap-like memory-management, such schemes are almost as feasible in high-level languages (with appropriate FFIs) as in low-level languages, provided you are accessing data and not code.

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

#53

Post by davidcuddeback » Mon, Jun 14, 2010, 1:09 AM UTC

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.

FTA: A 300-GB backing store, memory mapped on a machine with no more than 16 GB of RAM, is quite typical. The user paid for 64 bits of address space, and I am not afraid to use it.

He's writing a data structure that's not intended to fit within physical memory. mlock() doesn't do you any good in that scenario.

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

#54

Post by ErrantX » Mon, Jun 14, 2010, 11:09 AM UTC

jemfinch wrote: post #33

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…

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

You realize that the XKCD example is a warning for those in your position not timr's :)

(I have it hung on the wall in my office for this very reason)

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

#55

Post by kenjackson » Mon, Jun 14, 2010, 11:08 PM UTC

wingo wrote: post #52

kenjackson wrote: post #20

Earlier quoted context omitted.

Actually, even if your goal is to simply count jumps in the memory hierarchy, it can still be tough for several reasons. For example, the set associativity of a given level of the memory hierarchy can make analysis very tricky. Somethings that would ostensibly be efficient w/ respect to the memory hierarchy could actually have a whole bunch of conflict misses. Modeling this is possible, but not easy. Especially for n…

> We used to do all these tricks in 'C' to map data and move it around to get the best locality. This isn't nearly as feasible in C# and Java. Did we really? With malloc things are just as unpredictable. If you resort to mmap-like memory-management, such schemes are almost as feasible in high-level languages (with appropriate FFIs) as in low-level languages, provided you are accessing data and not code.

Well there are some big differences. One thing being that you don't have the same type safety in C as in many higher level languages. If I say the memory at 0xdeadbeef is of type X, well then its type X.

The other thing is that memory locations don't change. If my object is at location L then I know its at location L unless I move it. With compaction, unless I'm pinning objects (and making the GCs and allocators life hard) my object doesn't have a fixed location.

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

#56

Post by phkamp » Tue, Jun 15, 2010, 10:25 AM UTC

Ohh, dear, another forum to keep an eye on :-)

First: congratulations, the level of discussion here is a fair bit above what I have seen so far on reddit and slashdot.

Second: A sense a number of bruised egos. Good. That is often a sound indication that a sore point successfully poked.

Third: user "gaius" hits the problem spot on:

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

If I can get those two professors to talk to each other, my article will have been worth the effort. Hopefully the HW-prof will tease the algorithm-prof with my article and some fruitfull cooperation ensue.

The important point in my article is not the B-heap, that took me all of an hour to figure out and I'm sure most of you could have done the same thing, had your thoughts been wandering in that direction.

No, the important point is that most CS educations don't even mention that actual computers have Virtual Memory, Write buffers, multilevel caches and so on, and if they do, the certainly don't mention that the O() function depends on 13+ more or less stochastic variables extracted therefrom.

Several people here, and elsewhere, seem to make the sign of the cross at there mere mention of virtual memory and RAM overcommit. That is understandable, in particular if nobody ever taught them how to properly use those facilities.

Getting into a fight with the kernels VM bits is a sure-fire recipe for lousy performance, and after one or two such experiences, becoming a bit sceptical is fair.

But the facts are, that by intelligently using the those VM bits you save a lot of complex code, and get as good performance as you can hope for.

But you have to know what you are doing, and for most of us, that means that the professor should have told us.

Poul-Henning

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

#57

Post by wingo » Tue, Jun 15, 2010, 1:28 PM UTC

kenjackson wrote: post #55

wingo wrote: post #52

Earlier quoted context omitted.

> We used to do all these tricks in 'C' to map data and move it around to get the best locality. This isn't nearly as feasible in C# and Java. Did we really? With malloc things are just as unpredictable. If you resort to mmap-like memory-management, such schemes are almost as feasible in high-level languages (with appropriate FFIs) as in low-level languages, provided you are accessing data and not code.

Well there are some big differences. One thing being that you don't have the same type safety in C as in many higher level languages. If I say the memory at 0xdeadbeef is of type X, well then its type X. The other thing is that memory locations don't change. If my object is at location L then I know its at location L unless I move it. With compaction, unless I'm pinning objects (and making the GCs and allocators life…

Good points, though with FFIs you have the same level of unsafety. A more limited mmap wrapper could provide bounds checking, but it's still your job to interpret the bytes being mapped.

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

#58

Post by rlpb » Tue, Jun 15, 2010, 3:01 PM UTC

davidcuddeback wrote: post #53

haberman wrote: post #47

Earlier quoted context omitted.

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.

FTA: A 300-GB backing store, memory mapped on a machine with no more than 16 GB of RAM, is quite typical. The user paid for 64 bits of address space, and I am not afraid to use it. He's writing a data structure that's not intended to fit within physical memory. mlock() doesn't do you any good in that scenario.

I think your quote is about the entire cache, not just the heap.

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

#59

Post by mhartl » Thu, Jun 17, 2010, 3:12 PM UTC

phkamp wrote: post #56

Ohh, dear, another forum to keep an eye on :-) First: congratulations, the level of discussion here is a fair bit above what I have seen so far on reddit and slashdot. Second: A sense a number of bruised egos. Good. That is often a sound indication that a sore point successfully poked. Third: user "gaius" hits the problem spot on: "In mine, we learnt about the hardware, the cache hierarchy and so on, completely separ…

Glad to have you here! Since you're new to HN, I've got one quick note from the site guidelines (http://ycombinator.com/newsguidelines.html):

  Please don't sign comments, especially with your url. 
  They're already signed with your username. If other users
  want to learn more about you, they can click on it to see
  your profile.

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

#60

Post by mfukar » Sun, Jul 11, 2010, 6:25 PM UTC

acqq wrote: post #14

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…

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.

I'm willing to forgive his "poor" writing on account that he's right - most CS students and graduates don't have any clue about cache effects on algorithm implementations, and that's just wrong.