[linux] разрозненное чтение из файла
Неплохой вроде бы и переносимый способ:
запустить несколько потоков, и раздавать им запросы на чтение блоков в порядке возрастания номеров; если новые запросы поступают во время выполнения старых, то реализовать какой-нибудь простейший элеватор.
Оптимальное количество потоков определять экспериментально, т.к. это зависит от системы.
> Например, если нужные блоки 0,2,4,6,8 то можно прочитать блоки 0-8, а
> потом выбрать нужные.
С этим, по идее, должна справиться ОС.
запустить несколько потоков, и раздавать им запросы на чтение блоков в порядке возрастания номеров; если новые запросы поступают во время выполнения старых, то реализовать какой-нибудь простейший элеватор.
Оптимальное количество потоков определять экспериментально, т.к. это зависит от системы.
> Например, если нужные блоки 0,2,4,6,8 то можно прочитать блоки 0-8, а
> потом выбрать нужные.
С этим, по идее, должна справиться ОС.
readv разве может читать с пропусками?
мне кажется тут лучше всего сделать через mmap
а в 2.6 появился remap_file_pages - create a non-linear file mapping
вот только интересно какая стратегия у ядра загрузки страниц,
было бы замечательно если оно в очередь на загрузку ставило сразу же после ммапа.
мне кажется тут лучше всего сделать через mmap
а в 2.6 появился remap_file_pages - create a non-linear file mapping
вот только интересно какая стратегия у ядра загрузки страниц,
было бы замечательно если оно в очередь на загрузку ставило сразу же после ммапа.
> запустить несколько потоков, и раздавать им запросы на чтение блоков в порядке возрастания номеров;
Способ хороший, но есть одна проблема - файловая система. Из-за фрагментации и других причин порядок блоков на диске может существенно отличаться от порядка блоков в файле. Не приведет ли это к существенному снижению производительности?
Информация о том, что где лежит доступна только внутри ядра. Вся надежда была как раз на функции типа aio_read, поскольку они в работают ядре, то как раз могут осуществлять нужное преобразование и подрюхивание.
>> Например, если нужные блоки 0,2,4,6,8 то можно прочитать блоки 0-8, а
>> потом выбрать нужные.
>С этим, по идее, должна справиться ОС.
Насчет чтения промежуточных блоков - где найти инфу о том, работает оно или не работает (и в каких syscall-ах как)
Способ хороший, но есть одна проблема - файловая система. Из-за фрагментации и других причин порядок блоков на диске может существенно отличаться от порядка блоков в файле. Не приведет ли это к существенному снижению производительности?
Информация о том, что где лежит доступна только внутри ядра. Вся надежда была как раз на функции типа aio_read, поскольку они в работают ядре, то как раз могут осуществлять нужное преобразование и подрюхивание.
>> Например, если нужные блоки 0,2,4,6,8 то можно прочитать блоки 0-8, а
>> потом выбрать нужные.
>С этим, по идее, должна справиться ОС.
Насчет чтения промежуточных блоков - где найти инфу о том, работает оно или не работает (и в каких syscall-ах как)
> мне кажется тут лучше всего сделать через mmap
Страницы будут подгружаться по мере обращений, то есть это эвкивалентно обычным последовательным read-ам.
> а в 2.6 появился remap_file_pages - create a non-linear file mapping
> вот только интересно какая стратегия у ядра загрузки страниц,
> было бы замечательно если оно в очередь на загрузку ставило сразу же после ммап
Фича, безусловно, очень интересная. Но с другой стороны - есть четкое ощущение, что задача эта очень стара, ее начали решать еще в каких-нибудь 1960-х годах. Очень странно, что для решения такой типичной задачи нужно использовать такие сверхновые средства. Как например, эту проблему решают в BSD? Solaris? Windows?
Страницы будут подгружаться по мере обращений, то есть это эвкивалентно обычным последовательным read-ам.
> а в 2.6 появился remap_file_pages - create a non-linear file mapping
> вот только интересно какая стратегия у ядра загрузки страниц,
> было бы замечательно если оно в очередь на загрузку ставило сразу же после ммап
Фича, безусловно, очень интересная. Но с другой стороны - есть четкое ощущение, что задача эта очень стара, ее начали решать еще в каких-нибудь 1960-х годах. Очень странно, что для решения такой типичной задачи нужно использовать такие сверхновые средства. Как например, эту проблему решают в BSD? Solaris? Windows?
> Из-за фрагментации и других причин порядок блоков на диске может
> существенно отличаться от порядка блоков в файле. Не приведет ли это к
> существенному снижению производительности?
Хуже случайного порядка не будет.
Но слишком уж хитроумные алгоритмы именно поэтому не помогут.
Поэтому я и написал - простейший элеватор.
> Вся надежда была как раз на функции типа aio_read, поскольку они в
> работают ядре, то как раз могут осуществлять нужное преобразование и
> подрюхивание.
По крайней мере в линуксе aio_* делает примерно то же самое, но внутри библиотеки и/или ядра, и вроде бы без возможности контроля за числом потоков.
> Насчет чтения промежуточных блоков - где найти инфу о том, работает
> оно или не работает
Это обязанность механизмов read-ahead и elevator.
> существенно отличаться от порядка блоков в файле. Не приведет ли это к
> существенному снижению производительности?
Хуже случайного порядка не будет.
Но слишком уж хитроумные алгоритмы именно поэтому не помогут.
Поэтому я и написал - простейший элеватор.
> Вся надежда была как раз на функции типа aio_read, поскольку они в
> работают ядре, то как раз могут осуществлять нужное преобразование и
> подрюхивание.
По крайней мере в линуксе aio_* делает примерно то же самое, но внутри библиотеки и/или ядра, и вроде бы без возможности контроля за числом потоков.
> Насчет чтения промежуточных блоков - где найти инфу о том, работает
> оно или не работает
Это обязанность механизмов read-ahead и elevator.
> Но с другой стороны - есть четкое ощущение, что задача эта очень стара, ее
> начали решать еще в каких-нибудь 1960-х годах.
Осмелюсь предположить, что в 60х годах "очень большие" файлы были на лентах, и тогдашние алгоритмы сейчас не применимы.
А чуть попозже делали тоже просто - читали наверное по одному блоку за раз, и не парились - памяти-то тоже было немного, чтоб расбрасываться на большие буфера и кеши, и сложные алгоритмы.
> начали решать еще в каких-нибудь 1960-х годах.
Осмелюсь предположить, что в 60х годах "очень большие" файлы были на лентах, и тогдашние алгоритмы сейчас не применимы.
А чуть попозже делали тоже просто - читали наверное по одному блоку за раз, и не парились - памяти-то тоже было немного, чтоб расбрасываться на большие буфера и кеши, и сложные алгоритмы.
>Также очень желательно, чтобы блоки читались в порядке возрастания номера дорожки диска, чтобы минимизировать время передвижения головки диска.
то что ты хочешь реализуется в SCSI и SATA-NCQ.
если бы было просто реализовать реализовать эту оптимизацию програмно в ядре - стали бы это в железе городить?
то что ты хочешь реализуется в SCSI и SATA-NCQ.
если бы было просто реализовать реализовать эту оптимизацию програмно в ядре - стали бы это в железе городить?
Учи матчасть, чуве.
Оптимизации в железе не смогут полностью заменить элеватор в ОС, равно как и наоборот.
Оптимизации в железе не смогут полностью заменить элеватор в ОС, равно как и наоборот.
Я бы посмотрел в исходники уже существующих приложений. Ну например gigabase.
точно не уверен, но похоже gigabase читает страницы по необходимости обычными read-ом (файл gigabase/pagepool.cpp:122).
Драйвер сам производит слияние идущих подряд блоков и хранит их в нужном порядке. Есть несколько стратегий для elevator'ов, их можно выбрать в опциях ядра. Чем они отличаются, не знаю. Пользовательская функция не имеет доступа к физическим номерам блоков, поэтому ничего серьезного она сделать не сможет.
Если файл сильно фрагментирован, то все это имеет мало смысла. С другой стороны все ФС стараются разместить файл пооптимальнее, поэтому вероятность, что блоки идут подряд на диске велика. Смысла читать в память лишние мегабайты нет, на мой взгляд.
Если файл сильно фрагментирован, то все это имеет мало смысла. С другой стороны все ФС стараются разместить файл пооптимальнее, поэтому вероятность, что блоки идут подряд на диске велика. Смысла читать в память лишние мегабайты нет, на мой взгляд.
Оставить комментарий
Landstreicher
Такая задача: есть большой файл (много гигабайт). Он состоит из блоков (для простоты путь размер блока равен 4096 или 512). Есть массив чисел a_1 < a_2 < a_3 < ... < a_N. Нужно прочитать блоки с номерами a_1, a_2, ... a_N.Как лучше всего это сделать? Основной критерий - производительность.
Разрешается сделать небольшой оверхед по памяти (до M мегабайт). Например, если нужные блоки 0,2,4,6,8 то можно прочитать блоки 0-8, а потом выбрать нужные.
Также очень желательно, чтобы блоки читались в порядке возрастания номера дорожки диска, чтобы минимизировать время передвижения головки диска.
В процессе изучения документации возникли такие вопросы:
1) Делает ли функция readv подобные оптимизации (переупорядочение по возрастанию дорожек + слияние или она делает все по порядку и просто экономит на syscall-ах?
2) То же вопрос про функции вида aio_read, aio_suspend?
3) Тот же вопрос про io_submit, io_getevents?
4) Предыдущие функции привязаны к Linux. Какой есть переносимый способ решить подобную задачу?