branch-prediction - java - Почему обработка отсортированного массива происходит быстрее,чем обработка несортированного массива?

java / c++ / performance / optimization

Вот кусок Си++кода,который показывает очень своеобразное поведение.По какой-то странной причине чудесная сортировка данных делает код почти в шесть раз быстрее:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Генерируем данные
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! При этом следующий цикл выполняется быстрее.
    std::sort(data, data + arraySize);

    // Контрольная работа
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Первичный цикл
        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;
}

Сначала я подумал,что это может быть просто аномалия языка или компилятора,так что я попробовал Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Генерируем данные
        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;

        // !!! При этом следующий цикл выполняется быстрее.
        Arrays.sort(data);

        // Контрольная работа
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Первичный цикл
            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);
    }
}

Aplet123



Answer #1
==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%   )
==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%   )
          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }
          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Кроме того,на Linux вы можете использовать подсистему счетчиков производительности для выполнения той же задачи,но с собственной производительностью с помощью счетчиков процессора.

perf stat ./sumtest_sorted
 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
 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

Он также может делать аннотацию исходного кода с разборкой.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      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)
...





compiler-optimization - c++ - cflags - Почему в отдельных петлях элементное добавление происходит гораздо быстрее,чем в комбинированном? getline - ускоряем python - Почему в C++чтение строк из stdin происходит гораздо медленнее,чем в Python? c++ - why java is slow - Является ли<быстрее,чем <=? algorithm - english for mathematicians and information technologies learners ответы - Как определить,является ли мое вычисление числа пи точным? cpu-cache - c++ - виды кэш-памяти - Что такое "кэш-френдли" код? system.out - java - all the data which a computer are in the form of numbers - Почему печать "B" значительно медленнее,чем печать "#"? c++ - elegant objects на русском - Почему я должен использовать указатель,а не сам объект? compiler-optimization - swift с нуля - Производительность Swift Beta:сортировка массивов literals - python - Почему []быстрее,чем list()? x86 - Почему код на C++для проверки гипотезы Коллатца выполняется быстрее,чем написанный вручную ассемблер? jit - jmh fork - Почему 2*(i*i)быстрее,чем 2*i*i в Java?