Многопоточный подход для поиска текстового шаблона в файлах

Question

Рассмотрим простое Java-приложение, которое должно проходить по дереву файлов на диске, чтобы найти определенный шаблон в теле файла.

Интересно, можно ли добиться лучшей производительности, используя многопоточность, например, когда мы находим новую папку, мы отправляем новый Runnable в фиксированном ThreadPool. Выполняемая задача должна проходить через папку для поиска новых папок и т. Д. По моему мнению, эта операция должна быть связана с вводом-выводом, а не с процессором, поэтому создание нового потока не приведет к повышению производительности.

Зависит ли это от типа жесткого диска? (HDD, ... и т. д.) Это зависит от типа ОС?

ИМХО, единственное, что может быть параллельным, - это создание нового потока для анализа содержимого файла, чтобы найти шаблон в теле файла.

Какова общая схема решения этой проблемы? Должен ли он быть многопоточным или однопоточным?

Answer 1

Я провел несколько экспериментов только по этому вопросу некоторое время назад. В конце я пришел к выводу, что могу добиться гораздо лучшего улучшения, изменив способ доступа к файлу.

Вот файл-обходчик, который я в итоге использовал:

// 4k buffer size ... near-optimal for Windows.
static final int SIZE = 4 * 1024;

// Fastest because a FileInputStream has an associated channel.
private static void ScanDataFile(Hunter h, FileInputStream f) throws FileNotFoundException, IOException {
  // Use a mapped and buffered stream for best speed.
  // See: http://nadeausoftware.com/articles/2008/02/java_tip_how_read_files_quickly
  FileChannel ch = f.getChannel();
  // How much I've read.
  long red = 0L;
  do {
    // How much to read this time around. 
    long read = Math.min(Integer.MAX_VALUE, ch.size() - red);
    // Map a byte buffer to the file.
    MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, red, read);
    // How much to get.
    int nGet;
    // Walk the buffer to the end or until the hunter has finished.
    while (mb.hasRemaining() && h.ok()) {
      // Get a max of 4k.
      nGet = Math.min(mb.remaining(), SIZE);
      // Get that much.
      mb.get(buffer, 0, nGet);
      // Offer each byte to the hunter.
      for (int i = 0; i < nGet && h.ok(); i++) {
        h.check(buffer[i]);
      }
    }
    // Keep track of how far we've got.
    red += read;
    // Stop at the end of the file.
  } while (red < ch.size() && h.ok());
  // Finish off.
  h.close();
  ch.close();
  f.close();
}

Answer 2

Я провел некоторые исследования в этой области, работая над тестовым проектом, вы можете посмотреть на проект на github по адресу: http://github.com/4ndrew/filesearcher. Конечно, главная проблема - это скорость дискового ввода-вывода, но если выбудет использовать оптимальное количество потоков для параллельного чтения / поиска, вы можете получить лучшие результаты совместно.

UPD: Также посмотрите эту статью http://drdobbs.com/parallel/220300055

Answer 3

То, что вы могли бы сделать, это: реализовать шаблон с несколькими потребителями для одного производителя, где один поток просматривает диск, извлекает файлы, а затем потоки потребителя обрабатывают их.

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

Answer 4

Вы правильно заявили, что вам нужно определить, связана ли ваша задача с ЦП или вводом-выводом, а затем решить, выиграет ли она от многопоточности или нет.Как правило, дисковые операции выполняются довольно медленно, поэтому, если объем данных, которые вам необходимо проанализировать и проанализировать сложность, вы вряд ли выиграете от многопоточности.Я бы просто написал простой тест - просто прочитать файлы без разбора в одном потоке, измерить его, а затем добавить разбор и посмотреть, будет ли он намного медленнее, а затем решить.

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