{"id":743,"date":"2014-06-13T07:00:00","date_gmt":"2014-06-13T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/06\/13\/non-classical-processor-behavior-how-doing-something-can-be-faster-than-not-doing-it\/"},"modified":"2014-06-13T07:00:00","modified_gmt":"2014-06-13T07:00:00","slug":"non-classical-processor-behavior-how-doing-something-can-be-faster-than-not-doing-it","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20140613-00\/?p=743","title":{"rendered":"Non-classical processor behavior: How doing something can be faster than not doing it"},"content":{"rendered":"

\nConsider the following program:\n<\/p>\n

\n#include <windows.h>\n#include <stdlib.h>\n#include <stdlib.h>\n#include <stdio.h>\nint array[10000];\nint countthem(int boundary)\n{\n int count = 0;\n for (int i = 0; i < 10000; i++) {\n  if (array[i] < boundary) count++;\n }\n return count;\n}\nint __cdecl wmain<\/a>(int, wchar_t **)\n{\n for (int i = 0; i < 10000; i++) array[i] = rand() % 10;\n for (int boundary = 0; boundary <= 10; boundary++) {\n  LARGE_INTEGER liStart, liEnd;\n  QueryPerformanceCounter(&liStart);\n  int count = 0;\n  for (int iterations = 0; iterations < 100; iterations++) {\n   count += countthem(boundary);\n  }\n  QueryPerformanceCounter(&liEnd);\n  printf(\"count=%7d, time = %I64d\\n\",\n         count, liEnd.QuadPart - liStart.QuadPart);\n }\n return 0;\n}\n<\/pre>\n
\nThe program generates a lot of random integers in the range 0..9\nand then counts how many are less than 0, less than 1, less than 2,\nand so on.\nIt also prints how long the operation took in QPC units.\nWe don’t really care how big a QPC unit is; we’re just interested\nin the relative values.\n(We print the number of items found merely to verify that the result\nis close to the expected value of boundary * 100000<\/code>.)\n<\/p>\n
\nHere are the results:\n<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n
boundary<\/th>\ncount<\/th>\ntime<\/th>\n<\/tr>\n
0<\/td>\n0<\/td>\n1869<\/td>\n <\/span><\/td>\n<\/tr>\n
1<\/td>\n100000<\/td>\n5482<\/td>\n <\/span><\/td>\n<\/tr>\n
2<\/td>\n200800<\/td>\n8152<\/td>\n <\/span><\/td>\n<\/tr>\n
3<\/td>\n300200<\/td>\n10180<\/td>\n <\/span><\/td>\n<\/tr>\n
4<\/td>\n403100<\/td>\n11982<\/td>\n <\/span><\/td>\n<\/tr>\n
5<\/td>\n497400<\/td>\n12092<\/td>\n <\/span><\/td>\n<\/tr>\n
6<\/td>\n602900<\/td>\n11029<\/td>\n <\/span><\/td>\n<\/tr>\n
7<\/td>\n700700<\/td>\n9235<\/td>\n <\/span><\/td>\n<\/tr>\n
8<\/td>\n797500<\/td>\n7051<\/td>\n <\/span><\/td>\n<\/tr>\n
9<\/td>\n902500<\/td>\n4537<\/td>\n <\/span><\/td>\n<\/tr>\n
10<\/td>\n1000000<\/td>\n1864<\/td>\n <\/span><\/td>\n<\/tr>\n<\/table>\n
\nTo the untrained eye, this chart is strange.\nHere’s the naïve analysis:\n<\/p>\n
\nWhen the boundary is zero, there is no incrementing at all,\nso the entire running time is just loop overhead.\nYou can think of this as our control group.\nWe can subtract 1869 from the running time of every column\nto remove the loop overhead costs.\nWhat remains is the cost of running count<\/code>\nincrement instructions.\n<\/p>\n
\nThe cost of a single increment operation is highly variable.\nAt low boundary values, it is around 0.03 time units per increment.\nBut at high boundary values, the cost drops to one tenth that.\n<\/p>\n
\nWhat’s even weirder is that once the count crosses 600,000,\neach addition of another 100,000 increment operations makes the code\nrun faster<\/i>,\nwith the extreme case when\nthe boundary value reaches 10,\nwhere we run\nfaster than if we hadn’t done any incrementing at all!\n<\/p>\n
\nHow can the running time of an increment instruction be negative<\/i>?\n<\/p>\n
\nThe explanation for all this is that CPUs are more complicated\nthan the naïve analysis realizes.\nWe saw earlier that\n\nmodern CPUs contain all sorts of hidden variables<\/a>.\nToday’s hidden variable is the branch predictor.\n<\/p>\n
\nExecuting a single CPU instruction takes multiple steps,\nand modern CPUs kick off multiple instructions in parallel,\nwith each instruction at a different stage of execution,\na technique known as\n\npipelining<\/a>.\n<\/p>\n
Conditional branch instructions are bad for pipelining.\nThink about it:\nWhen a conditional branch instruction enters the pipeline,\nthe CPU doesn’t know whether the condition will be true\nwhen the instruction reaches the end of the pipeline.\nTherefore, it doesn’t know what instruction to feed into\nthe pipeline next.\n<\/p>\n
\nNow, it could just sit there and let the pipeline sit idle\nuntil the branch\/no-branch decision is made,\nat which point it now knows which instruction to feed into\nthe pipeline next.\nBut that wastes a lot of pipeline capacity,\nbecause it will take time for those new instructions to\nmake it all the way through the pipeline and start\ndoing productive work.\n<\/p>\n
\nTo avoid wasting time, the processor has an internal\nbranch predictor<\/i> which remembers the recent\nhistory of which conditional branches were taken and which\nwere not taken.\nThe fanciness of the branch predictor varies.\nSome processors merely assume that a branch will go the same\nway that it did the last time it was countered.\nOthers keep complicated branch history and try to infer\npatterns (such as “the branch is taken every other time”).\n<\/p>\n
\nWhen a conditional branch is encountered,\nthe branch predictor tells the processor which instructions\nto feed into the pipeline.\nIf the branch prediction turns out to be correct,\nthen we win!\nExecution continues without a pipeline stall.\n<\/p>\n
\nBut if the branch prediction turns out to be incorrect,\nthen we lose!\nAll of the instructions that were fed into the pipeline\nneed to be recalled and their effects undone,\nand the processor has to go find the correct instructions\nand start feeding them into the pipeline.\n<\/p>\n
\nLet’s look at our little program again.\nWhen the boundary is 0,\nthe result of the comparison is always false.\nSimilarly, when the boundary is 10, the result is always true.\nIn those cases, the branch predictor can reach 100% accuracy.\n<\/p>\n
\nThe worst case is when the boundary is 5.\nIn that case, half of the time the comparison is true\nand half of the time the comparison is false.\nAnd since we have random data,\n\nfancy historical analysis<\/a>\ndoesn’t help any.\nThe predictor is going to be wrong half the time.\n<\/p>\n
\nHere’s a tweak to the program:\nChange the line\n<\/p>\n
\n     if (array[i] < boundary) count++;\n<\/pre>\n
\nto\n<\/p>\n
\n     count += (array[i] < boundary) ? 1 : 0;\n<\/pre>\n
\nThis time, the results look like this:\n<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n
boundary<\/th>\ncount<\/th>\ntime<\/th>\n<\/tr>\n
0<\/td>\n0<\/td>\n2932<\/span>\n         <\/span><\/td>\n<\/tr>\n
1<\/td>\n100000<\/td>\n2931<\/span>\n         <\/span<\/td>\n<\/tr>\n
2<\/td>\n200800<\/td>\n2941<\/span>\n         <\/span<\/td>\n<\/tr>\n
3<\/td>\n300200<\/td>\n2931<\/span>\n         <\/span<\/td>\n<\/tr>\n
4<\/td>\n403100<\/td>\n2932<\/span>\n         <\/span<\/td>\n<\/tr>\n
5<\/td>\n497400<\/td>\n2932<\/span>\n         <\/span<\/td>\n<\/tr>\n
6<\/td>\n602900<\/td>\n2932<\/span>\n         <\/span<\/td>\n<\/tr>\n
7<\/td>\n700700<\/td>\n2999<\/span>\n         <\/span<\/td>\n<\/tr>\n
8<\/td>\n797500<\/td>\n2931<\/span>\n         <\/span<\/td>\n<\/tr>\n
9<\/td>\n902500<\/td>\n2932<\/span>\n         <\/span<\/td>\n<\/tr>\n
10<\/td>\n1000000<\/td>\n2931<\/span>\n         <\/span<\/td>\n<\/tr>\n<\/table>\n
\nThe execution time is now independent of the boundary value.\nThat’s because the optimizer was able to remove the branch from\nthe ternary expression:\n<\/p>\n
\n; on entry to the loop, ebx = boundary\n    mov edx, offset array ; start at the beginning of the array\n$LL3:\n    xor ecx, ecx    ; start with zero\n    cmp [edx], ebx  ; compare array[i] with boundary\n    setl cl         ; if less than boundary, then set al = 1\n    add eax, ecx    ; accumulate result in eax\n    add edx, 4      ; loop until end of array\n    cmp edx, offset array + 40000\n    jl $LL3\n<\/pre>\n
\nSince there are no branching decisions in the inner loop\naside from the loop counter,\nthere is no need for a branch predictor to decide which way\nthe comparison goes.\nThe same code executes either way.\n<\/p>\n
\nExercise<\/b>:\nWhy are the counts exactly the same for both runs,\neven though the dataset is random?<\/p>\n","protected":false},"excerpt":{"rendered":"
Consider the following program: #include <windows.h> #include <stdlib.h> #include <stdlib.h> #include <stdio.h> int array[10000]; int countthem(int boundary) { int count = 0; for (int i = 0; i < 10000; i++) { if (array[i] < boundary) count++; } return count; } int __cdecl wmain(int, wchar_t **) { for (int i = 0; i < 10000; […]<\/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-743","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Consider the following program: #include <windows.h> #include <stdlib.h> #include <stdlib.h> #include <stdio.h> int array[10000]; int countthem(int boundary) { int count = 0; for (int i = 0; i < 10000; i++) { if (array[i] < boundary) count++; } return count; } int __cdecl wmain(int, wchar_t **) { for (int i = 0; i < 10000; […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/743","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=743"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/743\/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=743"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=743"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=743"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}