Comments (4)
  • Add a Comment
  • Edit
  • More Actions v
  • Quarantine this Entry

1 IrvLustig commented Permalink

I think if you really want to prove the locality of reference theory, you have to code the same data structures in Java and C++. Otherwise, the 85x number is the effect of Java/C++ as well as the difference in data structures. So either implement the hash map approach in C++ and compare the two C++ approaches, or implement your approach in Java and compare the two Java approaches. Or maybe do both, as the results could be interesting.

Back in the days before we had caches, I did a very careful C/Fortran comparison that showed that the language you were using could affect the interpretation of the results of comparing two algorithms. The paper is "The Influence of Computer Language on Computational Comparisons: An Example from Network Optimization" and a link to it can be found here:

2 JeanFrancoisPuget commented Permalink

Irv, I agree I have not performed a scientific experiment here. If time permits we'll code in Java the same approach as in C++ to clear out any doubt, but that is of low priority compared to other tasks in our project. Anyway, I wanted to share this experience without waiting for a more scientific proof of the importance of memory locality.
Thank you for the link to your paper.

3 PaulRubin commented Permalink

If you do plan further tests, I suggest switching the Java code from HashMap to LinkedHashMap, at least if references the entry are made. Someone recently pointed out to me that iterating over the latter is deterministic (not true of the former).

4 JeanFrancoisPuget commented Permalink

Paul, thank you for the tip. I'll report on any experiment we do on the Java code, if any.