Как эффективно проверять битмаску?

Question

Я использую inotify и хочу эффективно проверять событие с сообщенной битовой маской (см. inotify man page).

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

(bitmask & mask) == mask 

для каждый маску уже сверхэффективной?

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

Answer 1

Если вы хотите проверить против один битовой маски, затем

if ((value & mask) == mask) 

даст вам точное совпадение («все биты в маске»), и

if ((value & mask) != 0) 

будет поставлять Свободное совпадение («любой бит в маске»). Компилятор дополнительно оптимизирует проверку против нуля.

Если у вас несколько битмаск, вы хотите извлечь максимальную информацию из каждой проверки во временной области (крайний случай: если все значения, которые вы получаете, равны , конечно, нечетные, вам не нужно проверять 0-й бит Это всегда будет 1). В идеале вам нужно идентифицировать первый раунд бит, который имеет 50% вероятность быть 1.

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

if ((value & SPECIAL_MASK_1) == SPECIAL_MASK_1) { 
    if ((value & SPECIAL_MASK_2) == SPECIAL_MASK_2) { 
     ... 
    } else { 
     ... 
    } 
} else { 
    if ((value & SPECIAL_MASK_3) == SPECIAL_MASK_3) { 
     ... 
    } else { 
     ... 
    } 
} 

Если у вас, скажем, 32 государства, каждый отображенные на один бит, и только один бит может быть установлен при каждом вызове - самый простой случай - «последовательный» последовательность была бы одна из 32 проверок, один за другая

if ((mask & 0x00000001) == 0x00000001) { 
} else if ((mask & 0x00000002) == 0x00000002) { 
} 
... 

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

Таким образом, вы получите только одну проверку на 33% времени; то, возможно, две проверки еще 20% времени, ..., а в конце в среднем вы можете запустить, скажем, семь чеков.

Другая возможность

if (mask & 0x0000FFFF) { 
    // The bit is in the LSW 
    if (mask & 0x0000FF00) { 
     // MSB of LSW 
     if (mask & 0x0000F000) { 
      ... 
     } else { 
     } 
    } 
} else { 
} 

Это будет работать каждый раз, точно пять проверок. Однако в этот момент соображения о архитектуре ЦП, прогнозировании ветвления и т. Д., Вероятно, превзойдут любую оптимизацию, которую вы могли бы попытаться сделать.

Если у вас нет сложной настройки очень или некоторые другие ограничения (например, встроенное устройство), я боюсь, что стоимость анализа, создания, отладки и поддержания «оптимизировано» против «грубой силы» проверки, скорее всего, более чем сбалансировать любое преимущество, которое вы могли бы выжать из первого.

Answer 2

Если необходимо проверить каждую битовую маску, нет другого способа, кроме как проверить явно. Однако, если известны определенные бит-маски, могут быть выполнены побитовые проверки, что фактически приводит к уменьшению половины возможных бит-масок на каждом шаге.

Answer 3

Для проверки нескольких битов маски я использую цикл. Если вы используете достойный компилятор, он должен оптимизировать код довольно прилично. Если у вас нет существенных проблем с производительностью, это не стоит оптимизировать вручную, так как все процессоры, которые я знаю, реализуют логический бит-тест или бит-мудрую операцию И в одной команде. Таким образом, у вас есть две инструкции: логическая инструкция и команда ветви-состояния процессора для каждого бита. Не огромное количество кода для запуска и, насколько я знаю, невозможно победить. (Обратите внимание, что поскольку mask 32 бита, если вы работаете на 16 битном ядерный процессор, там будет несколько больше инструкций, чтобы проверить обе половинки.)

void processEvents(uint32_t events) 
{ 
    uint32_t bitToTest; 
    // Check each bit in turn 
    for(bitToTest = 1; bitToTest < events; bitToTest << 1) 
    { 
     // Check which bit is set. If none then the default case is used. 
     switch(bitToTest & events) 
     { 
      case IN_ACCESS: 
       // Handle the IN_ACCESS event flag here. 
       break; 
      case IN_ATTRIB: 
       // Handle the IN_ATTRIB event flag here. 
       break; 
      // Et cetera... 
      default: 
       // No flag was set, so do nothing. 
       break; 
     } 
    } 
} 

Answer 4

Если есть только один набор бит и если ваш код не должен быть портативным, вы можете использовать встроенные функции, которые дают вам позицию установленного бита, а затем используют результат в инструкции switch. Для gcc, который будет, например, be

__builtin_ffs