Экономия памяти при работе.

← →
Riply © (2008-02-01 17:16) [0]

Здравствуйте !
Допустим, нам надо просканировать диск, двумя разными способами
и сравнить результаты.
При сканировании создается блок памяти (для каждого способа),
в который записывается информация о всех найденых объектах.
Итого имеем два больших блока.
С ними и пойдет дальнейшая работа.
Средний размер записи для объекта:
AverageRecordSize 212
в него входит размер имени
AverageObjNameLen 148 (размер в байтах, само имя в UNICODE)

Допустим мы исследуем диск с миллионом объектов.
Соответсвенно нам понадобиться два блока памяти
по 212 MB (212 * 1000000), итого почти пол гигабайта.
Если же хранить имена в ANSI, то
в этом случае для работы нам будет требоваться
два блока по 138 MB (138 * 1000000), итого чуть больше четверти гигабайта.
Стоит ли ради экономии памяти переходить на хранение имен в ANSI ?
(Очень не хочеться это делать)

P.S.
Размер структуры (без имени 64 B) приведен для Debug варианта.
В реальной работе он будет примерно 36 Byte.

← →
Rouse_ © (2008-02-01 17:42) [1]

Если хранение имен не принципиально - то может имеет смысл хранить только их хэш? :)

← →
Riply © (2008-02-01 17:45) [2]

> [1] Rouse_ © (01.02.08 17:42)
> Если хранение имен не принципиально - то может имеет смысл хранить только их хэш? :)

От имен требуется толко одно:
после обработки иметь возможность показать пользователю скрытые (не стандартные объекты)

← →
Rouse_ © (2008-02-01 17:48) [3]

Храни имена в ANSII + в Short формате - еще меньше памяти бу :)

← →
Riply © (2008-02-01 17:49) [4]

> [2] Riply © (01.02.08 17:45)
Внутри программы идентификатором объекта (если он не поток)
является не имя, а номер файловой записи в MFT.

← →
Джо © (2008-02-01 17:52) [5]

Сохранить все имена во временный файл, при запросе читать оттудова поодиночке :)

← →
antonn © (2008-02-01 18:04) [6]

а имена потом нельзя вывести? :)

← →
Игорь Шевченко © (2008-02-01 18:27) [7]

Дварковать диск влэндишным способом.

> Допустим мы исследуем диск с миллионом объектов.
> Соответсвенно нам понадобиться два блока памяти
> по 212 MB (212 * 1000000), итого почти пол гигабайта.

И чего ? Тебя это так смущает ?

> От имен требуется толко одно:
> после обработки иметь возможность показать пользователю
> скрытые (не стандартные объекты)

Ну так удаляй стандартные объекты по мере их опознания. Почему бы (для NTFS, насколько я понимаю) не хранить fileno объекта вместо его имени ? А после нахождения всех "нестандартных" получать имя объекта по этому fileno ?

Или я чего-то не понимаю ?

← →
Riply © (2008-02-01 19:10) [8]

> [7] Игорь Шевченко © (01.02.08 18:27)

> Дварковать диск влэндишным способом.

А можно пояснить (перевести) эту фразу ?
Уж очень напоминает "Сильпуете ли Вы Машек валически ?" :)
(с) Искаверканная, т.к. дословно не помню.

> И чего ? Тебя это так смущает ?

Ага. Уж очень астрономические цифры получаются :)

> Ну так удаляй стандартные объекты по мере их опознания.

Блок памяти выделяется заранее (один на всех) и туда,
как кирпичики дописываются новые объекты. Так что удалить сложновато.
Такой подход обусловлен форматом данных возвращаемых используемыми Nt - функциями.

> Почему бы (для NTFS, насколько я понимаю) не хранить fileno объекта вместо его имени ?
> А после нахождения всех "нестандартных" получать имя объекта по этому fileno ?
> Или я чего-то не понимаю ?

Все верно. Думала об этом. Есть несколько "но".
Первое:
"получать имя объекта по этому fileno" не очеь быстрая операция.
Может есть какая-то ф-ия ? Потому что если "в лоб через MFT", то для объекта
придется считывать не только его запись, но и запись родителя (для вытаскивания имени родителя)
Второе:
Объекты типа STREAM идентифицируются не fileno, а именам.

← →
guav © (2008-02-01 19:14) [9]

> AverageObjNameLen 148

Т.е. 74 символа ? Многовато. Это с полными путями, что ли ?

← →
Riply © (2008-02-01 19:17) [10]

