?
Solved

Delphi "Out Of Memory" Error

Posted on 2009-04-18
15
Medium Priority
?
3,994 Views
Last Modified: 2013-11-23
Hey there,

I needed a code to act like a bruteforcer so I found one, but the problem is I don't want to use TStringList, so I replaced it with array of strings and added some modifications.
The problem is when I run the code, after a certain time I get "Out Of Memory" error.

I hope someone can show me where is my error, I use FreeMem and SetLength to free the array of string each iteration.
Code is below..

Regards
function   bruteforce(astring:   string  ;substr:   string  ;  startlen: integer;
endlen: integer): LongInt; 
var   i,n,x: integer;
bi,bc,br:integer;
npw:   string  ;
counter:integer;
bhlplst: array of string;
bcluster : array of string;
bresults : array of string;
label   step1;
begin
bi := 0;
bc := 0;
br := 0;
//hlplst := TStringList.Create;    //The left column
//cluster := TStringList.Create;   //The middle section
//results := TstringList.Create;   //The combinations created
for   x := 1   to   length(substr)   do begin
//hlplst.Add(substr[x]);
SetLength(bhlplst, bi + 1);
bhlplst[bi] := substr[x];
Inc(bi);
end  ;
 
step1:
for   i := 0   to   {hlplst.Count}bi - 1   do begin
for   n := 1   to   length(astring)   do begin
//npw := hlplst.strings[i]+astring[n];
npw := bhlplst[i] +  astring[n];
//cluster.Add(npw);
 
SetLength(bcluster, bc + 1);
 
bcluster[bc] := npw;
 
Inc(bc);
 
 
if   length(npw) >= startlen   then
begin
//results.Add(npw);
//SetLength(bresults,br + 1);
//bresults[br] := npw;
//Inc(br);
Form1.Memo1.Lines.Add(npw);
end;
end  ;
end  ;
//hlplst.clear;
bi := 0;
SetLength(bhlplst, bi);
FreeMem(bhlplst);
//hlplst.addstrings(cluster);
SetLength(bhlplst, bc );
for counter := 0 to bc - 1 do
begin
bhlplst[bi] := bcluster[counter];
Inc(bi);
end;
//cluster.Clear;
bc := 0;
SetLength(bcluster, bc);
FreeMem(bcluster);
if   length(npw) + 1 <= endlen   then     goto   step1;
//hlplst.Clear;
bi := 0;
SetLength(bhlplst,bi);
FreeMem(bhlplst);
result := 0;
end  ;

Open in new window

0
Comment
Question by:circler
  • 9
  • 6
15 Comments
 

Author Comment

by:circler
ID: 24181683
bump
0
 

Author Comment

by:circler
ID: 24190462
I'm still waiting someone to help me out.. thanks
0
 
LVL 6

Expert Comment

by:JosephGlosz
ID: 24190958
the reason you are running out of memory is that the TStrings property of the Form1 Memo1 memobox keeps growing infinitely long:

this is the culprit:

        Form1.Memo1.Lines.Add(npw);


At some point, you need to do a "Form1.Memo1.Clear;"   However, keep in mind that this doesn't actually RELEASE the memory there. A TStringList always just grows until you "Free" them.  But if you do a 'clear' then at least the Lines[0] get reused, and the Lines[1], etc.

and, a little nicer formatting would be, well, nice.  Like below. Makes readability much easier.

Also, you don't really need to do a Freemem after a SetLength(x,0)  In fact, the array of strings are local anyway, so they go away anyway.  

But the Form's memobox does not go away, and it will grow indefinitely the way you coded it.  Somewhere, once you are done with those strings, you should free the memobox. Maybe do the Memobox in code (instead of just dropping it on the form) so you can create it and free it explicitly.


function bruteforce(astring,substr: string; startlen, endlen: integer): LongInt;
var  
  counter,i,n,x,bi,bc,br:integer;
  npw: string;
  bhlplst,bcluster,bresults: array of string;
label  
  step1;
