egmkang 服务端开发工程师

String.IndexOf

2016-08-11
C#

还是上次那个json解析程序的优化, 虽然速度已经比较理想, 但是看到IndexOf占到整个解析时长的20%+, 心里还是不爽. 我写的IndexOf是按照UTF16字符, 一个字符一个字符去比较的, 所以当时能想到的办法, 就是一次比较多个字符.

大概是五六年前, 我看过某一个libc里面实现的strlen, 算法就是((i - 0x1) & ~i) & 0x80, 这个算法只能针对\0比较, 所以我在想, 如果我把i矫正成0, 那么算法应该就会变得通用. 然后撸了一下午, 写了一个一次比较4个UTF16 char的版本.

const ulong l1u = 0x1ul | 0x1ul << 16 | 0x1ul << 32 | 0x1ul << 48;
const ulong l80u = 0x8000ul | 0x8000ul << 16 | 0x8000ul << 32 | 0x8000ul << 48;

public static int IndexOf(char* s, int length, char c)
{
  int offset = 0;
  int align = (int)s & 0x7;
  //8 byte aligned or 4 char aligned
  if (align != 0)
  {
    int index = IndexOf(s, offset, align >> 1, c);
    if (index >= 0) return index;
  }
  //strlen's quick check is based on ((i - 0x1) & ~i) & 0x80
  //so, if i add `-expectedChar` onto i
  //then i can reuse this formula
  ulong magic = (ulong)c;
  ulong expected = unchecked(magic | magic << 16 | magic << 32 | magic << 48);
  offset += align >> 1;
  int padLength = (length - offset) >> 2 << 2;
  for (; offset < padLength; offset += 4)
  {
    ulong p = *(ulong*)(s + offset);
    p = p >= expected ? unchecked(p - expected) : unchecked(expected - p);
    if (unchecked((p - l1u) & ~p & l80u) != 0)
    {
      return IndexOf(s, offset, 4, c);
    }
  }
  return IndexOf(s, offset, length - offset, c);
}

private static int IndexOf(char* s, int offset, int length, char c)
{
  if (length > 4) throw new System.Exception("FUCK U");
  char* p = s + offset;
  switch (length)
  {
    case 4: goto L4;
    case 3: goto L3;
    case 2: goto L2;
    case 1: goto L1;
  }
  L4: if (*p++ == c) goto Found;
  L3: if (*p++ == c) goto Found;
  L2: if (*p++ == c) goto Found;
  L1: if (*p++ == c) goto Found;
  return -1;
  Found: return (int)(p - s);
}

费劲了脑汁, 结果他妈的, 跑的还没一次比较四个char的快(就是四次if)…..

妈蛋, 我得什么时候去研究一下这个代码为啥会慢, 感觉不科学啊

感觉这就是玄学

PS:

今天把代码改了一下, 也没改多少, 就是以前一次扫描一个ulong, 现在一次扫描两个ulong, 算法还是一样的.

在x64下面, 速度是要比一次比较4个char来的快, 快50%以上; 不过在x86下面, 速度比4个char的版本慢一点, 应该是x86面, int64是模拟出来的缘故.


上一篇 base64

Comments