Комментарии 57
Насколько этот алгоритм быстрее простого цикла?
Написал код, измеряющий время
include
uint32_t getHighBit_32(uint32_t x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x — (x >> 1);
}
uint32_t getBitCount_32(uint32_t x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
return (x & 0x0000FFFF) + (x >> 16);
}
uint32_t getLog2_32(uint32_t x)
{
return getBitCount_32(getHighBit_32(x) — 1);
}
int getLog2Loop_32(uint32_t x)
{
int result = -1;
while (x)
{
x >>=1;
result++;
}
return result;
}
int main()
{
volatile int iterations = 2000000000;
volatile int value = 0x8;
int volatile temp;
unsigned int start_Log2 = clock(); // начальное время
for (int i = 0; i < iterations; i++)
{
temp = getLog2_32(value);
}
unsigned int end_Log2 = clock(); // начальное время
unsigned int start_Log2Loop = clock(); // начальное время
for (int i = 0; i < iterations; i++)
{
temp = getLog2Loop_32(value);
}
unsigned int end_Log2Loop = clock(); // начальное время
std::cout << "first algo time: " << end_Log2 - start_Log2 << "\n";
std::cout << "second algo time:" << end_Log2Loop - start_Log2Loop << "\n";}
Вывод программы такой:
first algo time: 8179
second algo time:3771
В итоге простой цикл быстрее в 2 раза, но не уверен насчет адекватности измерений
Извините, время редактирования истекло, а сразу не увидел сломавшееся форматирование
#include <iostream>
#include <ctime>
uint32_t getHighBit_32(uint32_t x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x - (x >> 1);
}
uint32_t getBitCount_32(uint32_t x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
return (x & 0x0000FFFF) + (x >> 16);
}
uint32_t getLog2_32(uint32_t x)
{
return getBitCount_32(getHighBit_32(x) - 1);
}
int getLog2Loop_32(uint32_t x)
{
int result = -1;
while (x)
{
x >>=1;
result++;
}
return result;
}
int main()
{
volatile int iterations = 2000000000;
volatile int value = 0x8;
int volatile temp;
unsigned int start_Log2 = clock(); // начальное время
for (int i = 0; i < iterations; i++)
{
temp = getLog2_32(value);
}
unsigned int end_Log2 = clock(); // начальное время
unsigned int start_Log2Loop = clock(); // начальное время
for (int i = 0; i < iterations; i++)
{
temp = getLog2Loop_32(value);
}
unsigned int end_Log2Loop = clock(); // начальное время
std::cout << "first algo time: " << end_Log2 - start_Log2 << "\n";
std::cout << "second algo time:" << end_Log2Loop - start_Log2Loop << "\n";
}итоге простой цикл быстрее в 2 раза на меленьких значениях и в 4 раза медленнее при максимальном значении аргумента
, но не уверен насчет адекватности измерений
int getLog2Loop2_32(uint32_t x)
{
int result = -1;
int y = x >> 16;
if (y > 0)
{
int z = x >> 23;
if (z > 0)
{
result = 22;
x = z;
}
else
{
result = 15;
x = y;
}
}
else
{
int z = x >> 8;
if (z > 0)
{
result = 7;
x = z;
}
}
while (x)
{
x >>=1;
result++;
}
return result;
}
в getHighBit_32 еще 10
это против 64 для цикла. причем для цикла констант меньше. так что вполне может быть. здесь все очень близко в плане количества операций тк O(N) и (O(lg(N)) при N=32 отличаются всего в 6 раз, то большую роль начинают играть константы при O. так что могло получится и то что алгоритм O(N) быстрее, а в некоторых случая O(lg(N)). все зависит от архитектуры и времени исполнения конкретных операций. всегда надо тестировать в таких случаях.
btw для логарифма можно было бы сократить число операций, за счет того, что getBitCount_32 для 32 бит числа не больше 32. это сэекономило бы 4 операции в getHighBit_32, но правда принципиально не изменило бы ничего.
Сложность в O нотации считается для тотальных функций.
Определённые на всем множестве натуральных чисел.
Да, рост будет небольшим, так на то и логарифмическая сложность!
В принципе это тот же цикл, только развернутый вручную. Интересно смог ли ты таким способом превзойти оптимизацию компилятора в сравнении с циклом. Ну и в сравнении со встроенной функцией тоже интересно посмотреть. Без этого это так, детское развлечение)
gcc существует интринсика __builtin_clz, которая считает количество ведущих нулей в числе.
int __builtin_popcount (unsigned int)
int __builtin_popcountl (unsigned long)
int __builtin_popcountll (unsigned long long)И ряд встроенных функций аналогичных lzcnt
int __builtin_ffs (int)
int __builtin_ffsl (long)
int __builtin_ffsll (long long)
int __builtin_clz (unsigned int)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)
int __builtin_ctz (unsigned int)
int __builtin_ctzl (unsigned long)
int __builtin_ctzll (unsigned long long)Для любителей писать код всегда есть IntegerLogDeBruijn
int log2 = 31 ^ __builtin_clz(someval);
с оптимизацией -O2 даёт «голую» BSR — вычисление искомого результата в одну инструкцию.
Примечание: на многих других популярных архитектурах (ARM, PowerPC) всё наоборот — есть CLZ в одну инструкцию, но нет аналога BSR, там выйдет логарифм в две инструкции (что тоже неплохо).
Вам придется применить линейное количество сдвигов битовЭто не так. Количество сдвигов log2 от количества бит, а количество итераций цикла всегда будет равно их количеству. Для 64-битного целого нужно добавить всего один сдвиг и тут преимущество будет гораздо больше чем при 32-х битном целом.
х = 0xff00;
x |= x << 16;
x |= x << 32;
x |= x << 64;
x |= x << 128;
x |= x << 256;
...
Ваш алгоритмв статье указан источник идеи
Боюсь, что Ваш алгоритм вовсе не константный, а линейный.
Полагаю под «константный» в данном случае имеется ввиду, что независимо от значения аргумента, всегда будет выполнено одно и то же количество действий.
Я даже посчитал, там 31 операция. :)
Если брать простой перебор, там на каждый бит делается по 3 операции: сравнение, сдвиг, увеличение счетчика, и чем меньше значение аргумента, тем меньше будет сделано операций.
А если мы возьмем 10,000-битное число? Тогда нам потребуется высчитать 10,000-битные константы. Как Вы видите, ваши "константы" зависят от длины входного числа.
Всё так, но тут начинает работать другой фактор: обычно не находится безумца, который будет хранить 10000-битные числа в области фиксированного размера, не сохраняя размер числа. Всё распространённые библиотеки длинной арифметики хранят число в виде примерно как
typedef ssize_t limb_t;
struct long_number {
size_t nlimbs;
limb_t *body;
};Термин limb — из Gnu MP. Бывают разные оптимизации — например, в mpz-слое nlimbs знаковый, и его знак равен знаку самого числа; в C# BigInteger, если body == null, число хранится в самом nlimbs (важный частный случай короткого числа); и так далее. Но всё это не меняет общего принципа, что длина числа с точностью до лимба уже известна, и алгоритм статьи надо применить только для body[nlimbs-1].
Хотя, возможно, что для относительно небольших чисел этот трюк довольно забавен и даже, думаю, будет эффективен.
Ну, как всегда, мерять надо.
Вообще в оригинале ("Hackersʼs Delight") показано много интересных методов, как вам такой?
Если Вы прочитаете всю ветку, то заметите, что там обсуждали сложность алгоритма в терминах количества бит числа, то есть мы предполагаем, что мы знаем это количество, а не высчитываем его.
Я начал с "всё так", то есть по сути сказанного в пределах заданного контекста у меня не было возражений. Дальше уже шли комментарии по осмысленности такого применения на практике — то есть, контекста рассмотрения.
Если Вы сохраняете положение максимальной единицы, то тут тогда вообще нет о чем говорить.
Она сохраняется обычно с точностью до лимба, но не до конкретного бита. Вот тут уже вступает в силу какой-то алгоритм из обсуждаемых. Какой окажется лучше — линейный, двоичный поиск на сдвигах, данный хитрый на масках — надо смотреть.
И да, с помощью бинарного поиска найти лидирующую единицу для больших чисел будет быстрей, чем данный алгоритм
Вот тут я очень сильно сомневаюсь, но это опять же вопрос контекста. Если мы работаем с теми же 10000-битовыми числами и у нас есть эффективные 10000-битовые операции — в это можно поверить. Но с нынешним железом этого нет, и ткнув в произвольное слово в памяти вы не знаете, есть ли старшие не равные 0 значения. А значит — линейный поиск.
Потому получается, что бинарный поиск такого рода это чисто "сферическое в вакууме" применение. Дальше уже вопрос, хотите ли вы его в этом случае всё равно рассматривать теоретически...
Но автор утверждал, будто он изобрел константный алгоритм, что совсем не соответствует действительности
Автор ничего не утверждал, что он изобрёл — посмотрите внимательно — он явно ссылается на "Hackerʼs Delight". Статья по сути изложение одного метода из книги. Не знаю, какая ценность статьи в этом случае — разве что привлечь почитать книгу. Но я бы тогда лучше пересказал хотя бы два метода, а не один. Может, ему чем-то понравился именно этот метод — не знаю, пусть сам скажет.
> Для начала переведем число x в двоичную запись определенной длины.
Смена системы из десятиричной в двоичную — сам по себе алгоритм O(log(n))
> постоянно делить число на два, пока оно не станет равно нулю
А это грозит бесконечным циклом :)
PS Вообще жалко что эти команды, как и битовые вращения, не вывели в операции языка C/C++ — они были бы более известны, как сдвиги например:) Для битовых сканирований можно было бы применить например унарные << и >>, для вращений бинарные <<< и >>>. Еще из полезных инструкций есть popcnt (количество единиц). А вот битового разворота (RBIT) в x86/x64 так и не завезли, к сожалению.
Ну, одной инструкцией не делается. Посмотреть реализацию можно у Agner Fog. Производительность, естественно, выше, чем у x87.
P.S. А за что минусы?! Сами Intel же говорили ещё в нулевых, что x87 больше не стоит использовать — юзайте SSE. Да и посмотрите на современные высокопроизводительные либы, как много x87 инструкций вы там найдёте?!
Ну высокопроизводительные обычно векторные, а x87 не векторизуется. Но и для обычной плавучки сейчас рекомендуют предпочитать SSE.
Такое вот исключение =)
- SSE и AVX не только про вектора. Ещё в SSE ввели типы данных: single float и single double. Как раз для замены x87 инструкций.
- X87 инструкции сейчас не распаяны на процессоре, они эмулируются. И исполняются как раз на том блоке, на котором исполняются SSE/AVX инструкции.
- Использование x87 инструкций в целом замедляет код, в котором используются SSE/AVX инструкции. (Грубо говоря, смешивание x87 и SSE/AVX инструкций) А используются эти инструкции повсеместно. Например, в Windows и linux ABI float и double передаются через SSE регистры.
- Ну и авторитеты. Intel уже неоднократно заявляли, что x87 больше использовать не нужно. Используйте SSE/AVX. Все хорошие либы также перестали использовать x87. GCC не будет генерировать x87 инструкции, если от него не требовать этого. (В ряде случаев может для long double, но long double совсем другая история)
Так что x87 остаётся для обратной совместимости. Float и double вычисления (даже не векторные) можно легко перенести на SSE/AVX и это будет, как минимум, не медленнее, чем x87, а, почти всегда, быстрее.
А вы меряли?
FYL2X требует на входе уже плавучее число, а для преобразования целого в него процессор уже исполняет операцию, идентичную задаче исходной статьи — чтобы получить порядок и сдвинуть мантиссу в нужную позицию.
Это еще одна операция FILD
Мнэээ… не совсем. Дело не в FILD самой по себе — она как раз, скорее всего, грузит без нормализации. Дело в том, что для получения логарифма FYL2X требует нормализации входного числа. А для него требуется вычисление ожидаемой позиции точки, для чего в свою очередь и вычисляется та самая позиция старшего ненулевого бита.
И вот тут если это действие аппаратно ускорено (ну, начиная с 486, наверняка, да) — то в простых случаях оно может работать и быстрее этого хитрого целочисленного подхода. Но я уверен, что вычисление всех значимых цифр логарифма перекроет этот выигрыш на десятки тактов. Ну да, померять надо. Соберу вдохновения — померяю.
Хм, выпрямил руки и прогнал тест. i3-4170, gcc 8 (или 7, без разницы), 64-битка.
Код.
Типовые результаты по времени:
With FYL2X: 23766
With builtin CLZ: 1882
With habr-522788: 6739это в пикосекундах получается на итерацию (то есть 24 нс с FYL2X) и с разрешением LZCNT для x86; без него получается ~2400 во второй строке. Третья строка — алгоритм из статьи, скопировал ничего не меняя.
Ну, я подозреваю, для FYL2X используется такой же аппаратный ускоритель на приоритетном энкодере, как и для BSR и LZCNT. Иначе бы не были такие хорошие времена.
Про AVX с реальной векторностью сейчас точно облом думать, но она вроде исходно и не предполагалась.
700 тактов, названные в статье по вашей ссылке, скорее всего, цифра от чего-то сильно более древнего (часом не оригинальный 8087?) Тут у меня на весь цикл 96 тактов, значит, сама команда сильно меньше занимает.
PS: Вообще вся та статья какая-то кривая. Где он на int(2+3000000000.0f) нашёл денормализованные??
builtin CLZ превращается просто в BSR или LZCNT(vplzcntd для O3) в зависимости от архитектуры.
А вот в какой фарш при -O3 превращается алгоритм из статьи, страшно смотреть. Но и ускоряется вдвое относительно O2
N=32 бита
2^5=32 в функции, например,
uint32_t getHighBit_32(uint32_t x)
5 строчек.
для 64 бит будет 6 срочек.
то что развернули цикл сложность не уменьшило
unsigned int mylog2(unsigned int x) {
unsigned int e;
*(float*)&e = (float)x;
e = (e >> 23) — 0x7F;
return e;
}
Может оказаться быстрее на процессоре с очень хорошей поддержкой плавучки, но без энкодера для CLZ-операции (x86: BSR, LZCNT). Помнится, 486-й был где-то таким. Но сейчас таких мало.
Ну и вы нарушили правила алиасинга, может быть чревато боком (tm).
Тоже решал такую задачку, но пошёл по другому пути.
Суть метода: преобразовать целое число в double и уже из двоичного представления double извлечь степень двойки.
#include <type_traits>
/// Integral part of log2(n), n - integral (interpreted as unsigned)
template <class _Int, class = std::enable_if_t<std::is_integral<_Int>::value>>
constexpr int ilog2(_Int n) noexcept
{
struct Bits {
constexpr auto bias() const noexcept { return 1023; }
uint64_t m: 52;
uint64_t e: 11;
uint64_t s: 1;
};
union FRep {
constexpr FRep(double f) noexcept : v(f) {}
constexpr int ilog2() const noexcept
{ return b.e >= b.bias() ? int(b.e) - b.bias() : -1; }
double v;
Bits b;
};
return FRep(double(uint64_t(n))).ilog2();
}
/// Most significant bit // Старший значащий бит
/// @return 2^i or 0, i = index of the MSB;
template <class _Int, class = std::enable_if_t<std::is_integral<_Int>::value>>
constexpr auto msb(_Int n) noexcept
{
using Unsigned = std::make_unsigned_t<_Int>;
return !n ? 0 : n == _Int(-1) ? Unsigned(-1) ^ (Unsigned(-1) >> 1)
: Unsigned(1) << ilog2(n);
}
Быстрый целочисленный логарифм по основанию 2