Почему ReversedLinesFileReader так медленно?

У меня есть файл, который составляет 21,6 ГБ, и я хочу прочитать его от конца до начала, а не от начала до конца, как обычно.

Если я прочитаю каждую строку файла от начала до конца, используя следующий код, это займет 1 минуту, 12 секунд.

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

Теперь я прочитал, что для чтения в файле в обратном порядке я должен использовать ReversedLinesFileReader из Apache 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 ?
  • Я использую Linux Mint с файловой системой Ext4 на SSD. Может ли это иметь к этому какое-то отношение?
  • Это просто случай, когда файлы не следует читать с конца до начала?

Вы просите очень дорогостоящую операцию. Вы не только используете произвольный доступ в блоках для чтения файла, но и назад (так что если файловая система читает вперед, она читает неправильное направление), вы также читаете XML-файл, который является UTF-8, и кодировка медленнее, чем фиксированное байтовое кодирование.

Тогда, кроме того, вы используете менее эффективный алгоритм. Он считывает блок во время неудобного размера (насколько известно размер блока на диске: вы устанавливаете размер блока в соответствии с вашей файловой системой?) Назад при обработке кодирования и делает (ненужную?) Копию массива частичных байтов, а затем поворачивается он в строку (вам нужна строка для синтаксического анализа?). Он мог бы создать строку без копии и действительно создать строку, возможно, можно отложить, и вы будете работать непосредственно из буфера только декодирования, если вам нужно (XML-парсеры, например, также работают с ByteArrays или буферами). И есть другие копии массивов, которые просто не нужны, но это более удобно для кода.

У этого также может быть ошибка в том, что он проверяет новые строки, не считая, что символ может означать что-то другое, если на самом деле является частью многобайтовой последовательности. Чтобы проверить это для кодирования переменной длины, мне придется оглянуться назад на несколько дополнительных символов, я не вижу, чтобы это делалось.

Таким образом, вместо приятного перехода вперед только буферизованное последовательное чтение файла, который является самым быстрым, что вы можете сделать в своей файловой системе, вы делаете случайные чтения по 1 блоку за раз. Он должен по крайней мере читать несколько блоков диска, чтобы он мог использовать импульс вперед (установить размер блока в несколько кратных размеру вашего дискового блока), а также избежать количества «оставшихся» копий, сделанных на границах буфера.

Скорее всего, существуют более быстрые подходы. Но это будет не так быстро, как чтение файла в прямом порядке.

ОБНОВИТЬ:

Итак, я попробовал эксперимент с довольно глупой версией, которая обрабатывает 27G данных, читая первые 10 миллионов строк из дампа JSON wikidata и реверсируя эти строки.

Сроки на моей MacBook Pro 2015 года (со всеми моими файлами dev и многими хромированными окнами открытая память для едения и некоторый процессор все время, около 5 Г общей памяти свободна, размер виртуальной машины по умолчанию без каких-либо параметров, установленных вообще, не запускается под отладчиком ):

 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 на размер дискового ввода-вывода и попробовать также использовать gzipped-файлы, возможно, двухпоточную модель для следующего gzipping буфера при обработке предыдущего. Меньше строковых распределений, проверяя каждую функцию файла, чтобы убедиться, что ничего лишнего не происходит, убедитесь, что нет двойной буферизации и т. Д.

Уродливым, но функциональным кодом является:

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

Правильный способ исследования этой проблемы:

  1. Напишите версию этого теста в чистой Java.
  2. Контролируйте его, чтобы убедиться, что проблема с производительностью все еще существует.
  3. Профилируйте его, чтобы выяснить, где узкое место производительности.

Q: Я использую ReversedLinesFileReader правильно?

Да. (Предполагая, что это подходящая вещь, чтобы использовать линейный ридер вообще. Это зависит от того, что вы действительно пытаетесь сделать. Например, если вы просто хотели подсчитать строки назад, тогда вы должны читать 1 символ на время и подсчет последовательностей новой строки.)

Q: Я использую Linux Mint с файловой системой Ext4 на SSD. Может ли это иметь к этому какое-то отношение?

Возможно. Чтение файла в обратном порядке означает, что стратегии чтения, используемые ОС для быстрого ввода-вывода, могут не работать. Он может взаимодействовать с характеристиками SSD.

В: Это просто случай, когда файлы не следует читать с конца до начала?

Возможно. См. Выше.


Другая вещь, которую вы не учли, заключается в том, что ваш файл может содержать очень длинные строки. Узким местом может быть сборка символов в (длинные) линии.

Рассматривая исходный код , казалось бы, существует потенциал для поведения O(N^2) когда линии очень длинные. Критическая часть (я думаю) в том, как «rollover» обрабатывается FilePart . Обратите внимание на то, как копируются «оставшиеся» данные.