Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Несколько ускоренный способ сканирования директории.

Страницы: 1 2 >
Riply © (2007-10-14 21:09:00)
Здравствуйте !
Т.к. последнее время эта тема стала популярной на форуме, решила
попробовать посмотреть на нее с точки зрения Naitive API.
(Если честно, то мне самой это понадобилось для сравнительного анализа
и контроля моих MFT-творений и изучения "как это делают другие" :)
Почитала, что по этому поводу говорят в интернете.
Во всех местах (которые я сумела найти) приходят к одному и тому-же
выводу: "Этим путем - не ускориться".

Давайте попробуем усомниться в этом ? :)
(Усомняться мы будем, подглядывая в исходники Игоря Шевченко :)
Сначала определим структуру в которой будем хранить данные
для каждого объекта. Она должна быть очень маленькой.
Ведь если мы сканируем диск с миллионом объектов, то увеличение ее размера
всего на один байт съест целый мегабайт памяти.

OBJ_DATA_INF0 = record case Integer of 0: (ChildCount: DWORD; FirstChildOffset: DWORD); // для директорий 1: (SizeOfData: LONGLONG); // для файлов и файловых потоков end; _NAMED_QUERY_OBJECT = packed record OffsetNextEntry : Word; // Смещение на следующий блок ObjAttributes : ULONG; // Атрибуты объекта ExternalData : OBJ_DATA_INF0; ObjNameLength : Word; // нилл-терминайт не считаем. ObjName : array[0..0] of Byte; end;
(Здесь оставлен простор для уменьшения :)
Например, в ExternalData.SizeOfData предполагается хранить размер файла.
Но для него вполне хватит и 48 бит. Так что туда можно запихать ObjNameLength
и сэкономить аж целых два байта :) Так же можно уменьшить и ObjAttributes,
переопределив, какие и сколько нам надо.
"Оставляю это заинтересованным лицам" (с) Leonid Troyanovsky

И заодно пара функций для расчета размера записи и выравнивания его до SizeOf(DWord)
(Мудрые люди из Microsoft выравнивают структуру FILE_BOTH_DIR_INFORMATION
до SizeOf(Int64), ну а мы (т.к. плохо понимаем "зачем и почему") остановимся на DWord :)
function NT_NameAddedSizeB(const NameLength: integer): integer; inline; begin if NameLength >= SizeOf(WideChar) then Result := NameLength - SizeOf(Byte) else Result := -1; end; function QueryObj_EdgeSize(const BytesInName: integer): integer; var Value: integer; begin Value := SizeOf(_NAMED_QUERY_OBJECT) + NT_NameAddedSizeB(BytesInName); Result := Value mod SizeOf(DWord); if Result > 0 then Result := Value + SizeOf(DWord) - Result else inc(Result, Value); end;

Ну а теперь можно и посканировать. Я приведу только схему кода,
оговорив параметры вызовов, т.к. кроме этого и обычной рекурсии в нем ничего нет :)
Используемые функции: NtQueryDirectoryFile, NtOpenFile и NtClose.

Нам понадобяться два блока памяти: для буффера, передаваемого в NtQueryDirectoryFile
и для списка наших NAMED_QUERY_OBJECT.

Попробуем оценить их размеры:
NtQueryDirectoryFile будем вызывать так:
ObjectAttr: POBJECT_ATTRIBUTES - инициализируем хендлом открытого родителя
(он у нас будет, мы же в рекурсии) и только именем файла (без пути).
NtQueryDirectoryFile(..., @ObjectAttr(POBJECT_ATTRIBUTES),...
FileDirectoryInformation(FILE_INFORMATION_CLASS), - выбор класса важен.
False(ReturnSingleEntry),...);
Мы за один вызов будем пытаться получить все объекты (ReturnSingleEntry = False),
и экономить на размере буфера не будем, т.к. его нехватка потребует не только
перевыделения памяти, но и лишнего вызова NtQueryDirectoryFile.
Такого размера: FS_OBJ_QUERY_INC_SIZE = $10000 * 8 хватает, примерно на 5000 объектов,
лежащих в корне сканируемого.
Примерная работа:
function TNtQueryObjectFS._QueryDirectoryFileMem(const ObjHandle: THandle; const InfoClass: FILE_INFORMATION_CLASS; RetSngleEntry, RestartScan: LongBool): NTSTATUS; var IoBlock: TIoStatusBlock; begin Result := NtQueryDirectoryFile(ObjHandle, FhEvent, nil, nil, @IoBlock, FpObjInfo, FcbObjInfo, InfoClass, RetSngleEntry, nil, RestartScan); while True do case Result of STATUS_BUFFER_OVERFLOW, STATUS_INFO_LENGTH_MISMATCH: begin _ReallocQueryBuffer(FcbObjInfo + FcbObjInfo); Result := NtQueryDirectoryFile(ObjHandle, FhEvent, nil, nil, @IoBlock, FpObjInfo, FcbObjInfo, InfoClass, RetSngleEntry, nil, Result = STATUS_INFO_LENGTH_MISMATCH); end; else Exit; end; end; function TNtQueryObjectFS._QueryDirectoryFile(const aOffset: DWord; const ObjHandle: THandle; const InfoClass: FILE_INFORMATION_CLASS; RetSngleEntry: LongBool): NTSTATUS; begin Result := _QueryDirectoryFileMem(ObjHandle, InfoClass, RetSngleEntry, True); while Result = STATUS_SUCCESS do begin FROOT_FIND_DATA.AddObjectsBlock(aOffset, FpObjInfo, InfoClass, FirstCall);<--Пишем наши данные Result := _QueryDirectoryFileMem(ObjHandle, InfoClass, RetSngleEntry, False); end; end;

