代码之家 › 专栏 › 技术社区 › Brian

更快的字符串获取哈希代码(例如,使用多核或GPU)

optimization .net c#

Brian · 技术社区 · 15 年前

根据 http://www.codeguru.com/forum/showthread.php?t=463663 C·C getHashCode 3.5中的功能实现如下:

public override unsafe int GetHashCode()
{
    fixed (char* str = ((char*) this))
    {
        char* chPtr = str;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*) chPtr;
        for (int i = this.Length; i > 0; i -= 4)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            if (i <= 2)
            {
                break;
            }
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
        }
        return (num + (num2 * 0x5d588b65));
    }
}

我很好奇是否有人能想出一个返回相同结果但速度更快的函数。可以增加主应用程序的总体启动和资源开销。需要一次性初始化(每个应用程序执行,而不是每个调用或每个字符串)是可以的。

请注意,与微软不同的是,“这样做会使其他事情变慢,而且成本也会使这种方法变得愚蠢!”可以忽略不计,所以即使假设微软是完美的,它也有可能被“愚蠢”的行为打败。

这纯粹是出于我自己的好奇心,不会在真正的代码中使用。

我想到的想法示例:

使用多个核心(独立计算num2和num)
使用GPU

6 回复 | 直到 14 年前

elder_george 15 年前

线程和GPU无疑会带来比可能的性能提升更大的开销。可以证明的方法是使用SIMD指令集,如SSE。然而,它将需要测试这个部分指令集是否可用,这可能需要花费。它也将只对长串带来提升。

如果你想尝试一下,可以考虑测试 Mono support for SIMD 在潜入C或组件之前。读 here 关于发展的可能性和问题。

Peter Mortensen icecrime 15 年前

使函数运行更快的一种方法是考虑特殊情况。具有可变大小输入的函数具有基于大小的特殊情况。

只有当平行的成本小于增益,对于这种计算,很可能为了克服成本,绳子必须相当大把平行的线分叉。但实现这一点并不困难; 基本上你需要做一个测试。长度超过了一个经验值。已确定阈值,然后分叉多个线程进行计算散列子字符串,最后一步将子字符串组成最后一个哈希。实现留给了读者。

现代处理器也有SIMD指令,可以处理在一条指令中为32(或64)字节。这会让你将字符串以32(16位字符)块的形式处理为1-2 每个块的SIMD指令;然后将64字节的结果折叠为最后是一个哈希代码。这可能非常快对于任何合理大小的字符串。这一点的实施从C更难,因为人们不期望虚拟机提供对SIMD指令的方便(或便携式)访问你需要的。实现也留给了读者。编辑:另一个答案表明单声道系统确实提供了 SIMD指令访问。

尽管如此,所展示的特定实现还是相当愚蠢的。关键的观察是循环在每次迭代中检查限制两次。我们可以通过提前检查结束条件案例来解决这个问题, 并执行一个循环来执行正确的迭代次数。一个人可以用 Duffs device 跳入n个迭代的展开循环。这样就摆脱了 n-1迭代的循环限制检查开销。那次修改这将是非常容易的,而且肯定值得努力实施。

编辑:你也可以结合simd的想法和循环展开的想法,使处理许多块8/16字符在几个simd指令。

对于无法跳入循环的语言,可以执行等效于达夫的设备,只需剥离最初的案例。一枪如何使用循环剥离方法重新编码原始代码如下:

    public override unsafe int GetHashCode()
    {
        fixed (char* str = ((char*) this))
        {
            const int N=3; // a power of two controlling number of loop iterations
            char* chPtr = str;
            int num = 0x15051505;
            int num2 = num;
            int* numPtr = (int*) chPtr;
            count = this.length;
            unrolled_iterations = count >> (N+1); // could be 0 and that's OK
            for (int i = unrolled_iterations; i > 0; i--)
            {
               // repeat 2**N times
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[4];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[5]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[6];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[7]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[8];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[9]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[10];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[11]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[12];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[13]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[14];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[15]; }
               numPtr += 16;
            }
            if (count & ((1<<N)-1))
            {
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[4];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[5]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[6];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[7]; }
               numPtr += 8;
            }
            if (count & ((1<<(N-1))-1))
            {
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1]; }
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3]; }
               numPtr += 4;
            }
            if (count & ((1<<(N-2)-1))
            {
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                 num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1]; }
               numPtr += 2;
            }
            // repeat N times and finally:
            if { count & (1) }
            {
               { num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
               // numPtr += 1;
            }

            return (num + (num2 * 0x5d588b65));
        }
    }

