Interrupt-driven garbage collection for BASIC variables?

[+OLD CS1]

This post got me thinking. So far as I know, the regular garbage collection routines are in-line with the rest of BASIC functionality in just about every BASIC implementation. With one huge exception this process is largely unnoticeable for whatever reasons: AppleSoft BASIC, BASIC 2.0 and 7.0 on the Commodore 64 and 128, respectively, with TI BASIC and Extended BASIC on a bare console being the exceptions.

 

I was thinking about ways to perform garbage collection in an interrupt routine which would constantly run in the background. Has this ever been implemented? Does anyone with deep systems experience have any thoughts on the pros and cons of such a beast?

 

Some things I was thinking is the IRQ routine could happen at any time, including during variable manipulations. As a result the routine would have to know if it is planning to mess in an area being used. For instance, if you were trying to change the contents of I$, the routine would at a minimum have to know to 1) not move I$ and 2) not mess with the area reserved for its new contents.

 

At least in Commodore BASIC, numeric (floating point and integer) variables will be easier to deal with since they are not subject to the fragmentation of string variables being manipulated. The five byes used for a numeric variable stay in one place during normal operations. Even so, if the collection is to move a numeric, then it would have to ensure it is not being used.

 

A potential issue I see is if the variable table becomes fragmented because a variable in use sits far below what should now be the bottom of the variable table. Work with a variable enough and the routine may not be able to keep up with the changes, and while dirty space is eliminated unused space is not eliminated because you have this group of variable parts sitting way out away from their friends. The only way I see around this is to maintain another couple of vectors, but these would only be useful to the collection routine and a modified BASIC (where the idea for a grafted-on routine like this would be to leave BASIC unmodified.)

[JamesD]

Interrupts take place pretty often compared to execution of a BASIC program and garbage collection can take a lot of time.
Given that I'd say the only thing you'd want to do in the interrupt is have a timer to set a flag after a certain number of interrupts for doing garbage collection.
Then you garbage collect if you have to or at timed intervals. Then you don't have long pauses while a garbage collect takes place.
The one possible drawback I see is you end up performing garbage collection too much and some time is wasted in garbage collection you wouldn't otherwise.

I think it would be actually better to focus on something inline based on the state of the machine.

[+OLD CS1]

Interrupts take place pretty often compared to execution of a BASIC program and garbage collection can take a lot of time.

Given that I'd say the only thing you'd want to do in the interrupt is have a timer to set a flag after a certain number of interrupts for doing garbage collection.

Then you garbage collect if you have to or at timed intervals. Then you don't have long pauses while a garbage collect takes place.

The one possible drawback I see is you end up performing garbage collection too much and some time is wasted in garbage collection you wouldn't otherwise.

 

True. One thing I forgot to mention about my imaginary implementation is it would only deal with one or two variables at a time, and use similar monitoring metrics (though a little more aggressive) as the regular collection routine to trigger. The former would hopefully reduce the amount of time spent in the interrupt, and the latter would be to support the idea of an unmodified BASIC environment.

 

 

 

I think it would be actually better to focus on something inline based on the state of the machine.

 

Could you do this without modifying the BASIC environment? I thought about an entirely new set of variable handling routines, but IIRC there are no RAM vectors to the existing routines so you could not just create simple hooks like you can with CHROUT, CHRIN, etc.

 

As I write, I have a vague memory of some garbage collection routines being published in COMPUTE! at some time. I will have to look those up and see what approaches were used.

[+OLD CS1]

Interesting:

 

 

Some BASIC interpreters, such as Applesoft BASIC on the Apple II family, repeatedly scanned the string descriptors for the string having the highest address in order to compact it toward high memory, resulting in O(n2) performance...

 

From https://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29

 

I never experienced this to my memory. But it is also likely that my limited experience with the Apple had me working with programs which either triggered relatively fast collections or perhaps no collections at all if that is possible.

[JamesD]

True. One thing I forgot to mention about my imaginary implementation is it would only deal with one or two variables at a time, and use similar monitoring metrics (though a little more aggressive) as the regular collection routine to trigger. The former would hopefully reduce the amount of time spent in the interrupt, and the latter would be to support the idea of an unmodified BASIC environment.

Variables are stored together in a block of memory. If you start and stop it without completing it you have to start over since the variables may have changed since the last garbage collection. If you can force fixed size variables to the top of variable storage, you could skip that section completely. Well, in theory anyway.

 

Could you do this without modifying the BASIC environment? I thought about an entirely new set of variable handling routines, but IIRC there are no RAM vectors to the existing routines so you could not just create simple hooks like you can with CHROUT, CHRIN, etc.

 

As I write, I have a vague memory of some garbage collection routines being published in COMPUTE! at some time. I will have to look those up and see what approaches were used.

Apple patched their garbage collection bug in DOS so there may be some way to tie into it.

 

To really do what you are talking about should involve replacing the existing routines.

[JamesD]

I never experienced this to my memory. But it is also likely that my limited experience with the Apple had me working with programs which either triggered relatively fast collections or perhaps no collections at all if that is possible.

That may have been the original routine which was patched by DOS and fixed on the IIe.

The fix was actually in ROM and they just had to call it but someone didn't have it enabled on that release of Applesoft.

I think it was fixed on the IIe.

[The Usotsuki]

The FRE command in ProDOS.

 

Actually, you can hook into the token parser, since in MS BASIC that's copied to zero page (CHRGET, it was pretty well known in both the Commodore and Apple worlds) and run out of there.

[landgraf]

Another potential problem I see with an interrupt driven GC is that it may strike in the middle of a string assignment/manipulation and thereby cause data corruption.

 

I'd therefore rather modify the variable assignment part of the interpreter to check each string assignment and clean up the heap right away whenever a string using it changed its size

[MarkO]

<< SNIP >>

 

Apple patched their garbage collection bug in DOS so there may be some way to tie into it.

 

To really do what you are talking about should involve replacing the existing routines.

Only in ProDOS is there a improved FRE(0) command.... and only for AppleSoft...

 

MarkO