Правильно ли использовать size_t для подсчета в операции битового сдвига?

Question

Этот небольшой, казалось бы, незначительный вопрос возник у меня недавно, но, немного погуглив, я не смог найти даже мнения по этому вопросу. Упоминаются только циклы и размеры объектов.

Я знаю людей, которым нравятся примеры, поэтому вот тот, который в первую очередь вызывает вопрос:

uint64_t deltaSwap( const uint64_t b, const size_t delta, uint64_t mask )
{
    return b ^ mask ^ ( mask &=  b ^ b >> delta ) << delta;
}

Я пытался слишком оптимизировать это на некоторое время, прекрасно зная, что это не способ написать правильный код, хотя он дал мне лучший результат до сих пор, по крайней мере, с G CC, а потом это пришло мне в голову. Если вы действительно хотите быть педанти c, разве дельта не должна иметь тип size_t?

Я никогда не понимал, когда использовать size_t, поэтому я никогда не делал, но если бы я Разве это не было бы правильным использованием?

Обновление: вот краткое объяснение того, что он делает, хотя не так, как это делает, поскольку я не совсем уверен, как это объяснить:

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

Цель кода - поменять местами два или более бит, например, если вы поменяете sh на первый и последний бит, это может быть сделано так:

deltaSwap(b, 63, 0x0000000000000001);

или если вы хотите sh изменить порядок битов:

deltaSwap(b, 32, 0x00000000ffffffff);
deltaSwap(b, 16, 0x0000ffff0000ffff);
deltaSwap(b,  8, 0x00ff00ff00ff00ff);
deltaSwap(b,  4, 0x0f0f0f0f0f0f0f0f);
deltaSwap(b,  2, 0x3333333333333333);
deltaSwap(b,  1, 0x5555555555555555);

хотя для этой конкретной задачи дельта-свопы вероятно, не самый лучший способ go.

Обновление 2: просто для завершения, это я Это самый правильный лайнер, который я могу себе представить (пока не получил мой ответ), и компилятор, очевидно, оптимизирует его идеально.

uint64_t deltaSwap( const uint64_t b, const uint_fast8_t delta, const uint64_t mask )
{
    return b ^ ( mask & ( b ^ b >> delta ) ) ^ ( mask & ( b ^ b >> delta ) ) << delta;
}

Я бы сократил имя переменной, чтобы она соответствовала всем 80 персонаж с навязанным моим ocd мозгом (и, видимо, этим сайтом тоже), но для всех вас я готов пострадать.

Answer 1

Если вы действительно хотите быть педанти c, разве delta не должно быть типа size_t?

Нет, если вы действительно хотите быть педанти c, delta должен быть просто целым типом без знака, способным содержать не менее диапазона значений от 0 до sizeof(uint64_t) * CHAR_BIT. В вашем случае это [0, 63]. Нет необходимости в том, чтобы это было size_t.

Я никогда не понимал, когда использовать size_t, поэтому я никогда не понимал, но если бы это было так, было бы неправильно использование?

С точки зрения правильности кода это нормально. С точки зрения оптимизации это не имеет особого смысла. size_t используется для хранения размера, потому что это тип, который может поддерживать максимально возможный размер объекта. Это, безусловно, , а не , гарантированно будет быстрее, чем обычный unsigned или любой другой целочисленный тип без знака (см. Нижнюю часть ответа для этого).

Еще одна важная вещь, на которую следует обратить внимание: :

 b ^ mask ^ ( mask &=  b ^ b >> delta ) << delta

Is неопределенное поведение в соответствии со стандартом C, поскольку вы используете значение переменной, а также применяете к ней побочный эффект в том же выражении (см. пункт 6.5, пункт 2, стр. 76 здесь ).

Правильный способ сделать то, что вы хотите:

mask &= b ^ (b >> delta);
return b ^ (mask ^ (mask << delta));

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

---

Теперь вернемся к реальной причине, по которой вы задаете этот вопрос: оптимизации.

Правильный способ оптимизировать ваш код - позволить компилятору выбрать оптимальный размер нужной вам переменной. Для этой цели вам нужен только один байт, и вы можете использовать uint_fast8_t из stdint.h, который является самым быстрым (определяется реализацией) целочисленным типом без знака с шириной не менее 8 бит. Компилятор выберет самую быструю ширину для своей цели.

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

uint64_t deltaSwap( const uint64_t b, const uint_fast8_t delta, uint64_t mask )
{
    mask &= b ^ (b >> delta);
    return b ^ (mask ^ (mask << delta));
}

В зависимости от того, что вы делаете, это может также имеет смысл объявить функцию как inline __attribute__ ((always_inline)), если G CC еще не встроил код для вас, хотя компилятор обычно лучше вычисляет, когда вставлять код, а когда нет. Скорее всего, ваша функция уже встроена.

Еще одна важная вещь: использование правильных флагов оптимизации часто имеет большее значение, чем ручная настройка кода. Например, для приведенного выше кода вы можете скомпилировать с -Ofast -march=native и, возможно, даже с другими флагами в зависимости от того, где вы используете функцию (например, -ftree-vectorize, если используется в al oop).

Кроме вышеперечисленного: тестирование производительности, переключение на сборку с ручной настройкой с помощью оператора asm() и просмотр окружающего кода - это единственные способы дальнейшей оптимизации приведенного выше, если предположить, что формула уже упрощена до своего ядра.

Answer 2

size_t - это целочисленный тип, который гарантированно сможет хранить выходные данные любой операции sizeof(). Это имеет несколько последствий: ни один блок когерентной памяти не может иметь больше байтов, чем size_t может представлять как число. Это также означает, что ни один массив не может иметь больше элементов, чем size_t может представлять в виде счетчика. Также ни одна строка C не может содержать больше символов, чем size_t может представлять длину.

Что касается времени использования size_t, вы всегда должны использовать его для хранения размеров памяти, количества массивов, индексов массивов. и длины строк, так как только это приведет к действительно переносимому коду C. Использование int, long или uintX_t для этой цели может работать на некоторых платформах, но может не работать на других платформах. Обратите внимание, что даже malloc ожидает аргумент типа size_t, printf также поддерживает его, используя %zu, и большинство строковых операций в C используют его как ввод / вывод для длин строк.

Что касается смешивания целых чисел различной ширины: только char, short, int, long и long long (а также их беззнаковые аналоги) являются реальными собственными целыми числами в C. Другие целочисленные типы являются просто псевдонимами одного из этих собственных типов, добавленных с более поздними стандартами C. При смешивании разных типов в одной операции меньший тип переводится в более крупный, если только оба типа не меньше int, и в этом случае они оба переводятся в int, так как C выполняет все операции на int или более крупные типы, но не более мелкие:

char a = 1;
char b = 2;
char c = a + b;
// Last line is in fact: char c = (char)( (int)a + (int)b );

long l = 20;
long m = m * b;
// Last line is in fact: long m = l * (long)b;

Так что, если вы смешаете uint64_t и size_t, то либо оба станут тем, что тип uint64_t является нативным типом, либо они оба станут какой бы тип size_t не был нативным, какой бы тип не был больше, если только оба не меньше, чем int, в этом случае оба становятся int.

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

Answer 3

Из ISO / IEC 9899: 1999 сечение 6.5.7

Если значение правого операнда отрицательно или больше или равно ширине повышенного левого операнда, поведение не определено.

Это означает, что в вашем случае требования для delta являются

0 <= delta < number of bits in the left operand