Consider this program. <\/p>\n
\nchar* malloc_random_string_length(int length)\n{\n char* s = (char*)malloc(length + 1);\n for (int i = 0; i < length; i++) {\n s[i] = '\\0' + (rand() % 10);\n }\n s[length] = '\\0';\n return s;\n}\n\nint test()\n{\n char* array1[NUMBER_OF_STRINGS];\n char* array2[NUMBER_OF_STRINGS];\n int i;\n int matches = 0;\n\n for (i = 0; i < NUMBER_OF_STRINGS; i++) {\n array1[i] = malloc_random_string_length(STRING_LENGTH);\n array2[i] = malloc_random_string_length(STRING_LENGTH);\n }\n\n \/\/ Okay, now time this loop\n start_stopwatch();\n matches = 0;\n for (i = 0; i < NUMBER_OF_STRINGS; i++) {\n if (compare_in_some_way(array1[i], array2[i])) {\n matches++;\n }\n }\n stop_stopwatch();\n\n \/\/ Return this value so the compiler won't optimize it out\n return matches;\n}\n<\/pre>\nThis code creates two arrays, each with NUMBER_<\/code>OF_<\/code>STRINGS<\/code> random strings, each of length STRING_<\/code>LENGTH<\/code>. It then calls compare_<\/code>in_<\/code>some_<\/code>way<\/code> on each pair of strings tallies how many of them pass the test. <\/p>\nConsider this comparison function: <\/p>\n
\nint compare_in_some_way(char* a, char* b)\n{\n return a == b; \/\/ just compare the raw pointers\n}\n<\/pre>\nWhen run with various values for each with NUMBER_<\/code>OF_<\/code>STRINGS<\/code> and STRING_<\/code>LENGTH<\/code>, this code’s running time is proportional to NUMBER_<\/code>OF_<\/code>STRINGS<\/code>, and the STRING_<\/code>LENGTH<\/code> doesn’t play a role. <\/p>\nOn the other hand, consider this alternate comparison function: <\/p>\n
\nint compare_in_some_way(char* a, char* b)\n{\n return *a == *b; \/\/ compare the first characters\n}\n<\/pre>\nThis compares the first characters of the strings. With this version, it naturally runs slower as NUMBER_<\/code>OF_<\/code>STRINGS<\/code> increases, but surprisingly, it also runs slower as STRING_<\/code>LENGTH<\/code> increases. <\/p>\nHow can the length of the string play a factor in how long it takes to compare the first character? The function doesn’t even know what the length of the string is! <\/p>\n
What we’re seeing is the effect of data locality. <\/p>\n
In the first version that compares only pointer values, the only memory accesses are to the memory for the arrays themselves. The data in those arrays are tightly packed, so the cache is used efficiently. Since you don’t dereference the pointers, it doesn’t matter where they point. <\/p>\n
Reading the first character from the string adds another memory access, and the characteristics of that memory access vary depending on the length of the string. <\/p>\n
From the experimental data, one can conclude that the string data is stored in roughly contiguous memory. When the strings are short, the first characters of each string are closer to each other, since there are fewer other characters in between. This means that they are more likely to occupy the same cache line. <\/p>\n
As the strings get longer, the distance between their first characters increases, and fewer strings will fit inside a cache line. Eventually, the strings are long enough that each string ends up on a separate cache line, and you don’t gain any significant benefit from locality. <\/p>\n
Although the access to the first character of the string is always O<\/var>(1), the constant inside the O<\/var> can vary wildly depending on cache conditions. <\/p>\n","protected":false},"excerpt":{"rendered":"There’s a lot hiding in that O<\/VAR>.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-100405","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"There’s a lot hiding in that O<\/VAR>.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/100405","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=100405"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/100405\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=100405"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=100405"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=100405"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}