时间戳

首页 > 解决方案 > C++ 二进制文件 I/O 操作减慢... DB 如何处理二进制文件？

c++ - C++ 二进制文件 I/O 操作减慢... DB 如何处理二进制文件？

问题描述

我正在尝试制作一个简单的基于文件的哈希表。这是我的insert成员函数：

private: std::fstream f;  // std::ios::in | std::ios::out | std::ios::binary

public: void insert(const char* this_key, long this_value) {
    char* that_key;
    long that_value;
    long this_hash = std::hash<std::string>{}(this_key) % M;
    long that_hash;  // also block status

    long block = this_hash;
    long offset = block * BLOCK_SIZE;
    while (true) {
        this->f.seekg(offset);
        this->f.read((char*) &that_hash, sizeof(long));
        if (that_hash > -1) {  // -1 (by default) indicates a never allocated block
            this->f.read(that_key, BLOCK_SIZE);
            if (strcmp(this_key, that_key) == 0) {
                this->f.seekp(this->f.tellg());
                this->f.write((char*) &this_value, sizeof(long));
                break;
            } else {
                block = (block + 1) % M;  // linear probing
                offset = block * BLOCK_SIZE;
                continue;
            }
        } else {
            this->f.seekp(offset);
            this->f.write((char*) &this_hash, sizeof(long));  // as block status
            this->f.write(this_key, KEY_SIZE);
            this->f.write((char*) &this_value, sizeof(long));
            break;
        }
    }
}

使用 50,000,017 个块测试多达 10M 的键值对是公平的。（二进制文件大小约为 3.8GB）。

但是，使用 50M 键和 250,000,013 个块的测试速度非常慢……（在这种情况下，二进制文件大小超过 19GB）。1,000 inserts 通常需要 4~5ms，但特别需要超过 2,000ms。它变得越来越慢，然后需要 40~150 毫秒......（x10 ~ x30 慢......）我绝对不知道......

标签： c++fstreambinaryfilesc++-ios

解决方案

数据大小

通常磁盘驱动器块大小是 2 的幂，因此如果您的数据块大小也是 2 的幂，那么您基本上可以消除数据块跨越磁盘块边界的情况。

在您的情况下，64 字节的值（如果您真的不需要存储散列，则为 32 字节）可能会稍微好一些。

广告订单

您可以做的另一件事来提高性能是插入是增加哈希顺序以减少必须从磁盘加载数据的次数。

通常当数据被读取或写入磁盘时，操作系统会一次读取/写入一个大卡盘（可能是 4k）所以如果你的算法是一种在本地及时写入数据的方式，你会减少时间数据必须实际读取或写入磁盘。

鉴于您进行了大量插入，一种可能性是一次处理 1000 个甚至 10000 个键/值对的批量插入。本质上，您将在内存中累积数据并对其进行排序，一旦您有足够的项目（或完成插入时），您将按顺序写入数据。

这样，您应该能够减少非常慢的磁盘访问。如果您使用传统硬盘驱动器，这可能更重要，因为移动磁头很慢（在这种情况下，整理碎片可能很有用）。此外，请确保您的硬盘驱动器有足够的可用空间。

在某些情况下，本地缓存（在您的应用程序中）也可能会有所帮助，特别是如果您知道如何使用您的数据。

文件大小 VS 冲突

当您使用散列时，您希望找到文件大小和冲突之间的最佳点。如果你有太多的碰撞，那么你会浪费很多时间，并且在某些时候，当几乎每次插入都很难找到一个空闲的地方时，它可能会退化。

另一方面，如果您的文件真的非常大，您可能会遇到这样的情况：您的 RAM 中可能会填充主要为空的数据，并且在几乎所有插入时仍需要用磁盘中的数据替换数据。

例如，如果您的数据是 20GB，并且您可以在内存中加载 2GB，那么如果插入确实是随机的，那么 90% 的时间您可能需要真正访问硬盘驱动器。

配置

那么选项将取决于操作系统，它超出了编程论坛的范围。如果您想优化您的计算机，那么您应该寻找其他地方。

阅读

阅读有关操作系统（文件系统、缓存层……）和算法（外部排序算法、B-Tree 和其他结构）的知识可能会有所帮助，以便更好地理解。

备择方案

  • 额外的内存
  • 快速固态硬盘
  • 多线程（例如输入和输出线程）
  • 重写算法（例如一次读取/写入整个磁盘页面）
  • 更快的 CPU / 64 位计算机
  • 使用为此类场景设计的算法。
  • 使用数据库。
  • 分析代码
  • 调整参数

推荐阅读