Рэймонд Чен. Почему драйвер называется FASTFAT.SYS? И где SLOWFAT?
Оригинал: Why is the FAT driver called FASTFAT? Why would anybody ever write SLOWFAT?
Анонимный комментатор спросил: почему драйвер FAT называется FASTFAT.SYS? И был ли до этого медленный драйвер FAT? И что плохого в первой реализации FAT, что её выкинули?
Первый драйвер, видимо, звался скучным именем FAT.SYS. Однажды кто-то решил написать новый драйвер, побыстрее, и назвал его FASTFAT. И имя прилипло.
На что вообще нужно переписывать реализацию FAT? Не забывайте, обстоятельства со временем меняются. Конструкция, замечательно работавшая в одних условиях, прогнётся в других. Дело не в том, что прежний FAT был плохой, просто в новых условиях новый FAT лучше.
Давным-давно были три версии FAT: FAT8, FAT12 и FAT16. Для маленьких дисков простые алгоритмы нормально работали. И, вообще-то, они даже лучше - их проще писать и проще отлаживать. А ещё они расходуют меньше памяти (а тогда она была на вес золота). Алгоритм, работающий за O(n), небольшая помеха, если n невелико и мала константа. Так как в FAT16 65535 кластеров на диск, вот вам предел на n. Если в типичном каталоге всего несколько десятков файлов, линейного просмотра более чем хватает.
Естественно выбирать такие алгоритмы, которые напрямую переносятся на дисковые структуры данных (помните - алгоритмы определяются структурами данных?) Каталог FAT - просто несортированный массив имён, так что функция поиска по каталогу просмотрит его по одной штуке, пока не найдёт нужное имя. Найти свободный кластер - это просто отыскать 0 в таблице размещения. Управление памятью простейшее: и не пытайся, свали работу на дисковый кэш.
И эти простенькие алгоритмы работали, пока FAT32 не поднялся на n небес. К тому времени и компьютеры были побыстрее, и памяти было больше, так что места на амбиции уже хватало.
Главная выгода от FASTFAT произошла из алгоритмических изменений. Например, дисковые структуры данных загружаются в память, преобразуются в более эффективный вид и кэшируются. Первый раз, когда вы проходите по каталогу, нужен линейный поиск, чтобы собрать все имена файлов. Но затем имена кэшируются (скажем, в хэш-таблице), и дальнейшие операции с каталогом ускоряются. А поскольку памяти много, можно позволить держать кэш каталогов - в отличие от тех времён, когда памяти не хватало и большие кэши отпадали.
(Хотел бы я узнать, как работают чужие драйверы FAT: делают такую оптимизацию или просто идут «в лоб» и работают в памяти с теми же структурами данных, что и на диске.)
Подытожим. Исходный драйвер FAT хорошо решал те задачи, под которые он писался, если оставаться в тех ограничениях, которые тогда были. Со временем задача изменилась, и старые решения не помогали. И, я думаю, пусть каждый сам ответит на вопрос «было ли это плохо». Если ребёнок вырос из детской кроватки, значит ли это, что кроватка - это ужасная ошибка?