Как fseek() реализован в файловой системе?
Это не просто вопрос программирования, однако он влияет на производительность программ, использующих fseek(), поэтому важно знать, как он работает. Небольшой отказ от ответственности, чтобы он не закрывался.
Мне интересно, насколько эффективно вставить данные в середину файла. Предположим, у меня есть файл с данными 1 МБ, а затем я вставляю что-то со смещением 512 КБ. Насколько это эффективно по сравнению с добавлением моих данных в конец файла? Просто чтобы завершить пример, скажем, я хочу вставить 16 КБ данных.
Я понимаю, что ответ варьируется в зависимости от файловой системы, однако я предполагаю, что методы, используемые в общих файловых системах, очень похожи, и я просто хочу получить правильное представление об этом.
6 ответов
(отказ от ответственности: я хочу просто добавить несколько подсказок к этой интересной дискуссии) ИМХО есть некоторые вещи, которые следует принять во внимание:
1) fseek - не основная системная служба, а библиотечная функция. Чтобы оценить его производительность, мы должны рассмотреть, как реализована библиотека файлового потока. В общем, библиотека файлового ввода-вывода добавляет слой буферизации в пользовательском пространстве, поэтому производительность fseek может сильно отличаться, если целевая позиция находится внутри или вне текущего буфера. Кроме того, системные службы, которые использует библиотека ввода-вывода, могут сильно различаться. Т.е. в некоторых системах библиотека широко использует отображение файловой памяти, если это возможно.
2) Как вы сказали, разные файловые системы могут вести себя по-разному. В частности, я ожидал бы, что транзакционная файловая система должна сделать что-то очень умное и, возможно, дорогое, чтобы подготовиться к возможному откату прерванной операции записи в середине файла.
3) Современные ОС имеют очень агрессивные алгоритмы кеширования. Вероятно, файл "fseeked" уже присутствует в кеше, поэтому операции становятся намного быстрее. Но они могут сильно ухудшиться, если общая активность файловой системы, вызванная другими процессами, станет важной.
Любые комментарии?
Давайте возьмем в качестве примера ext2 FS и ОС Linux. Я не думаю, что будет существенная разница в производительности между вставкой и дополнением. В обоих случаях должны быть прочитаны узел файлов и таблица смещений, соответствующий сектор диска сопоставлен с памятью, данные обновлены, а в какой-то момент позже данные записаны на диск. В этом примере большая разница в производительности - это хорошая временная и пространственная локальность при доступе к частям файла, поскольку это уменьшит количество комбинаций загрузки / сохранения.
Как говорилось в предыдущих ответах, вы можете ускорить обе операции, если будете иметь дело с записью данных, которая кратна размеру блока FS, в этом случае вы можете пропустить этап загрузки и просто вставить новые блоки в структуру данных inode файлов. Это не будет практично, так как вам потребуется низкоуровневый доступ к драйверу FS, и его использование будет очень ограничительным и непереносимым.
fseek(...) это библиотечный вызов, а не системный вызов ОС. Это библиотека времени выполнения, которая заботится о фактических издержках, связанных с выполнением системного вызова ОС, технически говоря, fseek косвенно выполняет вызов системы, но на самом деле это не так (это приводит к четкому различию между различия между вызовом библиотеки и системным вызовом). fseek(...) является стандартной функцией ввода-вывода независимо от базовой системы... однако... и это большая, однако...
Скорее всего, ОС будет кэшировать файл в своей памяти ядра, то есть прямое смещение к месту на диске, где хранятся единицы и 0, это происходит через уровни ядра ОС, скорее всего, самый верхний слой в ядре, который будет иметь моментальный снимок того, из чего состоит файл, то есть данные независимо от того, что он содержит (это не волнует в любом случае, пока "указатели" на структуру диска для этого смещения в Расположение на диске действительно!)...
когда fseek(..) происходит, будет много накладных расходов, косвенно, ядро делегировало задачу чтения с диска, в зависимости от того, насколько фрагментирован файл, теоретически это может быть "повсюду", что может быть значительным накладные расходы с точки зрения необходимости, с точки зрения пользователя земли, то есть код C делает fseek(...), это может быть разбросано по всему месту, чтобы собрать данные в "одно смежное представление данных" и впредь вставлять в середину файла (помните, что на этом этапе ядру придется корректировать местоположение / смещения в фактическое дисковое пространство для данных) будет считаться медленнее, чем добавление в конец файла.
Причина проста: ядро "знает", каким было последнее смещение, и просто стереть маркер EOF и вставить больше данных, за кадром ядру приходится выделять еще один блок памяти для дискового буфера с скорректированное смещение к месту на диске после маркера EOF после завершения добавления данных.
Одно наблюдение, которое я сделал о fseek в Solaris каждый вызов к нему сбрасывает буфер чтения FILE, Следующее чтение будет всегда читать полный блок (8K по умолчанию). Так что, если у вас много произвольного доступа с небольшими чтениями, неплохо бы сделать это без буфера (setvbuf с NULL буфер) или даже использовать прямые системные вызовы (lseek+read или даже лучше pread что составляет только 1 системный вызов вместо 2). Я полагаю, что это поведение будет аналогичным на других ОС.
Вы можете эффективно вставлять данные в середину файла, только если размер данных кратен сектору FS, но операционные системы не предоставляют таких функций, поэтому вы должны использовать низкоуровневый интерфейс для драйвера FS.
Вставка данных в середину файла менее эффективна, чем добавление в конец, потому что при вставке вам придется перемещать данные после точки вставки, чтобы освободить место для вставляемых данных. Перемещение этих данных потребовало бы чтения их с диска, записи данных для вставки, а затем записи старых данных после вставленных данных. Таким образом, у вас есть по крайней мере одно дополнительное чтение и запись при вставке.