{"id":652,"date":"2017-11-16T01:13:52","date_gmt":"2017-11-16T09:13:52","guid":{"rendered":"http:\/\/wonghoi.humgar.com\/blog\/?p=652"},"modified":"2017-11-16T01:17:11","modified_gmt":"2017-11-16T09:17:11","slug":"super-simplified-programming-high-performance-code-by-considering-cache","status":"publish","type":"post","link":"https:\/\/wonghoi.humgar.com\/blog\/2017\/11\/16\/super-simplified-programming-high-performance-code-by-considering-cache\/","title":{"rendered":"Super-simplified: Programming high performance code by considering cache"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"code::dive conference 2014 - Scott Meyers: Cpu Caches and Why You Care\" width=\"584\" height=\"329\" src=\"https:\/\/www.youtube.com\/embed\/WDIkqP4JbkE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<ul>\n<li>\n<p>Code\/data locality (compactness, % of each cache line that gets used)<\/p>\n<\/li>\n<li>\n<p>Predictable access patterns: pre-fetch (instructions and data) friendly. This explains branching costs, why linear transversal might be faster than trees at smaller scales because of pointer chasing, why bubble sort is the fastest if the chunks fit in the cache.<\/p>\n<\/li>\n<li>\n<p>Avoid false sharing: shared cache line unnecessarily with other threads\/cores (due to how the data is packed) might have cache invalidating each other when anyone writes.<\/p>\n<\/li>\n<\/ul>\n<div class=\"pvc_clear\"><\/div>\n<p id=\"pvc_stats_652\" class=\"pvc_stats all  \" data-element-id=\"652\" style=\"\"><i class=\"pvc-stats-icon medium\" aria-hidden=\"true\"><svg aria-hidden=\"true\" focusable=\"false\" data-prefix=\"far\" data-icon=\"chart-bar\" role=\"img\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" viewBox=\"0 0 512 512\" class=\"svg-inline--fa fa-chart-bar fa-w-16 fa-2x\"><path fill=\"currentColor\" d=\"M396.8 352h22.4c6.4 0 12.8-6.4 12.8-12.8V108.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v230.4c0 6.4 6.4 12.8 12.8 12.8zm-192 0h22.4c6.4 0 12.8-6.4 12.8-12.8V140.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v198.4c0 6.4 6.4 12.8 12.8 12.8zm96 0h22.4c6.4 0 12.8-6.4 12.8-12.8V204.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v134.4c0 6.4 6.4 12.8 12.8 12.8zM496 400H48V80c0-8.84-7.16-16-16-16H16C7.16 64 0 71.16 0 80v336c0 17.67 14.33 32 32 32h464c8.84 0 16-7.16 16-16v-16c0-8.84-7.16-16-16-16zm-387.2-48h22.4c6.4 0 12.8-6.4 12.8-12.8v-70.4c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v70.4c0 6.4 6.4 12.8 12.8 12.8z\" class=\"\"><\/path><\/svg><\/i> <img loading=\"lazy\" decoding=\"async\" width=\"16\" height=\"16\" alt=\"Loading\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/plugins\/page-views-count\/ajax-loader-2x.gif\" border=0 \/><\/p>\n<div class=\"pvc_clear\"><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Code\/data locality (compactness, % of each cache line that gets used) Predictable access patterns: pre-fetch (instructions and data) friendly. This explains branching costs, why linear transversal might be faster than trees at smaller scales because of pointer chasing, why bubble &hellip; <a href=\"https:\/\/wonghoi.humgar.com\/blog\/2017\/11\/16\/super-simplified-programming-high-performance-code-by-considering-cache\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n<div class=\"pvc_clear\"><\/div>\n<p id=\"pvc_stats_652\" class=\"pvc_stats all  \" data-element-id=\"652\" style=\"\"><i class=\"pvc-stats-icon medium\" aria-hidden=\"true\"><svg aria-hidden=\"true\" focusable=\"false\" data-prefix=\"far\" data-icon=\"chart-bar\" role=\"img\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" viewBox=\"0 0 512 512\" class=\"svg-inline--fa fa-chart-bar fa-w-16 fa-2x\"><path fill=\"currentColor\" d=\"M396.8 352h22.4c6.4 0 12.8-6.4 12.8-12.8V108.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v230.4c0 6.4 6.4 12.8 12.8 12.8zm-192 0h22.4c6.4 0 12.8-6.4 12.8-12.8V140.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v198.4c0 6.4 6.4 12.8 12.8 12.8zm96 0h22.4c6.4 0 12.8-6.4 12.8-12.8V204.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v134.4c0 6.4 6.4 12.8 12.8 12.8zM496 400H48V80c0-8.84-7.16-16-16-16H16C7.16 64 0 71.16 0 80v336c0 17.67 14.33 32 32 32h464c8.84 0 16-7.16 16-16v-16c0-8.84-7.16-16-16-16zm-387.2-48h22.4c6.4 0 12.8-6.4 12.8-12.8v-70.4c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v70.4c0 6.4 6.4 12.8 12.8 12.8z\" class=\"\"><\/path><\/svg><\/i> <img loading=\"lazy\" decoding=\"async\" width=\"16\" height=\"16\" alt=\"Loading\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/plugins\/page-views-count\/ajax-loader-2x.gif\" border=0 \/><\/p>\n<div class=\"pvc_clear\"><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[6,29],"tags":[],"class_list":["post-652","post","type-post","status-publish","format-standard","hentry","category-note-to-self","category-programming"],"_links":{"self":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts\/652","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/comments?post=652"}],"version-history":[{"count":2,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts\/652\/revisions"}],"predecessor-version":[{"id":654,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts\/652\/revisions\/654"}],"wp:attachment":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/media?parent=652"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/categories?post=652"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/tags?post=652"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}