Riply (2007-10-22 16:17:00) [1]
>[0] Riply © (14.10.07 21:09)
Хочу вернуться к нашим баранам. Тьфу... К Riply`ским баранам :)
Случайно напоролась на следующее:
Когда мы таким образом только сканируем, то выигрыш от 15 до 50 %
(зависит от "состояния" диска, соотношения кол-во файлов/кол-во директорий,
уровня вложенности, длин имен и т.д. и т.п.)
Но дело приобретает совсем другой оборот, если нам еще надо и открывать файлы:
выигрыш уже считается "в разы".
Пример теста:
Внутри FindFirst/Next работаем, примерно, так:
Handle:= CreateFileA(PChar(Buf), FILE_ANY_ACCESS, ..., OPEN_EXISTING, ...); if Handle <> INVALID_HANDLE_VALUE then CloseHandle(Handle);

В нашем же случае, я не только открывала все файлы и директории,
но еще и перебирала их потоки.
Каково же было мое удивление, когда наш вариант (вместе с потоками)
посчитался быстрее в три раза. (23891 и 8113 ms).
P.S.
Вобщем то, если вдуматься, то стоило ожидать, учитывая сколько MFT
записей придется просмотреть.

P.S.S.
Сама скорость открытия файла очень сильно зависит от уровня доступа,
который мы запрашиваем (почему - пока не знаю).
Так что не жадничайте ! :))

Такие новости с поля боя к этому часу :)

Dmitry S (2007-10-16 13:44:00) [2]
Удалено модератором
Примечание: Offtopic

Германн (2007-10-16 02:56:00) [3]

> Riply © (16.10.07 02:52) [17]
>
> >[16] Riply ©
> Напомнило. Взято из "Физики продолжают шутить"
>

Я знаю твоё знание сей замечательной книжки. И я всецело приветствую твоё стремление!

Германн (2007-10-16 02:53:00) [4]

> Поместила. Каюсь.

А я что против?
Да помещай сколько влезет. Наш форум из-за этого только станет лучше!
Но ведь это твои слова -
> А когда этот автор хочет задать вопрос, то он
> строевым шагом идет в "начинающие" и спрашивает :)
>

Или ты об обязательном наличии знака вопроса "?" ?
:-)

Riply (2007-10-16 02:52:00) [5]
>[16] Riply ©
Напомнило. Взято из "Физики продолжают шутить"
"Описание экспериментальной методики"
Фразу (в работе автора) типа:
«Для детального исследования мы выбрали три образца».
Надо понимать так:
"Результаты, полученные на остальных двадцати образцах,
не лезли ни в какие ворота".
:)

Riply (2007-10-16 02:41:00) [6]
> [15] Германн © (16.10.07 02:29)
> А разве ты свой пост не поместила в "Начинающие"?

Поместила. Каюсь. В следующий раз придеться учитывать, что только из одного
факта нахождения поста в "Начинающих" неотвратимо следует,
что в нем (посте) содержится вопрос :)

На самом деле причины были другие: Я здесь (на форуме) уже
столько "Великих Открытий" насовершала, что уже страшно что-то утверждать. :)
А то выдет как всегда :)
А в "Начинающих" - это просто попытка "начинающего" чуть поразглагольствовать на тему:)

Германн (2007-10-16 02:29:00) [7]

> Riply © (16.10.07 02:24) [14]

> P.S.
> А когда этот автор хочет задать вопрос, то он
> строевым шагом идет в "начинающие" и спрашивает :)

А разве ты свой пост не поместила в "Начинающие"?
http://www.delphimaster.ru/cgi-bin/forum.pl?id=1192381766&n=18

Riply (2007-10-16 02:24:00) [8]
> [13] Leonid Troyanovsky © (15.10.07 18:47)
> Дык, это, оказывается, был вопрос :)
> Чего сказать, хорошо завуалирован.

Нет. Это был не вопрос. Это было пояснение, что данное утверждение
взято автором с потолка и пояснить причины он пока не может. :)

P.S.
А когда этот автор хочет задать вопрос, то он
строевым шагом идет в "начинающие" и спрашивает :)
Благо опыт по вопросо-задаванию у нее имеется :)

Leonid Troyanovsky (2007-10-15 18:47:00) [9]

> Riply © (15.10.07 17:22) [12]

> на скорость не повлияет... ан нет. Причины мне не понятны

Дык, это, оказывается, был вопрос :)
Чего сказать, хорошо завуалирован.

http://rsdn.ru/?Info/Howtoask.xml
даже как-то неудобно вспоминать ;)

--
Regards, LVT.

Riply (2007-10-15 17:22:00) [10]
Для тех, кому интересно...
В [0] Riply © (14.10.07 21:09), я так скромненько упомянула:
"FileDirectoryInformation - выбор класса важен."
Пояснять "почему" не стала, что бы не бросалось в глаза, что сама не понимаю :)
Но использование, например, FileBothDirectoryInformation вместо
FileDirectoryInformation подтормаживает работу.
В структуру добавляются всего три поля, казалось бы
на скорость не повлияет... ан нет. Причины мне не понятны :(

Riply (2007-10-15 15:48:00) [11]
> [10] Ins © (15.10.07 15:42)
> Так используйте FindFirstFileW
Можно, но он не уберет преобразования DosPath ---> NtPath и обратно.
А они, в свою очередь, потребуют работы с памятью.

Ins (2007-10-15 15:42:00) [12]

> Мы же в нашем убрали все ANSI - Unicode преобразования.
> А их было-бы по два на объект. При миллионе объектов - два
> миллиона преобразований.
> Внушительно, не правда-ли ?
> Плюс, мы не таскаем за собой пути объектов и соответственно
> не преобразуем их :)

Так используйте FindFirstFileW

Riply (2007-10-15 15:39:00) [13]
> [8] Игорь Шевченко © (15.10.07 09:58)
>Не стоит думать, что систему дураки писали :)

Чем больше я изучаю систему, тем больше поражаюсь уму ее создателей.
Это без смайлика.

>Каталоги сканируются настолько быстро, насколько возможно :)

Да. Но при этом используются некоторые(вынужденные) ограничения
в угоду удобства (и надежности) ф-ий FindFirst/Next
Во-первых:
Читаем Рихтера:
"Например, функции ядра Windows 2000 выполняют все операции с использованием Unicode символов и строк
Если вызвать ANSI-версию какой-нибудь Windows-функции, ей придется, преобразовав строки ил ANSI в Unicode, вызывать свою Unicode-версию. Для преобразования строк ANSI-функции нужно выделить блок памяти,
в котором она размещает Unicode-версию строки."

Мы же в нашем убрали все ANSI - Unicode преобразования.
А их было-бы по два на объект. При миллионе объектов - два миллиона преобразований.
Внушительно, не правда-ли ?
Плюс, мы не таскаем за собой пути объектов и соответственно не преобразуем их :)

Так же Рихтер пишет о более медленном обращении к куче,
через которую идут эти преобразования.

Во-вторых:
За один запрос мы получаем сразу все корневые объекты.
В случае со стандартным сканированием, если корневых объектов 5000, то мы 5000 раз
делаем запрос, а так один. Тоже убедительно. Не правда-ли ? :)

В-третьих:
При открытии объекта, мы используем Handle его родителя, что нескольо ускоряет
поиск файловой записи в MFT

И напоследок:
Мы располагаем, полученные данные последовательно в одном блоке памяти.
Что тоже дает существенный прирост :)

Игорь Шевченко (2007-10-15 09:58:00) [14]
Riply © (14.10.07 21:09)

Не стоит думать, что систему дураки писали :) Каталоги сканируются настолько быстро, насколько возможно :)

vpbar (2007-10-15 09:58:00) [15]
Riply - ты супер. Не пойму, почему в начинающих. (Скромная наверно).
И мысль про статью действительно хорошая.
Если ты будешь публиковать свои изыскания, то лично мне это очень пригодится.
Спасибо.

Virgo_Style (2007-10-14 21:31:00) [16]
каждый раз, читая твои темы в " начинающих", я думаю - а какая же тема будет достойна обсуждения в Основной, или, избавь Тьма, в WinAPI? ))))

vasIZmax (2007-10-14 21:29:00) [17]
> Правильный Вася (14.10.07 21:23) [2]

мысли сходятся что ль?:-)

Riply (2007-10-14 21:29:00) [18]
> [2] Правильный Вася (14.10.07 21:23)
> лучше бы оформить статьей и выложить здесь же на сайте
> ведь есть такая возможность

Статьи надо уметь писать...
А я так... поразглагольствовала в "начинающих".
Если что не так, то уж очень сильно не накажут :)

vasIZmax (2007-10-14 21:28:00) [19]
//off topic
> Доводить это хозяйство "до ума" не буду

имхо, доведи как раз "до ума" (со всеми пояснениями ИШ и clickmaker`а) и получится статья, мож за одно и снимешь "занавес без статейности" на сайте:)
//off topic

Правильный Вася (2007-10-14 21:23:00) [20]
лучше бы оформить статьей и выложить здесь же на сайте
ведь есть такая возможность

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »