为什么 ReversedLinesFileReader 这么慢？

Question

我有一个 21.6GB 的文件，我想从头读到尾，而不是像通常那样从头读到尾。

如果我使用以下代码从头到尾读取文件的每一行，则需要 1 分 12 秒。

val startTime = System.currentTimeMillis()
File("very-large-file.xml").forEachLine {
    val i = 0
}
val diff = System.currentTimeMillis() - startTime
println(diff.timeFormat())

现在，我已经阅读了反向读取文件的内容，然后我应该使用 Apache Commons 中的 ReversedLinesFileReader。我创建了以下扩展函数来执行此操作：

fun File.forEachLineFromTheEndOfFile(action: (line: String) -> Unit) {
    val reader = ReversedLinesFileReader(this, Charset.defaultCharset())
    var line = reader.readLine()
    while (line != null) {
        action.invoke(line)
        line = reader.readLine()
    }

    reader.close()
}

然后通过下面的方式调用，和之前的方式一样，只是调用了forEachLineFromTheEndOfFile函数：

val startTime = System.currentTimeMillis()
File("very-large-file.xml").forEachLineFromTheEndOfFile {
    val i = 0
}
val diff = System.currentTimeMillis() - startTime
println(diff.timeFormat())

这花了 17 分 50 秒 到运行！

我使用 ReversedLinesFileReader 的方式是否正确？
我运行宁 Linux Mint 在 SSD 上使用 Ext4 文件系统。这和它有什么关系吗？
难道只是文件不应该从头读到尾吗？

Answer 1

调查此问题的正确方法是：

用纯 Java.
对其进行基准测试以确保性能问题仍然存在。
分析它以找出性能瓶颈所在。

Q: Am I using ReversedLinesFileReader in the correct way?

是的。（假设完全使用 reader 行是一件合适的事情。这取决于你真正想做什么。例如，如果你只是想向后数行，那么你应该阅读一次 1 个字符并计算换行符序列。)

Q: I am running Linux Mint with an Ext4 file system on an SSD. Could this have anything to do with it?

可能吧。反向读取文件意味着 OS 用于快速 I/O 的预读策略可能不起作用。它可能与SSD的特性相互作用。

Q: Is it just the case that files should not be read from the end to the start?

可能吧。见上文。

您没有考虑的另一件事是您的文件实际上可能包含一些非常长的行。瓶颈可能是将字符组装成（长）行。

查看 source code，当行很长时，似乎有可能出现 O(N^2) 行为。关键部分是（我认为）FilePart 处理 "rollover" 的方式。请注意复制 "left over" 数据的方式。

Answer 2

您要求的操作非常昂贵。您不仅在块中使用随机访问来读取文件并向后移动（因此，如果文件系统正在向前读取，则读取方向错误），您还在读取一个 XML 文件，该文件是 UTF-8并且编码比固定字节编码慢。

除此之外，您使用的算法效率不高。它在不方便大小的时候读取一个块（它是否知道磁盘块大小？您是否设置块大小以匹配您的文件系统？）在处理编码时向后并制作（不必要的？）部分字节数组的副本然后转向它变成一个字符串（你需要一个字符串来解析吗？）。它可以在没有副本的情况下创建字符串，并且真正创建字符串可能会被推迟，您可以直接从缓冲区工作，只在需要时解码（例如 XML 解析器也可以从 ByteArrays 或缓冲区工作）。还有其他一些不需要的数组副本，但代码更方便。

它也可能有一个错误，因为它检查换行符而不考虑字符可能意味着不同的东西，如果实际上是多字节序列的一部分。它必须回顾一些额外的字符来检查可变长度编码，我没有看到它这样做。

因此，您可以一次随机读取 1 个块，而不是仅对文件进行大量缓冲的顺序读取（这是您在文件系统上可以做的最快的事情）。它至少应该读取多个磁盘块，以便它可以使用前向动量（将块大小设置为磁盘块大小的某个倍数会有所帮助），并避免在缓冲区边界进行的 "left over" 副本数量。

可能有更快的方法。但它不会像按正向顺序读取文件那样快。

更新：

好的，所以我尝试了一个相当愚蠢的版本的实验，该版本通过从 wikidata JSON 转储中读取前 1000 万行并反转这些行来处理大约 27G 的数据。

