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