我没有编译或测试过这段代码,但是这个想法是正确的。这取决于编译器进行合理的持续折叠和地址算术。

我试着用代码来保存原始文件的哈希值, 但我不知道这真的是个要求。如果不使用的话,它会更简单,更快一点。 num/num2特技,但只是为每个字符更新num。

修正版本(由Brian)作为静态函数:

    public static unsafe int GetHashCodeIra(string x)
    {
        fixed (char* str = x.ToCharArray())
        {
            const int N = 2; // a power of two controlling number of loop iterations
            char* chPtr = str;
            int num = 0x15051505;
            int num2 = num;
            int* numPtr = (int*)chPtr;
            int count = (x.Length+1) / 2;
            int unrolled_iterations = count >> (N+1); // could be 0 and that's OK
            for (int i = unrolled_iterations; i > 0; i--)
            {  // repeat 2**N times
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
                }
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3];
                }
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[4];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[5];
                }
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[6];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[7];
                }
                numPtr += 8;
            }
            if (0 != (count & ((1 << N) )))
            {
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
                }
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[2];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[3];
                }
                numPtr += 4;
            }
            if (0 != (count & ((1 << (N - 1) ))))
            {
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                    num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
                }
                numPtr += 2;
            }
            // repeat N times and finally:
            if (1 == (count & 1))
            {
                {
                    num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                    // numPtr += 1;
                }
            }

            return (num + (num2 * 0x5d588b65));
        }
    }

BobbyShaftoe 15 年前

您可以将其并行化,但是您将遇到的问题是线程、CUDA等具有与之相关的开销。即使使用线程池,如果字符串不是很大,那么假设一个典型的字符串是128-256个字符(可能小于此字符),您可能仍然会使对该函数的每次调用花费的时间比原来更长。

现在,如果你处理的是非常大的字符串,那么是的,它将改善你的时间。简单的算法是“令人尴尬的并行”。

Peter Mortensen icecrime 15 年前

我认为与当前的实现相比,您建议的所有方法都非常低效。

使用GPU: 字符串数据需要传输到GPU并返回结果,这需要很多时间。GPU的速度非常快,但只有在比较浮点计算时才使用,这里不使用浮点计算。所有操作都是在整数上的,对于整数来说,x86 CPU的能力是相当不错的。

使用另一个CPU核心: 这将涉及创建一个单独的线程、锁定内存和同步请求哈希代码的线程。所产生的开销远远超过了并行处理的好处。

如果您想一次计算数千个字符串的散列值,事情可能看起来有点不同,但我无法想象这样一个场景可以使实现更快 GetHashCode() .

Eric J. 14 年前

计算中的每个步骤都建立在前一步骤的结果基础上。如果循环的迭代顺序不对,您将得到 不同的结果 (价值) 号码从上一个迭代作为下一个迭代的输入)。

因此,任何并行运行步骤的方法(多线程、在GPU上大规模并行执行)通常都会扭曲结果。

另外,如果前面讨论的循环展开还没有在内部由编译器完成,以至于它实际上在执行时间上产生了差异,我会感到惊讶(编译器现在比一般的程序员更聪明,而且循环展开作为编译器优化技术已经存在了很长时间了。HiNee)

Tim Cooper 14 年前

考虑到字符串是不可变的,我首先考虑的是缓存返回结果。