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...

Hi.
Sorry to resurrect an old-ish thread, but thought you may be interested in my new minimal 6502 computer. This also runs Microsoft BASIC but only needs 7 chips.

http://searle.hostei.com/grant/6502/Simple6502.html



In the same style as my other minimal computers - intended to be as simple as it possibly can be, but still expandable. This is to allow you to see what is really needed to make a computer without the peripheral circuitry complicating the design.

Anyway, as always, have fun

Check out my other projects here... http://searle.hostei.com/grant/index.html

Regards.

Grant

Sorry to dig up an oldish thread but did you ever work out why this was happening?

I have the same problem on my 6502 machine I am building. It seems like line numbers are lost somehow even though memory is being used up and I can see tokens and so on being stored in RAM (although I have seen some corruption in strings). I am using the OSI version of BASIC.

I am busy trying to go through and understand the code myself but any help would be much appreciated!

Simon

_________________
My 6502 related blog: http://www.asciimation.co.nz/bb/category/6502-computer

There is never a need to apologize for digging up an old thread. As BigEd said, this is a forum, not a chat room, and many projects take years. Also, do not start a new thread that would require finding the old one to review where we were in the development. Just keep the whole subject together. If you see something ten years old and want to tack on something relevant, go ahead.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Cool, will do that. I always try to update threads, especially ones I started, with relevant information once the issues are solved.

I don't think it's the cause of my issue but I took the listing of a patched version of the OSI Basic with the garbage collector bug fixes in it (from here: http://osiweb.org/software.html#BASIC_code) and have converted that to fit into Grant's single file version of Basic (from here: http://searle.hostei.com/grant/6502/Simple6502.html). That's the code I am trying to get running properly on my machine.

I'll try that out once I get home this evening. I am slowly trying to comment the code as I find it rather hard to follow what's going on!

One thing I don't understand is the following in the INLIN code:


What does the .BYTE $2C do and what is it for?

Simon

_________________
My 6502 related blog: http://www.asciimation.co.nz/bb/category/6502-computer

This is an obscure programming trick. Its effect is to Branch forward to the JSR, as if you had coded this:



It works because $2C is the opcode for BIT abs, an instruction that has two operand bytes following the opcode. But in this case the programmer's goal is not to do a BIT. Instead, the goal is to swallow (skip over) the two operand bytes but otherwise accomplish nothing. The two bytes swallowed are the lda #$07 instruction; that instruction does not get executed. Instead those two bytes -- $A9 $07 -- get interpreted as the operand of the BIT instruction.

This is weird to wrap your brain around. But the CPU doesn't find it difficult at all! From its POV, (and with the $2C restored) it just sees...



Certain factors make this trick undesirable. Yes, it saves a byte or two (compared with an actual BRA or JMP). But -- besides any human confusion it may cause! -- there will also be an access to location $07A9, and that can disrupt operation of certain I/O chips should they happen to be mapped there.

-- Jeff

_________________
In 1988 my 65C02 got six new registers and 44 new full-speed instructions!
https://laughtonelectronics.com/Arcana/ ... mmary.html

Can't say this is the right interpretation, but it looks like an optimization I saw in something Bruce Clark wrote. The $2C is the opcode for a BIT abs instruction. It looks like if the firts test does not branch to LDA #$07 instruction, then after the INX istruction a BIT $07A9 instruction is performed before the JSR OUTDO instruction. Only you can determine if the BIT $07A9 instruction is meanigful in the context of the program.

Seems Jeff beat me to it, and his explanation is more complete.

_________________
Michael A.