比scanf更快的方法？

Question

我正在使用scanf("%d", &someint)进行大量正整数解析。为了确定scanf是否成为瓶颈，我实现了一个使用fread的简单整数解析函数，代码如下：

int result;
char c;

while (fread(&c, sizeof c, 1, stdin), c == ' ' || c == '\n')
    ;

result = c - '0';
while (fread(&c, sizeof c, 1, stdin), c >= '0' || c <= '9') {
     result *= 10;
     result += c - '0';
}

return result;

但是令我惊讶的是，即使进行内联，这个函数的性能也要差约50%。难道没有可能针对特定情况改进scanf吗？fread不应该很快吗（另一个提示：整数（编辑：大多数情况下）只有1或2位数字）？

- Jo So

---

您的意思是 c >= '0' && c <= '9' 吗？ - Dan

scanf的优化可能是由编译器完成的。fread几乎肯定没有被优化为使用标准输入作为输入。 - Ry-

至少你应该使用 fgetc 函数... - kennytm

fread()并不是用来逐个读取字符的，即使使用fgetc()也可能更有效率。 - wildplasser

从吹毛求疵的角度来看，我建议使用 isdigit() 而不是 c>='0' && c<='9'，因为在某些字符集中数字可能不是连续的，例如 EBCDIC。 - Philip

Answer 1

我遇到的问题并不是解析本身，而是对fread（还有fgetc等类似函数）的多次调用。每次调用时，libc都必须锁定输入流以确保两个线程不会互相干扰。锁定是一项非常昂贵的操作。

我们需要的是一个能提供缓冲输入的函数（重新实现缓冲区太费力了），但又避免了fgetc所带来的巨大锁定开销。

如果我们可以保证只有一个线程使用输入流，那么我们可以使用unlocked_stdio(3)中的函数，例如getchar_unlocked(3)。以下是一个示例：

static int parseint(void)
{
    int c, n;

    n = getchar_unlocked() - '0';
    while (isdigit((c = getchar_unlocked())))
        n = 10*n + c-'0';

    return n;
}

以上版本没有检查错误。但它保证终止。如果需要错误处理，可能只需在结尾处检查 feof(stdin) 和 ferror(stdin)，或者让调用者来做。

我的最初目的是在SPOJ提交编程问题的解决方案，其中输入仅包含空格和数字。因此，仍有改进的空间，即 isdigit 检查。

static int parseint(void)
{
    int c, n;

    n = getchar_unlocked() - '0';
    while ((c = getchar_unlocked()) >= '0')
        n = 10*n + c-'0';

    return n;
}

这个解析程序非常优秀，无论是在性能、方便性还是可维护性方面，都很难被超越。

- Jo So

Answer 2

您可以通过缓冲来显著改善示例 - 将大量字符读入内存，然后从内存版本解析它们。

如果您从磁盘中读取数据，则将缓冲区大小设置为块大小的倍数可能会提高性能。

编辑：您可以使用mmap将文件映射到内存中，让内核代替您处理这个问题。 （参考链接）

- Timothy Jones

---

我想表示怀疑。我非常确定libc本身会进行缓冲。除非你正在使用系统调用（read(2)/write(2)），否则实现自己的缓冲区可能会减慢速度。 - Jo So

试一下 - 很高兴错了 :) 我记得手动缓冲显著加速了以前使用getc()的代码，但那可能是stdin，它不是块缓冲的。您还可以尝试给setvbuf()一个更大的缓冲区。 - Timothy Jones

@JoSo：只是为了好玩，我用每次读取1个字节的fread函数读取了一个372MB的文件，结果花费了将近30秒的时间。而每次读取4K的数据只需要1.3秒。当然，你可能已经知道这一点了。不过，接受这个答案可能会很不错。 - Mark Wilkins

这并不完全是我的问题的答案，我的问题是如何在更狭窄的领域中击败scanf（scanf（％d，...）也不应该进行缓冲！）。无论如何，我接受了它，因为没有其他人想写一个答案;-) - Jo So

@JoSo 是的，stdio会缓冲，但更可能的是瓶颈只是 3.72 亿次 fgetc 调用而不是双缓冲的任何副作用。 - jørgensen

Answer 3

这是我使用的东西。

 #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
 char _;

然而，这仅适用于整数。

- Boris

---

这个很好！不过，我建议使用getcx()或者getchar_unlocked()代替getchar()。 - diegocaro

char _; 做什么？ - user5164080

@light2yellow char _; 定义了一个名为下划线字符 _ 的变量，该变量在宏中被使用，例如 (_=getchar())。其目的是定义一个全局变量，在宏被定义的地方使用该变量。我建议改用 static char _; 来限制作用域仅在文件或编译单元中。对于多线程应用程序可能不是一个好主意。最好改成函数而不是宏。读取第一个数字并将一系列数字转换为整数值。停止读取第一个非数字字符。 - Richard Chambers

Answer 4

从你所说的，我得出以下事实：

• 数字范围在0-99之间，共有10+100个不同的字符串（包括前导零）
• 你相信你的输入流遵循某种规范，并且不会包含任何意外的字符序列

在这种情况下，我会使用查找表将字符串转换为数字。给定一个字符串s[2]，可以通过s[1]*10 + s[0]计算出您的查找表的索引，交换数字并利用ASCII中'\0'等于0的事实。

然后，您可以按以下方式读取输入：

// given our lookup method, this table may need padding entries
int lookup_table[] = { /*...*/ };

// no need to call superfluous functions
#define str2int(x) (lookup_table[(x)[1]*10 + (x)[0]])

while(read_token_from_stream(stdin, buf))
        next_int = str2int(buf);

在今天的计算机上，很难想出一种更快的技术。我猜这种方法可能比任何基于scanf()的方法运行速度快2到10倍。

- Philip

---

抱歉，我的意思是“大多数”数字都是1或2位数。无论如何，使用查找表有什么意义呢？我看不出来你在节省哪些周期。（您从我的解决方案中节省了c - '0'的部分，但另一方面，您会有更多的重定向。） - Jo So

Jo So: 我也在尽可能地用不超过三条指令保存 c >= '0' || c <= '9' 和 c == ' ' || c == '\n' 部分。但是，诚实地说，我在 read_token_from_stream() 中缩写的这些操作中需要一个真正的子集。 - Philip