Резкое увеличение размера динамического массива

← →
vint45 (2007-10-11 16:25) [0]

Здраствуйте!

Есть динамический массив, в который помещаются записи (record) с описанием файлов при сканировании диска. Записи такого вида:
TFile = record Folder: string; FullName: string; Size: int64; end;

При сканировании всего диска создается довольно большой массив, около 60000 элементов. При этом программа вылетает с ошибкой "Out of memory".
Диспетчер задач показывает, что программа съела около 250 метров. Хотя если подсчитать сколько должен занимать массив (подсчетом длины строк помещаемых в массив + указатели), то получится примерно метров 5.
Замена типа string (AnsiString) на PChar для FullName решает проблемму (диспетчер показывает, что приложение съедает мах 3 метра). Но вопрос остается, почему при работе с AnsiString приложение выделяет так непропорционально память.
Может так диспетчер памяти выделяет блоки с резервироваем пространства, или может я все-таки что-то не так делаю (тогда могу привести весь код)?

← →
clickmaker © (2007-10-11 16:26) [1]

а как выделяешь память и как записываешь строки?

← →
Суслик © (2007-10-11 16:30) [2]

вроде все ок, не должно быть такой ошибки.
где-то еще ошибка, или строке несусветной длины.

← →
vint45 (2007-10-11 16:35) [3]

Под массив память выделяю через SetLength (SetLength(arrFiles, Length(arrFiles)+1);)
Память под строки выдяется через заполнение структуры TSearchRec.
Запись идет через простое присвоение:
arrFiles[High(arrFiles)].FullName:=sr.Name;

← →
clickmaker © (2007-10-11 16:45) [4]

> SetLength (SetLength(arrFiles, Length(arrFiles)+1);)

неэффективно
лучше сразу выделить некоторое количество - у тебя ж всяко не один файл?
Потом по достижении границы прираститься на некоторую дельту.

← →
Ping (2007-10-11 16:45) [5]

И дублирующиеся, дублирующиеся папки. То, что строки в Delphi могут быть расшаренными, частично спасает положение. Но как-то это "некрасиво".

Размещай папки в такие же записи, а у вложенных файлов и папок - сделай ссылку на родительскую папку.

← →
Ping (2007-10-11 16:48) [6]

неэффективно

Более того, запрос увеличивающихся участков памяти вызывает фрагментацию памяти. Не знаю тонких деталей реализации менеджера памяти, но, в любом случае, это нехорошо.

← →
Суслик © (2007-10-11 16:52) [7]

> [3] vint45 (11.10.07 16:35)
> Под массив память выделяю через SetLength (SetLength(arrFiles,
> Length(arrFiles)+1);)
> Память под строки выдяется через заполнение структуры TSearchRec.
> Запись идет через простое присвоение:
> arrFiles[High(arrFiles)].FullName:=sr.Name;

все ок. где-то ты ошибаешься в оценке объемов - либо общего кол-ва записей, либо длинн строк.

← →
Сергей М. © (2007-10-11 16:55) [8]

> Есть динамический массив, в который помещаются записи (record)
> с описанием файлов при сканировании диска

Довольно глупо хранить данные древовидной структуры в контейнере линейной структуры.

← →
vint45 (2007-10-11 16:59) [9]

Спасибо всем за подсказки по оптимизации, но вопрос имхо остается таким же.
Я вычленил из общего программного кода код по сканированию папок, Скомпилировал эффект остался тот же. Так как код получился не очень большой, приведу здесь описание всего модуля, так будет наглядней:
unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type TFile = record Folder: string; FullName: string; Size: int64; end; TProcForScanPath = procedure(Path, InitPath: string; sr: TSearchRec) of object; TfmMain = class(TForm) Button1: TButton; Label1: TLabel; Label2: TLabel; procedure Button1Click(Sender: TObject); private { Private declarations } public { Public declarations } fDoRecursPath: boolean; arrFiles: array of TFile; procedure AddFilesToArray(Path, InitPath: String; sr: TSearchRec); procedure ScanPath(Path, InitPath: string; Func: TProcForScanPath); // recurce end; var fmMain: TfmMain; implementation {$R *.dfm} var len, len2: integer; procedure TfmMain.ScanPath(Path, InitPath: string; Func: TProcForScanPath); // recurce var sr: TSearchRec; arrFold: array of String; i: integer; begin len2:=len2+1; Label2.Caption:=inttostr(len2); Application.ProcessMessages; // ïåðåä âûçîâîì ïðîöåäóðû íåîáõîäèìî óñòàíàâëèâàòü ïåðåìåííóþ fDoRecursPath â True if FindFirst(Path+"*", sysutils.faAnyFile, sr) = 0 then begin repeat if (sr.Name<>".") and (sr.Name<>"..") then begin if (((sr.Attr and SysUtils.faDirectory)=SysUtils.faDirectory) or ((sr.Attr and SysUtils.faVolumeID)=SysUtils.faVolumeID)) then begin SetLength(arrFold, Length(arrFold)+1); arrFold[High(arrFold)]:=Path+sr.Name+"\"; end else Func(Path, InitPath, sr); if not fDoRecursPath then begin FindClose(sr); Finalize(arrFold); exit; end; end; until FindNext(sr)<>0; end; FindClose(sr); for i:=0 to High(arrFold) do ScanPath(arrFold[i],InitPath,Func); Finalize(arrFold); len2:=len2-1; Label2.Caption:=inttostr(len2); Application.ProcessMessages; end; procedure TfmMain.AddFilesToArray(Path, InitPath: String; sr: TSearchRec); begin if not (((sr.Attr and SysUtils.faDirectory)=SysUtils.faDirectory) or ((sr.Attr and SysUtils.faVolumeID)=SysUtils.faVolumeID)) then begin SetLength(arrFiles, Length(arrFiles)+1); arrFiles[High(arrFiles)].Folder:=InitPath; arrFiles[High(arrFiles)].FullName:=Path+sr.Name; len:=len+Length(Path+sr.Name); Label1.Caption:=inttostr(len); Application.ProcessMessages; arrFiles[High(arrFiles)].Size:=sr.Size; end; end; procedure TfmMain.Button1Click(Sender: TObject); begin fDoRecursPath:=True; ScanPath("D:\", "D:", AddFilesToArray); end; end.

