News for hackers. Stuff that matters.
Re:You're Doing It Wrong: CS in the real world by kenjackson on Saturday June 12, 2010 @04:12PM (#1426445)
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 non-trivial algorithms.

Another example of a complicating issue is garbage collection. If the GC uses something like compaction you really don't have a great idea of where your data is. 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.

And there really are kind of two related questions: 1) How does this algorithm perform for a given memory hierarchy? 2) What is the best parameterization of this algorithm for the memory hierarchy?

Question 1 is a fair bit easier than question 2. And you'd be surprised at how much faster you can make the same algorithm, by changing certain parameters (chunk size, etc...) for a given architecture. And these things are hard to answer by simple reasoning. And a local maxima, may in fact be far from the global maxima.

Re:You're Doing It Wrong: CS in the real world by wingo on Sunday June 13, 2010 @04:35PM (#1428156)
> 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 by kenjackson on Monday June 14, 2010 @07:08PM (#1431319)
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 by wingo on Tuesday June 15, 2010 @09:28AM (#1432655)
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.