HackerPapers

arXiv:1212.0703cs.DS

The Cost of Address Translation

Tomasz Jurkiewicz, Kurt Mehlhorn

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.

arXiv comments
A extended abstract of this paper was published in the proceedings of ALENEX13, New Orleans, USA
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms cs.CCComputational Complexity cs.PFPerformance

On Hacker News

Linked by 4 identifiable commenters in 4 comments across 4 threads, from Dec 2015 to May 2018. Found in 2 HN submissions from Aug 2016 to Oct 2020. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. A new fast hash table in response to Google’s new fast hash table 1 comment

    • You just need to use a machine model that takes into account the cost of address translation and the TLB. Check out https://arxiv.org/abs/1212.0703 for some introduction to the topic.

      adrianNView on HNParent context

  2. Maps and sets can have quadratic-time performance 1 comment

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

      corysamaView on HNParent context

  3. Accessing RAM sometimes costs extra log(N) 1 comment

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

      TojotView on HNParent context

  4. Test results for Broadwell and Skylake 1 comment

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

      matt_dView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.