← →
vint45 (2007-10-11 17:12) [10]

Только в данной редакции замена FullName: String на PChar не помогает, память все так же лавинообразно увеличивается до 250 метров и потом программа вылетает, хотя в основной программе такой же код увеличивает использование памяти максимум на 2 метра.

← →
vpbar © (2007-10-11 17:15) [11]

может это

"creates a variable S that holds a string. In the default {$H+} state, the compiler interprets string (when it appears without a bracketed number after it) as AnsiString. Use the {$H-} directive to turn string into ShortString."

← →
vpbar © (2007-10-11 17:17) [12]

Т.е. если в опциях не стоит Huge strings то String будет занимать не 4 байта и 256

← →
vint45 (2007-10-11 17:19) [13]

> vpbar © (11.10.07 17:15) [11]

ну с ShortString точно будет неэффективное расходование памяти, да и строки путей могут быть длинее, чем 255 символов. Предпочитаю с ними не работать.

← →
vpbar © (2007-10-11 17:23) [14]

>>vint45 (11.10.07 17:19) [13]
эээ. Так в опцией Huge strings и директивой {$H+} у тебя все в порядке??

← →
vint45 (2007-10-11 17:28) [15]

да, стоит по-умолчанию $H+ AnsiString.

← →
vpbar © (2007-10-11 17:32) [16]

хм. Посмотрю дома. Хотя мне вот это SetLength(arrFold, Length(arrFold)+1); не нравится. Лучше со списком строк сделать.
ЗЫ. Кстатит есть же реализация поиска могу дать, или тебе свое нужно

← →
Суслик © (2007-10-11 17:34) [17]

все же - проверь объем данных. точно 60000 тыс. записей?
суммарная длина строк?

имей, кстати, в виду, что arrFold тоже занимает память, причем с полными путями. имхо тут собака порылась.

← →
vint45 (2007-10-11 17:46) [18]

> Суслик © (11.10.07 17:34) [17]

объем данных легко подсчитать через вычисление переменных len, len2. В данном алгоритме len считает общую длину строк FullName (чтобы ее посчитать, надо заккоментировать строку присвоения для FullName, иначе будет вылетать с ошибкой переполнения памяти). Len2 считает текущий уровень вложенности процедуры ScanPath, чем больше уровень тем больше локальных переменных хранится в стеке. У меня он достигал где-то 20. Тоже не критично, потому как массив arrFold хранит папки только одного уровня и не может быть большим ~ 10-20Кб * 20 = мах 400 Кб.

← →
Sapersky (2007-10-11 19:59) [19]

Всё-таки виноват оказался SetLength(arrFold, Length(arrFold)+1).
Теоретически оно не должно приводить к фатальным последствиям, но в данном случае приводит - видимо, из-за фрагментации.
Если не хочется писать перевыделение блоками для каждого типа массивов - см. сюда:
http://sapersky.narod.ru/files/Arrays.rar

← →
Sapersky (2007-10-11 20:02) [20]

Перепутал - не arrFold, а arrFiles, но тоже SetLength.

← →
Суслик (2007-10-11 20:05) [21]

> [19] Sapersky (11.10.07 19:59)
> Всё-таки виноват оказался SetLength(arrFold, Length(arrFold)+1).
> Теоретически оно не должно приводить к фатальным последствиям,
> но в данном случае приводит - видимо, из-за фрагментации.
> Если не хочется писать перевыделение блоками для каждого
> типа массивов - см. сюда:
> http://sapersky.narod.ru/files/Arrays.rar

