{"id":17364,"date":"2024-04-12T11:37:07","date_gmt":"2024-04-12T11:37:07","guid":{"rendered":"http:\/\/www.max-sperling.bplaced.net\/?p=17364"},"modified":"2024-04-12T11:39:28","modified_gmt":"2024-04-12T11:39:28","slug":"cache-friendly-code","status":"publish","type":"post","link":"http:\/\/www.max-sperling.bplaced.net\/?p=17364","title":{"rendered":"Cache friendly code"},"content":{"rendered":"<p><strong>Example<\/strong><\/p>\n<pre class=\"brush: cpp; gutter: false; title: ; notranslate\" title=\"\">\r\nint main()\r\n{\r\n    int arr[1000][1000];\r\n\r\n    for (int a = 0; a &lt; sizeof(arr)\/sizeof(arr[0]); ++a)\r\n    {\r\n        for (int b = 0; b &lt; sizeof(arr[0])\/sizeof(arr[0][0]); ++b)\r\n        {\r\n            arr[a][b] = 0; \/\/ vs. arr[b][a] = 0;\r\n        }\r\n    }\r\n\r\n    return 0;\r\n}\r\n<\/pre>\n<hr>\n<p><strong>Analysis<\/strong><\/p>\n<p>The array will be stored in memory like this:<\/p>\n<pre>\r\n[row_0, col_0] ... [row_0, col_999] ... [row_999, col_0] ... [row_999, col_999]\r\n<\/pre>\n<p>For better performance, the CPU will typically cache a specific amount of bytes after the accessed one. For better understanding, let&#8217;s assume it will always cache exactly one row of that array.<\/p>\n<p><u>Cache friendly approach<\/u><br \/>\nWith &#8216;arr[a][b]&#8217; it will iterate over the columns, row by row. Because the current row is in the cache, it only has to reload after all cells of that row have been accessed.<\/p>\n<p><u>Cache unfriendly approach<\/u><br \/>\nWith &#8216;arr[b][a]&#8217; it will iterate over the rows, column by column. Because only the current row is in the cache, it has to reload a whole new row after every cell access.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Example Analysis The array will be stored in memory like this: [row_0, col_0] &#8230; [row_0, col_999] &#8230; [row_999, col_0] &#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false},"categories":[27],"tags":[],"_links":{"self":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17364"}],"collection":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=17364"}],"version-history":[{"count":19,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17364\/revisions"}],"predecessor-version":[{"id":17382,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17364\/revisions\/17382"}],"wp:attachment":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=17364"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=17364"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=17364"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}