什么是将bool转换为字节的最快方法？

Question

什么是将bool转换为字节的最快方法？

我想要这个映射:False = 0,True = 1

注意:我不想使用任何if语句或其他条件语句.我不希望CPU停止或猜测下一个语句.

更新: 对于那些想要看到这个问题的人.此示例显示如何从代码中减少两个if语句.

byte A = k > 9 ; //If it was possible (k>9) == 0 || 1
c[i * 2] = A * (k + 0x37) - (A - 1) * (k + 0x30);

Answer 1

使用unsafe代码这种方法非常快.启用优化后,它比条件运算符快约30%.

bool input = true;
byte value = *((byte*)(&input)); // 1

Answer 2

怎么样:

byte x = value ? (byte) 1 : (byte) 0;

如果你在谈论这样做的最有效的方式,有可能是一些技巧,你可以用不安全的代码做......但是这真的是一个瓶颈吗？

编辑:我刚刚意识到条件运算符需要操作数的转换,以使整个表达式成为一个字节.

编辑:看过你的问题,有一个更好的方法来优化它IMO.目前,您将执行任何一种方式都不需要的操作.试试这个:

c[i << 1] = k > 9 ? k + 0x37 : k + 0x30;

要么

c[i << 1] = k + (k > 9 ? 0x37 : 0x30);

(我怀疑哪个没关系.)

您只需要执行比较然后再添加一个 - 而不是在从bool转换为byte 之后的两次加法和两次乘法.

编辑:刚试过这个,由于潜在的分支未命中,这仍然肯定比不安全版本慢......或者它可以更快.在[0,18]范围内选取k的随机值,这种方法需要的时间是不安全代码的两倍.在范围[0,1000)中挑选k的随机值(即,一个分支比另一个分支更频繁地被挑选),这种方法比无条件分支更快.那么你的k价值模式是什么？

这是一些基准代码:

using System;
using System.Diagnostics;

class Test
{
    static void Main()
    {
        Random rng = new Random();
        int[] ks = new int[100000000];
        for (int i = 0; i < ks.Length; i++)
        {
            ks[i] = rng.Next(1000);
        }

        for (int i = 0; i < 3; i++)
        {
            Console.WriteLine("Iteration {0}", i);
            long sum = 0;
            Stopwatch sw = Stopwatch.StartNew();
            for (int j = 0; j < ks.Length; j++)
            {
                int k = ks[j];
                unsafe
                {
                    bool input = k > 9;
                    byte A = *((byte*)(&input)); // 1
                    sum += A * (k + 0x37) - (A - 1) * (k + 0x30);
                }
            }
            sw.Stop();
            Console.WriteLine("Unsafe code: {0}; {1}ms",
                              sum, sw.ElapsedMilliseconds);

            sum = 0;
            sw = Stopwatch.StartNew();
            for (int j = 0; j < ks.Length; j++)
            {
                int k = ks[j];
                sum += k > 9 ? k + 0x37 : k + 0x30;
            }
            sw.Stop();
            Console.WriteLine("Conditional: {0}; {1}ms",
                              sum, sw.ElapsedMilliseconds);
        }
    }
}

请注意,在我的计算机上,这确实给出了相同的值sum,但我不确定它是否保证.我不知道有什么内存表示true是什么保证...所以在一些CLR上你可能会得到错误的答案.

但是,我要指出,在我的笔记本电脑上,这个1亿次操作的循环只需要大约300ms(这包括增加总和和初始阵列访问,这可能需要很长时间,特别是由于缓存未命中). ..你真的确定这是瓶颈吗？你怎么希望获得数据如此快速地散列,这成为问题？

编辑:我刚刚添加了另一个循环来查看"基本案例":

for (int j = 0; j < ks.Length; j++)
{
    int k = ks[j];
    sum += k + 0x30;
}

这花费了大约一半的时间......所以只有一半的时间实际花在特定于哈希的代码上.您是否真的,确定这是以可读性和潜在正确性为代价进行优化的关键代码？

Answer 3

怎么样

byte x = Convert.ToByte(true);

Answer 4

// Warning! Brain-compiled code ahead!
static readonly char[] HexChars = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
public static string ToHex(this byte[] me)
{
    if ( me == null ) return null;
    int ml = me.Length;
    char[] c = new char[2*ml];

    int cp = 0;
    for (int i = 0; i < ml; i++ )
    {
        c[cp++] = HexChars[me[i]&15];
        c[cp++] = HexChars[me[i]>>4];
    }
    return new string(c);
}

Answer 5

以下是比较三个选项的简单基准:

    Int32 j = 0;
    bool b = true;

    for (int n = 0; n < 5; n++) {
        Stopwatch sw1 = new Stopwatch();
        Stopwatch sw2 = new Stopwatch();
        Stopwatch sw3 = new Stopwatch();
        sw1.Start();
        for (int i = 100 * 1000 * 1000; i > 0; i--)
            unsafe { j = *(int*)(&b); }
        sw1.Stop();

        sw2.Start();
        for (int i = 100 * 1000 * 1000; i > 0; i--)
            j = b ? 1 : 0;
        sw2.Stop();

        sw3.Start();
        for (int i = 100 * 1000 * 1000; i > 0; i--)
            j = Convert.ToInt32(b);
        sw3.Stop();
        Trace.WriteLine("sw1: " + sw1.ElapsedMilliseconds +
            "  sw2:" + sw2.ElapsedMilliseconds + ", +" + 100 * (sw2.ElapsedMilliseconds - sw1.ElapsedMilliseconds) / sw1.ElapsedMilliseconds + "% relative to sw1" +
            "  sw3:" + sw3.ElapsedMilliseconds + ", +" + 100 * (sw3.ElapsedMilliseconds - sw1.ElapsedMilliseconds) / sw1.ElapsedMilliseconds + "% relative to sw1"
            );
    }

结果:

sw1: 172  sw2:218, +26% relative to sw1  sw3:213, +23% relative to sw1
sw1: 168  sw2:211, +25% relative to sw1  sw3:211, +25% relative to sw1
sw1: 167  sw2:212, +26% relative to sw1  sw3:208, +24% relative to sw1
sw1: 167  sw2:211, +26% relative to sw1  sw3:209, +25% relative to sw1
sw1: 167  sw2:212, +26% relative to sw1  sw3:210, +25% relative to sw1

结论:

不安全的方法比其他两个快约25%!

"if"版本的相对慢度是由于分支的高成本.如果Microsoft在编译时进行转换,则可以避免转换成本.