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

java / performance / optimization / branch-prediction

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

#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

В той же строке (я думаю, что это не было выделено ни одним ответом) хорошо упомянуть, что иногда (особенно в программном обеспечении, где важна производительность - например, в ядре Linux) вы можете найти некоторые операторы if, подобные следующему:

if (likely( everything_is_ok ))
{
    /* Сделай что-нибудь */
}

или что-то в этом роде:

if (unlikely(very_improbable_condition))
{
    /* Сделай что-нибудь */    
}





performance - c++ - gcc avx - Почему в отдельных петлях элементное добавление происходит гораздо быстрее,чем в комбинированном? timeit python как пользоваться - Почему в C++чтение строк из stdin происходит гораздо медленнее,чем в Python? relational-operators - java vs c++ performance - Является ли<быстрее,чем <=? pi - algorithm - english for mathematicians and information technologies learners ответы - Как определить,является ли мое вычисление числа пи точным? performance - java - all the data which a computer are in the form of numbers - Почему печать "B" значительно медленнее,чем печать "#"? c++-faq - c++ - unique_ptr c - Почему я должен использовать указатель,а не сам объект? performance - swift язык программирования основы - Производительность Swift Beta:сортировка массивов performance - python - Почему []быстрее,чем list()? performance - Почему код на C++для проверки гипотезы Коллатца выполняется быстрее,чем написанный вручную ассемблер? performance - climbing stairs - leetcode - Почему 2*(i*i)быстрее,чем 2*i*i в Java?