out of memory

[edinky]

Hey there,

I'm trying to track down an out of memory error in my game..
I'm running on full memory expansion, with new character set.

I've checked the memory pointers when the error occurs, they come out as:

SOB: 1801
SOV: 3E8A
SOA: 407B
EOA: 42BE

BOS: 7F68
TOM: 8000

BOS seems too close to TOM, is this what the issue is? If so, how do I clean up the dynamic strings area?
The game does construct a lot of strings, so it is using this area a lot.

I've looked into garbage collection and used the x=fre(0) in the main game loop, but it doesn't seem to do anything.

Any ideas?

E

[malcontent]

Hard to say without more detail (what line does the error occur on)

Out of memory error could also be you running out of stack space. Gosubs eat stack and complex expressions (lots of parenthesis. although maybe that's a ?formula too complex error, i don't remember) so maybe something like that is happening. I.e escaping a subroutine without return, or subroutines calling subroutines calling subroutines.

Like if you are using a lot of mid$ left$ etc on one line, maybe break it between two lines.

[wimoos]

FOR/NEXT loops eat stack as well. And a combination of nested FORs and GOSUBs is disastrous.
The following example throws an OUT OF MEMORY in no time, leaving unclosed FOR/NEXTs and GOSUBs on the stack.

Code: Select all

10 FOR I=1 TO 100
20 GOSUB 100
30 NEXT
40 END

100 FOR I=1 TO 100
110 GOSUB 200
120 NEXT
130 RETURN

200 GOTO 10

[javierglez]

I remember reading a magazine, probably a Your Computer issue belonging to a friend. There was a recursive bitmap fill routine for the Spectrum which was something like

Code: Select all

10 if not point(x,y) then plotx,y: x=x+1: gosub 10: x=x-2: gosub 10: x=x+1: y=y-1: gosub 10: y=y+2: gosub 10
20 return

I was so impressed it was so short. I tried it in my VIC but it crashed immediately (with some routines instead of plot, point ofc). The stack is so small.

[wimoos]

In order to set up a FOR/NEXT loop, a check is done if there is still 18 (decimal) bytes free on stack. For a GOSUB/RETURN a check for 6 bytes is done.
Knowing that the stack of the 6502 processor is only 256 bytes, and there is some amount reserved, this gives room for some 40 levels of GOSUBs deep or 13 levels of FOR/NEXTs. Generally this should be plenty for regular use. It is not infinite though.

[Mike]

Code: Select all

10 if not point(x,y) then plotx,y: x=x+1: gosub 10: x=x-2: gosub 10: x=x+1: y=y-1: gosub 10: y=y+2: gosub 10
20 return

... also, that flood fill routine is a particularly bad one to begin with. It uses a depth-first approach with a scan to the right being prioritized, which requires an excessive huge stack (on the order of area/number of pixels to fill!) to have any hope to finish without stack overflow.

Much better is an iterative, queue-based approach using line spans. You won't be able to fit that on one line, but it's still a nice application of the string functions in CBM BASIC:

Code: Select all

70 X$=CHR$(X):Y$=CHR$(Y)
71 IFX$=""THENRETURN
72 X=ASC(X$):X$=MID$(X$,2)
73 Y=ASC(Y$):Y$=MID$(Y$,2):GOSUB82:IFPTHEN71
74 X=X-1:GOSUB82:IFNOTPTHEN74
75 X=X+1:U=0:D=0
76 @1,X,Y:Y=Y-1:GOSUB82:IFPTHENU=0:GOTO78
77 IFNOTUTHENX$=X$+CHR$(X):Y$=Y$+CHR$(Y):U=-1
78 Y=Y+2:GOSUB82:IFPTHEND=0:GOTO80
79 IFNOTDTHENX$=X$+CHR$(X):Y$=Y$+CHR$(Y):D=-1
80 Y=Y-1:X=X+1:GOSUB82:IFNOTPTHEN76
81 GOTO71
82 IFX<0ORX>159ORY<0ORY>191THENP=-1:RETURN
83 P=-@(X,Y):RETURN

This subroutine uses the pixel set command and test function of MINIGRAFIK.

