{"id":955,"date":"2020-11-22T23:47:17","date_gmt":"2020-11-22T15:47:17","guid":{"rendered":"https:\/\/markjohntaylor.com\/blog\/wordpress\/?p=955"},"modified":"2021-01-11T18:56:24","modified_gmt":"2021-01-11T10:56:24","slug":"memory-cpu-caches","status":"publish","type":"post","link":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/2020\/11\/22\/memory-cpu-caches\/","title":{"rendered":"Memory &#038; CPU Caches"},"content":{"rendered":"\n<p>This week and last weekend I was primarily focusing on memory pools, allocators,  CPU caches. I now probably know how allocators work, simply separating memory allocation &amp; objects initialization, for example, reserve() function in std::vector, it doesn&#8217;t initialize the allocated data segment, thus permitting better performance when we don&#8217;t need initialize the data immediately.  <\/p>\n\n\n\n<p>CPU cache is another very interesting &amp; important aspect that can (hugely) influence the performance of our programs, as it&#8217;s way faster than main memory (RAM). Smaller is faster. A great resource I found on Tuesday evening was a YouTube video &#8211; Scott Meyers&#8217;s presentation on <a href=\"https:\/\/www.youtube.com\/watch?v=WDIkqP4JbkE\">code::drive conference 2014<\/a>, a very humorous &amp; high-quality speech!! Really awesome!<\/p>\n\n\n\n<p>Here are a few slides screenshots, the complete presentation pdf version can be downloaded from <a href=\"https:\/\/github.com\/How-u-doing\/My_Library\/blob\/master\/Computer%20Science\/OS\/CPU%20Caches%20and%20Why%20You%20Care.pdf\">here<\/a>.<\/p>\n\n\n\n<figure class=\"wp-container-2 wp-block-gallery-1 wp-block-gallery columns-3 is-cropped\"><ul class=\"blocks-gallery-grid\"><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_084540-1024x576.png\" alt=\"\" data-id=\"964\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_084540.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/2020-11-18_084540\/\" class=\"wp-image-964\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_084540-1024x576.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_084540-300x169.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_084540-768x432.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_084540-1536x864.png 1536w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_084540-1568x882.png 1568w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_084540.png 1920w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085622-1024x576.png\" alt=\"\" data-id=\"959\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085622.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/?attachment_id=959\" class=\"wp-image-959\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085622-1024x576.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085622-300x169.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085622-768x432.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085622-1536x864.png 1536w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085622-1568x882.png 1568w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085622.png 1920w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085813-1024x576.png\" alt=\"\" data-id=\"960\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085813.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/?attachment_id=960\" class=\"wp-image-960\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085813-1024x576.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085813-300x169.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085813-768x432.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085813-1536x864.png 1536w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085813-1568x882.png 1568w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_085813.png 1920w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_090314-1024x576.png\" alt=\"\" data-id=\"961\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_090314.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/?attachment_id=961\" class=\"wp-image-961\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_090314-1024x576.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_090314-300x169.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_090314-768x432.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_090314-1536x864.png 1536w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_090314-1568x882.png 1568w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_090314.png 1920w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_091545-1024x576.png\" alt=\"\" data-id=\"962\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_091545.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/?attachment_id=962\" class=\"wp-image-962\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_091545-1024x576.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_091545-300x169.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_091545-768x432.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_091545-1536x864.png 1536w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_091545-1568x882.png 1568w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_091545.png 1920w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_225847-1024x576.png\" alt=\"\" data-id=\"956\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_225847.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/?attachment_id=956\" class=\"wp-image-956\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_225847-1024x576.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_225847-300x169.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_225847-768x432.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_225847-1536x864.png 1536w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_225847-1568x882.png 1568w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_225847.png 1920w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_092710-1024x576.png\" alt=\"\" data-id=\"963\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_092710.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/?attachment_id=963\" class=\"wp-image-963\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_092710-1024x576.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_092710-300x169.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_092710-768x432.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_092710-1536x864.png 1536w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_092710-1568x882.png 1568w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_092710.png 1920w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_233555-1024x576.png\" alt=\"\" data-id=\"957\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_233555.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/?attachment_id=957\" class=\"wp-image-957\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_233555-1024x576.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_233555-300x169.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_233555-768x432.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_233555-1536x864.png 1536w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_233555-1568x882.png 1568w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-17_233555.png 1920w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"1024\" height=\"576\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_000705-1024x576.png\" alt=\"\" data-id=\"958\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_000705.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/?attachment_id=958\" class=\"wp-image-958\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_000705-1024x576.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_000705-300x169.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_000705-768x432.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_000705-1536x864.png 1536w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_000705-1568x882.png 1568w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/2020-11-18_000705.png 1920w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/li><\/ul><\/figure>\n\n\n\n<p>There are some interesting tops contained within it: cache lines, false sharing, data-oriented design, etc. Very practical and constructive.<\/p>\n\n\n\n<p>From Wednesday and later, I reviewed my <a href=\"https:\/\/github.com\/How-u-doing\/DataStructures\/tree\/master\/Sorting\/compare2c\">qsort vs std::sort<\/a> problem in terms of cpu cache and cache lines. I found a hug bug (typo) in my qsort function call (embarrassed).  Then I further developed that, added a few more tests (for instance, <a href=\"https:\/\/github.com\/How-u-doing\/DataStructures\/blob\/master\/Sorting\/test\/indirection_sort.cpp\">indirect sort<\/a>), and drew some charts. The details can be found <a href=\"https:\/\/github.com\/How-u-doing\/DataStructures\/tree\/master\/Sorting\/test\">here<\/a>.<\/p>\n\n\n\n<figure class=\"wp-container-4 wp-block-gallery-3 wp-block-gallery columns-2 is-cropped\"><ul class=\"blocks-gallery-grid\"><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"820\" height=\"530\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/ubuntu_line_chart.png\" alt=\"\" data-id=\"967\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/ubuntu_line_chart.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/2020\/11\/22\/memory-cpu-caches\/ubuntu_line_chart\/\" class=\"wp-image-967\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/ubuntu_line_chart.png 820w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/ubuntu_line_chart-300x194.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/ubuntu_line_chart-768x496.png 768w\" sizes=\"(max-width: 820px) 100vw, 820px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" width=\"840\" height=\"511\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/kali_line_chart.png\" alt=\"\" data-id=\"968\" data-full-url=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/kali_line_chart.png\" data-link=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/2020\/11\/22\/memory-cpu-caches\/kali_line_chart\/\" class=\"wp-image-968\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/kali_line_chart.png 840w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/kali_line_chart-300x183.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2020\/11\/kali_line_chart-768x467.png 768w\" sizes=\"(max-width: 840px) 100vw, 840px\" \/><\/figure><\/li><\/ul><\/figure>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<p>Supplemented on Nov 24, 2020<\/p>\n\n\n\n<p>About cache associativity: see <a href=\"https:\/\/www.youtube.com\/watch?v=UCK-0fCchmY\">https:\/\/www.youtube.com\/watch?v=UCK-0fCchmY<\/a>, a very detailed &amp; intuitive demonstration.<\/p>\n\n\n\n<p>Additional resource: <a href=\"http:\/\/igoro.com\/archive\/gallery-of-processor-cache-effects\/\">Gallery of Processor Cache Effects by <\/a><a href=\"http:\/\/igoro.com\/\">Igor Ostrovsky<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This week and last weekend I was primarily focusing on memory pools, allocators, CPU caches. I now probably know how allocators work, simply separating memory allocation &amp; objects initialization, for example, reserve() function in std::vector, it doesn&#8217;t initialize the allocated data segment, thus permitting better performance when we don&#8217;t need initialize the data immediately. CPU &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/2020\/11\/22\/memory-cpu-caches\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Memory &#038; CPU Caches&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[13],"tags":[],"_links":{"self":[{"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/955"}],"collection":[{"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/comments?post=955"}],"version-history":[{"count":14,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/955\/revisions"}],"predecessor-version":[{"id":1022,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/955\/revisions\/1022"}],"wp:attachment":[{"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/media?parent=955"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/categories?post=955"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/tags?post=955"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}