为什么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())

现在,我已经读过要反向读取文件然后我应该使用ReversedLinesFileReaderApache Commons.我创建了以下扩展函数来做到这一点:

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是以正确的方式使用的吗？
• 我在SSD上运行带有Ext4文件系统的Linux Mint.这跟它有什么关系吗？
• 是不是不应该从头到尾读取文件？

Answer 1

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

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

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

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

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

更新：

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

我的 2015 Mac Book Pro 上的计时（我所有的开发工具和许多 chrome 窗口一直打开，占用内存和一些 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.stackoverflow.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  ")
}