Как отключить предсказание ветвлений C ++ / Mac / Intel - PullRequest
Новая
       51

Как отключить предсказание ветвлений C ++ / Mac / Intel

1 голос
/ 10 июля 2019

Я работаю над заданием для школы.По сути, мы анализируем алгоритмы сортировки и их стоимость на больших наборах чисел.У нас есть лучший случай (в порядке уже), худший случай (обратный порядок) и средний случай (случайный порядок).Тем не менее, почти для всех моих алгоритмов сортировки сортировка в худшем случае занимает меньше времени, чем в среднем.После прочтения это определенно кажется предсказанием ветвлений.Это распознавание паттерна (убывающий порядок) и выполнение кода быстрее, чем это должно быть теоретически (большие обозначения O).

Я провел некоторое исследование по прогнозированию ветвлений, и, хотя, похоже, есть способыоптимизировать это, чтобы быть быстрее, я не могу найти что-нибудь о его отключении полностью.Можно ли использовать флаг G ++?Или команда терминала?

Это пример моего алгоритма сортировки пузырьков: 

void bubble(vector<long> &vector) {
    for (int i = 0; i < vector.size() - 1; i++){
        for (int j = 0; j < vector.size() - i - 1; j++) {
            if (vector[j] > vector[j + 1]) {
                long tmp = vector[j];
                vector[j] = vector[j+1];
                vector[j+1] = tmp;
            }
        }
    }
}

Мои тайминги для моего среднего случая почти удваиваются для худшего случая.

1 Ответ

2 голосов
/ 10 июля 2019

Big-O нотация - это все о асимптотическом поведении.Другими словами, он описывает, какие факторы становятся доминирующими по мере увеличения размера проблемы.

Микрооптимизация ЦП, такая как предварительная выборка и предсказание ветвлений, может иметь большие относительные эффекты при меньших размерах.Но природа процедуры O (n ^ 2) относительно процедуры O (n) заключается в том, что она будет становиться медленнее, когда размер проблемы достаточно велик.

не беспокойтесь или не беспокойтесь о последствиях предсказания ветвлений.Просто сделайте ваш массив больше.Попробуйте отсортировать массив из 1 миллиона элементов.Или 1 млрд.Я гарантирую вам: если вы правы в том, что одна ситуация является наихудшей, она будет медленнее, чем в лучшем случае.(Подсказка: вы не правы в этом.)

...