это особенность манагера памяти в д6.
в д2007 проблемы нет, ибо манагер памяти иной.

← →
vpbar © (2007-10-11 20:08) [22]

нда, код жуткий

вот
TFile = Class Folder: string; FullName: string; Size: int64; end; TProcForScanPath = procedure(Path, InitPath: string; sr: TSearchRec) of object; TForm1 = class(TForm) Button1: TButton; Button2: TButton; Label1: TLabel; Label2: TLabel; procedure Button1Click(Sender: TObject); private { Private declarations } public fDoRecursPath: boolean; arrFiles: Tlist;//array of TFile; procedure AddFilesToArray(Path, InitPath: String; sr: TSearchRec); procedure ScanPath(Path, InitPath: string;Func: TProcForScanPath); // recurce end; var Form1: TForm1; implementation {$R *.dfm} var len, len2: integer; { TForm1 } procedure TForm1.AddFilesToArray(Path, InitPath: String; sr: TSearchRec); var eFile:TFile; begin if not (((sr.Attr and SysUtils.faDirectory)=SysUtils.faDirectory) or ((sr.Attr and SysUtils.faVolumeID)=SysUtils.faVolumeID)) then begin eFile:=TFile.Create; //SetLength(arrFiles, Length(arrFiles)+1); eFile.Folder:=InitPath; eFile.FullName:=Path+sr.Name; len:=len+Length(Path+sr.Name); Label1.Caption:=inttostr(len); Application.ProcessMessages; eFile.Size:=sr.Size; arrFiles.Add(eFile); end; end; procedure TForm1.ScanPath(Path, InitPath: string; Func: TProcForScanPath ); var sr: TSearchRec; arrFold: TStringList; i: integer; begin len2:=len2+1; Label2.Caption:=inttostr(len2); Application.ProcessMessages; arrFold:=TStringList.Create; if FindFirst(Path+"*", sysutils.faAnyFile, sr) = 0 then begin repeat if (sr.Name<>".") and (sr.Name<>"..") then begin if (((sr.Attr and SysUtils.faDirectory)=SysUtils.faDirectory) or ((sr.Attr and SysUtils.faVolumeID)=SysUtils.faVolumeID)) then begin arrFold.Add(Path+sr.Name+"\"); end else Func(Path, InitPath, sr); end; until FindNext(sr)<>0; end; FindClose(sr); for i:=0 to arrFold.Count-1 do ScanPath(arrFold[i],InitPath,Func); arrFold.Free; len2:=len2-1; Label2.Caption:=inttostr(len2); Application.ProcessMessages; end; procedure TForm1.Button1Click(Sender: TObject); begin //fDoRecursPath:=True; arrFiles:=TList.Create; // создавать не здесь len2:=0; len:=0; ScanPath("E:\BPK\Comp_delphi\", "E:\BPK\Comp_delphi", AddFilesToArray); end;
работает на порядок быстрее и памяти не жрет

← →
vpbar © (2007-10-11 20:10) [23]

гы. Вообщем интуитивно я угадал. Да и перераспределять память при каждом добавлении долго

← →
Galinka © (2007-10-11 22:26) [24]