begin
  bc := 0;    br := 0;
  bi := length(substr);    // why reset this on every loop; you already know it's max size
  SetLength(bhlplst, bi + 1);
  for x := 1 to length(substr)   do
    bhlplst[x-1] := substr[x];

  step1:
  for   i := 0 to bi - 1   do
    for   n := 1   to   length(astring)   do
      begin
      npw := bhlplst[i] +  astring[n];
      SetLength(bcluster, bc + 1);
      bcluster[bc] := npw;
      inc(bc);
      if length(npw) >= startlen   then
        Form1.Memo1.Lines.Add(npw);
      end;

  bi := 0;
  SetLength(bhlplst,bi);
  FreeMem(bhlplst);
  SetLength(bhlplst,bc);
  for counter := 0 to bc - 1 do
    begin
    bhlplst[bi] := bcluster[counter];
    inc(bi);
    end;
  bc := 0;
  SetLength(bcluster, bc);
  FreeMem(bcluster);
  if length(npw) + 1 <= endlen   then    
    goto   step1;
  bi := 0;
  SetLength(bhlplst,bi);
  FreeMem(bhlplst);
  result := 0;
end;
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 

Author Comment

by:circler
ID: 24197022
JosephGlosz, thanks for your help, but I tried your code and I'm still getting Out Of Memory error ;(
you can try it yourself and see..
I commented this part too "//Form1.Memo1.Lines.Add(npw);" and still getting same problem
I hope you can find out what's going on
Thanks!
0
 
LVL 6

Expert Comment

by:JosephGlosz
ID: 24198529
running the function below, with the call

 i := bruteforce('12345','23',1,5);

I can see what is happening. The"endlen" is the length of the strings in which you will try ALL permutations.  So that is 5, then you will generate 99,999 strings, in addition to the 9,999 strings you generated in the previous pass, and the 999 strings before that.

When I run the above call (see below) it runs and completes just fine.

But if that endlen number is much larger, say 7, then you are creating 10 million strings.   At some point, there is no wonder you run out of memory.

What parameters do you call BruteForce with?  I'll try the same thing and see if we can't optimize this.




function bruteforce(astring,substr: string; startlen, endlen: integer): LongInt;
var
  counter,i,n,x,bi,bc,br:integer;
  npw: string;
  bhlplst,bcluster,bresults: array of string;
label
  step1;
begin
  bc := 0;    br := 0;
  bi := length(substr);    // why reset this on every loop; you already know it's max size
  SetLength(bhlplst, bi + 1);
  for x := 1 to length(substr)   do
    bhlplst[x-1] := substr[x];

  step1:
  for   i := 0 to bi - 1   do
    for   n := 1   to   length(astring)   do
      begin
      npw := bhlplst[i] +  astring[n];
      SetLength(bcluster, bc + 1);
      bcluster[bc] := npw;
      inc(bc);
      if length(npw) >= startlen   then
        Form1.Memo1.Lines.Add(npw);
      end;

  bi := 0;
  SetLength(bhlplst,bc);
  for counter := 0 to bc - 1 do
    begin
    bhlplst[bi] := bcluster[counter];
    inc(bi);
    end;
  bc := 0;
  SetLength(bcluster, bc);
  if length(npw) + 1 <= endlen   then
    goto step1;
  bi := 0;
  SetLength(bhlplst,bi);
  result := 0;
end;


procedure TForm1.Button1Click(Sender: TObject);
var
  i: longint;
begin
  i := bruteforce('12345','23',1,5);
end;
0
 

Author Comment

by:circler
ID: 24201064
What I am trying is:
 bruteforce('ABCDEFGHIJKLMNOPQRSTUVWXYZ','ABCDEFGHIJKLMNOPQRSTUVWXYZ',4,4);

Thanks in advance :)
0
 
LVL 6

Expert Comment

by:JosephGlosz
ID: 24201088
ok, I'll try it at work in the morning.  
0
 

Author Comment

by:circler
ID: 24201094
Thank you, I'm waiting :)
0
 

Author Comment

by:circler
ID: 24221255
Does anyone have an idea?
0
 

Author Comment

by:circler
ID: 24235539
Can I please get someone's attention ;x, it's been a week.
0
 
LVL 6

