为什么ReversedLinesFileReader这么慢?

我有一个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 ?
我在SSD上运行Ext4文件系统的Linux Mint。会不会跟这个有关?
是不是文件不应该从头到尾读?

调查这个问题的正确方法是:

用纯Java编写这个测试的一个版本。
对其进行基准测试以确保性能问题仍然存在。
配置文件以找出性能瓶颈在哪里

问:我是否以正确的方式使用ReversedLinesFileReader ?

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

问:我正在运行Linux Mint，在SSD上安装Ext4文件系统。会不会跟这个有关?

可能。反向读取文件意味着操作系统用于提供快速I/O的预读策略可能不起作用。它可能与SSD的特性交互。

Q:是不是文件不应该从头到尾读?

可能。看到上面。

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

查看源代码，当行很长时，似乎有可能出现O(N^2)行为。关键的部分是(我认为)FilePart处理"翻转"的方式。请注意复制"剩余"数据的方式。

您正在请求一个非常昂贵的操作。您不仅使用块中的随机访问来读取文件并向后读取(因此，如果文件系统正在向前读取，则读取方向错误)，而且还读取了UTF-8的XML文件，其编码速度比固定字节编码慢。

那么最重要的是，你使用了一个效率不高的算法。它在不方便的时候读取一个块(它知道磁盘块大小吗?)您是否在处理编码时设置块大小以匹配您的文件系统?)，并(不必要?)复制部分字节数组，然后将其转换为字符串(您需要字符串来解析吗?)它可以在没有复制的情况下创建字符串，真正创建字符串可能会被推迟，如果需要，您可以直接从缓冲区解码(例如XML解析器也可以从ByteArrays或缓冲区工作)。还有一些数组拷贝是不需要的，但是对于代码来说更方便。

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

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

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

更新:

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

在我2015年的Mac Book Pro上的时间(我所有的开发人员和许多chrome窗口一直打开内存和一些CPU，大约5G的总内存是空闲的，虚拟机大小是默认的，根本没有设置参数，不在调试器下运行):

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文件，也许是一个双线程模型，以便在处理前一个缓冲区时压缩下一个缓冲区。更少的字符串分配，检查每个文件函数以确保没有发生额外的事情，确保没有双重缓冲，等等。

丑陋但功能强大的代码是:

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  ")
}

相关内容

最新更新

热门标签：