按年被提到
20122016 · 2 次2026
系统、数据库与网络›计算机体系结构与硬件·arXiv:1212.0703 · cs.DS

The Cost of Address Translation

地址转换的代价
Tomasz Jurkiewicz, Kurt Mehlhorn · 2012

提出 VAT 模型,刻画虚拟内存地址转换对算法耗时的影响

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 5 人首次 2015-12-29 · 最近 2020-10-21发表于 Society for Industrial and Applied Mathematics eBooks
5不同的人
5活跃月份
5讨论串
6被引(OpenAlex)

论文指出现代计算机并非随机访问机,而是有内存层次、多核和虚拟内存。作者的出发点是:对数组随机扫描、二分查找、堆排序等简单算法,用 RAM 模型或外存(EM)模型的分析无法正确预测实际运行时间的增长率。为此提出 VAT(虚拟地址转换)模型来计入地址转换的代价,并用它分析上述算法及其他算法,预测与测量结果吻合,还分析了缓存无关算法的 VAT 代价。

HN 为什么提它

HN 上的人引用它说明虚拟地址转换和 TLB 开销会让 C 数组访问呈现类似 log(N) 的行为,也被推荐为这一话题的入门材料。

实证研究难度 4 / 5约 40 分钟经得起时间
读之前最好知道
1RAM 计算模型与外存模型
2虚拟内存与页表
3TLB 与缓存层次
4算法分析(二分查找、堆排序)

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐Tojot · 2016-08

“Feel free to take a look at a free copy at The Cost of Address Translation where we establish the VAT cost model.”

推荐自己的论文,其中建立了虚拟地址转换的成本模型
Accessing RAM sometimes costs extra log(N)原评论 ↗
推荐adrianN · 2018-05

“Check out The Cost of Address Translation for some introduction to the topic.”

推荐这篇作为地址转换与 TLB 开销的入门
A new fast hash table in response to Google’s new fast hash table原评论 ↗
引用matt_d · 2015-12

“as demonstrated in the following work by Jurkiewicz & Mehlhorn: The Cost of Address Translation”

引用这项工作,证明地址转换代价会影响常见算法的运行时间
Test results for Broadwell and Skylake原评论 ↗
引用corysama · 2017-01

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

提到论文显示 TLB 压力大时 C 数组访问呈 log(N) 行为
Maps and sets can have quadratic-time performance原评论 ↗
被提交为 story · 2 次