Recursivity

BlitzMax Forums/BlitzMax Beginners Area/Recursivity

Casaber

(Posted 2016) [#1]

I was thinking.. what about using Bmax for code that's extremely recursive? Can you pump up the stack for a minute or two
using some simple commands? I remember having a crash in Bmax when trying something out and since then I've been weary about using
recursive solutions, which is a shame.

Extreme stacks might not be best practice often but when they're needed they're extremely handy.

grable

(Posted 2016) [#2]

Depends on which OS your on, they all have different defaults for stack size and ways to deal with it.

I only know that Windows has 1MB by default. Which means you can go 10000+ deep depending on argument/local count.

The only way to change the stack size in a running program on Windows is by creating new threads or fibers with an explicit stack size.
But since bmx threading api hasnt exposed that, you would have to modify it a bit.

Or, modify bmk and set the stack size in the link stage.

There is also a field for stack size in the executable header that can be modified after the fact, which is probably the cleanest approach.

Casaber

(Posted 2016) [#3]

Grable, thanks. I guess the best way to be economical about the stack without hacking would be to use VAR keyword and keep
all the parameters inside that single address / pointer?

grable

(Posted 2016) [#4]

Var arguments still have to copy the address to the stack, so use the same amount of memory.

I dont think arguments are the biggest worry here anyway. Your bound to have more locals than arguments in a sufficiently advanced function.
And even if you have NO arguments and locals, the stack would still grow by at least 8 bytes because of the return pointer and stack frame setup.

You can estimate the maximum recursion depth though:

Local stacksize:Int = 2097152' 2mb
Local numargs:Int = 2
Local numlocals:Int = 5
Local framesize:Int = 5	' RET,EBX,ESI,EDI,EBP
Local funcsize:Int = (numargs + numlocals + framesize) * 4
Print "maxdepth=" + (stacksize / funcsize)

May i ask what are you doing that requires such deep recursion?

Casaber

(Posted 2016) [#5]

I won't bore you with the details but I've used Bmax for a month now and already I'm considering to use Bmax as my primary programming language and prototyping tool, as I love it.
But if I am to throw away all my other tools, which I hope to do, then I know I really need to be able to do recursive algorithms of some level with it. And I don't want any nasty surprises.

It's more the concept that needs to be available in some form. I need to be able to do stuff, it does not have to be quick or anything.

grable

(Posted 2016) [#6]

Its not something ive ever worried about to be honest.
Just know that 2MB (the default on my setup) is a lot, and in the general case youl never overflow it.
And when in doubt, calculate an estimate.

After making a tool to change the stack size in the executable header, i found out that MinGW (at least 5.1.0 that i use) sets the reserved stack size to 2MB, commit is still 4K.
For comparison, BCC sets its stack to 4MB.

EDIT: After some more digging, it seems BMK sets the stack size to 4MB as well.

So you can go pretty deep :)

Im posting the tool here if you ever need more stack space, i made it in C though because it was easier.

pestacksize.c

/*
  * pestacksize.c - shows or changes stack sizes of 32 and 64 bit PE executables
  *
  *  usage: pestacksize executable [stackreserve] [stackcommit]
  */
#include <windows.h>
#include <winnt.h>
#include <stdio.h>
#include <stddef.h>

int main( int argc, const char* argv[argc]) {
	ULONGLONG stackreserve = -1;
	ULONGLONG stackcommit = -1;
	int readonly = 1;
	
	// check arguments
	if(argc < 2) {
		printf( "usage: pestacksize executable [stackreserve] [stackcommit]\n");
		return 1;
	}	
	if(argc >= 3) {
		stackreserve = strtol( argv[2], NULL, 10);
		if(stackreserve <= 0) {
			fprintf( stderr, "error: invalid reserved stack size (%d)\n", stackreserve);
			return 1;
		}
		readonly = 0;
	}
	if(argc >= 4) {
		stackcommit = strtol( argv[3], NULL, 10);
		if(stackcommit <= 0) {
			fprintf( stderr, "error: invalid commit stack size (%d)\n", stackcommit);
			return 1;
		}
	}
	
	// slurp the entire file
	size_t sz;	
	void* p;	
	FILE* f = fopen( argv[1], readonly ? "rb" : "r+b");
	if(!f) {
		fprintf( stderr, "error: file not found \"%s\"\n", argv[1]);
		return 1;
	}
	fseek( f, 0, SEEK_END);
	sz = ftell(f);
	p = malloc(sz);
	rewind(f);
	if( fread( p, sz, 1, f) != 1) {
		fprintf( stderr, "error: unable to read from file\n");
		goto err_file;
	}
	rewind(f);
	
	IMAGE_DOS_HEADER* dos = p;
	IMAGE_OPTIONAL_HEADER32* opt32;
	IMAGE_OPTIONAL_HEADER64* opt64;
	
	// verify executable signature
	if(dos->e_magic != IMAGE_DOS_SIGNATURE) {
		fprintf( stderr, "error: file not an executable\n");
		goto err_file;
	}
	
	// verify image signature
	char* sig = ((char*)dos) + dos->e_lfanew;
	if( *((DWORD*)sig) != IMAGE_NT_SIGNATURE) {
		fprintf( stderr, "error: unsupported image format (%x)\n", *((DWORD*)sig));
		goto err_file;
	}
	
	// get the headers
	opt32 = (IMAGE_OPTIONAL_HEADER32*)(sig + sizeof(dos->e_lfanew) + sizeof(IMAGE_FILE_HEADER));
	opt64 = (IMAGE_OPTIONAL_HEADER64*)opt32;
	
	// update reserved and commit based on bitsize
	switch(opt32->Magic) {
		case IMAGE_NT_OPTIONAL_HDR32_MAGIC:
			if(readonly) {
				printf( "reserved stack size = %d\n", opt32->SizeOfStackReserve);
				printf( "commit stack size = %d\n", opt32->SizeOfStackCommit);
			} else {
				if(fseek( f, ((char*)&opt32->SizeOfStackReserve) - ((char*)dos), SEEK_SET)) {
					fprintf( stderr, "error: unable to seek the file\n");
					goto err_file;
				}
				if(fwrite( &stackreserve, sizeof(opt32->SizeOfStackReserve), 1, f) != 1) {
					fprintf( stderr, "error: unable to write reserved stack size\n");
					goto err_file;
				}
				int r = 1;
				if(stackcommit >= 0)
					r = fwrite( &stackcommit, sizeof(opt32->SizeOfStackCommit), 1, f);
				else if(opt32->SizeOfStackCommit > stackreserve)
					r = fwrite( &stackreserve, sizeof(opt32->SizeOfStackReserve), 1, f);
				 if(r != 1) {
					fprintf( stderr, "error: unable to write commit stack size\n");
					goto err_file;
				}
			}
			break;
			
		case IMAGE_NT_OPTIONAL_HDR64_MAGIC:
			if(readonly) {
				printf( "reserved stack size = %lld\n", opt64->SizeOfStackReserve);
				printf( "commit stack size = %lld\n", opt64->SizeOfStackCommit);
			} else {
				if( fseek( f, ((char*)&opt64->SizeOfStackReserve) - ((char*)dos), SEEK_SET)) {
					fprintf( stderr, "error: unable to seek the file\n");
					goto err_file;
				}
				if( fwrite( &stackreserve, sizeof(opt64->SizeOfStackReserve), 1, f) != 1) {
					fprintf( stderr, "error: unable to write reserved stack size\n");
					goto err_file;
				}
				int r = 1;
				if(stackcommit >= 0)
					r = fwrite( &stackcommit, sizeof(opt64->SizeOfStackCommit), 1, f);
				else if(opt64->SizeOfStackCommit > stackreserve)
					r = fwrite( &stackreserve, sizeof(opt64->SizeOfStackReserve), 1, f);
				 if(r != 1) {
					fprintf( stderr, "error: unable to write commit stack size\n");
					goto err_file;
				}
			}
			break;
			
		default:
			fprintf( stderr, "error: unsupported machine type (%X)\n", opt32->Magic);
			goto err_file;
	}
	
	free(p);
	fclose(f);
	return 0;
	
err_file:
	free(p);
	fclose(f);
	return 1;
}

Casaber

(Posted 2016) [#7]

Nice, thanks alot.