> [8] Riply © (01.02.08 19:10)
> Объекты типа STREAM идентифицируются не fileno, а именам.

Некузяво выразилась.
Объекты типа STREAM идентифицируются связкой: fileno + имя.

← →
Riply © (2008-02-01 19:19) [11]

> [9] guav © (01.02.08 19:14)
> Т.е. 74 символа ? Многовато. Это с полными путями, что ли ?

Да. Сейчас я рассматриваю вариант с полными путями.

← →
Игорь Шевченко © (2008-02-01 19:31) [12]

Riply © (01.02.08 19:10) [8]

> А можно пояснить (перевести) эту фразу ?
> Уж очень напоминает "Сильпуете ли Вы Машек валически ?"
> :)
> (с) Искаверканная, т.к. дословно не помню.

Это оттуда же. Из рассказов Роберта Шекли

> Ага. Уж очень астрономические цифры получаются :)

Так ты имена не храни и цифры сразу станут не астрономическими.

> Блок памяти выделяется заранее (один на всех) и туда,
> как кирпичики дописываются новые объекты. Так что удалить
> сложновато.
> Такой подход обусловлен форматом данных возвращаемых используемыми
> Nt - функциями.

Вряд ли Nt-функция обеспечит работу при объеме данных, превосходящем стандартные 2 гигабайта пользовательского адресного пространства. Впрочем, это можно проверить, создав каталог с несколькими миллионами мелких файлов и вызвав NtQueryDirectoryInformation, например.
Поэтому все объемы, лежащие ниже этого могут не приниматься во внимание - ну разве что своппинг будет.

> "получать имя объекта по этому fileno" не очеь быстрая операция.

Если она нечастая, то какая, собственно, беда от того, что она небыстрая ?

> Второе:
> Объекты типа STREAM идентифицируются не fileno, а именам.
>

Кто-то мешает хранить составной идентификатор ? fileno и имя потока данных, например.

Я к чему клоню - может быть, есть смысл для хранения нужных тебе объектов завести совершенно отдельную структуру.

Я понимаю, конечно, что просканировать диск два раза, загнав все содержимое его каталогов в память, это кульно и рульно, но какой смысл сравнивать %SystemRoot%\System32\Kernel32.dll с самим собой, ища каждый из них среди миллиона файлов ?
А таких сравнений всяко будет.
Не проще ли, как делает Руссинович, сравнивать содержимое конкретного каталога, полученное двумя разными способами, и хранить разницу отдельно.
Разумеется, если у тебя окажется каталог с миллионами файлов, проблемы памяти все равно будут наличествовать, но, на мой взгляд, ситуация не так часто встречающаяся, и ради редких случаев, можно и потерпеть.

← →
Riply © (2008-02-01 20:03) [13]

> [12] Игорь Шевченко © (01.02.08 19:31)

> Это оттуда же. Из рассказов Роберта Шекли
:)

> Впрочем, это можно проверить, создав каталог с несколькими миллионами мелких файлов и
> вызвав NtQueryDirectoryInformation, например.
> Поэтому все объемы, лежащие ниже этого могут не приниматься во внимание - ну разве что своппинг будет.

Попробую проверить :)

> Кто-то мешает хранить составной идентификатор ? fileno и имя потока данных, например.

> Я к чему клоню - может быть, есть смысл для хранения нужных тебе объектов завести совершенно отдельную структуру.

> Я понимаю, конечно, что просканировать диск два раза, загнав все содержимое его каталогов в память, это кульно и рульно, но какой смысл > сравнивать %SystemRoot%\System32\Kernel32.dll с самим собой, ища каждый из них среди миллиона файлов ?
> А таких сравнений всяко будет.
> Не проще ли, как делает Руссинович, сравнивать содержимое конкретного каталога,
> полученное двумя разными способами, и хранить разницу отдельно.

Самое интересное, что в работе мне имена, можно считать, не нужны.
Благо NtQueryDirectoryInformation предоставляет возможность
получать объекты, сразу вместе с их fileno.
Так что в сортировке и сравнении блоков, имена не участвуют - все идет через номер. :)

> Так ты имена не храни и цифры сразу станут не астрономическими.

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

← →
Игорь Шевченко © (2008-02-01 21:33) [14]

Riply © (01.02.08 20:03) [13]

> Так жалко выкидывать имена, добытые потом и кровью :)

А зачем их выкидывать - они себе в MFT преспокойно лежат, ждут когда их по fileno достанут.

← →
guav © (2008-02-02 18:33) [15]

> [11] Riply © (01.02.08 19:19)

