代码之家  ›  专栏  ›  技术社区  ›  Trevor Robinson

最快的方式,做许多小,盲目写在一个巨大的文件(在C++)?

  •  5
  • Trevor Robinson  · 技术社区  · 16 年前

    我有一些很大的(>4 GB)文件,其中包含(数百万)固定长度的二进制记录。我想(有效地)将它们与其他文件中的记录连接起来,方法是将指针(即64位记录号)以特定的偏移量写入这些记录中。

    更详细地说,我有一对(key,record number)元组的列表,按key对我要在给定的一对文件(比如a和B)上执行的每个连接进行排序。遍历一个列表对并匹配这些键会产生一个(key,record number a,record number B)元组列表,这些元组表示连接的记录(为简单起见,假设1:1映射)。为了完成连接,我在概念上需要查找列表中的每个A记录,并在适当的偏移量处写入相应的B记录编号,反之亦然。我的问题是什么才是最快的方法?

    由于连接的记录列表是按键排序的,因此关联的记录编号基本上是随机的。假设文件比操作系统磁盘缓存大得多,执行一系列随机查找和写入似乎效率极低。我试着通过将A->B和B->在一个稀疏数组中进行映射,并在内存耗尽时将最密集的条目群集刷新到磁盘。这样做的好处是,在更新集群的第一个指针之后,可以极大地增加为集群缓存适当记录的机会。然而,即使在这一点上,通常是做一堆查找和盲写,还是手动读取文件的块,更新适当的指针,然后写回这些块更好?虽然前一种方法简单得多,并且可以由操作系统进行优化,以尽可能减少扇区读取(因为它知道扇区大小)和拷贝(它可以通过直接读取到正确对齐的缓冲区来避免拷贝),但它似乎会招致极高的系统调用开销。

    虽然我喜欢一个可移植的解决方案(即使它依赖于一个广泛使用的库,比如Boost),但是现代的Windows和Linux是唯一必须的,所以我可以使用特定于操作系统的api(比如CreateFile提示或者scatter/gather I/O)。然而,这可能涉及到很多工作,甚至尝试,所以我想知道是否有人可以告诉我,如果可能值得的努力。

    4 回复  |  直到 16 年前
        1
  •  3
  •   Dummy00001    16 年前

    我试着通过将A->B和B->在一个稀疏数组中进行映射,并在内存耗尽时将最密集的条目群集刷新到磁盘。 它似乎会产生非常高的系统调用开销。

    mmap() 在*尼克斯,和 CreateFileMapping() on Windows .

    以逻辑方式将文件拆分为块,例如32MB。如果需要更改块中的某些内容,请单击mmap(),修改数据,如果需要,可以选择msync(),munmap(),然后移动到下一个块。

    重要的是要记住,真正的IO没有那么快。随机存取的性能限制因素是(1)存储器每秒可处理的IOPS数和(2)磁盘寻道数(通常IOPS在数百范围内。通常的寻道延迟是3-5ms。)例如,存储可以读/写50MB/s:一秒钟内一个50MB的连续块。但是,如果您尝试修补字节为50MB的文件,那么查找时间只会降低性能。在某种程度上,读多写多是可以的,即使只更新几个字节。

    另一个需要注意的限制是操作系统的最大IO操作大小:它取决于存储空间,但大多数操作系统会将超过128K的IO任务拆分。如果它与存储器中的类似限制同步,则该限制可以更改并且是最佳的。

    还要记住存储。许多人忘记了存储往往只有一个。我想说的是,除非你有多个存储器,否则开始加载线程对IO没有帮助。即使是单CPU/内核也可以轻松地饱和RAID10,其读IOPS为800,写IOPS为400(但每个存储都有一个专用线程至少在理论上是合理的。)

    希望有帮助。这里的其他人经常提到Boost.Asio,我对此没有经验,但值得一看。

    另外,坦率地说,我很想听到其他(更多的信息)回答你的问题。我已经在船上呆过好几次了,但还没有机会真正开始工作。欢迎使用与IO优化相关的书籍/链接等(不考虑平台)

        2
  •  4
  •   Billy ONeal IS4    16 年前

    看起来您可以通过使用数据结构来解决这个问题。你有三个限制条件:

    • 访问时间必须相当快
    • 数据必须保持分类
    • 你在旋转的圆盘上

    B+ Trees

    从本质上讲,B+树是一个二叉搜索树,不同的是节点组是按组进行的。这样,B+树一次只加载一个块,而不必为每个节点四处搜索。它还保留了一些信息,以便知道在搜索中需要哪个块。

    编辑:如果需要按多个项目排序,可以执行以下操作:

    
    +--------+-------------+-------------+---------+
    | Header | B+Tree by A | B+Tree by B | Records |
    +--------+-------------+-------------+---------+
          ||      ^     |     ^    |          ^
          |\------/     |     |    |          |
          \-------------------/    |          |
                        |          |          |
                        \----------+----------/
    

        3
  •  1
  •   Managu    16 年前

    按索引对新文件进行排序。使用为外部排序而设计的排序算法(虽然我自己没有尝试过,但当我研究类似问题时,STXXL.sourceforge.net中的STXXL库看起来很有前途)

    依次遍历A记录文件和排序对列表。读入一大块,在内存中做所有相关的改变,写出大块。再也不要碰记录文件的那个部分(因为您计划进行的更改是按顺序进行的)

        4
  •  1
  •   joe snyder    16 年前

    我正在做非常类似的大文件操作,这些新机器非常快,根本不需要很长时间:

    在配备3gb ram和32位Vista的cheapo 2.4gHz HP Pavilion上,使用Delphi库例程(与Win API相反)将300万条1008字节的连续记录写入一个新文件需要56秒。