А вот мне в соседней ветке говорили про фрагментацию. Может в том же дело? Или в дельфи фрагментации не бывает. Т.е. каждый раз при перераспределении памяти под массив, все время выделяется все большее место, а старое уже не используется. Тогда понятна лавинообразность. Т.е. при втором выделении памяти объем под первую запись не освободится, а под две выделится новые два размера, и так по нарастающей (( Произойдет утечка памяти. поэтому вместо прикидочных 5 программа занимает 250.

← →
Anatoly Podgoretsky © (2007-10-11 22:28) [25]

> Galinka (11.10.2007 22:26:24) [24]

Именно это и происходит.
Не понимаю, почему нет функции принудительной дефрагментации памяти, не помешала бы.

← →
Galinka © (2007-10-11 22:34) [26]

Anatoly Podgoretsky © (11.10.07 22:28) [25]

и это понятно. Тут же мне и сказали, если во время работы программы начать менять адреса то потом вообще ничего не найдешь. ((

Кстати на Королевстве довольно доходчивая статья по этому поводу. Там автор даже свой менеджер памяти писал. Который и собирал освобожденные участки памяти, объединял и проверял, можно ли поместить новый объем в уже освобожденные участки памяти.

← →
Германн © (2007-10-11 22:42) [27]

> А вот мне в соседней ветке говорили про фрагментацию. Может
> в том же дело? Или в дельфи фрагментации не бывает. Т.е.
> каждый раз при перераспределении памяти под массив, все
> время выделяется все большее место, а старое уже не используется.
>

Это где сказали? Приведи ссылку. Я сегодня злой. :-)

← →
Anatoly Podgoretsky © (2007-10-11 22:46) [28]

> Galinka (11.10.2007 22:34:26) [26]

Так адреса менять не надо, требуется только объединять соседнии свободные участки.
Ведь что сейчас происходит, есть примерно 250 мб, и не возможно этой памятью воспользоваться, поскольку новые запросы на память больше чем свободные куски, вот и происходит экскалация.

> и проверял, можно ли поместить новый объем в уже освобожденные участки памяти.

Вот это лишнее, менеждер должен просматривать цепочку сначала в сторону конца.
Операцию дефрагментации делать по запросу из программы или в свободное время.

Не. Это было давно. Моя натура не позволит потратить мою злость на тех, кто давно уже молчит.
P.S. А фрагментация есть всегда!

Anatoly Podgoretsky © (11.10.07 22:46) [28]

так я подозреваю, что чтобы объединить, то надо знать адрес и размер. А как их запомнить? Особенно при числе перераспределений в 60 000 операций. Серьезно спрашиваю.

Здесь я вижу только одну неясность. Мало что массив нарастает, так еще и размер одного из полей строго не определен.

Это как раз то же самое, когда я делала парсер текстового файла, в котором содержатся числа определенного типа. Файл со строками переменной длины и количество строк в файле заранее неизвестно. Т.е. надо перераспределять при каждом считывании числа, и при каждом переходе на новую строку. И тогда я решила сначала "оценить" размер: посчитать количество строк и количество "слов" в каждой строке. Потом один раз выделяем память под количество строк, а для каждого указателя вновь "объявленного" массива один раз перераспределяем по количеству "слов".

> Galinka (11.10.2007 23:06:31) [31]

Не знаю как в данном случае, возможно и нельзя, поскольку может получиться

*array
S1
*array
S2
...
array
Sn

В этом случае не возможно, о перемещении и речи быть не может.

> Anatoly Podgoretsky (11.10.2007 23:10:32) [32]

Но можно сменить алгоритм на другой

array[60000]
S1
...
Sn

так вот там автор как раз и сделал "таблицу адресов" участков памяти фиксированного размера. И первичная работа с памятью велась через эту таблицу. А вот если в ней не находилось участка необходимого размера, тогда уже он как-то расширял вероятно эту таблицу.

Т.е. не экономя "пару байтов" на "длине строки", он выигрывал "точное знание" адресов и размеров для объединения уже освобожденных блоков. И не допускал фрагментации.

Anatoly Podgoretsky © (11.10.07 23:12) [33]

ну я так и сделала. Но предварительно надо откуда-то узнать, сколько папок/папок в каталоге. Если это можно как-то оценить, то и задача значительно упрощается. Короче лучше потерять "пару минут" на определение общего кол-ва файлов и длинны "пути", а потом один раз выделить память.

> Galinka (11.10.2007 23:22:35) [35]

Если задача повторяемая, то задача упрощается, запоминаем старое значение, а при новом прогоне выделяем на N% больше. Это к обсуждаемой проблеме. Иначе или эмпирически или по алгоритму TList

в современных версяих дельфи СОВСЕМ-СОВСЕМ другой манагер памяти.
Просто ничего общего.

Тот, что описан на Королевсте (мистик, кстати описывал) сложнее теперешнего раз в 100. Теперь FastMM. Он и быстрее и проще.

Алгоритма из TList достаточно для любых практических задач.
Говорю как про Д7, так и про соверменный манарег памяти в Д2007 и Д2006.

> про соверменный манарег

Про что, про что ты говоришь?
:-)

P.S. Кроме меня это помнит только Кэтмар:
"Юлыстрация к трогедии Борис Гадунв"

Блин. Даже я ошибся. :-(

Вот цитата из первоисточника:
Горбушка, презиравший рассуждения о высоких материях, был больше поэтом и назвал свой журнал исключительно поэтично:
ЗОРИ
Однако Горбушка при всех своих поэтических талантах был безграмотен и уже с первого номера скандально опростоволосился.
На первой странице Горбушкиного издания по случаю бывшего месяца три назад спектакля красовался рисунок из пушкинского "Бориса Годунова".
Рисунок Горбушки изображал Японца в роли Годунова, с большим жезлом в руке.
Но не рисунок заставил всю школу покатываться со смеху, а пояснительная надпись под ним: Юлыстрация к трогедие "Борис Гадунв".
Горбушка умудрился в пяти словах сделать семь ошибок и здорово поплатился.
Поэтичные "Зори" читали все и не потому, что шкидцев очень уж интересовала поэзия, их читали как .хороший юмористический журнал, и даже Янкель обижался:
- Сволочь этот Горбушка... Конкурент.

Резкое увеличение размера динамического массива Найти похожие ветки