Самый быстрый способ считать каждый 30-й байт большого двоичного файла?
Что самый быстрый путь состоит в том, чтобы считать каждый 30-й байт большого двоичного файла (2-3 ГБ)? Я читал существуют проблемы производительности с fseek из-за буферов ввода-вывода, но я не хочу читать 2-3 ГБ данных в память прежде, чем захватить каждый 30-й байт также.
7 ответов
Тест производительности. Если вы хотите использовать его самостоятельно, обратите внимание, что проверка целостности (общая печать) работает только в том случае, если «шаг» делит BUFSZ, а MEGS достаточно мал, чтобы вы не читали конец файла. Это происходит из-за (а) лени, (б) желания не заслонять реальный код. rand1.data - это несколько ГБ, скопированные из / dev / urandom с использованием dd .
#include <stdio.h>
#include <stdlib.h>
const long long size = 1024LL*1024*MEGS;
const int step = 32;
int main() {
FILE *in = fopen("/cygdrive/c/rand1.data", "rb");
int total = 0;
#if SEEK
long long i = 0;
char buf[1];
while (i < size) {
fread(buf, 1, 1, in);
total += (unsigned char) buf[0];
fseek(in, step - 1, SEEK_CUR);
i += step;
}
#endif
#ifdef BUFSZ
long long i = 0;
char buf[BUFSZ];
while (i < size) {
fread(buf, BUFSZ, 1, in);
i += BUFSZ;
for (int j = 0; j < BUFSZ; j += step)
total += (unsigned char) buf[j];
}
#endif
printf("%d\n", total);
}
Результаты:
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=20 && time ./buff2
83595817
real 0m1.391s
user 0m0.030s
sys 0m0.030s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=20 && time ./buff2
83595817
real 0m0.172s
user 0m0.108s
sys 0m0.046s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=20 && time ./buff2
83595817
real 0m0.031s
user 0m0.030s
sys 0m0.015s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=20 && time ./buff2
83595817
real 0m0.141s
user 0m0.140s
sys 0m0.015s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DSEEK -DMEGS=20 && time ./buff2
83595817
real 0m20.797s
user 0m1.733s
sys 0m9.140s
Резюме:
Сначала я использую 20 МБ данных, которые, конечно же, помещаются в кеш. Первый раз, когда я его читаю (с использованием буфера 32 КБ), занимает 1,4 секунды, помещая его в кеш. Второй раз (с использованием 32-байтового буфера) занимает 0,17 с. Третий раз (снова с буфером 32 КБ) занимает 0,03 секунды, что слишком близко к степени детализации моего таймера, чтобы иметь смысл. fseek занимает более 20 секунд, , даже если данные уже находятся в дисковом кэше .
На этом этапе я вытаскиваю fseek из кольца, чтобы два других могли продолжить:
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=1000 && time ./buff2
-117681741
real 0m33.437s
user 0m0.749s
sys 0m1.562s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=1000 && time ./buff2
-117681741
real 0m6.078s
user 0m5.030s
sys 0m0.484s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=1000 && time ./buff2
-117681741
real 0m1.141s
user 0m0.280s
sys 0m0.500s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=1000 && time ./buff2
-117681741
real 0m6.094s
user 0m4.968s
sys 0m0.640s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=1000 && time ./buff2
-117681741
real 0m1.140s
user 0m0.171s
sys 0m0.640s
1000 МБ данных также, по-видимому, в значительной степени кэшированы. Буфер 32 КБ в 6 раз быстрее, чем буфер 32 байта. Но разница во времени пользователя, а не во времени, затраченном на дисковый ввод-вывод. Теперь 8000MB - это намного больше, чем у меня RAM, поэтому я могу избежать кеширования:
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=8000 && time ./buff2
-938074821
real 3m25.515s
user 0m5.155s
sys 0m12.640s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=8000 && time ./buff2
-938074821
real 3m59.015s
user 1m11.061s
sys 0m10.999s
$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=8000 && time ./buff2
-938074821
real 3m42.423s
user 0m5.577s
sys 0m14.484s
Игнорируйте первую из этих трех, она выиграла от того, что первые 1000MB файла уже были в RAM.
Теперь версия с 32 КБ только немного быстрее по времени настенных часов (и меня не беспокоит повторный запуск, поэтому давайте пока проигнорируем это), но посмотрите на разницу во времени user + sys: 20-е против 82-х.Я думаю, что спекулятивное кэширование диска с упреждающим чтением в моей ОС спасло здесь 32-байтовый буферный буфер: пока 32-байтовый буфер медленно пополняется, ОС загружает следующие несколько секторов диска, хотя их никто не просил. Я подозреваю, что без этого он был бы на минуту (20%) медленнее, чем буфер 32 КБ, который тратит меньше времени в пользовательском пространстве перед запросом следующего чтения.
Мораль истории: стандартная буферизация ввода-вывода не сокращает ее в моей реализации, производительность fseek ужасна, как говорит собеседник. Когда файл кэшируется в ОС, размер буфера имеет большое значение. Когда файл не кэшируется в ОС, размер буфера не имеет большого значения для времени настенных часов, но мой процессор был более загружен.
Фундаментальное предложение incrediman об использовании буфера чтения жизненно важно, поскольку fseek ужасен. Спорить о том, должен ли буфер составлять несколько КБ или несколько сотен КБ, на моей машине, скорее всего, бессмысленно, вероятно потому, что ОС сделала работу по обеспечению жесткой привязки операции к вводу-выводу. Но я почти уверен, что это связано с упреждающим чтением с диска ОС, а не со стандартной буферизацией ввода-вывода, потому что, если бы это было последнее, то fseek был бы лучше, чем он есть. На самом деле может случиться так, что стандартный ввод-вывод выполняет упреждающее чтение, но слишком простая реализация fseek каждый раз отбрасывает буфер. Я не изучал реализацию (и я бы не смог проследить ее за границей в ОС и драйверы файловой системы, если бы я это сделал).
Ну, вы можете прочитать байт, а затем искать 29 байт в цикле. Но подсистема ввода-вывода должна читать из файла по секторам, размер которых обычно составляет 512 байт, поэтому в итоге все равно будет прочитан весь файл.
В конечном счете, будет быстрее просто прочитать весь файл кусками, кратными размеру вашего шага, а затем просто посмотреть в буфер. Вы немного упростите себе жизнь, если убедитесь, что размер буфера кратен 30, и облегчите жизнь подсистеме fileio, если он будет кратен 512.
while (still more file to read)
{
char buf[30 * 512];
int cread = fread (buf, sizeof(buf), 1, fd);
for (int ii = 0; ii < cread; ii += 30)
{
}
}
Это может показаться неэффективным, но это будет быстрее, чем пытаться читать 30-байтовыми кусками.
Кстати. Если вы работаете под Windows и готовы учитывать особенности ОС, то производительность файлов, отображаемых в памяти, действительно не превзойти. Как сканировать действительно огромные файлы на диске?
Я бы посоветовал вам создать буфер на несколько тысяч байтов, прочитать из него каждый 30-й байт, перезагрузить буфер следующими несколькими тысячами байтов и продолжать, пока не достигнете eof. Таким образом, объем данных, считываемых в память, ограничен, и вам также не придется так часто читать из файла. Вы обнаружите, что чем больше буфер вы создаете, тем быстрее он будет.
Правка: На самом деле, как предлагается ниже, вы, вероятно, захотите сделать свой буфер размером в несколько сотен килобайт, а не несколько тысяч байтов (как я уже сказал - больший буфер = более быстрое чтение файла).
Если вы готовы выйти из ANSI-C и использовать вызовы, специфичные для ОС, я бы рекомендовал использовать файлы с отображением памяти. Это версия для Posix (Windows имеет свои собственные вызовы, специфичные для ОС):
#define MAPSIZE 4096
int fd = open(file, O_RDONLY);
struct stat stbuf;
fstat(fd, &stbuf);
char *addr = 0;
off_t last_mapped_offset = -1;
off_t idx = 0;
while (idx < stbuf.st_size)
{
if (last_mapped_offset != (idx / MAPSIZE))
{
if (addr)
munmap(addr, MAPSIZE);
last_mapped_offset = idx / MAPSIZE;
addr = mmmap(0, MAPSIZE, PROT_READ, MAP_FILE, fd, idx, last_mapped_offset);
}
*(addr + (idx % MAPSIZE));
idx += 30;
}
munmap(addr, MAPSIZE);
close(fd);
Вся цель библиотеки буферизованного ввода-вывода - избавить вас от подобных проблем. Если вам нужно прочитать каждый 30-й байт, ОС будет читать весь файл, потому что ОС читает большими кусками. Вот ваши варианты, от максимальной до самой низкой:
Если у вас большое адресное пространство (т. Е. Вы используете 64-битную ОС на 64-битном оборудовании), то используйте ввод-вывод с отображением памяти (
mmapв системах POSIX) сэкономит вам затраты на копирование данных ОС из пространства ядра в пространство пользователя. Эта экономия может быть значительной.Как показано в подробных примечаниях ниже (и спасибо Стиву Джессопу за тест), если вам важна производительность ввода-вывода, вам следует загрузить библиотеку sfio Phong Vo из группы AT&T Advanced Software Technology. Она безопаснее, лучше спроектирована и быстрее стандартной библиотеки ввода-вывода C. В программах, которые часто используют
fseek, он значительно быстрее: до семи раз быстрее на простом микротест.Просто расслабьтесь и используйте
fseekиfgetc, которые разработаны и реализованы как раз для решения вашей проблемы.
Если вы серьезно относитесь к этой проблеме, вам следует измерить все три альтернативы . Стив Джессоп и я показали, что использование fseek медленнее, а если вы используете библиотеку GNU C, fseek будет на много медленнее. Вы должны измерить mmap ; он может быть самым быстрым из всех.
Приложение: вы хотите заглянуть в свою файловую систему и убедиться, что она может быстро снять 2–3 ГБ с диска. XFS может, например, превзойти ext2. Конечно, если вы застряли с NTFS или HFS +, это будет медленно.
Шокирующие результаты только в
Я повторил измерения Стива Джессопа на Linux. Библиотека GNU C выполняет системный вызов при каждом fseek . Если этого не требует POSIX по какой-либо причине, это безумие. Я мог пережевывать кучу нулей и единиц и блевать лучшую буферизованную библиотеку ввода-вывода, чем эта. В любом случае затраты увеличиваются примерно в 20 раз, большая часть которых тратится на ядро. Если вы используете fgetc вместо fread для чтения отдельных байтов, вы можете сэкономить около 20% на небольших тестах.
Менее шокирующие результаты с приличной библиотекой ввода-вывода
Я снова провел эксперимент, на этот раз используя библиотеку Phong Vo sfio . Чтение 200 МБ занимает
- 0,15 с без использования
fseek(BUFSZсоставляет 30 кБ) - 0,57 с с использованием
fseek
Повторные измерения показывают, что без fseek , использование sfio по-прежнему сокращает время выполнения примерно на 10%, но время выполнения очень шумное (почти все время тратится в ОС).
На этом компьютере (ноутбуке) у меня недостаточно свободного места на диске для работы с файлом, который не помещается в кеш диска, но я готов сделать следующие выводы:
Используя разумный I Библиотека / O,
fseekдороже, но не дороже , достаточно , чтобы иметь большое значение (4 секунды, если все, что вы делаете, это ввод-вывод).Проект GNU не предоставляет разумную библиотеку ввода-вывода. Как это часто бывает, программа GNU - отстой.
Заключение: если вам нужен быстрый ввод-вывод, первым делом нужно заменить библиотеку ввода-вывода GNU библиотекой AT&T sfio . Другие эффекты, вероятно, будут небольшими по сравнению.
Вам почти наверняка не стоит об этом беспокоиться. Среда выполнения вполне может буферизовать последний прочитанный блок для каждого дескриптора файла. Даже если это не так, операционная система кэширует доступ к файлам за вас.
При этом, если вы читаете блок за раз, вы действительно экономите на вызовах функций fseek и fread. Чем больше блок, который вы читаете за один раз, тем больше вы экономите на накладных расходах, хотя другие затраты, очевидно, начинают сказываться после определенного момента.
Если вы читаете данные с жесткого диска с вращающейся тарелкой, ответ заключается в том, что вы читаете весь файл последовательно, используя большой буфер, и отбрасываете ненужные части в память.
Наименьшей единицей доступа, возможной для стандартного жесткого диска, является сектор. Размер сектора для всех распространенных вращающихся дисков во много раз превышает 30 байт. Это означает, что контроллер жесткого диска должен получить доступ к каждому сектору в любом случае, независимо от того, как выглядит запрос от хоста. Нет никакой низкоуровневой магии, чтобы изменить это.
Даже если бы это было не так, и вы могли бы читать отдельные байты, существует огромная премия за операции поиска по сравнению с последовательным чтением. Наилучший возможный случай все равно такой же, как и при последовательном чтении. В реальном мире я не удивлюсь, если накладные расходы на сигнализацию исключат работу таких схем даже с массивным буфером команд.