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

В заголовке 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-разрядных системах.

Ответы

Ответ 1

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

Ответ 2

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

Ответ 3

Я не уверен, что я действительно понимаю вопрос, но почему бы вам просто не использовать int? Цитата из моей (свободной черновиковой копии неправильного, например, С++) стандарта, "Plain ints имеют естественный размер, предложенный архитектурой среды исполнения".

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

EDIT:

Что бы это ни стоило, я сделал небольшой тест. На моей конкретной системе (Intel i7 920 с Linux, gcc-O3) получается, что длинные ints (64 бита) в этом конкретном примере довольно немного быстрее, чем простые ints (32 бита). Я бы догадался об обратном.

Ответ 4

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

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

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

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

Ответ 5

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

Ответ 6

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

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

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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

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

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

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

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

Ответ 9

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

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

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