(A naive implementation of this queue-based routine queues all neighboring pixels, which results in a 'diamond-shape' fill. That approach however, inevitably queues most fill seeds at the fill edge twice, which is a waste. The algorithm above only needs to queue the left-most pixel of horizontal line spans and that approach needs much less memory in 99%+ of all cases)


Other than that, the other posters already have pointed out the possible pitfalls: badly nested GOSUBs without RETURNs, probably in conjunction with open FOR loops. The ?OUT OF MEMORY error is possibly even triggered in a unrelated expression evaluation which just doesn't have anymore the necessary stack space available (and which would have worked otherwise!).

[edinky]

i'm using tons of gosub sub routines alright, and i guess there must be one leaking somewhere. any tips on how to hunt it down?

[Mike]

With a properly structured program, each and every of the GOSUB callable sub-routines should be separated into blocks, i.e. their own range of line numbers, with no overlap between any two of those sub-routines. If that is not the case with your program, that is the first step you need to do.

Then, an exit from all those sub-routines must only be done with RETURN. Any GOTO going outside the line number range of a sub-routine is a candidate for error. For example, this method would directly show the error in wimoos' example:

Code: Select all

10 FOR I=1 TO 100
20 GOSUB 100
30 NEXT
40 END

100 FOR I=1 TO 100
110 GOSUB 200
120 NEXT
130 RETURN

200 GOTO 10

Here the 'sub-routine' in line 200 jumps outside its own line number range.

There's also the approach to keep a 'call depth counter', by prepending *each* GOSUB with N=N+1 and *each* RETURN with N=N-1 (rename N in case of a clash), and printing N at strategic places. If N does not remain bounded, the instances/actions where it 'drifts' gives good hints where to look. That especially applies to the case where a sub-routine calls itself, or two or more sub-routines call each other. Then there needs to be a guaranteed way to end the recursion - i.e. at least one path must exist in the sub-routine that does not recurse. As an example:

Code: Select all

1 DIMD(4):D(1)=1:D(3)=-1:FORP=-1TO0:INPUT"R=1..6";R:P=R<1ORR>6:NEXT
2 @ON:@CLR:W=0:D=1:S=1:FORP=1TO7-R:S=2*S:NEXT:X=16.5+S/2:Y=160.5-S/2:GOSUB4
3 GETA$:ON-(A$="")GOTO3:@RETURN:END
4 IFR=0THENRETURN
5 R=R-1:W=W+D:D=-D:GOSUB4:D=-D:GOSUB7:W=W-D:GOSUB4:GOSUB7
6 GOSUB4:W=W-D:GOSUB7:D=-D:GOSUB4:D=-D:W=W+D:R=R+1:RETURN
7 X2=X+S*D(W+1AND3):Y2=Y-S*D(WAND3):@1,X,YTOX2,Y2:X=X2:Y=Y2:RETURN

This is a graphical example that (again) uses the MINIGRAFIK extension to draw the Hilbert curve. The sub-routine in line 4 recursively calls itself, four times in its body. The variable R accounts for a 'remaining' recursion depth (in a similar manner to the variable N above). When R reaches 0, the sub-routine immediately returns, and that is where the recursion ends.

This example is included in the disk image of the MG batch suite.

[javierglez]

This subroutine uses the pixel set command and test function of MINIGRAFIK.

Additionally I guess the algorithm you posted produces a nice graphical effect while it is displaying the intermediate results.

Any ideas?
E

At each subroutine add a sentence placed so as it executes just once each time the subroutine is called, printing some identifier. It's a lot of work but I tend to obfuscate and then do heavy debugging.

Maybe the SuperExpander provides TRON, I never used this command but I would expect it to do some similar tracing.

I'd say thanks to emulators debugging is easier in assembly than in BASIC nowadays.

[Mike]

Additionally I guess the algorithm you posted produces a nice graphical effect while it is displaying the intermediate results.

Well, yes, it does a flood fill as described, but not in diamond shape. Rather it extends full horizontal lines upward and downwards 'simultaneously' (sort of round-robin), and if a 'branch' is found, that branch immediately is included in the round-robin schedule.

An example is also included as MINIGRAFIK DEMO on said disk image, there it fills the gap between two circles. BASIC is rather slow, so you'd need 'no speed limit' in VICE to fully appreciate the effect.

I'd say thanks to emulators debugging is easier in assembly than in BASIC nowadays.

One can still write spaghetti code in both.