They have but all the ones I've looked at depend on there never being a string byte with bit 7 set in any string. It uses this space to mark in the string memory which strings are active so, at worst, only three passes of all the strings need to be made.

Lee.

Yes, but by simply allocating one more byte in string space when you store the string in string space, you can store the length after the string (the bit 7 limitation is based on the fact that Applesoft is in ROM and you can't very easily change how it stores strings). With the length it's easy (and, in general, faster) to move backwards in memory to the beginning of the string. Furthermore, if you always allocate a minimum of 4 bytes, you have room for length (1 byte), active string flag (1 bit), and pointer to variable space (2 bytes), and 1-2 character strings are no longer a special case. At a cost of one byte per string (for most strings, and only 3 bytes for the very smallest strings) you can have fast, O(n) garbage collection. GC will happen slightly more frequently, and not quite as many strings will fit in memory, but this seems like a reasonable trade-off to me. (Heck, even if I'm forgetting something it takes two or three bytes per string, it doesn't seem that bad to me.)

From a very, very quick look at the ProDOS GC, it appears to be (windowed) stop-and-copy GC. There's a GC window, which is the size of free memory minus whatever GC overhead there is. I'll ignore the overhead to keep the math simple. For a 1k window, copy all active strings in the top 1k of string space to free memory (between variable space and string space). Now the top 1k is free, so copy the active strings in free memory there. Now work on the next 1k window, copying the active strings to free memory, then from free memory to wherever the already-collected strings in the top 1k end. And so on for the rest of string space.

It appears that ProDOS triggers automatic GC whenever free space gets to be around 1-2k. So it's still O(n^2) (but if GC is manually triggered when free space >= string space, the window can be large enough to do this in one iteration, and it's O(n)), but finding the highest N strings is faster than finding the one highest string. One other downside is that it requires a reasonably sized window. If the goal is for EhBASIC (in ROM for this example) to be able to run with, say 4k of RAM for program, variables, and strings, then having a minimum GC window of, say 1k makes for an even tighter fit.

Again, by no means am I saying that there isn't a fair amount of work here, just that there seem to be at least a couple of feasible approaches to improved GC performance, if anyone wants to put in the time.

The cost for the program demonstrating the GC's lack of speed would be 3400 bytes or so, not a trivial ammount of RAM even on a 32K system.

Of course the program demonstrating the GC's lack of speed plays to the weaknesses of the GC which you wouldn't often meet in practice. Programs with large arrays of strings, such as ELiza and adventure programs, did work without such a noticeable slowdown because the majority of the strings weren't stored in string space and so didn't add much to the GC time.

I still think the GC could be speeded up but not by changing how strings are stored in string space which would need more code to handle. I think there is room for some optimization in the decisions about which strings to move and when.

For anyone interested, I dug out my July 1985 issue of Nibble magazine; the Disassembly Lines article in that issue covers the ProDOS garbage collector. It discusses the implementation details garbage collector on a fairly low level; even though my description above is more of a high level summary, it basically agrees with what the article says.

Hi.
Please note that the http://home.micros.users.btopenworld.com/ web addresses mentioned in earlier posts no longer work.
BT has not stopped it's free web hosting so I have had to move my pages to another hosting service.

All my pages are now accessible from my main page at
http://searle.hostei.com/grant
...that's my recommended URL, you can also see other things that I have been up to.

However, you can go directly to the UK101 page here...
http://searle.hostei.com/grant/uk101/uk101.html

Regards

Grant

Excellent page, Grant! Very much appreciated.

Thanks Grant, I have updated the link in the original post.

And what's this I see... a CP/M board??

Here we go again!

Hee hee.
Don't want you having too much spare time in the evenings, Jon

6502, 6809 or Z80... take your pick

Grant.
http://searle.hostei.com/grant/

I'll take the twin register set any time, Grant! But... should I use prototyping wire and tri-pad veroboard again? Hmmm...