Улучшение производительности ввода-вывода в программах на C ++ [внешняя сортировка слиянием] - PullRequest
2 голосов
/ 23 апреля 2010

В настоящее время я работаю над проектом, включающим внешнюю сортировку слиянием с использованием замены-выбора и k-way merge. Я реализовал проект на C ++ [работает на Linux]. Это очень просто и сейчас имеет дело только с записями фиксированного размера.

Для чтения и записи я использую (i / o) fstream классы. После выполнения программы за несколько итераций я заметил, что

  • Блоки чтения ввода / вывода для запросов размером более 4 КБ (типичный размер блока). Infact, дающий размер буфера больше 4K, приводит к снижению производительности.
  • Операции вывода, похоже, не нуждаются в буферизации, похоже, linux позаботился о буферизации вывода. Поэтому я выдаю запись (запись) вместо того, чтобы поддерживать специальный буфер записей, а затем сразу же очищать их, используя запись (records []).

Но производительность приложения не кажется большой. Как я мог улучшить производительность? Должен ли я поддерживать специальные потоки ввода / вывода, чтобы позаботиться о чтении блоков, или уже существуют классы C ++, уже обеспечивающие эту абстракцию? (Что-то вроде BufferedInputStream в java)

Ответы [ 3 ]

3 голосов
/ 23 апреля 2010

Такой высокопроизводительный ввод / вывод проще всего сделать с mmap. Это дает ядру гораздо больше свободы для выполнения операций ввода-вывода и планирования времени процессора для вашего приложения. Например, когда вы читаете в 1 МБ, используя ifstream, ядро ​​может вернуться только тогда, когда все данные прочитаны. Но с помощью mmap () данные могут возвращаться постепенно, по мере их доступности.

Однако вы должны понимать, как это происходит. То, что данные находятся в оперативной памяти, не означает, что вы должны обращаться с ними как с произвольной доступностью. Не кормите его до std::sort. Это коснется случайных частей области mmap, вызывая сбои страниц слева и по центру. В результате вы будете вызывать тяжелые попытки поиска диска для устранения случайных сбоев страниц. Вместо этого mmap() два входа и объединить их. Поскольку команда mmap сообщает ядру, какие данные вам понадобятся в будущем, ядро ​​будет передавать вам данные настолько быстро, насколько это возможно, а сортировка слиянием вызовет ошибку страницы (т.е. остановку), когда для нее временно не будет данных.

2 голосов
/ 23 апреля 2010

Посмотрите на использование библиотеки низкоуровневого ввода-вывода C.http://www.linuxtopia.org/online_books/programming_books/gnu_libc_guide/Low_002dLevel-I_002fO.html или ftp: //ftp2.developpez.be/developps/linux/alp/alp-apB-low-level-io.pdf

В окнах длинныйНекоторое время назад у меня было несколько операций ввода-вывода, которые запускались в 10 раз быстрее при использовании открытия низкого уровня ввода-вывода, чем при использовании fopen.

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

1 голос
/ 23 апреля 2010

Потоки известны своими проблемами с производительностью по сравнению с обычным вводом / выводом.На самом деле они действуют как «простые в использовании и подходящие для разных ситуаций», но им не хватает производительности.В вашей ситуации я бы переключился на ввод-вывод в стиле C, профилируя и затем действуя на основании результатов профилирования.

...