Jump to content

Sky Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate
Photo

In to deep? - Recursion crashes AHK


  • Please log in to reply
15 replies to this topic
Zed Gecko
  • Members
  • 149 posts
  • Last active:
  • Joined: 23 Sep 2006
this little script crashes ahk on my system possible due to recursive use of a function:
(it is supposed to create all possible permutations of a 255-char long string containing all 255 ASCII-Chars)
SetBatchlines -1
#NoEnv

loop, 255
	baselist .= Chr(A_Index)

makelists(baselist, "")
Tooltip
Listvars
MsgBox Done. %list_idx% strings created.

makelists(baselist, newlist)
{
	loop, parse, baselist
	{
		thischar := A_Loopfield
		StringReplace, newbaselist, baselist, %thischar%,, All
		new_newlist := newlist . thischar
		if (newbaselist = "")
		{
			newlist(new_newlist)
		}
		else
		{
			makelists(newbaselist, new_newlist)	
		}
	}
	return
}

newlist(newlist)
{
	global
	SetFormat, float, 3.0
	list_idx ++
	codelist_%list_idx% := newlist
	tooltip % list_idx
	return	
}
Does this happen on other systems, too? (please test)
Has anyone an idea for a work-around or knows a better way?

Edited the script to enhance testing comfort ;-)

lilalurl.T32
  • Members
  • 391 posts
  • Last active: Jul 05 2011 03:39 PM
  • Joined: 17 May 2007
Seems to work for me if this the expected result:
Posted Image

No crashing at all (XP SP3, French version)
________
Love Forum

hugson
  • Members
  • 12 posts
  • Last active: Oct 17 2011 03:29 PM
  • Joined: 07 Apr 2007
Works fine for me using Windows XP SP3 and AHK 1.0.48.3!
Regards,

Paul

Z_Gecko
  • Guests
  • Last active:
  • Joined: --
Oh sorry, i was inacurate.
It crashes after the Msgbox is shown.

At the end, it should show a long list of variables via listvars.
Could you please uncomment the ; tooltip % list_idx - line to see if the script is working. (Tooltip should show the amount of created strings).

btw. i´m running W2K SP4

Zed Gecko
  • Members
  • 149 posts
  • Last active:
  • Joined: 23 Sep 2006
i changed the script above to not show the misleading MsgBox and have the Tooltip display the number of generated strings. MsgBox is shown when done.
please test again.

lilalurl.T32
  • Members
  • 391 posts
  • Last active: Jul 05 2011 03:39 PM
  • Joined: 17 May 2007
Well, nothing happens: the tray icon appears and when you go to click on it it disappear. Neither tooltip nor msgbox is displayed.

No error message (if this is what you mean by crash).
________
Silversurfer Vaporizer

Z_Gecko
  • Guests
  • Last active:
  • Joined: --
i get an errormessage actually:

Programmfehler
AutoHotkey.exe hat Fehler verursacht und wird geschlossen.
Starten Sie das Programm neu.

Ein Fehlerprotokoll wird erstellt.

roughly translated: AHK caused an error and will be closed. Restart the program. An errorlog will be created.

Sean
  • Members
  • 2462 posts
  • Last active: Feb 07 2012 04:00 AM
  • Joined: 12 Feb 2007
Were you out of your mind? Open the task manager and observe how much consumed memory is increased.

nick
  • Members
  • 549 posts
  • Last active: Jul 03 2010 09:31 PM
  • Joined: 24 Aug 2005
Moin Z_Gecko,

255! (Fakultät/factorial) :wink:
nick :wink:

Lexikos
  • Administrators
  • 9844 posts
  • AutoHotkey Foundation
  • Last active:
  • Joined: 17 Oct 2006
this little script crashes ahk and my system :(
shutdown 12
Sorry. :lol:

Murp-e
  • Members
  • 531 posts
  • Last active: Sep 27 2011 11:44 AM
  • Joined: 12 Jan 2007
A tray icon pops up and then a tray icon pops down. So to speak.

Zed Gecko
  • Members
  • 149 posts
  • Last active:
  • Joined: 23 Sep 2006

Were you out of your mind? Open the task manager and observe how much consumed memory is increased.

Well here the script uses no more than 10MB memory before it crahes. So i assumed the crash is caused by the recusrsion and not by excessive memory usage.

255!

I am aware that final memory usage would exceed any physical possible amount. And i was prepared for a crash later on, but here it crashes instantly; it does not even pass through to the end of the first recursion which should only only use about 40MB if i estimate it right.

i modified the script a bit, so it does not keep the results in memory. But it still crashes almost instantly, it seems it does only reach a recursion-depth of 85 and crash with a memory use of around 7.8 MB:
SetBatchlines -1
#NoEnv

loop, 255
	baselist .= Chr(A_Index)

makelists(baselist, "")
Tooltip
Listvars
MsgBox Done. %list_idx% strings created.

makelists(baselist, newlist)
{
	loop, parse, baselist
	{
		global rec_depth
		thischar := A_Loopfield
		StringReplace, newbaselist, baselist, %thischar%,, All
		new_newlist := newlist . thischar
		if (newbaselist = "")
		{
			rec_depth := 0
			Tooltip, %rec_depth%, 0, 40, 2
			newlist(new_newlist)
		}
		else
		{
			rec_depth ++
			Tooltip, %rec_depth%, 0, 40, 2
			makelists(newbaselist, new_newlist)	
		}
	}
	return
}

newlist(newlist)
{
	global list_idx
	SetFormat, float, 3.0
	list_idx ++
	MsgBox % newlist
	tooltip %list_idx%, 0, 0, 1
	return	
}

I´m still clueless.

btw: the point of all this was to try an brute-force attack on the encryption this script from nick provides.

Edit: i created a much simpler recursive function that does not bloat the memory that much just for testing:
MsgBox % rec(0, 1000)
return
rec(deep, end)
{
	Tooltip %deep%
	if (deep = end)
		return "done"
	else
		return rec(deep + 1, end)
}
it crashes at 662 recursions.

Sean
  • Members
  • 2462 posts
  • Last active: Feb 07 2012 04:00 AM
  • Joined: 12 Feb 2007
I suspect a stack overflow then, but need to inspect the source code to be sure. BTW, what about the following?
MsgBox % rec(0, 1000)
return
rec(deep, end)
{
   Tooltip %deep%
   return (deep = end) ? "done" : rec(deep+1, end)
}


Z_Gecko
  • Guests
  • Last active:
  • Joined: --

BTW, what about the following?

Dies at 817 recursions.

Lexikos
  • Administrators
  • 9844 posts
  • AutoHotkey Foundation
  • Last active:
  • Joined: 17 Oct 2006
Sean is right, script function recursion is limited by available stack space.

Simple comparison of the esp register before and after entering ExpandExpression() in debug mode shows around 4.5KB of stack usage. Furthermore, temporary string values less than 4KB may be stored on the stack, up to a total of about 40K. This is per expression/function-call, before even beginning to evaluate the expression. Compare that to a compiled/machine code function call, which would use minimum 4 bytes (32 bits) on a 32-bit system.

Dies at 817 recursions.

FYI, I got up to 818 on v1.0.48.03, 804 on my current custom build, and 287 on v1.0.47.06. The last one is probably because that version used much more stack space, as it had to convert the textual form of the expression into a tokenized form before every evaluation. Now this is done only once per expression, at load time. My current custom build uses a few more local variables than v1.0.48.03, so dies a little sooner.