{"id":3204,"date":"2017-04-01T18:28:42","date_gmt":"2017-04-01T12:58:42","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=3204"},"modified":"2017-04-01T18:28:42","modified_gmt":"2017-04-01T12:58:42","slug":"faster-process-sorted-array-unsorted-array","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/faster-process-sorted-array-unsorted-array\/","title":{"rendered":"[ Solved -11 Answers] JAVA &#8211; Why is it faster to process a sorted array than an unsorted array"},"content":{"rendered":"<p><label class=\"label label-warning\">PROBLEM:<\/label><\/p>\n<p>A piece of C++ code that seems very peculiar. For some reason, sorting the data miraculously makes the code almost six times faster.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%20%3Calgorithm%3E%0A%23include%20%3Cctime%3E%0A%23include%20%3Ciostream%3E%0A%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Generate%20data%0A%20%20%20%20const%20unsigned%20arraySize%20%3D%2032768%3B%0A%20%20%20%20int%20data%5BarraySize%5D%3B%0A%0A%20%20%20%20for%20(unsigned%20c%20%3D%200%3B%20c%20%3C%20arraySize%3B%20%2B%2Bc)%0A%20%20%20%20%20%20%20%20data%5Bc%5D%20%3D%20std%3A%3Arand()%20%25%20256%3B%0A%0A%20%20%20%20%2F%2F%20!!!%20With%20this%2C%20the%20next%20loop%20runs%20faster%0A%20%20%20%20std%3A%3Asort(data%2C%20data%20%2B%20arraySize)%3B%0A%2F%2F%20Test%0A%20%20%20%20clock_t%20start%20%3D%20clock()%3B%0A%20%20%20%20long%20long%20sum%20%3D%200%3B%0A%20for%20(unsigned%20i%20%3D%200%3B%20i%20%3C%20100000%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Primary%20loop%0A%20%20%20%20%20%20%20%20for%20(unsigned%20c%20%3D%200%3B%20c%20%3C%20arraySize%3B%20%2B%2Bc)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(data%5Bc%5D%20%3E%3D%20128)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20data%5Bc%5D%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20double%20elapsedTime%20%3D%20static_cast%3Cdouble%3E(clock()%20-%20start)%20%2F%20CLOCKS_PER_SEC%3B%0A%20std%3A%3Acout%20%3C%3C%20elapsedTime%20%3C%3C%20std%3A%3Aendl%3B%0A%20std%3A%3Acout%20%3C%3C%20%22sum%20%3D%20%22%20%3C%3C%20sum%20%3C%3C%20std%3A%3Aendl%3B%0A%7D%0A\u201d message=\u201dc++ code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li>Without\u00a0std::sort(data, data + arraySize);, the code runs in 11.54 seconds.<\/li>\n<li>With the sorted data, the code runs in 1.93 seconds.<\/li>\n<\/ul>\n<p><strong>Initially, this might be just a language or compiler anomaly. So a Trail in Java.<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dimport%20java.util.Arrays%3B%0Aimport%20java.util.Random%3B%0A%0Apublic%20class%20Main%0A%7B%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Generate%20data%0A%20%20%20%20%20%20%20%20int%20arraySize%20%3D%2032768%3B%0A%20%20%20%20%20%20%20%20int%20data%5B%5D%20%3D%20new%20int%5BarraySize%5D%3B%0A%0A%20%20%20%20%20%20%20%20Random%20rnd%20%3D%20new%20Random(0)%3B%0A%20%20%20%20%20%20%20%20for%20(int%20c%20%3D%200%3B%20c%20%3C%20arraySize%3B%20%2B%2Bc)%0A%20%20%20%20%20%20%20%20%20%20%20%20data%5Bc%5D%20%3D%20rnd.nextInt()%20%25%20256%3B%0A%0A%20%20%20%20%20%20%20%20%2F%2F%20!!!%20With%20this%2C%20the%20next%20loop%20runs%20faster%0A%20%20%20%20%20%20%20%20Arrays.sort(data)%3B%0A%2F%2F%20Test%0A%20%20%20%20%20%20%20%20long%20start%20%3D%20System.nanoTime()%3B%0A%20%20%20%20%20%20%20%20long%20sum%20%3D%200%3B%0A%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20100000%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Primary%20loop%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20c%20%3D%200%3B%20c%20%3C%20arraySize%3B%20%2B%2Bc)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(data%5Bc%5D%20%3E%3D%20128)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20data%5Bc%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20%20%20%20%20System.out.println((System.nanoTime()%20-%20start)%20%2F%201000000000.0)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22sum%20%3D%20%22%20%2B%20sum)%3B%0A%20%20%20%20%7D%0A%7D%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>With a somewhat similar but less extreme result.<\/p>\n<p><label class=\"label label-info\">SOLUTION 1:<\/label><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201dif%20(data%5Bc%5D%20%3E%3D%20128)%20sum%20%2B%3D%20data%5Bc%5D%3B\u201d message=\u201dc ++ code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li>Notice that the data is evenly distributed between 0 and 255.<\/li>\n<li>When the data is sorted, roughly the first half of the iterations will not enter the if-statement.<\/li>\n<li>After that, they will all enter the if-statement.<\/li>\n<li>This is very friendly to the branch predictor since the branch consecutively goes the same direction many times.<\/li>\n<li>Even a simple saturating counter will correctly predict the branch except for the few iterations after it switches direction.<\/li>\n<\/ul>\n<h4 id=\"quick-visualization\"><span style=\"color: #ff6600;\"><b>Quick visualization:<\/b><\/span><\/h4>\n<p>T = branch taken N = branch not taken data[] = 0, 1, 2, 3, 4, \u2026 126, 127, 128, 129, 130, \u2026 250, 251, 252, \u2026 branch = N N N N N \u2026 N N T T T \u2026 T T T \u2026 = NNNNNNNNNNNN \u2026 NNNNNNNTTTTTTTTT \u2026 TTTTTTTTTT (easy to predict)<\/p>\n<ul>\n<li>However, when the data is completely random, the branch predictor is rendered useless because it can\u2019t predict random data.<\/li>\n<\/ul>\n<p>data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, \u2026 branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N \u2026 = TTNTTTTNTNNTTTN \u2026 (completely random \u2013 hard to predict)<\/p>\n<p>If the compiler isn\u2019t able to optimize the branch into a conditional move,<\/p>\n<h4 id=\"replace\"><span style=\"color: #808000;\"><strong>Replace:<\/strong><\/span><\/h4>\n[pastacode lang=\u201dcpp\u201d manual=\u201dif%20(data%5Bc%5D%20%3E%3D%20128)%20%0Asum%20%2B%3D%20data%5Bc%5D%3B%20%0A\u201d message=\u201dc++ code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"with\"><strong><span style=\"color: #800080;\">with:<\/span><\/strong><\/h4>\n[pastacode lang=\u201dcpp\u201d manual=\u201dint%20t%20%3D%20(data%5Bc%5D%20-%20128)%20%3E%3E%2031%3B%0Asum%20%2B%3D%20~t%20%26%20data%5Bc%5D%3B%20%0A\u201d message=\u201dc++ code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li>This eliminates the branch and replaces it with some bitwise operations.<\/li>\n<\/ul>\n<h4 id=\"c-visual-studio-2010-x64-release\"><strong><span style=\"color: #ff6600;\">C++ \u2013 Visual Studio 2010 \u2013 x64 Release<\/span><\/strong><\/h4>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20Branch%20-%20Random%20%0Aseconds%20%3D%2011.777%20%0A%2F%2F%20Branch%20-%20Sorted%20%0Aseconds%20%3D%202.352%20%0A%2F%2F%20Branchless%20-%20Random%20%0Aseconds%20%3D%202.564%20%0A%2F%2F%20Branchless%20%E2%80%93%20Sorted%0Aseconds%20%3D%202.587%20%0A\u201d message=\u201dc ++ code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"java-netbeans-7-1-1-jdk-7-x64\"><strong><span style=\"color: #808000;\">Java \u2013 Netbeans 7.1.1 JDK 7 \u2013 x64<\/span><\/strong><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Branch%20-%20Random%20%0Aseconds%20%3D%2010.93293813%20%0A%2F%2F%20Branch%20-%20Sorted%20%0Aseconds%20%3D%205.643797077%20%0A%2F%2F%20Branchless%20%E2%80%93%20Random%0A%20seconds%20%3D%203.113581453%20%0A%2F%2F%20Branchless%20%E2%80%93%20Sorted%0A%20seconds%20%3D%203.186068823%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li><b>With the Branch:<\/b>There is a huge difference between the sorted and unsorted data.<\/li>\n<li><b>With the Hack:<\/b>There is no difference between sorted and unsorted data.<\/li>\n<li>In the C++ case, the hack is actually a tad slower than with the branch when the data is sorted.<\/li>\n<\/ul>\n<p><label class=\"label label-info\">SOLUTION 2:<\/label><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201dif%20(data%5Bc%5D%20%3E%3D%20128)%0A%20sum%20%2B%3D%20data%5Bc%5D%3B%20%0A\u201d message=\u201dc++ code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li>The meaning of this particular\u00a0if\u2026 else\u2026\u00a0branch is to add something when a condition is satisfied.<\/li>\n<li>This type of branch can be easily transformed into a\u00a0<b>conditional move<\/b>statement, which would be compiled into a conditional move instruction:\u00a0cmovl, in an\u00a0x86\u00a0system.<\/li>\n<li>The branch and thus the potential branch prediction penalty is removed.<\/li>\n<\/ul>\n<ul>\n<li>In\u00a0C, thus\u00a0C++, the statement, which would compile directly (without any optimization) into the conditional move instruction in\u00a0x86, is the ternary operator\u00a0\u2026 ? \u2026 : \u2026.<\/li>\n<li>So it can be rewritten as:<\/li>\n<\/ul>\n[pastacode lang=\u201dcpp\u201d manual=\u201dsum%20%2B%3D%20data%5Bc%5D%20%3E%3D128%20%3F%20data%5Bc%5D%20%3A%200%3B%20%0A\u201d message=\u201dc++ code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201djava\u201d manual=\u201dx86%0A%2F%2F%20Branch%20-%20Random%20%0Aseconds%20%3D%208.885%20%0A%2F%2F%20Branch%20-%20Sorted%20%0Aseconds%20%3D%201.528%0A%20%2F%2F%20Branchless%20-%20Random%20seconds%20%3D%203.716%20%0A%2F%2F%20Branchless%20-%20Sorted%20seconds%20%3D%203.71%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[pastacode lang=\u201djava\u201d manual=\u201dx64%0A%2F%2F%20Branch%20%E2%80%93%20Random%0A%20seconds%20%3D%2011.302%0A%20%2F%2F%20Branch%20%E2%80%93%20Sorted%0A%20seconds%20%3D%201.830%20%0A%2F%2F%20Branchless%20-%20Random%20%0Aseconds%20%3D%202.736%0A%20%2F%2F%20Branchless%20%E2%80%93%20Sorted%0A%20seconds%20%3D%202.737%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><label class=\"label label-info\">SOLUTION 3:<\/label><\/p>\n<p>Thus from the previous fix, lets investigate the\u00a0x86\u00a0assembly they generate. For simplicity, we use two functions\u00a0max1\u00a0and\u00a0max2.<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dmax1%C2%A0uses%20the%20conditional%20branch%C2%A0if\u2026%20else%20\u2026%3A%0Aint%20max1(int%20a%2C%20int%20b)%20%0A%7B%20%0Aif%20(a%20%3E%20b)%0A%20return%20a%3B%0A%20else%20return%20b%3B%20%0A%7D%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[pastacode lang=\u201djava\u201d manual=\u201dmax2%C2%A0uses%20the%20ternary%20operator%C2%A0\u2026%20%3F%20\u2026%20%3A%20\u2026%3A%0Aint%20max2(int%20a%2C%20int%20b)%0A%20%7B%20%0Areturn%20a%20%3E%20b%20%3F%20a%20%3A%20b%3B%20%0A%7D%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[pastacode lang=\u201dcpp\u201d manual=\u201dmax1%20%0Amovl%20%25edi%2C%20-4(%25rbp)%20%0Amovl%20%25esi%2C%20-8(%25rbp)%20%0Amovl%20-4(%25rbp)%2C%20%25eax%20%0Acmpl%20-8(%25rbp)%2C%20%25eax%20%0Ajle%20.L2%20%0Amovl%20-4(%25rbp)%2C%20%25eax%20%0Amovl%20%25eax%2C%20-12(%25rbp)%20%0Ajmp%20.L4%20%0A.L2%3A%20%0Amovl%20-8(%25rbp)%2C%20%25eax%20%0Amovl%20%25eax%2C%20-12(%25rbp)%20%0A.L4%3A%20%0Amovl%20-12(%25rbp)%2C%20%25eax%20%0Aleave%20%0Aret%20%0A%3Amax2%20%0Amovl%20%25edi%2C%20-4(%25rbp)%20%0Amovl%20%25esi%2C%20-8(%25rbp)%20%0Amovl%20-4(%25rbp)%2C%20%25eax%20%0Acmpl%20%25eax%2C%20-8(%25rbp)%20%0Acmovge%20-8(%25rbp)%2C%20%25eax%20%0Aleave%20%0Aret%20%0A\u201d message=\u201dC++ code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li>max2\u00a0uses much less code due to the usage of instruction\u00a0cmovge<\/li>\n<li>But the real gain is that\u00a0max2does not involve branch jumps,\u00a0jmp, which would have a significant performance penalty if the predicted result is not right<\/li>\n<li>In a typical\u00a0x86\u00a0processor, the execution of an instruction is divided into several stages.<\/li>\n<li>Thus they have different hardware to deal with different stages.<\/li>\n<li>So we do not have to wait for one instruction to finish to start a new one.<\/li>\n<li>This is called\u00a0<b>pipelining<\/b>.<\/li>\n<\/ul>\n<p><label class=\"label label-info\">SOLUTION 4:<\/label><\/p>\n<h4 id=\"starting-with-the-original-loop\">\u00a0<span style=\"color: #ff6600;\">Starting with the original loop:<\/span><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201dfor%20(unsigned%20i%20%3D%200%3B%20i%20%3C%20100000%3B%20%2B%2Bi)%0A%20%7B%20%0Afor%20(unsigned%20j%20%3D%200%3B%20j%20%3C%20arraySize%3B%20%2B%2Bj)%0A%20%7B%20%0Aif%20(data%5Bj%5D%20%3E%3D%20128)%0A%20sum%20%2B%3D%20data%5Bj%5D%3B%20%0A%7D%20%0A%7D%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"with-loop-interchange-we-can-change-this-loop-to\"><span style=\"color: #808000;\">With loop interchange, we can change this loop to:<\/span><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201dfor%20(unsigned%20j%20%3D%200%3B%20j%20%3C%20arraySize%3B%20%2B%2Bj)%20%0A%7B%20%0Afor%20(unsigned%20i%20%3D%200%3B%20i%20%3C%20100000%3B%20%2B%2Bi)%0A%20%7B%20%0Aif%20(data%5Bj%5D%20%3E%3D%20128)%0A%20sum%20%2B%3D%20data%5Bj%5D%3B%20%0A%7D%20%0A%7D%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>if\u201d conditional is constant throughout the execution of the \u201ci\u201d loop, so you can hoist the \u201cif\u201d out:<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dfor%20(unsigned%20j%20%3D%200%3B%20j%20%3C%20arraySize%3B%20%2B%2Bj)%20%0A%7B%20%0Aif%20(data%5Bj%5D%20%3E%3D%20128)%20%0A%7B%20%0Afor%20(unsigned%20i%20%3D%200%3B%20i%20%3C%20100000%3B%20%2B%2Bi)%20%0A%7B%20%0Asum%20%2B%3D%20data%5Bj%5D%3B%20%0A%7D%20%7D%20%7D%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>the inner loop can be collapsed into one single expression, assuming the floating point model allows it<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dfor%20(unsigned%20j%20%3D%200%3B%20j%20%3C%20arraySize%3B%20%2B%2Bj)%0A%20%7B%20%0Aif%20(data%5Bj%5D%20%3E%3D%20128)%0A%20%7B%20%0Asum%20%2B%3D%20data%5Bj%5D%20*%20100000%3B%0A%20%7D%20%0A%7D%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><label class=\"label label-info\">SOLUTION 5:<\/label><\/p>\n<ul>\n<li>The Valgrind tool cachegrind has a branch-predictor simulator, enabled by using the \u2013branch-sim=yes flag.<\/li>\n<li>Running it over the examples in this question, with the number of outer loops reduced to 10000 and compiled with g++, gives these results:<\/li>\n<\/ul>\n<h4 id=\"sorted\"><span style=\"color: #800080;\"><strong>Sorted:<\/strong><\/span><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201d%3D%3D32551%3D%3D%20Branches%3A%20%20%20%20%20%20%20%20656%2C645%2C130%20%20(%20%20656%2C609%2C208%20cond%20%2B%20%20%20%2035%2C922%20ind)%0A%3D%3D32551%3D%3D%20Mispredicts%3A%20%20%20%20%20%20%20%20%20169%2C556%20%20(%20%20%20%20%20%20169%2C095%20cond%20%2B%20%20%20%20%20%20%20461%20ind)%0A%3D%3D32551%3D%3D%20Mispred%20rate%3A%20%20%20%20%20%20%20%20%20%20%20%200.0%25%20(%20%20%20%20%20%20%20%20%20%200.0%25%20%20%20%20%20%2B%20%20%20%20%20%20%201.2%25%20%20%20)%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"unsorted\"><strong><span style=\"color: #ff6600;\">Unsorted:<\/span><\/strong><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201d%3D%3D32555%3D%3D%20Branches%3A%20%20%20%20%20%20%20%20655%2C996%2C082%20%20(%20%20655%2C960%2C160%20cond%20%2B%20%2035%2C922%20ind)%0A%3D%3D32555%3D%3D%20Mispredicts%3A%20%20%20%20%20164%2C073%2C152%20%20(%20%20164%2C072%2C692%20cond%20%2B%20%20%20%20%20460%20ind)%0A%3D%3D32555%3D%3D%20Mispred%20rate%3A%20%20%20%20%20%20%20%20%20%20%2025.0%25%20(%20%20%20%20%20%20%20%20%2025.0%25%20%20%20%20%20%2B%20%20%20%20%201.2%25%20%20%20)%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li>Drilling down into the line-by-line output produced by cg_annotate we see for the loop in question:<\/li>\n<\/ul>\n<h4 id=\"sorted-2\"><span style=\"color: #808000;\"><strong>Sorted:<\/strong><\/span><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201dBc%20%20%20%20Bcm%20Bi%20Bim%0A%20%20%20%20%20%2010%2C001%20%20%20%20%20%204%20%200%20%20%200%20%20%20%20%20%20for%20(unsigned%20i%20%3D%200%3B%20i%20%3C%2010000%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%09%09%09%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%20%20%20%09%09%09%20%20%2F%2F%20primary%20loop%0A%20327%2C690%2C000%2010%2C016%20%200%20%20%200%20%20%20%20%20%20%20%20%20%20for%20(unsigned%20c%20%3D%200%3B%20c%20%3C%20%09%09%09%09arraySize%3B%20%2B%2Bc)%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%20%20%20%09%09%09%20%20%7B%0A%20327%2C680%2C000%2010%2C006%20%200%20%20%200%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(data%5Bc%5D%20%3E%3D%20128)%0A%20%20%20%20%20%20%20%20%20%20%200%20%20%20%20%20%200%20%200%20%20%200%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20data%5Bc%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%20%20%20%20%09%09%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%09%09%09%20%7D%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"unsorted-2\"><span style=\"color: #800080;\"><strong>Unsorted:<\/strong><\/span><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201d%0A%20%20%20%20%20%20%20%20%20%20Bc%20%20%20%20%20%20%20%20%20Bcm%20Bi%20Bim%0A%20%20%20%20%20%2010%2C001%20%20%20%20%20%20%20%20%20%20%204%20%200%20%20%200%20%20%20%20%20%20for%20(unsigned%20i%20%3D%200%3B%20i%20%3C%2010000%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%09%09%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%20%20%20%20%09%09%20%2F%2F%20primary%20loop%0A%20327%2C690%2C000%20%20%20%20%20%2010%2C038%20%200%20%20%200%20%20%20%20%20%20%20%20%20%20for%20(unsigned%20c%20%3D%200%3B%20c%20%3C%20%09%09%09%09%09arraySize%3B%20%2B%2Bc)%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%20%20%20%09%09%20%20%7B%0A%20327%2C680%2C000%20164%2C050%2C007%20%200%20%20%200%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(data%5Bc%5D%20%3E%3D%20128)%0A%20%20%20%20%20%20%20%20%20%20%200%20%20%20%20%20%20%20%20%20%20%200%20%200%20%20%200%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%09sum%20%2B%3D%20data%5Bc%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%20%20%20%20%09%09%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20.%20%20%20%20%20%20%20%20%20%20%20.%20%20.%20%20%20.%20%20%20%20%20%09%09%20%7D%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<ul>\n<li>the problematic line \u2013 in the unsorted version the if (data[c] >= 128) line is causing 164,050,007 mispredicted conditional branches (Bcm) under cachegrind\u2019s branch-predictor model, whereas it\u2019s only causing 10,006 in the sorted version.<\/li>\n<\/ul>\n<p><label class=\"label label-info\">SOLUTION 6:<\/label><\/p>\n<ul>\n<li>On Linux you can use the performance counters subsystem to accomplish The Valgrind tool cachegrind has a branch-predictor simulator, enabled by using the \u2013branch-sim=yes flag, but with native performance using CPU counters.<\/li>\n<\/ul>\n<h4 id=\"sorted-3\"><strong><span style=\"color: #ff6600;\">Sorted:<\/span><\/strong><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201dPerformance%20counter%20stats%20for%20\u2032.%2Fsumtest_sorted\u2019%3A%20%0A11808.095776%20task-clock%20%23%200.998%20CPUs%20utilized%20%0A1%2C062%20context-switches%20%23%200.090%20K%2Fsec%20%0A14%20CPU-migrations%20%23%200.001%20K%2Fsec%20%0A337%20page-faults%20%23%200.029%20K%2Fsec%20%0A26%2C487%2C882%2C764%20cycles%20%23%202.243%20GHz%20%0A41%2C025%2C654%2C322%20instructions%20%23%201.55%20insns%20per%20cycle%206%2C558%2C871%2C379%20branches%20%23%20555.455%20M%2Fsec%20%0A567%2C204%20branch-misses%20%23%200.01%25%20of%20all%20branches%2011.827228330%20seconds%20time%20elapsed%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"unsorted-3\"><span style=\"color: #808000;\"><b>Unsorted:<\/b><\/span><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201dPerformance%20counter%20stats%20for%20\u2032.%2Fsumtest_unsorted\u2019%3A%2028877.954344%20task-clock%20%23%200.998%20CPUs%20utilized%0A%202%2C584%20context-switches%20%23%200.089%20K%2Fsec%0A%2018%20CPU-migrations%20%23%200.001%20K%2Fsec%20%0A335%20page-faults%20%23%200.012%20K%2Fsec%20%0A65%2C076%2C127%2C595%20cycles%20%23%202.253%20GHz%20%0A41%2C032%2C528%2C741%20instructions%20%23%200.63%20insns%20per%20cycle%206%2C560%2C579%2C013%20branches%20%23%20227.183%20M%2Fsec%0A%201%2C646%2C394%2C749%20branch-misses%20%23%2025.10%25%20of%20all%20branches%2028.935500947%20seconds%20time%20elapsed%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li>It can also do source code annotation with dissassembly.<\/li>\n<li>perf record -e branch-misses .\/sumtest_unsorted<\/li>\n<li>perf annotate -d sumtest_unsorted<\/li>\n<\/ul>\n<p>Percent | \u00a0 Source code & Disassembly of sumtest_unsorted<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d\u2026%0A%20%20%20%20%20%20%20%20%20%3A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20data%5Bc%5D%3B%0A%20%20%20%200.00%20%3A%20%20%20%20%20%20%20%20400a1a%3A%20%20%20%20%20%20%20mov%20%20%20%20-0x14(%25rbp)%2C%25eax%0A%20%20%2039.97%20%3A%20%20%20%20%20%20%20%20400a1d%3A%20%20%20%20%20%20%20mov%20%20%20%20%25eax%2C%25eax%0A%20%20%20%205.31%20%3A%20%20%20%20%20%20%20%20400a1f%3A%20%20%20%20%20%20%20mov%20%20%20%20-0x20040(%25rbp%2C%25rax%2C4)%2C%25eax%0A%20%20%20%204.60%20%3A%20%20%20%20%20%20%20%20400a26%3A%20%20%20%20%20%20%20cltq%20%20%20%0A%20%20%20%200.00%20%3A%20%20%20%20%20%20%20%20400a28%3A%20%20%20%20%20%20%20add%20%20%20%20%25rax%2C-0x30(%25rbp)%0A\u2026%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><label class=\"label label-info\">SOLUTION 7:<\/label><\/p>\n<p>A common way to eliminate branch prediction is that, to work in managed languages -a table lookup instead of using a branch<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20generate%20data%0Aint%20arraySize%20%3D%2032768%3B%0Aint%5B%5D%20data%20%3D%20new%20int%5BarraySize%5D%3B%0A%0ARandom%20rnd%20%3D%20new%20Random(0)%3B%0Afor%20(int%20c%20%3D%200%3B%20c%20%3C%20arraySize%3B%20%2B%2Bc)%0A%20%20%20%20data%5Bc%5D%20%3D%20rnd.Next(256)%3B%0A%0A%2F%2F%20Too%20keep%20the%20spirit%20of%20the%20code%20in-tact%20we%20will%20make%20a%20separate%20lookup%20table%0A%2F%2F%20(Assume%20we%20cannot%20modify%20\u2019data\u2019%20or%20the%20number%20of%20loops)%0Aint%5B%5D%20lookup%20%3D%20new%20int%5B256%5D%3B%0A%0Afor%20(int%20c%20%3D%200%3B%20c%20%3C%20256%3B%20%2B%2Bc)%0A%20%20%20%20lookup%5Bc%5D%20%3D%20(c%20%3E%3D%20128)%20%3F%20c%20%3A%200%3B%0A%2F%2F%20test%0ADateTime%20startTime%20%3D%20System.DateTime.Now%3B%0Along%20sum%20%3D%200%3B%0A%0Afor%20(int%20i%20%3D%200%3B%20i%20%3C%20100000%3B%20%2B%2Bi)%0A%7B%0A%20%20%20%20%2F%2F%20primary%20loop%0A%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20arraySize%3B%20%2B%2Bj)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20here%20you%20basically%20want%20to%20use%20simple%20operations%20-%20so%20no%20%0A%20%20%20%20%20%20%20%20%2F%2F%20random%20branches%2C%20but%20things%20like%20%26%2C%20%7C%2C%20*%2C%20-%2C%20%2B%2C%20etc%20are%20fine.%0A%20%20%20%20%20%20%20%20sum%20%2B%3D%20lookup%5Bdata%5Bj%5D%5D%3B%0A%20%20%20%20%7D%0A%7D%0A%0ADateTime%20endTime%20%3D%20System.DateTime.Now%3B%0AConsole.WriteLine(endTime%20-%20startTime)%3B%0AConsole.WriteLine(%22sum%20%3D%20%22%20%2B%20sum)%3B%0A%0AConsole.ReadLine()%3B%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><label class=\"label label-info\">SOLUTION 8:<\/label><\/p>\n<ul>\n<li>measure the performance of this loop with different conditions:<\/li>\n<\/ul>\n[pastacode lang=\u201djava\u201d manual=\u201dfor%20(int%20i%20%3D%200%3B%20i%20%3C%20max%3B%20i%2B%2B)%20if%20(condition)%20sum%2B%2B%3B%20%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Here are the timings of the loop with different True-False patterns:<\/p>\n<blockquote><p>Condition \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Pattern\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 Time (ms)<\/p>\n<p>(i & 0\u00d780000000) == 0\u00a0 \u00a0 \u00a0T repeated\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 322<\/p>\n<p>(i & 0xffffffff) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0F repeated\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 276<\/p>\n<p>(i & 1) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 TF alternating\u00a0\u00a0\u00a0 \u00a0 760<\/p>\n<p>(i & 3) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 TFFFTFFF\u2026 \u00a0 \u00a0 \u00a0 513<\/p>\n<p>(i & 2) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 TTFFTTFF\u2026 \u00a0 \u00a0 \u00a01675<\/p>\n<p>(i & 4) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 TTTTFFFFTTTTFFFF1275<\/p>\n<p>(i & 8) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a08T 8F 8T 8F \u2026\u00a0\u00a0\u00a0\u00a0 \u00a0 752<\/p>\n<p>(i & 16) == 0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 16T 16F 16T 16F \u2026 \u00a0 \u00a0490<\/p><\/blockquote>\n<ul>\n<li>A \u201c<b>bad<\/b>\u201d true-false pattern can make an if-statement up to six times slower than a \u201c<b>good<\/b>\u201d pattern!<\/li>\n<li>\u00a0Thus which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.<\/li>\n<\/ul>\n<p><label class=\"label label-info\">SOLUTION 9:<\/label><\/p>\n<ul>\n<li>The\u00a0way to avoid branch prediction errors is to build a lookup table, and index it using the data<\/li>\n<li>By using the 0\/1 value of the decision bit as an index into an array, we can make code that will be equally fast whether the data is sorted or not sorted.<\/li>\n<li>Our code will always add a value, but when the decision bit is 0, we will add the value somewhere we don\u2019t care<\/li>\n<\/ul>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Test%0Aclock_t%20start%20%3D%20clock()%3B%0Along%20long%20a%5B%5D%20%3D%20%7B0%2C%200%7D%3B%0Along%20long%20sum%3B%0A%0Afor%20(unsigned%20i%20%3D%200%3B%20i%20%3C%20100000%3B%20%2B%2Bi)%0A%7B%0A%20%20%20%20%2F%2F%20Primary%20loop%0A%20%20%20%20for%20(unsigned%20c%20%3D%200%3B%20c%20%3C%20arraySize%3B%20%2B%2Bc)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20j%20%3D%20(data%5Bc%5D%20%3E%3E%207)%3B%0A%20%20%20%20%20%20%20%20a%5Bj%5D%20%2B%3D%20data%5Bc%5D%3B%0A%20%20%20%20%7D%0A%7D%0A%0Adouble%20elapsedTime%20%3D%20static_cast%3Cdouble%3E(clock()%20-%20start)%20%2F%20CLOCKS_PER_SEC%3B%0Asum%20%3D%20a%5B1%5D%3B%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>This code wastes half of the adds, but never has a branch prediction failure.<\/strong><\/p>\n<ul>\n<li>The technique of indexing into an array, instead of using an if statement, can be used for deciding which pointer to use.<\/li>\n<li>A library that implemented binary trees, and instead of having two named pointers (pLeft and pRight or whatever) had a length-2 array of pointers, and used the \u201cdecision bit\u201d technique to decide which one to follow.<\/li>\n<li>For example, instead of:<\/li>\n<\/ul>\n[pastacode lang=\u201djava\u201d manual=\u201dif%20(x%20%3C%20node-%3Evalue)%0A%20%20%20%20node%20%3D%20node-%3EpLeft%3B%0Aelse%0A%20%20%20%20node%20%3D%20node-%3EpRight%3B%0Athis%20library%20would%20do%20something%20like%3A%0A%0Ai%20%3D%20(x%20%3C%20node-%3Evalue)%3B%0Anode%20%3D%20node-%3Elink%5Bi%5D%3B%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><label class=\"label label-info\">SOLUTION 10:<\/label><\/p>\n<ul>\n<li>In the sorted case, you can do better than relying on successful branch prediction or any branchless comparison trick: completely remove the branch.<\/li>\n<li>The array is partitioned in a contiguous zone with data < 128 and another with data >= 128. So you should find the partition point with a dichotomic search (using Lg(arraySize) = 15 comparisons), then do a straight accumulation from that point.<\/li>\n<\/ul>\n<h4 id=\"something-like-unchecked\"><span style=\"color: #800080;\"><b>Something like (unchecked)<\/b><\/span><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201dint%20i%3D%200%2C%20j%2C%20k%3D%20arraySize%3B%0Awhile%20(i%20%3C%20k)%0A%7B%0A%20%20j%3D%20(i%20%2B%20k)%20%3E%3E%201%3B%0A%20%20if%20(data%5Bj%5D%20%3E%3D%20128)%0A%20%20%20%20k%3D%20j%3B%0A%20%20else%0A%20%20%20%20i%3D%20j%3B%0A%7D%0Asum%3D%200%3B%0Afor%20(%3B%20i%20%3C%20arraySize%3B%20i%2B%2B)%0A%20%20sum%2B%3D%20data%5Bi%5D%3B%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"slightly-more-obfuscated\"><span style=\"color: #ff6600;\"><b>slightly more obfuscated<\/b><\/span><\/h4>\n[pastacode lang=\u201djava\u201d manual=\u201dint%20i%2C%20k%2C%20j%3D%20(i%20%2B%20k)%20%3E%3E%201%3B%0Afor%20(i%3D%200%2C%20k%3D%20arraySize%3B%20i%20%3C%20k%3B%20(data%5Bj%5D%20%3E%3D%20128%20%3F%20k%20%3A%20i)%3D%20j)%0A%20%20j%3D%20(i%20%2B%20k)%20%3E%3E%201%3B%0Afor%20(sum%3D%200%3B%20i%20%3C%20arraySize%3B%20i%2B%2B)%0A%20%20sum%2B%3D%20data%5Bi%5D%3B%0A\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><label class=\"label label-info\">SOLUTION 11:<\/label><\/p>\n<p>The diagram shows\u00a0why the branch predictor gets confused.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-3228 size-full\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/03\/Pinj.png\" alt=\"\" width=\"604\" height=\"124\" \/><\/p>\n<ul>\n<li>Each element in the original code is a random value<\/li>\n<\/ul>\n[pastacode lang=\u201djava\u201d manual=\u201ddata%5Bc%5D%20%3D%20std%3A%3Arand()%20%25%20256%3B\u201d message=\u201djava code\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li>so the predictor will change sides as the std::rand() blow.<\/li>\n<li>Once it\u2019s sorted, the predictor will first move into a state of strongly not taken and when the values change to the high value the predictor will in three runs through change all the way from strongly not taken to strongly taken.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Why is it faster to process a sorted array than an unsorted array -When the data is sorted, roughly the first half of the<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2139],"tags":[6042,6043,6040,6038,6041,6047,6034,6030,6046,6044,6045,6036,6033,6029,6015,6035,6031,6032,6037,6039],"class_list":["post-3204","post","type-post","status-publish","format-standard","hentry","category-java","tag-branch-prediction-program-in-java","tag-c-branch-prediction","tag-difference-between-sorted-and-unsorted-array","tag-does-a-sorted-array-run-faster-than-an-unsorted-array-in-java","tag-explain-how-you-know-whether-google-keeps-its-inventory-of-webpage-content-sorted","tag-how-does-branch-prediction-work","tag-is-in-sorted-array-not-faster-than-unsorted-array","tag-is-faster-than","tag-java-branch-prediction","tag-sorted-and-unsorted-array-in-c","tag-sorted-array-c","tag-why-is-ab-0-faster-than-a-0-b-0-in-java","tag-why-is-faster-than-list","tag-why-is-one-loop-so-much-slower-than-two-loops","tag-why-is-printing-b-dramatically-slower-than-printing","tag-why-is-processing-a-sorted-array-slower-than-an-unsorted-array-javas-arraylist-indexof","tag-why-is-processing-a-sorted-array-not-faster-than-an-unsorted-array-in-python","tag-why-is-processing-a-sorted-array-slower-than-an-unsorted-array","tag-why-is-this-c-code-faster-than-my-hand-written-assembly-for-testing-the-collatz-conjecture","tag-why-processing-a-sorted-array-might-be-faster-than-unsorted"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/3204","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=3204"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/3204\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=3204"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=3204"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=3204"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}