Вопроса являетсябыстрого внедрение log2 (INT) и log2 (поплавок)
Существует ли какая-либо другая (и/или быстрее) реализация основного 2log?
Приложения
log2 (INT) и log2 операции (с плавающей точкой), очень полезны во многих различных контекстах. Чтобы назвать несколько: алгоритмы сжатия, 3d-двигатели и машинное обучение. Почти во всех этих контекстах они используются в низкоуровневом коде, который называется миллиардами раз ... Особенно полезно использовать операцию log2 (int).
Поскольку я все время использую log2, я не хочу давать конкретное приложение, над которым я работаю здесь. То же самое происходит и в том, что это реальный осушитель производительности (как показывают тесты производительности различных приложений). Для меня это ключ к тому, чтобы сделать это как можно быстрее.
Полный исходный код для проверки всех реализаций добавлен снизу, поэтому вы можете сами убедиться.
И, конечно же, запустите ваши тесты не менее 3 раз и убедитесь, что счетчики достаточно большие, чтобы нанести несколько секунд. Также я делаю операцию «добавить», чтобы весь цикл не был магически удален JIT'ter. Давайте начнем с настоящей работы.
Trivial реализация
тривиальная реализация 2log в C# является:
(int)(Math.Log(x)/Math.Log(2))
Этой реализация тривиальна, но очень медленно. Для этого требуется 2 Log-операции, которые уже сами по себе довольно медленные. Конечно, мы можем оптимизировать это, сделав константу 1.0/Math.Log(2).
Обратите внимание, что нам нужно немного изменить эту константу, чтобы получить правильные результаты (в результате ошибок с плавающей запятой) или добавить небольшое число, чтобы получить правильные результаты. Я выбрал последнее, но это не имеет большого значения - конечный результат медленный во всех случаях.
Таблица поиска
Более быстрое решение этого заключается в том, чтобы использовать таблицу поиска. Хотя вы можете использовать таблицу поиска любой мощностью 2, я обычно использую таблицу размером 256 или 64 тыс. Записей.
Сначала мы создаем таблицу поиска:
lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
lookup[i] = (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[i]; }
}
Как вы можете видеть, табличный поиск являются намного быстрее реализациями - но как con, он не может использоваться для вычисления log2(float).
удаление Отделения
Как мы все знаем, процессоры не очень хорошо ветвящийся, поэтому я решил, что табличный поиск может быть улучшен путем удаления ветвей.Вместо сгустков Иф х я введенными вторую таблицу со значениями и сдвигают биты вокруг, чтобы найти запись в таблице:
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;
}
Если запустить этот тест, вы увидите, что это на самом деле медленнее, чем если -те-другое решение.
А потом был Intel 80386
Intel понял года назад, что это важная операция, поэтому они реализовали Bit-Scan-Forward (BSF) в свои процессоры. Другие процессоры имеют схожие инструкции. Это, безусловно, самый быстрый способ сделать 2log, о котором я знаю, но, к сожалению, теперь я знаю, как использовать эти прекрасные функции из C# ... Мне не нравится идея иметь реализацию, которая больше не запускается когда на рынок выходит новый планшет или телефон - и я не знаю какого-либо кросс-платформенного решения, которое позволяет мне напрямую использовать эту функцию.
Другие реализации
Как l4V указал (спасибо!) Есть несколько других реализаций, в частности:
- Trivial петля. Я опустил это, потому что это тривиально, это не очень быстро. Реализовано в
TestTrivial. - 64-разрядное соединение IEEE/int, которое может использоваться. Реализовано в
TestFloat - Таблицы поиска DeBruijn. Реализовано в
TestDeBruijn - Двоичный поиск. Реализовано в
TestBinary
Apart, что мне нравится имя, таблицы подстановки DeBruijn так же быстро, как и обычные справочные таблицы, что делает его одним из самых быстрых алгоритмов здесь ... все другие алгоритмы, которые я пробовал являются гораздо медленнее.
Полный тестовый код
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[i]; }
}
public static void TestLookup()
{
lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
lookup[i] = (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[i]) != 0)
{
v >>= S[i];
r |= S[i];
}
}
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();
}
}
http://graphics.stanford.edu/~seander /bithacks.html#IntegerLogObvious – I4V
@ I4V, это отличный ответ. – Ben
@ l4V ах да, это те из книги Хакеры Восторг. Я проверю оставшиеся и добавлю их в код. Давайте посмотрим, как быстро они на C# ... Я был удивлен более одного раза ... – atlaste