我 2015 年 Mac Book Pro 的时间安排（包括我所有的开发资料和许多 chrome windows 打开吃内存和一些 CPU 一直，大约 5G总内存的空闲，VM 大小是默认的，根本没有设置任何参数，在调试器下不是运行):

reading in reverse order: 244,648 ms = 244 secs = 4 min 4 secs
reading in forward order:  77,564 ms =  77 secs = 1 min 17 secs

temp file count:   201
approx char count: 29,483,478,770 (line content not including line endings)
total line count:  10,050,000

该算法是按行读取原始文件，一次缓冲 50000 行，将这些行以相反的顺序写入一个编号的临时文件。然后在写入所有文件后，按行向前倒序读取它们。基本上将它们分成原始的反向排序片段。它可以被优化，因为这是该算法最原始的版本，没有调整。但它确实做了文件系统最擅长的事情，使用大小适中的缓冲区进行顺序读取和顺序写入。

所以这比您使用的要快得多，可以从这里调整它以提高效率。您可以用 CPU 换取磁盘 I/O 大小，并尝试使用 gzip 文件，也许是双线程模型，以便在处理前一个缓冲区时对下一个缓冲区进行 gzip 压缩。更少的字符串分配，检查每个文件函数以确保没有额外的事情发生，确保没有双缓冲，等等。

丑陋但实用的代码是：

package com.Whosebug.reversefile

import java.io.File
import java.util.*

fun main(args: Array<String>) {
    val maxBufferSize = 50000
    val lineBuffer = ArrayList<String>(maxBufferSize)
    val tempFiles = ArrayList<File>()
    val originalFile = File("/data/wikidata/20150629.json")
    val tempFilePrefix = "/data/wikidata/temp/temp"
    val maxLines = 10000000

    var approxCharCount: Long = 0
    var tempFileCount = 0
    var lineCount = 0

    val startTime = System.currentTimeMillis()

    println("Writing reversed partial files...")

    try {
        fun flush() {
            val bufferSize = lineBuffer.size
            if (bufferSize > 0) {
                lineCount += bufferSize
                tempFileCount++
                File("$tempFilePrefix-$tempFileCount").apply {
                    bufferedWriter().use { writer ->
                        ((bufferSize - 1) downTo 0).forEach { idx ->
                            writer.write(lineBuffer[idx])
                            writer.newLine()
                        }
                    }
                    tempFiles.add(this)
                }
                lineBuffer.clear()
            }

            println("  flushed at $lineCount lines")
        }

        // read and break into backword sorted chunks
        originalFile.bufferedReader(bufferSize = 4096 * 32)
                .lineSequence()
                .takeWhile { lineCount <= maxLines }.forEach { line ->
                    lineBuffer.add(line)
                    if (lineBuffer.size >= maxBufferSize) flush()
                }
        flush()

        // read backword sorted chunks backwards
        println("Reading reversed lines ...")
        tempFiles.reversed().forEach { tempFile ->
            tempFile.bufferedReader(bufferSize = 4096 * 32).lineSequence()
                .forEach { line ->
                    approxCharCount += line.length
                    // a line has been read here
                }
            println("  file $tempFile current char total $approxCharCount")
        }
    } finally {
        tempFiles.forEach { it.delete() }
    }

    val elapsed =  System.currentTimeMillis() - startTime

    println("temp file count:   $tempFileCount")
    println("approx char count: $approxCharCount")
    println("total line count:  $lineCount")
    println()
    println("Elapsed:  ${elapsed}ms  ${elapsed / 1000}secs  ${elapsed / 1000 / 60}min  ")

    println("reading original file again:")
    val againStartTime = System.currentTimeMillis()
    var againLineCount = 0
    originalFile.bufferedReader(bufferSize = 4096 * 32)
            .lineSequence()
            .takeWhile { againLineCount <= maxLines }
            .forEach { againLineCount++ }
    val againElapsed =  System.currentTimeMillis() - againStartTime
    println("Elapsed:  ${againElapsed}ms  ${againElapsed / 1000}secs  ${againElapsed / 1000 / 60}min  ")
}

为什么 ReversedLinesFileReader 这么慢？

Why is ReversedLinesFileReader so slow?

java

kotlin

apache-commons-io