{"id":15707,"date":"2016-08-31T14:22:01","date_gmt":"2016-08-31T18:22:01","guid":{"rendered":"http:\/\/mjtsai.com\/blog\/?p=15707"},"modified":"2016-08-31T16:56:34","modified_gmt":"2016-08-31T20:56:34","slug":"the-myth-of-ram","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2016\/08\/31\/the-myth-of-ram\/","title":{"rendered":"The Myth of RAM"},"content":{"rendered":"<p><a href=\"http:\/\/www.ilikebigbits.com\/blog\/2014\/4\/21\/the-myth-of-ram-part-i\">Emil Ernerfeldt<\/a> (via <a href=\"https:\/\/twitter.com\/xenadu02\/status\/770303885185470464\">Russ Bishop<\/a>, <a href=\"https:\/\/news.ycombinator.com\/item?id=12383012\">Hacker News<\/a>, <a href=\"https:\/\/www.reddit.com\/r\/programming\/comments\/2v8dty\/the_myth_of_ram_part_i_why_a_random_memory_read\/\">Reddit<\/a>):<\/p>\n<blockquote cite=\"http:\/\/www.ilikebigbits.com\/blog\/2014\/4\/21\/the-myth-of-ram-part-i\"><p>This article is the first of four in a series, in which I argue that thinking of a memory access as <em>O(1)<\/em> is generally a bad idea, and we should instead think of them as taking <em>O(&#8730;N)<\/em> time. In part one I lay out a hand-wavy argument based on a benchmark. In <a href=\"http:\/\/www.ilikebigbits.com\/blog\/2014\/4\/28\/the-myth-of-ram-part-ii\">part II<\/a> I build up a mathematical argument based in theoretical physics, and in <a href=\"http:\/\/www.ilikebigbits.com\/blog\/2014\/4\/29\/the-myth-of-ram-part-iii\">part III<\/a> I investigate some implications. <a href=\"http:\/\/www.ilikebigbits.com\/blog\/2015\/2\/9\/the-myth-of-ram-part-iv\">Part IV<\/a> is a FAQ in which I answers some common questions and misunderstandings.<\/p><\/blockquote>\n<p>I think he&rsquo;s misusing O-notation by not focusing on the asymptotic behavior. However, the general point that memory access times are nonuniform and layers of cache matter is sound.<\/p>\n<p>See also: Erik Demaine&rsquo;s <a href=\"http:\/\/courses.csail.mit.edu\/6.851\/spring12\/lectures\/\">Memory Hierarchy lectures<\/a>.<\/p>\n<p>Update (2016-08-31): See also: <a href=\"http:\/\/www.overbyte.com.au\/misc\/Lesson3\/CacheFun.html\">CacheFun<\/a> (via <a href=\"https:\/\/twitter.com\/McCloudStrife\/status\/771089008545845248\">McCloud<\/a>).<\/p>","protected":false},"excerpt":{"rendered":"<p>Emil Ernerfeldt (via Russ Bishop, Hacker News, Reddit): This article is the first of four in a series, in which I argue that thinking of a memory access as O(1) is generally a bad idea, and we should instead think of them as taking O(&#8730;N) time. In part one I lay out a hand-wavy argument [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[4],"tags":[289,263,138,71,1056],"class_list":["post-15707","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-algorithm","tag-theory","tag-optimization","tag-programming","tag-ram"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/15707","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=15707"}],"version-history":[{"count":2,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/15707\/revisions"}],"predecessor-version":[{"id":15716,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/15707\/revisions\/15716"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=15707"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=15707"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=15707"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}