c++ - 我为类编写了这个汉明编码代码。为什么这么慢？

Question

我为我的操作系统课写了这个:

#include <iostream>
#include <fstream>

//encodes a file using the (8,4) Hamming Code.
//usage : HammingEncode.out < inputFile > outputFile 
int main() {
    unsigned char const codebook[] = {0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78, 0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF};
    unsigned char in, nextByte;
    unsigned char const leftMask = 0xF0, rightMask = 0x0F;

    in = std::cin.get();
    while (!std::cin.eof()) {
        nextByte = (in & leftMask) >> 4;
        std::cout << codebook[nextByte];
        nextByte = in & rightMask;
        std::cout << codebook[nextByte];
        in = std::cin.get();
    }
}

然后我决定在 King James Bible 的 Old Testamenet 上测试它的速度(只是为了看看)。这是我们用 Java 教授的数据结构类的标准测试文件，我们基本上可以立即对其进行排序和霍夫曼编码，但这需要相当长的时间来编码。这是怎么回事？

Answer 1

std::cin以文本模式打开，因此它一直在寻找各种值得关注的东西(如换行符等)。

鉴于 std::cin 不断嗅探字符输入流，我并不惊讶它需要更长的时间，但它似乎有点过分。以下，绕过iostream并使用 FILE流直接可能会做你所期望的:

#include <cstdlib>
#include <cstdio>

int main(int argc, char *argv[])
{
    static unsigned char const codebook[] =
    {
        0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78,
        0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF
    };

    for (int c = std::fgetc(stdin); c!=EOF; c=std::fgetc(stdin))
    {
        std::fputc(codebook[c >> 4], stdout);
        std::fputc(codebook[c & 0x0F], stdout);
    }

    return EXIT_SUCCESS;
}

我在加载了 a 范围内的字符的 10MB 随机文件上测试了上面的精确代码。至 z , 使用 std::cin 时结果长得离谱和 std::cout .使用 FILE直接流，差异巨大。此答案中的所有代码均使用 Apple LLVM version 5.1 (clang-503.0.38) (based on LLVM 3.4svn) 进行了测试使用 -O3优化。

使用 FILE流

time ./hamming < bigfile.txt > bigfile.ham 
real 0m1.855s
user 0m1.812s
sys  0m0.041s

使用 std::cin和 std::cout

time ./hamming < bigfile.txt > bigfile.ham
real 0m23.819s
user 0m7.416s
sys  0m16.377s

使用 std::cin和 std::cout与 std::cout.sync_with_stdio(false);

time ./hamming < bigfile.txt > bigfile.ham
real 0m24.867s
user 0m7.705s
sys  0m17.118s

总而言之，哎哟。值得注意的是在系统 中花费的时间。如果我有机会用 std::istream::get() 更新这个和 put()我会的方法，但老实说，我不期待任何奇迹。除非有一些神奇的方法(对我而言，对其他人而言不是)从 std::cin 关闭 io xlat| FILE流可能是一个合理的选择。我还没有调查是否吸食std::cin的 rdbuf()也是一个可行的选择，但它也可能有希望。

---

编辑:使用 std::istreambuf_iterator<char>

使用 streambuf 迭代器类有一个显着的改进，因为它基本上绕过了所有内联板条垃圾，但它仍然不如 FILE 高效流:

#include <iostream>
#include <cstdlib>
#include <cstdio>

int main(int argc, char *argv[])
{
    static unsigned char const codebook[] =
    {
        0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78,
        0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF
    };

    std::istreambuf_iterator<char> cin_it(std::cin), cin_eof;
    std::for_each(cin_it, cin_eof, [](char c)
        {
          std::cout.put(static_cast<char>(codebook[static_cast<unsigned char>(c) >> 4]));
          std::cout.put(static_cast<char>(codebook[static_cast<unsigned char>(c) & 0x0F]));
        });

    return EXIT_SUCCESS;
}

结果:

time ./hamming < bigfile.txt > bigfile.ham

real 0m6.062s
user 0m5.795s
sys  0m0.053s

请注意 system现在可与 FILE 相媲美流结果，但来自 user 中其余 iostream 模板的开销似乎是一个痛点(但仍然比其他 iostream 尝试更好)。你赢了一些，你输了一些 =P

---

编辑:无缓冲系统 IO

为了完全公平，绕过所有运行时缓冲并仅依靠系统调用来完成这种疯狂行为，以下内容也值得注意:

#include <cstdlib>
#include <cstdio>
#include <unistd.h>

int main(int argc, char *argv[])
{
    static unsigned char const codebook[] =
    {
        0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78,
        0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF
    };

    unsigned char c;
    while (read(STDIN_FILENO, &c, 1)> 0)
    {
        unsigned char duo[2] =
        {
            codebook[ c >> 4 ],
            codebook[ c & 0x0F ]
        };
        write(STDOUT_FILENO, duo, sizeof(duo));
    }

    return EXIT_SUCCESS;
}

如您所料，结果很糟糕:

time ./hamming < bigfile.txt > bigfile.ham

real 0m26.509s
user 0m2.370s
sys  0m24.087s