Expert Comment

by:JosephGlosz
ID: 24236697
I'll try tomorrow morning if I can. I've been away for a while due a family emergency, which is still ongoing.
0
 
LVL 6

Expert Comment

by:JosephGlosz
ID: 24246387
Well, running it through the debugger, I can see what is happening now.  I think you just have some phenomenally inefficient code.  If you want to use the algorithm as is, you'll probably need to store the bcluster[x] values in a database instead of in memory.

Here is what happens. Your initial double for loop goes from 0 to 25 and 1 to 26. So eventually, you set the bcluster array to a length of 26*26 or 676.   At a bc of 30, bcluster is
('AA', 'AB', 'AC', 'AD', 'AE', 'AF', 'AG', 'AH', 'AI', 'AJ', 'AK', 'AL', 'AM', 'AN', 'AO', 'AP', 'AQ', 'AR', 'AS', 'AT', 'AU', 'AV', 'AW', 'AX', 'AY', 'AZ', 'BA', 'BB', 'BC', 'BD')

The 2nd time through the loops, bi starts at 676 so bc ends up at 17576, because the for loops say:

for i := 0 to 675 do for n := 1 to 26 do....  

that's because in this loop below, bi is incremented to the value of bc, which is always i and n multiplied together. On the first time through, that is 26*26; the second time, it's 26*676, etc etc.

  for counter := 0 to bc - 1 do
    begin
    bhlplst[bi] := bcluster[counter];
    inc(bi);
    end;

So, eventually you will try to allocate 26! (26 factorial) bytes of memory (and possibly that, squared).  No wonder you run out of memory.

Basically you are trying hold all possible permutations of the alphabet, A..Z, in memory, starting with 'AA' and ending with 'ZZZZZZZZZZZZZZZZZZZZZZZZZZ'.

My calculator lists 26! = 403,291,461,126,605,635,584,000,000.  That's :

403,291,461,126,605,635,584,000 Kilobytes or
403,291,461,126,605,635,584 megabytes or
403,291,461,126,605,635 GB or
403,291,461,126,605 Terabytes

So unless I am miscalculating, you are looking to store 400 trillion terabytes in memory...

I don't think this is possible. You might want look into databases. ;-)

0
 

Author Comment

by:circler
ID: 24248481
Thank you very much JosephGlosz for your explanantion.. :)
But what I need from this code is generate test of the combinations which will start with AAAA and end with ZZZZ each time, so if there is a solution to have the same concept without storing in a variable, and testing the combination each iteration, I'd be very thankful..
0
 
LVL 6

Accepted Solution

by:
JosephGlosz earned 2000 total points
ID: 24252103
I wish I could help. Right now, I have no time whatsoever. If you just want to limit the combinations to be stored in memory from AAAA to ZZZZ, that should be do-able. If you step through the code with the debugger and examine the variables during the loops, you might be able to find the right places to put some conditionals to limit the storage.  

For example, probably something like this:

  for   i := 0 to bi - 1   do
    for   n := 1   to   length(astring)   do
      begin
      npw := bhlplst[i] +  astring[n];

      if (length(npw) >= startlen) and (length(npw) <= endlen)   then
        begin
        SetLength(bcluster, bc + 1);
        bcluster[bc] := npw;
        inc(bc);
        Form1.Memo1.Lines.Add(npw);
        end;
      end;


this puts the "if" statement ABOVE the "setlength" and memory allocation, and also makes both "startlen" and "endlen" part of the condition.

unfortunately, I can't test this right now as I will not be at work for awhile.

0
 

Author Comment

by:circler
ID: 24345717
I would've liked to have a full solution, but it's thanks JosephGlosz for trying to help, got 70% of solution
Regards
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction Raise your hands if you were as upset with FireMonkey as I was when I discovered that there was no TListview.  I use TListView in almost all of my applications I've written, and I was not going to compromise by resorting to TStringGrid…
Jaspersoft Studio is a plugin for Eclipse that lets you create reports from a datasource.  In this article, we'll go over creating a report from a default template and setting up a datasource that connects to your database.
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.
Suggested Courses

569 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question