Я бы рассмотрел вариант, когда имена содержат ссылки на их начала. Т.е. stringlist:
pathParts[0] = "\", object = -1
pathParts[1] = "My Documents", object = 0
pathParts[2] = "Pictures", object = 1
pathParts[3] = "Music", object = 1

\My Documents\Pictures\ кодируется как 2, а \My Documents\Pictures\Music\ - как 3.

Или вариант когда имя - массив из индексов его кусков в стринглисте.
т.е.
pathParts[0] = "\"
pathParts[1] = "My Documents"
pathParts[2] = "Pictures"
pathParts[3] = "Music"
\My Documents\Pictures\ кодируется как {0, 1, 2}, а \My Documents\Pictures\Music\ - как {0, 1, 3}.

Чтобы сэкономить больше, можно не сохранять (или старатся не сохранять) все повторяющиеся части:
повторящиеся имена файлов в разных папках, повторяющиеся имена атрибутов, повторяющиеся имена папок
на разных дисках. Но, возможно, не получится реализовать это с достаточным быстродействием.
Для обычного несортированного стринглиста поиск дупликатов не эффективен, а сортированный не будет
иметь фиксированных индеков.
Можно иметь sorted stringlist для отсева дупликатов, в его объектах индексы несортированного.
Можно попробвать использовать более хитрую структуру с поиском дупликатов по хешам (можно посмотреть
как THashedStringList работает).

← →
ANTPro © (2008-02-02 19:03) [16]

> [15] guav © (02.02.08 18:33)
> pathParts[3] = "Music", object = 1

А не pathParts[3] = "Music", object = 2 ?

← →
Riply © (2008-02-02 23:00) [17]

> [14] Игорь Шевченко © (01.02.08 21:33)
> А зачем их выкидывать - они себе в MFT преспокойно лежат, ждут когда их по fileno достанут.

> [15] guav © (02.02.08 18:33)
> Я бы рассмотрел вариант, когда имена содержат ссылки на их начала.

После тяжких раздумий и ожесточенной борьбы с жадностью,
остановилась на следующем варианте:
Остаемся в UNICODE.
Для объектов типа директория храним полные пути.
(уходим от пробежки по цепочке Parents в MFT для получения полного имени)
Для объектов типа файл, в зависимости от параметра(настроек)
либо храним короткое имя, либо нет.
Для объектов типа поток храним имя.
В запись объекта добавляется поле ObjParent.
По предварительным оценкам AverageRecordSize будет от 48 до 80 байт.
Т.е. (для диска с миллионом объектов) на два блока,
потребуется, примерно, от 96 до 160 MB.
Это приемлемые цифры для работы или лучше попробовать ужаться еще ?

← →
Игорь Шевченко © (2008-02-02 23:03) [18]

> Это приемлемые цифры для работы или лучше попробовать ужаться
> еще ?

Полгигабайта тоже вполне приемлемая цифра :)
Я серьезно. Ну где ты возьмешь диск с миллионом объектов. Другое дело, что у тебя может сильно тормозить поиск и сравнение в таком массиве - я бы все-таки как-то организовал.

А что ты ввобще с этой информацией собираешься делать - зачем файлы-то коллекционируешь ?

← →
ketmar © (2008-02-03 00:40) [19]

>[15] guav ©(02.02.08 18:33)
кстати, да. это string ropes называется, что ли…

← →
Riply © (2008-02-03 04:44) [20]

> [18] Игорь Шевченко © (02.02.08 23:03)

> Полгигабайта тоже вполне приемлемая цифра :)
Да меня даже не от смысла, а только от того как звучит фраза:
"Потребуется не более полугигабайта памяти", бросает в дрожь :)

> Я серьезно. Ну где ты возьмешь диск с миллионом объектов.
Мне такой достать негде, а вот пользователь что нибудь да придумает :)

> Другое дело, что у тебя может сильно тормозить поиск и сравнение
> в таком массиве - я бы все-таки как-то организовал.
Здесь чуть-чуть полегче, т.к. и ищем и сортируем по FileReferenceNumber, а не по именам.
И потом, два блока требуются только для сравнения, после этого Nt-шный блок
сразу освобождается. Остальная работа идет только с блоком от MFT.

