С++ Оптимизировать условие if else

Ответ 1

Позвольте мне предисловие к этому с тем, что то, что я собираюсь описать здесь, является хрупким и не совсем переносимым - но при правильных обстоятельствах (которые в значительной степени вы указали) я вполне уверен, что это должен работать правильно.

Один момент зависит от того, что числа с плавающей запятой IEEE тщательно разработаны таким образом, что если вы обрабатываете свой битовый шаблон как целое число, они все равно будут сортироваться в правильном порядке (по модулю несколько вещей, таких как NaNs, для которых там действительно нет "правильного порядка" ).

Чтобы использовать это, мы делаем пачку Entry, чтобы между двумя частями, составляющими наш ключ, не было отступов. Затем мы гарантируем, что структура в целом выровнена с 8-байтной границей. Я также изменил _id на int32_t, чтобы гарантировать, что он останется 32 бит, даже в 64-разрядной системе/компиляторе (что почти наверняка даст лучший код для этого сравнения).

Затем мы укажем адрес структуры, чтобы мы могли рассматривать число с плавающей запятой и целое число вместе как одно 64-битное целое число. Поскольку вы используете малоинтенсивный процессор, чтобы поддержать то, что нам нужно сначала поставить менее значительную часть (id), а более значительную часть (cost) - вторую, поэтому, когда мы рассматриваем их как 64-битное целое число, часть с плавающей запятой станет наиболее значимыми битами, а целочисленная часть - менее значимыми битами:

struct __attribute__ ((__packed__)) __attribute__((aligned(8)) Entry {
  // Do *not* reorder the following two fields or comparison will break.
  const int32_t _id;
  const float _cost;

  // some other vars

    Entry(long id, float cost) : _cost(cost), _id(id) {} 
};

Тогда у нас есть наша уродливая небольшая функция сравнения:

bool operator<(Entry const &a, Entry const &b) { 
   return *(int64_t const *)&a < *(int64_t const *)&b;
}

Как только мы правильно определили структуру, сравнение становится довольно простым: просто возьмите первые 64 бита каждой структуры и сравните их, как если бы они были 64-битными целыми числами.

Наконец, немного тестового кода, чтобы дать хотя бы небольшую уверенность, что он корректно работает для некоторых значений:

int main() { 
    Entry a(1236, 1.234f), b(1234, 1.235f), c(1235, 1.235f);

    std::cout << std::boolalpha;

    std::cout << (b<a) << "\n";
    std::cout << (a<b) << "\n";
    std::cout << (b<c) << "\n";
    std::cout << (c<b) << "\n";
    return 0;
}

По крайней мере, для меня это дает ожидаемые результаты:

false
true
true
false

Теперь некоторые из возможных проблем: если два элемента будут перегруппированы либо между собой, либо любая другая часть структуры будет помещена перед ними или между ними, сравнение, безусловно, будет нарушено. Во-вторых, мы полностью зависим от размеров элементов, оставшихся 32 бит за штуку, поэтому, когда они объединены, они будут 64 бит. В-третьих, если кто-то удалит атрибут __packed__ из определения структуры, мы могли бы получить отступы между _id и _cost, снова нарушив сравнение. Аналогично, если кто-то удаляет выравнивание (8), код может потерять некоторую скорость, потому что он пытается загрузить 8-байтовые количества, которые не выровнены с 8-байтовыми границами (а на другом процессоре это может завершиться неудачно). [Изменить: К сожалению. @rici напомнил мне то, что я намеревался перечислить здесь, но забыл: это работает корректно только тогда, когда оба _id и cost являются положительными. Если _cost является отрицательным, сравнения будут испорчены тем фактом, что плавающая точка IEEE использовала представление с фиксированной величиной. Если символ _id отрицательный, его знаковый бит будет обрабатываться как обычный бит в середине числа, поэтому отрицательный _id будет отображаться больше, чем положительный _id.]

Подводя итог: это хрупкий. Об этом не спрашивайте. Тем не менее, это должно быть довольно быстро - особенно если вы используете 64-битный компилятор, и в этом случае я ожидаю, что сравнение выйдет на две нагрузки и одно сравнение. Чтобы сделать длинный рассказ коротким, вы находитесь в точке, что, вероятно, вы не можете сделать сравнение само по себе быстрее - все, что вы можете сделать, это попытаться сделать больше параллельно, оптимизировать шаблоны использования памяти и т.д.

Ответ 2

Мне трудно полагать, что:

a) Функция сравнения работает 180 миллионов раз за 30 секунд

и

b) Функция сравнения использует 25% времени процессора

являются истинными. Даже Core 2 Duo легко сможет выполнить 180 миллионов сравнений менее чем за секунду (в конце концов, утверждается, что он может делать что-то вроде 12 000 MIPS, если это на самом деле означает что-либо). Поэтому я склонен полагать, что в сравнении с программным обеспечением для профилирования есть что-то еще. (Например, выделение памяти для новых элементов.)

Однако вы должны хотя бы рассмотреть возможность того, что std:: set не является структурой данных, которую вы ищете. Если вы делаете миллионы вставок до того, как вам действительно нужны отсортированные значения (или максимальное значение, даже), тогда вам может быть лучше помещать значения в вектор, который представляет собой гораздо более дешевую структуру данных как по времени, так и по пространству и сортировку это по требованию.

