Câu hỏi đặt ra làthực hiện nhanh nhất của log2 (int) và log2 (float)
Có bất kỳ khác (và/hoặc nhanh hơn) triển khai của một 2log cơ bản?
Applications
Các log2 (int) và (float) hoạt động log2 là rất hữu ích trong rất nhiều hoàn cảnh khác nhau. Để đặt tên một vài: thuật toán nén, động cơ 3d và học máy. Trong hầu hết các bối cảnh này, chúng được sử dụng trong mã mức thấp được gọi là hàng tỉ lần ... Đặc biệt hoạt động log2 (int) rất hữu ích.
Bởi vì tôi thấy mình sử dụng log2 mọi lúc, tôi không muốn cung cấp cho một ứng dụng cụ thể mà tôi đang làm việc ở đây. Điều tương tự là thực tế rằng đây là một drainer hiệu suất thực (như được hiển thị bởi các bài kiểm tra hiệu suất của các ứng dụng khác nhau). Đối với tôi đó là chìa khóa để có được điều này càng nhanh càng tốt.
Mã nguồn hoàn chỉnh để kiểm tra tất cả các triển khai được thêm ở dưới cùng, vì vậy bạn có thể tự mình xem.
Và tất nhiên ... chạy thử nghiệm của bạn ít nhất 3 lần và đảm bảo rằng các quầy là đủ lớn để đạt nhiều giây. Ngoài ra tôi thực hiện thao tác 'thêm' để đảm bảo toàn bộ vòng lặp không được JIT'ter loại bỏ một cách kỳ diệu. Vì vậy, chúng ta hãy bắt đầu với công việc thực sự.
thực hiện Trivial
Việc thực hiện tầm thường của một 2log trong C# là:
(int)(Math.Log(x)/Math.Log(2))
thực hiện này là tầm thường, nhưng cũng rất chậm. Nó đòi hỏi 2 hoạt động Log, đó là bản thân nó khá chậm. Tất nhiên, chúng ta có thể tối ưu hóa điều này bằng cách làm cho 1.0/Math.Log(2) một hằng số.
Lưu ý rằng chúng ta cần sửa đổi hằng số này một chút để có được kết quả đúng (do lỗi dấu phẩy động) hoặc thêm một số nhỏ để có kết quả chính xác. Tôi đã chọn thứ hai, nhưng nó không thực sự quan trọng - kết quả cuối cùng là chậm trong mọi trường hợp.
Bảng tra cứu
Một giải pháp nhanh hơn cho điều này là sử dụng một bảng tra cứu. Trong khi bạn có thể sử dụng bảng tra cứu của bất kỳ sức mạnh nào của 2, tôi thường sử dụng kích thước bảng là 256 hoặc 64K mục.
Đầu tiên chúng ta tạo ra các bảng tra cứu:
lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
lookup[i] = (int)(Math.Log(i)/Math.Log(2));
}
Tiếp theo, chúng ta thực hiện các 2log như sau:
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]; }
}
Như bạn thấy, tra cứu bảng là một nhiều, thực hiện nhanh hơn nhiều - nhưng như một con nó không thể được sử dụng để tính toán log2(float).
loại bỏ chi nhánh
Như chúng ta đều biết, bộ vi xử lý không phải là rất tốt ở phân nhánh, vì vậy tôi figured rằng tra cứu bảng có thể được cải thiện bằng cách loại bỏ các chi nhánh.Thay vì các chùm nếu của tôi giới thiệu một bảng thứ hai với các giá trị và dịch chuyển bit xung quanh để tìm mục trong bảng:
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;
}
Nếu bạn chạy thử nghiệm này, bạn sẽ thấy rằng nó thực sự là chậm hơn so với nếu - giải pháp khác.
Và sau đó là Intel 80386
Intel hiểu năm trước rằng đây là một hoạt động quan trọng, vì vậy họ thực hiện Bit-Scan-Forward (BSF) vào bộ vi xử lý của họ. Các bộ vi xử lý khác có hướng dẫn tương tự. Đây là cách nhanh nhất để làm một 2log mà tôi biết - nhưng tiếc là tôi biết bây giờ cách để sử dụng các chức năng tốt đẹp từ C# ... Tôi không thích ý tưởng có một thực hiện mà không chạy nữa khi một máy tính bảng hoặc điện thoại mới tung ra thị trường - và tôi không biết bất kỳ giải pháp đa nền tảng nào cho phép tôi sử dụng chức năng này trực tiếp.
triển khai khác
Như l4V chỉ ra (nhờ!) Có một vài hiện thực khác, cụ thể:
- Trivial vòng lặp. Tôi bỏ qua điều này vì nó tầm thường không thực sự nhanh. Được triển khai trong
TestTrivial. - Công nghệ IEEE/int của 64 bit có thể được sử dụng. Triển khai trong
TestFloat - Bảng tra cứu DeBruijn. Được triển khai trong
TestDeBruijn - Tìm kiếm nhị phân. Được triển khai trong
TestBinary
Ngoài ra tôi thích tên, bảng tra cứu DeBruijn nhanh như bảng tra cứu thông thường, làm cho nó trở thành một trong những thuật toán nhanh nhất ở đây ... tất cả các thuật toán khác mà tôi đã thử chậm hơn nhiều.
Toàn bộ mã kiểm tra
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, đó là một câu trả lời tuyệt vời. – Ben
@ l4V ah vâng, đây là những cái từ cuốn sách Hacker Delight. Tôi sẽ kiểm tra những cái còn lại và thêm chúng vào mã. Hãy xem nhanh như thế nào trong C# ... Tôi đã ngạc nhiên nhiều lần ... – atlaste