{"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 – Why is it faster to process a sorted array than an unsorted array"},"content":{"rendered":"

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

c++ code<\/span> <\/div> 
#include <algorithm>#include <ctime>#include <iostream>int main(){    \/\/ Generate data    const unsigned arraySize = 32768;    int data[arraySize];    for (unsigned c = 0; c < arraySize; ++c)        data[c] = std::rand() % 256;    \/\/ !!! With this, the next loop runs faster    std::sort(data, data + arraySize);\/\/ Test    clock_t start = clock();    long long sum = 0; for (unsigned i = 0; i < 100000; ++i)    {        \/\/ Primary loop        for (unsigned c = 0; c < arraySize; ++c)        {            if (data[c] >= 128)                sum += data[c];        }    } double elapsedTime = static_cast<double>(clock() - start) \/ CLOCKS_PER_SEC; std::cout << elapsedTime << std::endl; std::cout << "sum = " << sum << std::endl;}<\/code><\/pre> <\/div>\n
    \n
  • Without\u00a0std::sort(data, data + arraySize);, the code runs in 11.54 seconds.<\/li>\n
  • With the sorted data, the code runs in 1.93 seconds.<\/li>\n<\/ul>\n
    Initially, this might be just a language or compiler anomaly. So a Trail in Java.<\/strong><\/p>\n
     
     java code<\/span> <\/div> 
    import java.util.Arrays;import java.util.Random;public class Main{    public static void main(String[] args)    {        \/\/ Generate data        int arraySize = 32768;        int data[] = new int[arraySize];        Random rnd = new Random(0);        for (int c = 0; c < arraySize; ++c)            data[c] = rnd.nextInt() % 256;        \/\/ !!! With this, the next loop runs faster        Arrays.sort(data);\/\/ Test        long start = System.nanoTime();        long sum = 0;        for (int i = 0; i < 100000; ++i)        {            \/\/ Primary loop            for (int c = 0; c < arraySize; ++c)            {                if (data[c] >= 128)                    sum += data[c];            }        }        System.out.println((System.nanoTime() - start) \/ 1000000000.0);        System.out.println("sum = " + sum);    }}<\/code><\/pre> <\/div>\n
    With a somewhat similar but less extreme result.<\/p>\n
     
     c ++ code<\/span> <\/div> 
    if (data[c] >= 128) sum += data[c];<\/code><\/pre> <\/div>\n
      \n
    • Notice that the data is evenly distributed between 0 and 255.<\/li>\n
    • When the data is sorted, roughly the first half of the iterations will not enter the if-statement.<\/li>\n
    • After that, they will all enter the if-statement.<\/li>\n
    • This is very friendly to the branch predictor since the branch consecutively goes the same direction many times.<\/li>\n
    • Even a simple saturating counter will correctly predict the branch except for the few iterations after it switches direction.<\/li>\n<\/ul>\n
      Quick visualization:<\/b><\/span><\/h4>\n
      T = branch taken N = branch not taken data[] = 0, 1, 2, 3, 4, … 126, 127, 128, 129, 130, … 250, 251, 252, … branch = N N N N N … N N T T T … T T T … = NNNNNNNNNNNN … NNNNNNNTTTTTTTTT … TTTTTTTTTT (easy to predict)<\/p>\n
        \n
      • However, when the data is completely random, the branch predictor is rendered useless because it can’t predict random data.<\/li>\n<\/ul>\n
        data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, … branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N … = TTNTTTTNTNNTTTN … (completely random – hard to predict)<\/p>\n
        If the compiler isn’t able to optimize the branch into a conditional move,<\/p>\n
        Replace:<\/strong><\/span><\/h4>\n
         
         c++ code<\/span> <\/div> 
        if (data[c] >= 128) sum += data[c]; <\/code><\/pre> <\/div>\n
        with:<\/span><\/strong><\/h4>\n
         
         c++ code<\/span> <\/div> 
        int t = (data[c] - 128) >> 31;sum += ~t & data[c]; <\/code><\/pre> <\/div>\n
          \n
        • This eliminates the branch and replaces it with some bitwise operations.<\/li>\n<\/ul>\n
          C++ – Visual Studio 2010 – x64 Release<\/span><\/strong><\/h4>\n
           
           c ++ code<\/span> <\/div> 
          \/\/ Branch - Random seconds = 11.777 \/\/ Branch - Sorted seconds = 2.352 \/\/ Branchless - Random seconds = 2.564 \/\/ Branchless \u2013 Sortedseconds = 2.587 <\/code><\/pre> <\/div>\n
          Java – Netbeans 7.1.1 JDK 7 – x64<\/span><\/strong><\/h4>\n
           
           java code<\/span> <\/div> 
          \/\/ Branch - Random seconds = 10.93293813 \/\/ Branch - Sorted seconds = 5.643797077 \/\/ Branchless \u2013 Random seconds = 3.113581453 \/\/ Branchless \u2013 Sorted seconds = 3.186068823 <\/code><\/pre> <\/div>\n
            \n
          • With the Branch:<\/b>There is a huge difference between the sorted and unsorted data.<\/li>\n
          • With the Hack:<\/b>There is no difference between sorted and unsorted data.<\/li>\n
          • In the C++ case, the hack is actually a tad slower than with the branch when the data is sorted.<\/li>\n<\/ul>\n
             
             c++ code<\/span> <\/div> 
            if (data[c] >= 128) sum += data[c]; <\/code><\/pre> <\/div>\n
              \n
            • The meaning of this particular\u00a0if… else…\u00a0branch is to add something when a condition is satisfied.<\/li>\n
            • This type of branch can be easily transformed into a\u00a0conditional move<\/b>statement, which would be compiled into a conditional move instruction:\u00a0cmovl, in an\u00a0x86\u00a0system.<\/li>\n
            • The branch and thus the potential branch prediction penalty is removed.<\/li>\n<\/ul>\n
                \n
              • 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… ? … : ….<\/li>\n
              • So it can be rewritten as:<\/li>\n<\/ul>\n
                 
                 c++ code<\/span> <\/div> 
                sum += data[c] >=128 ? data[c] : 0; <\/code><\/pre> <\/div>\n[ad type=”banner”]\n
                 
                 java code<\/span> <\/div> 
                x86\/\/ Branch - Random seconds = 8.885 \/\/ Branch - Sorted seconds = 1.528 \/\/ Branchless - Random seconds = 3.716 \/\/ Branchless - Sorted seconds = 3.71 <\/code><\/pre> <\/div>\n
                 
                 java code<\/span> <\/div> 
                x64\/\/ Branch \u2013 Random seconds = 11.302 \/\/ Branch \u2013 Sorted seconds = 1.830 \/\/ Branchless - Random seconds = 2.736 \/\/ Branchless \u2013 Sorted seconds = 2.737 <\/code><\/pre> <\/div>\n[ad type=”banner”]\n
                Thus from the previous fix, lets investigate the\u00a0x86\u00a0assembly they generate. For simplicity, we use two functions\u00a0max1\u00a0and\u00a0max2.<\/p>\n
                 
                 java code<\/span> <\/div> 
                max1\u00a0uses the conditional branch\u00a0if... else ...:int max1(int a, int b) { if (a > b) return a; else return b; } <\/code><\/pre> <\/div>\n
                 
                 java code<\/span> <\/div> 
                max2\u00a0uses the ternary operator\u00a0... ? ... : ...:int max2(int a, int b) { return a > b ? a : b; } <\/code><\/pre> <\/div>\n
                 
                 C++ code<\/span> <\/div> 
                max1 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl -8(%rbp), %eax jle .L2 movl -4(%rbp), %eax movl %eax, -12(%rbp) jmp .L4 .L2: movl -8(%rbp), %eax movl %eax, -12(%rbp) .L4: movl -12(%rbp), %eax leave ret :max2 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl %eax, -8(%rbp) cmovge -8(%rbp), %eax leave ret <\/code><\/pre> <\/div>\n
                  \n
                • max2\u00a0uses much less code due to the usage of instruction\u00a0cmovge<\/li>\n
                • 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
                • In a typical\u00a0x86\u00a0processor, the execution of an instruction is divided into several stages.<\/li>\n
                • Thus they have different hardware to deal with different stages.<\/li>\n
                • So we do not have to wait for one instruction to finish to start a new one.<\/li>\n
                • This is called\u00a0pipelining<\/b>.<\/li>\n<\/ul>\n
                  \u00a0Starting with the original loop:<\/span><\/h4>\n
                   
                   java code<\/span> <\/div> 
                  for (unsigned i = 0; i < 100000; ++i) { for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) sum += data[j]; } } <\/code><\/pre> <\/div>\n
                  With loop interchange, we can change this loop to:<\/span><\/h4>\n
                   
                   java code<\/span> <\/div> 
                  for (unsigned j = 0; j < arraySize; ++j) { for (unsigned i = 0; i < 100000; ++i) { if (data[j] >= 128) sum += data[j]; } } <\/code><\/pre> <\/div>\n
                  if” conditional is constant throughout the execution of the “i” loop, so you can hoist the “if” out:<\/p>\n
                   
                   java code<\/span> <\/div> 
                  for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { for (unsigned i = 0; i < 100000; ++i) { sum += data[j]; } } } <\/code><\/pre> <\/div>\n
                  the inner loop can be collapsed into one single expression, assuming the floating point model allows it<\/p>\n
                   
                   java code<\/span> <\/div> 
                  for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { sum += data[j] * 100000; } } <\/code><\/pre> <\/div>\n
                    \n
                  • The Valgrind tool cachegrind has a branch-predictor simulator, enabled by using the –branch-sim=yes flag.<\/li>\n
                  • 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
                    Sorted:<\/strong><\/span><\/h4>\n
                     
                     java code<\/span> <\/div> 
                    ==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )<\/code><\/pre> <\/div>\n
                    Unsorted:<\/span><\/strong><\/h4>\n
                     
                     java code<\/span> <\/div> 
                    ==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )<\/code><\/pre> <\/div>\n
                      \n
                    • Drilling down into the line-by-line output produced by cg_annotate we see for the loop in question:<\/li>\n<\/ul>\n
                      Sorted:<\/strong><\/span><\/h4>\n
                       
                       java code<\/span> <\/div> 
                      Bc    Bcm Bi Bim      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)           .      .  .   .     \t\t\t {           .      .  .   .        \t\t\t  \/\/ primary loop 327,690,000 10,016  0   0          for (unsigned c = 0; c < \t\t\t\tarraySize; ++c)           .      .  .   .        \t\t\t  { 327,680,000 10,006  0   0              if (data[c] >= 128)           0      0  0   0                  sum += data[c];           .      .  .   .         \t\t }           .      .  .   .     \t\t\t }<\/code><\/pre> <\/div>\n
                      Unsorted:<\/strong><\/span><\/h4>\n
                       
                       java code<\/span> <\/div> 
                                Bc         Bcm Bi Bim      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)           .           .  .   .     \t\t {           .           .  .   .         \t\t \/\/ primary loop 327,690,000      10,038  0   0          for (unsigned c = 0; c < \t\t\t\t\tarraySize; ++c)           .           .  .   .        \t\t  { 327,680,000 164,050,007  0   0              if (data[c] >= 128)           0           0  0   0                  \tsum += data[c];           .           .  .   .         \t\t }           .           .  .   .     \t\t }<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
                        \n
                      • the problematic line – in the unsorted version the if (data[c] >= 128) line is causing 164,050,007 mispredicted conditional branches (Bcm) under cachegrind’s branch-predictor model, whereas it’s only causing 10,006 in the sorted version.<\/li>\n<\/ul>\n
                          \n
                        • On Linux you can use the performance counters subsystem to accomplish The Valgrind tool cachegrind has a branch-predictor simulator, enabled by using the –branch-sim=yes flag, but with native performance using CPU counters.<\/li>\n<\/ul>\n
                          Sorted:<\/span><\/strong><\/h4>\n
                           
                           java code<\/span> <\/div> 
                          Performance counter stats for '.\/sumtest_sorted': 11808.095776 task-clock # 0.998 CPUs utilized 1,062 context-switches # 0.090 K\/sec 14 CPU-migrations # 0.001 K\/sec 337 page-faults # 0.029 K\/sec 26,487,882,764 cycles # 2.243 GHz 41,025,654,322 instructions # 1.55 insns per cycle 6,558,871,379 branches # 555.455 M\/sec 567,204 branch-misses # 0.01% of all branches 11.827228330 seconds time elapsed <\/code><\/pre> <\/div>\n
                          Unsorted:<\/b><\/span><\/h4>\n
                           
                           java code<\/span> <\/div> 
                          Performance counter stats for '.\/sumtest_unsorted': 28877.954344 task-clock # 0.998 CPUs utilized 2,584 context-switches # 0.089 K\/sec 18 CPU-migrations # 0.001 K\/sec 335 page-faults # 0.012 K\/sec 65,076,127,595 cycles # 2.253 GHz 41,032,528,741 instructions # 0.63 insns per cycle 6,560,579,013 branches # 227.183 M\/sec 1,646,394,749 branch-misses # 25.10% of all branches 28.935500947 seconds time elapsed <\/code><\/pre> <\/div>\n
                            \n
                          • It can also do source code annotation with dissassembly.<\/li>\n
                          • perf record -e branch-misses .\/sumtest_unsorted<\/li>\n
                          • perf annotate -d sumtest_unsorted<\/li>\n<\/ul>\n
                            Percent | \u00a0 Source code & Disassembly of sumtest_unsorted<\/p>\n
                             
                             java code<\/span> <\/div> 
                            ...         :                      sum += data[c];    0.00 :        400a1a:       mov    -0x14(%rbp),%eax   39.97 :        400a1d:       mov    %eax,%eax    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax    4.60 :        400a26:       cltq       0.00 :        400a28:       add    %rax,-0x30(%rbp)...<\/code><\/pre> <\/div>\n
                            A common way to eliminate branch prediction is that, to work in managed languages -a table lookup instead of using a branch<\/p>\n
                             
                             java code<\/span> <\/div> 
                            \/\/ generate dataint arraySize = 32768;int[] data = new int[arraySize];Random rnd = new Random(0);for (int c = 0; c < arraySize; ++c)    data[c] = rnd.Next(256);\/\/ Too keep the spirit of the code in-tact we will make a separate lookup table\/\/ (Assume we cannot modify 'data' or the number of loops)int[] lookup = new int[256];for (int c = 0; c < 256; ++c)    lookup[c] = (c >= 128) ? c : 0;\/\/ testDateTime startTime = System.DateTime.Now;long sum = 0;for (int i = 0; i < 100000; ++i){    \/\/ primary loop    for (int j = 0; j < arraySize; ++j)    {        \/\/ here you basically want to use simple operations - so no         \/\/ random branches, but things like &, |, *, -, +, etc are fine.        sum += lookup[data[j]];    }}DateTime endTime = System.DateTime.Now;Console.WriteLine(endTime - startTime);Console.WriteLine("sum = " + sum);Console.ReadLine();<\/code><\/pre> <\/div>\n
                              \n
                            • measure the performance of this loop with different conditions:<\/li>\n<\/ul>\n
                               
                               java code<\/span> <\/div> 
                              for (int i = 0; i < max; i++) if (condition) sum++; <\/code><\/pre> <\/div>\n
                              Here are the timings of the loop with different True-False patterns:<\/p>\n
                              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
                              (i & 0\u00d780000000) == 0\u00a0 \u00a0 \u00a0T repeated\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 322<\/p>\n
                              (i & 0xffffffff) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0F repeated\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 276<\/p>\n
                              (i & 1) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 TF alternating\u00a0\u00a0\u00a0 \u00a0 760<\/p>\n
                              (i & 3) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 TFFFTFFF\u2026 \u00a0 \u00a0 \u00a0 513<\/p>\n
                              (i & 2) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 TTFFTTFF\u2026 \u00a0 \u00a0 \u00a01675<\/p>\n
                              (i & 4) == 0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 TTTTFFFFTTTTFFFF1275<\/p>\n
                              (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
                              (i & 16) == 0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0 16T 16F 16T 16F \u2026 \u00a0 \u00a0490<\/p><\/blockquote>\n
                                \n
                              • A \u201cbad<\/b>\u201d true-false pattern can make an if-statement up to six times slower than a \u201cgood<\/b>\u201d pattern!<\/li>\n
                              • \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
                                  \n
                                • The\u00a0way to avoid branch prediction errors is to build a lookup table, and index it using the data<\/li>\n
                                • 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
                                • Our code will always add a value, but when the decision bit is 0, we will add the value somewhere we don’t care<\/li>\n<\/ul>\n
                                   
                                   java code<\/span> <\/div> 
                                  \/\/ Testclock_t start = clock();long long a[] = {0, 0};long long sum;for (unsigned i = 0; i < 100000; ++i){    \/\/ Primary loop    for (unsigned c = 0; c < arraySize; ++c)    {        int j = (data[c] >> 7);        a[j] += data[c];    }}double elapsedTime = static_cast<double>(clock() - start) \/ CLOCKS_PER_SEC;sum = a[1];<\/code><\/pre> <\/div>\n
                                  This code wastes half of the adds, but never has a branch prediction failure.<\/strong><\/p>\n
                                    \n
                                  • The technique of indexing into an array, instead of using an if statement, can be used for deciding which pointer to use.<\/li>\n
                                  • 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 “decision bit” technique to decide which one to follow.<\/li>\n
                                  • For example, instead of:<\/li>\n<\/ul>\n
                                     
                                     java code<\/span> <\/div> 
                                    if (x < node->value)    node = node->pLeft;else    node = node->pRight;this library would do something like:i = (x < node->value);node = node->link[i];<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
                                      \n
                                    • 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
                                    • 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
                                      Something like (unchecked)<\/b><\/span><\/h4>\n
                                       
                                       java code<\/span> <\/div> 
                                      int i= 0, j, k= arraySize;while (i < k){  j= (i + k) >> 1;  if (data[j] >= 128)    k= j;  else    i= j;}sum= 0;for (; i < arraySize; i++)  sum+= data[i];<\/code><\/pre> <\/div>\n
                                      slightly more obfuscated<\/b><\/span><\/h4>\n
                                       
                                       java code<\/span> <\/div> 
                                      int i, k, j= (i + k) >> 1;for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)  j= (i + k) >> 1;for (sum= 0; i < arraySize; i++)  sum+= data[i];<\/code><\/pre> <\/div>\n
                                      The diagram shows\u00a0why the branch predictor gets confused.<\/p>\n
                                      \"\"<\/p>\n
                                        \n
                                      • Each element in the original code is a random value<\/li>\n<\/ul>\n
                                         
                                         java code<\/span> <\/div> 
                                        data[c] = std::rand() % 256;<\/code><\/pre> <\/div>\n
                                          \n
                                        • so the predictor will change sides as the std::rand() blow.<\/li>\n
                                        • Once it’s 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":"
                                          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}]}}