Подтвердить что ты не робот

Самый быстрый способ читать каждый 30-й байт большого двоичного файла?

Каков самый быстрый способ прочитать каждый 30-й байт большого двоичного файла (2-3 ГБ)? Я читал, что есть проблемы производительности с fseek из-за буферов ввода-вывода, но я не хочу читать 2-3 ГБ данных в памяти, прежде чем хватать каждый 30-й байт.

4b9b3361

ОТВЕТЫ

Ответ 1

Тест производительности. Если вы хотите использовать его самостоятельно, обратите внимание, что проверка целостности (общая сумма печати) работает только в том случае, если "шаг" делит BUFSZ, а MEGS достаточно мал, чтобы вы не читали конец файла. Это связано с (а) лень, (б) желание не скрывать реальный код. rand1.data - это несколько GB, скопированных из /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-байтовый буфер. Но разница - это все время пользователя, а не время, затраченное на блокирование ввода-вывода на диске. Теперь 8000 МБ намного больше, чем у меня есть ОЗУ, поэтому я могу избежать кэширования:

$ 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

Игнорировать первый из этих трех, он выиграл от первого 1000 МБ файла, уже находящегося в ОЗУ.

Теперь версия с 32 Кбайт только немного быстрее в часы настенных часов (и меня не беспокоит повторное выполнение, поэтому пока не будем игнорировать ее), но посмотрите на разницу в времени пользователя + sys: 20s против 82s. Я думаю, что мое кэширование кэшей с предварительным чтением ОС для ОС было сохранено здесь 32-байтовым буфером: в то время как 32-байтовый буфер медленно пополняется, ОС загружает следующие несколько дисковых секторов, хотя никто их не просил. Без этого я подозреваю, что это была бы минута (20%) медленнее, чем буфер 32 КБ, который тратит меньше времени на пользовательскую землю, прежде чем запрашивать следующее чтение.

Мораль истории: стандартная буферизация ввода-вывода не сокращает ее в моей реализации, производительность fseek ужасна, как говорит собеседник. Когда файл кэшируется в ОС, размер буфера - большое дело. Когда файл не кэшируется в ОС, размер буфера не имеет большого значения для настенных часов, но мой процессор был более занят.

Нельзя сказать, что фундаментальное предложение использовать буфер чтения жизненно важно, так как fseek ужасно. Рассуждая о том, должен ли буфер быть несколько КБ или несколько сотен КБ, скорее всего, бессмысленны на моей машине, возможно, потому, что ОС выполнила задачу обеспечения жесткой привязки ввода/вывода. Но я уверен, что это не так, как на диске с ОС, а не на стандартную буферизацию ввода-вывода, потому что если бы это был последний, то fseek был бы лучше, чем есть. На самом деле, может случиться так, что стандартный ввод-вывод выполняет чтение вперед, но слишком простая реализация fseek каждый раз отбрасывает буфер. Я не изучал реализацию (и я не мог следовать за ней через границу в ОС и драйверы файловой системы, если бы сделал это).

Ответ 2

Я бы предположил, что вы создаете буфер из нескольких тысяч байт, читаете каждый 30-й байт, перезагружаете буфер несколькими тысячами байтов и продолжаете, пока не достигнете eof. Таким образом, количество данных, считываемых в память, ограничено, и вам также не нужно читать из файла так часто. Вы обнаружите, что чем больше создаваемый буфер, тем быстрее он будет.

Изменить: на самом деле, как это предлагается ниже, вы, вероятно, захотите сделать свой буфер несколько сотен килобайт, а не несколько тысяч байтов (например, я сказал - больший буфер = более быстрый просмотр файла).

Ответ 3

Ну, вы можете прочитать байт, а затем запросить 29 байтов в цикле. Но подсистема IO должна читать из файла по секторам, размер которых обычно составляет 512 байт, поэтому он все равно будет читать весь файл.

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

Ответ 4

Если вы хотите выйти из 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);

Ответ 5

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

  • Если у вас большое адресное пространство (то есть вы используете 64-разрядную ОС на 64-разрядном оборудовании), то использование IO (mmap с отображением памяти в системах POSIX) сэкономит вам стоимость копирования данных ОС из пространства ядра в пространство пользователя. Эта экономия может быть значительной.

  • Как показано в подробных примечаниях ниже (и благодаря Стив Джессопу для теста), если вы заботитесь о производительности ввода/вывода, вы должны скачать Phong Vo sfio library из группы AT & T Advanced Software Technology. Он безопаснее, лучше разработан и быстрее, чем стандартная библиотека ввода-вывода C. В программах, которые используют fseek много, это значительно быстрее: до семи раз быстрее на простой микрофункции.

  • Просто расслабьтесь и используйте fseek и fgetc, которые разработаны и реализованы точно для решения вашей проблемы.

Если вы серьезно относитесь к этой проблеме, вы должны измерить все три альтернативы. Стив Джессоп и я показали, что использование fseek происходит медленнее, и если вы используете библиотеку GNU C, fseek намного медленнее. Вы должны измерить mmap; это может быть самый быстрый из всех.

Приложение: вы хотите заглянуть в свою файловую систему и убедиться, что она может быстро вытащить 2 диска с диска. Например, XFS может бить ext2. Конечно, если вы застряли в NTFS или HFS +, это будет медленным.

Шокирующие результаты только в

Я повторил измерения Стива Джессопа в Linux. Библиотека GNU C делает системный вызов на каждом fseek. Если POSIX не требует этого по какой-то причине, это безумие. Я мог бы пережевывать кучу и нулей, а также лучше использовать буферную библиотеку ввода-вывода. Во всяком случае, затраты растут примерно в 20 раз, большая часть которых израсходована на ядро. Если вы используете fgetc вместо fread для чтения одиночных байтов, вы можете сэкономить около 20% на небольших тестах.

Менее шокирующие результаты с приличной библиотекой ввода/вывода

Я снова повторил эксперимент, на этот раз используя библиотеку Phong Vo sfio. Чтение 200 МБ занимает

  • 0.15 с без использования fseek (BUFSZ равно 30k)
  • 0.57 с помощью fseek

Повторные измерения показывают, что без fseek, используя sfio, все еще бреет около 10% от времени выполнения, но время работы очень шумное (почти все время тратится в ОС).

На этом компьютере (ноутбуке) мне не хватает свободного места на диске для работы с файлом, который не поместится в кэш диска, но я готов сделать следующие выводы:

  • Используя разумную библиотеку ввода-вывода, fseek является более дорогим, но не более дорогим, чтобы иметь большое значение (4 секунды, если все, что вы делаете, это ввод-вывод).

  • Проект GNU не обеспечивает разумную библиотеку ввода-вывода. Как это часто бывает, программное обеспечение GNU отстойно.

Заключение: , если вам нужен быстрый ввод-вывод, первым шагом должен стать замена библиотеки ввода-вывода GNU библиотекой AT & T sfio. Другие эффекты, вероятно, будут незначительными по сравнению.

Ответ 6

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

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

Ответ 7

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

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

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