Если вам действительно нужен набор, потому что вы беспокоитесь о столкновениях, то вместо этого вы можете рассмотреть неупорядоченную_запись, что немного дешевле, но не так дешево, как вектор. (Именно потому, что векторы не могут гарантировать вам уникальность.) Но, честно говоря, глядя на определение этой структуры, я с трудом верю, что уникальность важна для вас.

"Benchmark"

На моем маленьком ноутбуке Core i5, который, я полагаю, не в той же лиге, что и в OP-машине, я провел несколько тестов, вставив 10 миллионов случайных уникальных записей (только с двумя полями сравнения) в std:: set и в std::vector. В конце этого я сортирую вектор.

Я сделал это дважды; один раз со случайным генератором, который производит, вероятно, уникальные затраты, и один раз с генератором, который производит ровно две разные затраты (что должно сделать сравнение медленнее). Десять миллионов вставок приводит к чуть большему количеству сравнений, чем сообщает OP.

              unique cost         discrete cost
           compares     time    compares     time
set       243002508    14.7s   241042920    15.6s   
vector    301036818     2.0s   302225452     2.3s

В попытке еще раз изолировать время сравнения я перечеркнул векторные тесты, используя как std:: sort, так и std:: partial_sort, используя 10 элементов (по существу выбор из 10-ти) и 10% элементов (что есть, один миллион). Результаты большего partial_sort удивили меня - кто бы мог подумать, что сортировка 10% вектора будет медленнее, чем сортировка всего этого, но они показывают, что затраты на алгоритмы намного более значительны, чем затраты на сравнение:

                     unique cost         discrete cost
                  compares     time    compares     time
partial sort 10   10000598     0.6s    10000619     1.1s
partial sort 1M   77517081     2.3s    77567396     2.7s
full sort        301036818     2.0s   302225452     2.3s   

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

Небольшое примечание, для чего оно стоит:

Единственное, что я получил от этого кода сборочного кода, это то, что вы ничего не спасаете, сделав стоимость float. Он фактически выделяет восемь байтов для float, поэтому вы не сохраняете память, и ваш процессор не делает ни одного сравнения с плавающей точкой быстрее, чем одно двойное сравнение. Просто скажите (т.е. Остерегайтесь преждевременной оптимизации).

Downvoter, помогите объяснить?

Ответ 3

Простое решение представляет собой прекомпутный идентификатор сортировки, включающий стоимость как наиболее значимую, а идентификатор - как остальные.

например.

struct Entry
{
    double cost_;
    long id_;
    long long sortingId_;

  // some other vars

    Entry( double cost, float id )
        : cost_( cost ), id_( id ), sortingId_( 1e9*100*cost + id )
    {} 
};

Отрегулируйте значение sortingId_ на основе того, что вы можете предположить о диапазонах значений.

Затем просто сортируйте по sortingId_.

Или как изменение той же идеи, если вы не можете сделать подходящие предположения о данных, тогда рассмотрите подготовку данных, особенно для memcmp.

Для решения более высокого уровня помните, что std::set::insert имеет перегрузку с аргументом hint. Если ваши данные уже находятся в упорядоченном порядке, это может серьезно снизить количество вызовов вашей функции компаратора.

И вы можете подумать, достаточно ли std::unordered_set? То есть нужно ли перечислять данные в отсортированном порядке. Или, если сортировка является всего лишь внутренним элементом вставки элемента std::set.

Наконец, для других читателей (ОП ясно дал понять, что он это понимает), запомните MEASURE.

Ответ 4

У меня есть много вставок для каждого извлечения минимума. Я думал об использовании Fibonacci-Heaps, но мне сказали, что они теоретически хороши, но страдают от высоких констант и довольно сложно реализовать. А так как вставка находится в O (log (n)), увеличение времени выполнения почти постоянное с большим n. Поэтому я думаю, что все в порядке, чтобы придерживаться набора.

Это звучит для меня как типичное приложение с приоритетной очередью. Вы говорите, что считаете, что используете кучу Фибоначчи, поэтому я предполагаю, что такая реализация очереди приоритетов будет достаточной для ваших нужд (нажатие элементов и извлечение минимального элемента по одному). Прежде чем уйти с пути и навязать оптимизацию одного или двух тактов из этой функции сравнения, я предлагаю вам попробовать несколько готовых реализаций очереди приоритетов. Например, std::priority_queue, boost::d_ary_heap (или boost::d_ary_heap_indirect для изменяемой очереди приоритетов) или любая другая структура кучи бустеров.

Я столкнулся с аналогичной ситуацией раньше, я использовал std::set вместо очереди приоритета в * -подобном алгоритме (а также попытался отсортировать std::vector с std::inplace_merge для вставки) и переключить до std::priority_queue было огромным повышением производительности, а затем переход на boost::d_ary_heap_indirect прошел лишнюю милю. Я рекомендую вам хотя бы попробовать, если вы еще этого не сделали.

Ответ 5

У меня нет ответа как такового - всего пару идей:

• Если вы используете GCC, я бы запускал некоторые тесты с включен параллельный режим
• Вы уверены, что не имеете дело с денормализованными номерами для компонента затрат?