Самый быстрый целочисленный тип для распространенных архитектур

Question

В заголовке stdint.h отсутствуют символы int_fastest_t и uint_fastest_t, соответствующие типам {,u}int_fastX_t. Для случаев, когда ширина целочисленного типа не имеет значения, как выбрать целочисленный тип, который позволяет обрабатывать наибольшее количество битов с наименьшим ухудшением производительности? Например, если кто-то искал первый установленный бит в буфере, используя наивный подход, такой цикл можно рассмотреть следующим образом:

// return the bit offset of the first 1 bit
size_t find_first_bit_set(void const *const buf)
{
    uint_fastest_t const *p = buf; // use the fastest type for comparison to zero
    for (; *p == 0; ++p); // inc p while no bits are set
    // return offset of first bit set
    return (p - buf) * sizeof(*p) * CHAR_BIT + ffsX(*p) - 1;
}

Естественно, использование char приведет к большему количеству операций, чем int. Но long long может привести к более дорогим операциям, чем использование int в 32-битной системе и т. Д.

Мое текущее предположение относится к основным архитектурам, использование long - самая безопасная ставка: 32-битная в 32-битных системах и 64-битная в 64-битных.

Answer 1

int_fast8_t всегда самый быстрый целочисленный тип в правильной реализации. Никогда не может быть целочисленных типов, меньших 8 бит (поскольку требуется CHAR_BIT>=8), а поскольку int_fast8_t является самым быстрым целочисленным типом, по крайней мере, с 8 битами, таким образом, это самый быстрый целочисленный тип, точка.

Answer 2

Теоретически, int - лучшая ставка.Он должен соответствовать собственному размеру регистра ЦП и, таким образом, быть «оптимальным» в том смысле, о котором вы спрашиваете.

Однако вы можете все же обнаружить, что int-64 или int-128 быстрее на некоторых процессорах, чем int-32, потому что, хотя они больше, чем размер регистра, они уменьшат количество итераций вашего цикла и, следовательно, могут работать более эффективно, минимизируя издержки цикла и / или принимаяПреимущество DMA в более быстрой загрузке / хранении данных.

(Например, на процессорах ARM-2 потребовалось 4 цикла памяти для загрузки одного 32-разрядного регистра, но только 5 циклов для загрузки двух последовательно, и 7циклы для последовательной загрузки 4. Процедура, которую вы предлагаете выше, будет оптимизирована для использования максимально возможного количества регистров (обычно от 8 до 10), и, следовательно, может выполняться в 3 или 4 раза быстрее при использовании нескольких регистров на одну итерацию цикла)

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

Answer 3

Я не уверен, что действительно понимаю вопрос, но почему вы просто не используете int ?Цитируя мой (бесплатная черновик, копия неправильного, то есть C ++) стандарта: «Простые целые имеют естественный размер, предложенный архитектурой среды выполнения».Целочисленный тип для определенной операции, он будет отличаться в зависимости от того, какая операция это.Попытка найти первый бит в большом буфере данных, или найти число в последовательности целых чисел, или переместить их, вполне может иметь совершенно разные оптимальные типы.Для чего бы это ни стоило, я сделал небольшой тест.В моей конкретной системе (Intel i7 920 с Linux, gcc -O3) получается, что длинные целые числа (64 бита) в этом конкретном примере работают немного быстрее, чем обычные целые числа (32 бита).Я бы догадался об обратном.

Answer 4

Если вы хотите быть уверены, что у вас самая быстрая реализация, почему бы не сравнить каждый из них в системах, на которых вы ожидаете работать, вместо того, чтобы пытаться угадать?

Answer 5

Ответ int сам. По крайней мере в C ++, где 3.9.1 / 2 стандарта гласит:

Обычные int с имеют натуральный размер предложено архитектурой среда исполнения

Я ожидаю, что то же самое верно для C, хотя у меня нет документов по стандартам.

Answer 6

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

Но ничего не можетдокажите это, чем проверить произведенный ассемблер и сделать тесты.

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

size_t и ptrdiff_tявляются единственными определениями типов, которые являются нормативными в C99 и для которых можно разумно предположить, что они связаны с архитектурой.

Существует 5 различных рангов для стандартных целочисленных типов (char, short, int, long, long long).Все силы идут на то, чтобы иметь типы ширины 8, 16, 32, 64 и в ближайшем будущем 128. Как следствие, int будет зависать на 32 битах.Его определение не будет иметь ничего общего с эффективностью на платформе, но будет ограничено этим требованием ширины.

Answer 7

Для всех существующих основных архитектур long - самый быстрый тип в настоящее время для пропускной способности петли.

Answer 8

Невозможно ответить на этот вопрос, так как вопрос неполный.В качестве аналогии рассмотрим вопрос:

Какой самый быстрый автомобиль

A Bugatti Veyron ?Конечно, быстро, но бесполезно для поездки из Лондона в Нью-Йорк.

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

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

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

Answer 9

Если вы компилируете с помощью gcc, я бы порекомендовал использовать __ builtin_ffs () для нахождения первого установленного бита:

Встроенная функция: int __builtin_ffs (без знака int x) Возвращает один плюс индекс младшего значащего 1-бита x или, если x равен нулю, возвращает ноль.

Это будет скомпилировано в (часто одну) нативную инструкцию по сборке.