Есть ли способ избежать ветвления / условной логики в этой функции? - PullRequest
Новая
       13

Есть ли способ избежать ветвления / условной логики в этой функции?

2 голосов
/ 24 апреля 2019

В моей программе есть простая функция: 

enum {
   TABLE_INDEX_TYPE_UINT8 = 0,
   TABLE_INDEX_TYPE_UINT16,
   TABLE_INDEX_TYPE_UINT32,
};

// inline method
uint8_t MyTable :: GetTableIndexTypeForTableSize(uint32_t tableSize) const
{
   // Deliberately testing for strictly-less-than-255/65535 here, 
   // because 255 and 65535 are used as special sentinel values
   return (tableSize < 255) ? TABLE_INDEX_TYPE_UINT8 
        : ((tableSize < 65535) ? TABLE_INDEX_TYPE_UINT16 : TABLE_INDEX_TYPE_UINT32);
}

В текущей версии моей программы я вызываю этот метод всякий раз, когда tableSize изменяется, и сохраняю результат в переменной-члене для быстрого повторного использования, и это прекрасно работает.

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

Это также хорошо работает (и позволяет мне уменьшить sizeof(MyTable) на 4 байта, ага), но это приводит к ощутимому (~ 5%) снижению производительности в моем тесте производительности - я считаю, что это потому, что текущая реализация GetTableIndexForTableSize() включает две операции ветвления.

Итак, мой вопрос: есть ли умный способ переопределить вышеуказанную функцию, чтобы она не требовала какого-либо ветвления, и таким образом избежать замедления на 5%? (Я предполагаю, что использование таблицы поиска будет плохая идея, так как я бы заменил задержки из-за неправильного предсказания ветвлений задержками доступа к ОЗУ, что еще больше замедлило бы работу *

1 Ответ

5 голосов
/ 24 апреля 2019

Если вы тщательно выберете значения перечисления, то будет возможно поразрядно или самостоятельно выбрать правильное значение перечисления. Но я сомневаюсь, что это будет намного быстрее. 

#include <cstdint>
enum {
  TABLE_INDEX_TYPE_UINT8 = 0,
  TABLE_INDEX_TYPE_UINT16 = 1,
  TABLE_INDEX_TYPE_UINT32 = 3
};

uint8_t MyTable::GetTableIndexTypeForTableSize(uint32_t tableSize) const
{
  return (tableSize >= 255) | ( (tableSize >= 65535) << 1 );
}
...