Skip to content
The methodOpen data
Back to the collection

The Cost of Address Translation

Tomasz Jurkiewicz, Kurt Mehlhorn

2012 · arXiv

AlgorithmsComputer systems
Read the paper
HN score
0
Mentions
4
Readers
4
Months
4
What’s in a score?

From the abstract

Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and virtual memory. In this paper, we address the computational cost of address translation in virtual memory. Starting point for our work is the observation that the analysis of some simple algorithms (random scan of an array, binary search, heapsort) in either the RAM model or the EM model (external memory model) does not correctly predict growth rates of actual running times. We propose the VAT model (virtual address translation) to account for the cost of address translations and analyze the algorithms mentioned above and others in the model. The predictions agree with the measurements. We also analyze the VAT-cost of cache-oblivious algorithms.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

4 selected excerpts · 4 total mentions

corysama
Neutral mention · rule
A paper came up on HN recently that showed that C arrays could have log(N) behavior for individual accesses if you antagonized the TLB cache hard enough. It got more discussion on Reddit than HN though. https://arxiv.org/abs/1212.0703 https://news.ycombinator.com/item?id=12385458 https://www.reddit.com/r/programming/comments/509qhd/randoml...
Original comment Maps and sets can have quadratic-time performance
Tojot
Neutral mention · rule
In response to "The Myth of RAM" https://news.ycombinator.com/item?id=12383012 It so happens that a large part of my PhD was on this very subject. The result I've got N log(N), this is more visible when you get to larger RAM (I had 0,5 TB RAM at the time). We have an empirical result, a justification and a rigorous predictive model. The reason has to do with hashing, but a different type: TLB. Feel free to take a look at a free copy at http://arxiv.org/abs/1212.0703 where we establish the VAT cost model.
Original comment Accessing RAM sometimes costs extra log(N)
matt_d
Neutral mention · rule
I realize that this is another topic, although in a somewhat similar context, so I thought I may just ask: Have there been any advances in reducing the page walk latency? I'm thinking of the virtual address translation costs having impact on the run times of common algorithms, e.g., as demonstrated in the following work by Jurkiewicz & Mehlhorn: http://arxiv.org/abs/1212.0703 The recent research I'm aware of is, e.g., Generalized Large-page Utilization Enhancements (GLUE) mechanism, proposed in "Large Pages and Lightweight Memory Management in Virtualized Environments" (from this year's Micro): slides: https://dl.dropboxusercontent.com/u/36554102/BPC-1.pdf ; paper:…
Read the full comment
http://paul.rutgers.edu/~binhpham/phamMICRO15.pdf Admittedly, it focuses specifically on one aspect (the Double Address Translation on Virtual Machines issue in the Jurkiewicz & Mehlhorn context). What I'm wondering about is: Has there been any progress on that on the "practical implementation" side, in the recent/coming Intel (or other, for that matter) CPUs?
Original comment Test results for Broadwell and Skylake

Keep following the thread.

More in Algorithms

More from the same topics.

2000arXiv

Dancing links

Donald E. Knuth

The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.

AlgorithmsProgramming languages
10 mentions10 months
2HN score