Мобильная версияСуществуют ли какие-либо другие (и/или более быстрые) реализации базового 2log?
Приложения
Операции log2(int) и log2(float) очень полезны во многих разные контексты. Вот лишь некоторые из них: алгоритмы сжатия, 3D-движки и машинное обучение. Почти во всех этих контекстах они используются в низкоуровневом коде, который вызывается миллиарды раз... Особенно полезна операция log2(int).
Поскольку я постоянно использую log2, я не хочу описывать здесь конкретное приложение, над которым работаю. То же самое и с тем, что это реальный слив производительности (как показали тесты производительности различных приложений). Для меня важно сделать это как можно быстрее.
Полный исходный код для тестирования всех реализаций добавлен внизу, так что вы можете убедиться в этом сами. p>
И, конечно же... запустите тесты как минимум 3 раза и убедитесь, что счетчики достаточно велики, чтобы достигать нескольких секунд. Также я выполняю операцию добавления, чтобы гарантировать, что весь цикл не будет волшебным образом удален JIT-тером. Итак, давайте приступим к реальной работе.
Тривиальная реализация
Тривиальная реализация реализация 2log в C#:
(int)(Math.Log(x) / Math.Log(2))
Эта реализация тривиальна, но при этом очень медленна. Для этого требуются 2 операции журнала, которые сами по себе уже довольно медленны. Конечно, мы можем оптимизировать это, сделав 1.0/Math.Log(2) константой.
Обратите внимание, что нам нужно немного изменить эту константу, чтобы получить правильные результаты (в результате ошибок с плавающей запятой), или добавить небольшое число, чтобы получить правильные результаты. Я выбрал последнее, но это не имеет особого значения — конечный результат во всех случаях медленный.
Поиск таблицы
Более быстрое решение этой проблемы — использовать таблицу поиска. Хотя вы можете использовать таблицу поиска
любой степени 2, я обычно использую размер таблицы 256 или 64 КБ записей.
Сначала мы создаем таблицу поиска:
lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
lookup = (int)(Math.Log(i) / Math.Log(2));
}
Далее мы реализуем 2log следующим образом:
private static int LogLookup(int i)
{
if (i >= 0x1000000) { return lookup[i >> 24] + 24; }
else if (i >= 0x10000) { return lookup[i >> 16] + 16; }
else if (i >= 0x100) { return lookup[i >> 8] + 8; }
else { return lookup; }
}
Как видите, поиск по таблицам — гораздо более быстрая реализация, но в качестве минуса его нельзя использовать для вычисления log2(float).< /p>
Удаление ветвей
Как мы все знаем, процессоры не очень хорошо справляются с ветвления, поэтому я решил, что поиск по таблицам можно улучшить, удалив ветки. Вместо набора if я ввел вторую таблицу со значениями и битами сдвига, чтобы найти запись в таблице:
nobranch = new int[16] { 0, 0, 8, 8, 16, 16, 16, 16, 24, 24, 24, 24, 24, 24, 24, 24 };
private static int LogDoubleLookup(int i)
{
int n = (i | (i >> 4));
n = (n | (n >> 2));
n = (n | (n >> 1));
n = ((n & 0x1000000) >> 21) | ((n & 0x10000) >> 14) | ((n & 0x100) >> 7) | (n & 1);
int br = nobranch[n];
return lookup[i >> br] + br;
}
Если вы запустите этот тест, вы обнаружите, что он на самом деле медленнее, чем решение if-then-else.
А потом появился Intel 80386
Много лет назад в Intel поняли, что это важная операция, поэтому они внедрили Bit-Scan- Вперед (BSF) в свои процессоры. Другие процессоры имеют аналогичные инструкции. Это, безусловно, самый быстрый способ создания 2log, который я знаю, но, к сожалению, теперь я знаю, как использовать эти замечательные функции из C#... Мне не нравится идея иметь реализацию, которая больше не запускается когда на рынке появится новый планшет или телефон – и я не знаю ни одного кроссплатформенного решения, которое позволило бы мне использовать эту функцию напрямую.
Другое реализации
Как указал l4V (спасибо!), есть еще несколько реализаций, а именно:
- Тривиальный цикл. Я пропустил это, потому что это тривиально: это не очень быстро. Реализовано в TestTrivial.
- Можно использовать 64-битные объединения IEEE/int. Реализовано в таблицах поиска TestFloat
- DeBruijn. Реализовано в TestDeBruijn
- Двоичный поиск. Реализовано в TestBinary
Не считая того, что мне нравится название, таблицы поиска ДеБрюйна работают так же быстро, как и обычные таблицы поиска. , что делает его одним из самых быстрых алгоритмов... все остальные алгоритмы, которые я пробовал, намного медленнее.
Полный тестовый код< /p>
public class Log2Test
{
public static void TestNaive()
{
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += (int)(Math.Log(i) / Math.Log(2.0));
}
sw.Stop();
Console.WriteLine("Result: {0} - naive implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
public static int LogTrivialLoop(int v)
{
int r = 0;
while ((v >>= 1) > 0) // unroll for more speed...
{
r++;
}
return r;
}
public static void TestTrivialLoop()
{
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogTrivialLoop(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - loop implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
public static int LogFloat(int v)
{
Helper h = new Helper() { U1 = v, U2 = 0x43300000 };
h.D -= 4503599627370496.0;
return (h.U2 >> 20) - 0x3FF;
}
public static void TestFloat()
{
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogFloat(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - IEEE float implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
[StructLayout(LayoutKind.Explicit)]
private struct Helper
{
[FieldOffset(0)]
public int U1;
[FieldOffset(4)]
public int U2;
[FieldOffset(0)]
public double D;
}
public static void TestConstant()
{
double c = 1.0 / Math.Log(2.0);
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += (int)(0.00000000001 + Math.Log(i) * c);
}
sw.Stop();
Console.WriteLine("Result: {0} - naive 2 implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static int LogLookup(int i)
{
if (i >= 0x1000000) { return lookup[i >> 24] + 24; }
else if (i >= 0x10000) { return lookup[i >> 16] + 16; }
else if (i >= 0x100) { return lookup[i >> 8] + 8; }
else { return lookup; }
}
public static void TestLookup()
{
lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
lookup = (int)(Math.Log(i) / Math.Log(2));
}
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogLookup(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - table lookup implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static int LogDoubleLookup(int i)
{
int n = (i | (i >> 4));
n = (n | (n >> 2));
n = (n | (n >> 1));
n = ((n & 0x1000000) >> 21) | ((n & 0x10000) >> 14) | ((n & 0x100) >> 7) | (n & 1);
int br = nobranch[n];
return lookup[i >> br] + br;
}
public static void TestDoubleLookup()
{
// Lookup table was already constructed earlier
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogDoubleLookup(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - double table lookup implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static int LogBinary(int v)
{
/* This is the worst implementation ever... - apparently C# is a slow-branching language
int[] b = { 0x2, 0xC, 0xF0, 0xFF00, 0x7FFF0000 };
int[] S = { 1, 2, 4, 8, 16 };
int r = 0; // result of log2(v) will go here
for (int i = 4; i >= 0; i--) // unroll for speed...
{
if ((v & b) != 0)
{
v >>= S;
r |= S;
}
}
return r;
*/
int r = (((v > 0xFFFF)) ? 0x10 : 0);
v >>= r;
int shift = ((v > 0xFF) ? 0x8 : 0);
v >>= shift;
r |= shift;
shift = ((v > 0xF) ? 0x4 : 0);
v >>= shift;
r |= shift;
shift = ((v > 0x3) ? 0x2 : 0);
v >>= shift;
r |= shift;
r |= (v >> 1);
return r;
}
public static void TestBinary()
{
// Lookup table was already constructed earlier
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogBinary(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - binary search implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static readonly int[] MultiplyDeBruijnBitPosition = new int[32]
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
private static int LogDeBruijn(int v)
{
v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return MultiplyDeBruijnBitPosition[(uint)(v * 0x07C4ACDDU) >> 27];
}
public static void TestDeBruijn()
{
// Lookup table was already constructed earlier
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogDeBruijn(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - de Bruijn implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static int[] lookup;
private static readonly int[] nobranch = new int[16] { 0, 0, 8, 8, 16, 16, 16, 16, 24, 24, 24, 24, 24, 24, 24, 24 };
static void Main(string[] args)
{
TestConstant();
TestNaive();
TestDeBruijn();
TestBinary();
TestFloat();
TestTrivialLoop();
TestLookup();
TestDoubleLookup();
Console.ReadLine();
}
}
Подробнее здесь: https://stackoverflow.com/questions/159 ... -log2float