> А что ты ввобще с этой информацией собираешься делать - зачем файлы-то коллекционируешь ?
Да вот, в свое время, не слушалась старших, умудренных опытом людей. :)
Теперь приходиться расхлебывать. Ну не бросать же все на пол-пути в самом деле :)
Цель не только показать пользователю, все что спрятано от API ф-ий,
"не стандартно" или к чему его "не пускают",
но и предоставить хоть какой-то инструмент для работы с этими "объектами".
(Чтение, копирование, вероятно - затирание, и в идеале - удаление.)
Последнее - самое сложное, врядли буду пытаться реализовать.
Последствия такой "работы" на совести пользователя - должен понимать что делает :)

← →
TUser © (2008-02-03 09:55) [21]

Миллион не миллион, а вот пости сто тысяч файлов у меня сейчас есть в одной папке.

← →
Riply © (2008-02-03 10:57) [22]

> [21] TUser © (03.02.08 09:55)
> Миллион не миллион, а вот пости сто тысяч файлов у меня сейчас есть в одной папке.

Надеюсь не в ее корне ?
Или моим надеждам не суждено сбыться ? :)

← →
Anatoly Podgoretsky © (2008-02-03 11:10) [23]

> Riply (03.02.2008 04:44:20) [20]

Создай сама, Ctrl+C/Ctrl+V

← →
Riply © (2008-02-03 11:18) [24]

> [23] Anatoly Podgoretsky © (03.02.08 11:10)
> Создай сама, Ctrl+C/Ctrl+V

Создать то не проблемма.
Но для этого лучше взять диск, который потом можно будет форматировать,
ибо другого способа приведения MFT в "нормальное" состояние я не знаю :)
(Дефрагментация не поможет)

← →
Anatoly Podgoretsky © (2008-02-03 11:27) [25]

Сами мы не местные.

>[24] Riply©(03.02.08 11:18)
а ничего с MFT не будет, если ты файлы не по 12–14 байт будешь делать. иначе да — в драйвере NTFS был баг: забыли проверить «выпадение» из MFT. может, уже починили, не знаю.

> [17] Riply © (02.02.08 23:00)
> Т.е. (для диска с миллионом объектов) на два блока,
> потребуется, примерно, от 96 до 160 MB.

Ну я считаю что уже норамльно. Если вариант не сохранять вообще не рассматривается то на этом можно и остановится.

> [19] ketmar © (03.02.08 00:40)
> это string ropes называется

То есть велосипед уже изобретён, изготовлен и упакован ? Тогда тем более стоит рассмотреть использование.

> [26] ketmar © (03.02.08 12:16)

Если создать миллион файлов, то MFT потребуется вырасти на около миллиона записей (запись обычно килобайт, т.е. это будет около гигабайта). Удаление файлов не приведёт к уменьшению. Т.е. уже гигабайт будет пропадать зря. А если MFT не будет места расти нефрагментированно, она будет расти и фрагментироватся. А это уже и серьёзные проблемы с производительностью, и баг во многих програмах, включая даже Windows NT, которая перестанет загружатся - http://www.google.com.ua/search?hl=ru&q=highly+fragmented+MFT&meta= .

>[27] guav ©(03.02.08 13:19)
>То есть велосипед уже изобретён, изготовлен и упакован ?
угу. правда, я не уверен, что правильно его назвал. но ropes там точно было.

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

впрочем, спорить не стану, ибо давно оно было, не правда, и не помню я кишок NTFS. у нашего райзера такой ерунды нет. %-)

> [28] ketmar © (03.02.08 13:39)
> в MFT пихаются именно что маленькие файлы. если же файлы
> большие — там несколько другая кухня, кажется.

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

Заинтриговал своим райзером, это очередная UFS/Ext подобная система или что-то другое ? Полез гуглить...

Сравнение ФС.
http://en.wikipedia.org/wiki/Comparison_of_file_systems
http://en.wikipedia.org/wiki/List_of_file_systems

>[31] Zeqfreed ©(03.02.08 14:27)
я же не говорю, что неинтересно. я говорю, что ничего суперноваторского. просто родная (гляньте список программеров %-) и надёжная.

> [26] ketmar © (03.02.08 12:16)
> а ничего с MFT не будет

Неравда Ваша. :)
MFT очень нежна, черезвычайно ранима и совершенно(ну... почти) не способна к регенерации :)
Или MFT это "он" ?

>[34] Riply©(03.02.08 18:41)
это «оно». %-)

емнип, с достаточно большими файлами ничего страшного, кроме тормозов, не случается. а вот с мелкими — там можно MFT развалить только так.

← →
Michael (2008-02-03 19:13) [36]

Похоже ветка выродилась и ее искусственно вытягивают (поднимают), хотя начало было интересным и интригующим:(

Экономия памяти при работе. Найти похожие ветки