compiled languages on 8bit computers

[kisrael]

Hey there--

 

this thread started talking a bit about the Famicom keyboard and BASIC, which made me think about how few of the 8bit built-in BASICS had support for sprites, which brought up Simons' BASIC on the C=64, and its relative slowness, which got me thinking about the (relative) lack of compiled languages on the platforms of the day...

 

I know there were a few, like Action! for the Atari 8bits.

 

I guess I'm not sure how the BASIC interpreters usually worked, in terms of steps...

 

I think there's a tokenizer that more or less parses each line. When is that done, as each line is entered? Did most of the basics store the raw strings or the tokens? (I *think* tokens, so sometimes you'd see your ? statement restored to being a PRINT when you listed it)

 

So assuming it was tokenized when you hit enter, the tokens could then be stored as a... sort of bytecode, I'd say. And then when you hit run, each line of byte code would be translated into assembly and executed. Is that where the slowness crept into the process?

 

It seems to be that if you had a decent interpreter, you should be able to make a decent compiler. (I vaguely *think* I remember some utility that did that, but not sure what platform or what magazine it came from) Would a compiled BASIC provide as huge a speed boost as I would expect? Or is it more difficult than I give it credit for? I know at some point you probably have more things to take care of (memory location labels and what not) and system resources might be tough...

 

Well, any thoughts on that welcome. I know a lot of folks here cut their teeth on this stuff (even if the really good homebrewers moved to Assembly back in the day, even, which I failed to do.)

[Tom]

C64 BASIC parses and indeed tokenizes each line as you enter it. If you entered a leading line number, the line is stored in memory as part of the current program, if you didn't enter a line number the line is executed immediately.

 

So, when executing a program or a single line in immediate mode, C64 BASIC doesn't really need to parse human readable text anymore, which makes things faster. Additionally, because it doesn't store PRINT or INPUT etc. as text in memory but as some one byte token, programs take up less space. Now, when the interpreter encounters the PRINT token, it just calls some routine in ROM which IS the PRINT command, so there's no translation to assembly language done.

 

I suppose most BASICs on 8 bit computers handled programs similarly.

 

Whatever, I think the *main* slowness from C64 BASIC comes from the fact that all (!) arithmetic is done using some floating point format (don't know wether it's IEEE sevenhundredandsomething, and it doesn't really matter anyway). IIRC there were integer variables, but their values were converted to float when they were read, so using integer variables might have made things even slower because the interpreter was spending loads of time converting between integer/float.

 

Anyway, you do know CC65? This is a somewhat okayish 6502 C Compiler, and the authors provide support (that is, basically, libraries and linker scripts) for a number of computers/consoles.

Edited December 27, 2006 by Tom

[+remowilliams]

Hmm... speaking of compiled languages, I remember using a C compiler on my XL. I know it was the A8 because I remember doing P/M graphics with it. I keep thinking 'Laser C' for some reason, but that may have been on the ST only.

[deathtrappomegranate]

An interesting example of 8-bit BASIC dialects is Sinclair BASIC.

 

Beginning with the ZX-80, and continuing through the ZX-81 and Spectrum, all of the BASIC keywords were entered via keystrokes - so, if you pressed the "P" key, in immediate or programming mode, the keyword "PRINT" appeared on screen. Now that's upfront tokenising! There was a very clear compromise between ease of use and power - Sinclair BASIC was *slow*.

 

In fact, Sinclair's approach to BASIC led to the development of many third-party BASIC extensions. Typically, they were loaded as memory-resident machine language routines which hooked an interrupt to parse the program. Additional commands were very often contained in REM statements (which allowed free-text entry). There were also many BASIC compilers for the Spectrum.

 

Unfortunately, the Spectrum had no hardware sprites at all, and very limited sound capabilities.

 

For Atari machines, there were several compiled versions of BASIC - Turbo BASIC XL is one of the better flavours.

[mos6507]

It's probably possible to write an interpreter that is closer to assembly than Basic, kind of like an interpreted version of Batari BASIC, something that is a little closer to the metal. I'd like to see someone try that.

[djmips]

Whatever, I think the *main* slowness from C64 BASIC comes from the fact that all (!) arithmetic is done using some floating point format (don't know wether it's IEEE sevenhundredandsomething, and it doesn't really matter anyway). IIRC there were integer variables, but their values were converted to float when they were read, so using integer variables might have made things even slower because the interpreter was spending loads of time converting between integer/float.

 

I examined some of the Basic compilers available back in the day. There were several on the different platforms. Specifically I looked at one on the Apple ][. The main trick that the compiler did was to do away with the interpreter inner loop. So instead of reading the stream of instructions of what numbers to add, compare etc. It would do this directly with lda immediates and jsr to the appropriate routine. So in my experience, the overhead was in the interpreter inner loop.

 

I hand compiled one of my basic programs, a lunar lander program, by essentially doing the same thing in an assembler. It was quite an improvement in execution performance, without resorting to integers.

 

There was an assembler macro package that someone sold as well, that made writing code like this more straightforward (I don't recall the name). It was like writing in a higher level language in that you had the entire BASIC math library at your disposal.

[Nukey Shay]

Advan Basic also interpreted full programs before execution (instead of line-by-line)...and could handle most programs written for Atari Basic. Made a good bridge for users who wanted the least amount of effort.

 

BTW although direct player/missile support is missing from little ol' 8k Atari Basic, you could easily add it in most any program by sticking the area into string variable(s). Need to change or move the sprite? Just modify the string.

Edited February 4, 2007 by Nukey Shay

[JamesD]

As stated, most BASICs parse the line when you enter it, tokenize it, execute it in immediate mode or store it. Computers where you input the keywords with a single keystroke did so to reduce the size of the interpreter. No parser means a smaller/cheaper ROM. Later Speccy's used a tokenizer like everyone else as did the American version from Timex.

 

To interpret a BASIC program the interpreter finds the current line and looks for a token. To interpret a token, BASIC just uses a jump table that has pointers to the routines they represent. Some tokens were two bytes long. The first byte was usually 255 which pointed to a 2nd table and the 2nd byte of the token was the routine to call from that table. If an unsupported token is found it just jumps to a routine that gives an error.

 

Once a routine is called it has to parse the current line after the token to find parameters for that BASIC keyword. The more options for a keyword the longer it takes to parse. If the parameter is a variable there is even more work to do. Compiled languages do type checking at compile time and any conversion must be explicitly handled by the program itself. BASIC does it at runtime and is constantly checking what type variables are every time you used them and the constant conversion from one type to another.

 

The typical way to store a BASIC program isn't exactly geared for speed either. The program is usually stored line by line with the line number, a pointer to the next line and then the tokenized code for the line.

In the factory supplied BASICs I've looked at, they don't embed a pointer to lines that are called by GOTO or GOSUB with the call, they do a search by line number. That is done by searching through the program line by line looking for the line number. This made long programs slower than short ones. At least one replacement for Atari BASIC about doubled execution speed by adding pointers along with the tokenized lines. It did a scan of the program when you ran it to add all the pointers if you enabled that mode.

 

Variables are handled in a similar manner. The variables are stored in a table as they are created and whenever you access them the interpreter looks them up in that table. That's why a program would run faster if you placed variables that were used the most first.

 

Several BASICs omitted INT (integer) variables. Even loop counters are stored as FLOAT which goes back to the constant conversion. That alone slowed down many machines.

 

On top of that a lot of the design of BASIC interpreters from back then was to fit everything in a small ROM and use little RAM instead of doing it in the fastest possible way. If someone were to rewrite BASIC for one of the 24 bit address buss CPUs (65816, ez80, etc...) where RAM and ROM limitations aren't an issue then I'm sure they could run BASIC much faster even without a lot of tricks.

 

 

No, most BASICs didn't include support for sprites. I think the Tandy CoCo was the first machine to include an extended BASIC and even then it was an option. People had always used PEEK and POKE until then so nobody dealt with it any other way.

 

After Microsoft created Level III BASIC for the TRS-80 Model 1, Tandy thought it was a good idea and decided to offer it with the CoCo as Extended BASIC. After a few magazines proclaimed the CoCo's Extended BASIC as the best, everyone else offered an enhanced or Extended BASIC.

 

I have no idea why Simon's BASIC is so slow. The Plus/4 had most of it's features and did a lot of bank switching but was still pretty fast. But then the Plus/4 did have a faster CPU. FWIW, the Plus/4 also offered the largest amount of memory for a BASIC program of any 8 bit I'm aware of. It just didn't have hardware sprites or a SAM chip so people shunned it.

 

 

I think there were plenty of BASIC compilers for most machines but many were pretty limited and usually just converted the code to a machine language program that made a lot of ROM calls. In the end they skipped most of the parsing or type conversion stages and made variable manipulation a lot faster but they were still hampered by slow ROM routines and little if any optimization to the machine code. The compiled programs were also very dependent on ROM routines being at a certain address and any upgraded ROM might cause them to fail. I think the Amiga was the first machine that really dealt with the ROM call issue well but then it was a much later 16/32 bit machine.

 

 

I know Small C compilers made it to most 8 bit CPU's but the commercial ones were expensive on a lot of machines so very few people every bought them and it never really caught on. On top of that the size of the code the compiler could handle was pretty limited and they didn't optimize code very much if at all. Limited compatibility with the C standard was often a problem and you still see that on most of the open source cross compilers available now. Even the 6809 port of GCC fails over 1000 ANSI C compatibility tests and GCC is very compatible on other CPUs. Others don't even support floating point numbers or worse!

 

Pascal was actually pretty popular on the Apple II and many commercial games such as Wizardry were written in it. It was a PCode interpreter (similar to Java) but by elimination of run time type identification/conversion and much more efficient code representation it was very fast. It also allowed programs that were larger than RAM to be written by swapping modules in and out of RAM. Still, the PCode interpreter it used is now looked at as pretty inefficient compared to what it could have been from what I've read. I think part of Turbo Pascal's popularity was due to people moving over from Apple II Pascal.

 

Operating systems like CP/M, FLEX and OS-9 had many languages including Cobol, Fortran, Pascal, C, APL.... the list goes on and on but I'm not sure any machine but the CoCo had many graphics games written under such an OS. BASIC-09 was pretty popular on the CoCo and it also used a PCode type interpreter. Several commercial games were written in it.

[Bruce Tomlin]

So assuming it was tokenized when you hit enter, the tokens could then be stored as a... sort of bytecode, I'd say. And then when you hit run, each line of byte code would be translated into assembly and executed. Is that where the slowness crept into the process?

You almost had it until then. The statements are tokenized, but then the tokens are interpreted using jump tables. Tokenizing isn't just to save memory, it's also to keep you from having to identify the word "PRINT" every time.

 

A BASIC compiler could be as simple as getting rid of the inner loop and making code that directly calls the ROM BASIC. I tried to do this on the TRS-80 but gave up because straight assembly language was easier if you didn't care about float. Or it could have the various subroutines that would be in a ROM BASIC and call them as a stand-alone executable.

 

The time savings wasn't just in losing the inner interpreter that uses the jump table, but in the routine that searches the variables table all the time. Every time you had to access a variable A or B or C, most interpreters would search the variables table linearly until it found the right variable.

 

There also could be some savings from not interpreting line numbers and numeric constants all the time, but Atari BASIC and later versions of Microsoft BASIC (CP/M, 8086, 68000) tokenized those as well.

 

EDIT: oh yeah, and line number searches in MS-BASIC were linear as well, with the only optimization being a compare of the current line number with the desired line number. If it was a later line, it started the search from the current line instead of the start of the program.

Edited February 5, 2007 by Bruce Tomlin

[JamesD]

There also could be some savings from not interpreting line numbers and numeric constants all the time, but Atari BASIC and later versions of Microsoft BASIC (CP/M, 8086, 68000) tokenized those as well.

 

EDIT: oh yeah, and line number searches in MS-BASIC were linear as well, with the only optimization being a compare of the current line number with the desired line number. If it was a later line, it started the search from the current line instead of the start of the program.

I think line numbers were normally stored as a 16 bit integer all the way back to the early tiny BASIC interpreters for the first hobby computers. That also explains the limit on what line numbers can be used. I'm not aware of any versions that use floats for line numbers including many that otherwise only use floats. That includes Atari BASIC, Tandy CoCo BASIC and I think Sinclair BASIC. Those would be the first ones that come to mind. I don't remember if Applesoft had INT or not but since the Apple Integer BASIC was much faster I'm guessing it also was float only for numeric variables.

On the other hand, the Atari corp Assembler cartridge (from what I understand) used floats for line numbers and it was much slower than it's competitors.

 

I think the test to see if the line number called by a goto or gosub follows the current line was common.

The pointer idea used by that version of Atari BASIC was pretty unique and the way it *should* have been handled.

 

A similar optimization could have been used for variables but I'm not sure if it was ever used. Variables should have had an index into a table of pointers that linked to the actual variable. That way if the interpreter moved a string or other variable at runtime all that would need adjusted is the pointer in the table and it's much faster than searching a linked list.

Edited February 6, 2007 by JamesD

[Bruce Tomlin]

I think line numbers were normally stored as a 16 bit integer all the way back to the early tiny BASIC interpreters for the first hobby computers.

But they weren't tokenized in GOTO/GOSUB statements. Trust me, I've disassembled lots of versions of MS-BASIC, starting with the TRS-80. Atari's BASIC was the first "pack-in" BASIC to tokenize line numbers inside a line.

Edited February 6, 2007 by Bruce Tomlin

[JamesD]

I think line numbers were normally stored as a 16 bit integer all the way back to the early tiny BASIC interpreters for the first hobby computers.

But they weren't tokenized in GOTO/GOSUB statements. Trust me, I've disassembled lots of versions of MS-BASIC, starting with the TRS-80. Atari's BASIC was the first "pack-in" BASIC to tokenize line numbers inside a line.

I wasn't aware of that... and it makes me wonder what they were thinking since it's such an obvious way to speed up BASIC.

[+karri]

I just wanted to drop in to advertise the www.cc65.org compiler. It creates absolutely fabulous code nowadays.

 

Here is a snippet of compiled output. The input language is C as you can see in the comments.

;
; ++misscount;
;
inc	 _misscount
;
; missspake = 1;
;
tya
sta	 _missspake
;
; if ((misscount < 25) ||
;
lda	 _misscount
cmp	 #$19
bcc	 L0802
;
; (misscount > 50 && misscount < 75) ||
;
lda	 _misscount
cmp	 #$33
bcc	 L0B1E
lda	 _misscount
cmp	 #$4B
bcc	 L0802
;
; (misscount > 100 && misscount < 125)) {
;
L0B1E:	lda	 _misscount
cmp	 #$65
bcc	 L0801
lda	 _misscount
cmp	 #$7D
bcs	 L0801

 

It has very good support for different 65-series CPU's.

 

--

Karri

[JamesD]

It has very good support for different 65-series CPU's.

 

--

Karri

Yeah, but how ANSI compatible is it? While I here it's very usable, I thought you did have to program around it's limitations. But I haven't tried it so I don't know. Still no floats I'm guessing.

 

Wasn't there another 6502 compiler that had a better compiler front end but didn't optimize well on the back end?

I think people claimed it still produced faster code. I think it was called lcc65?

 

I know Z88dk is a pretty decent Z80 cross compiler but the last version I used still had some missing stuff that my program needed. I haven't tried the latest version but it sounds promising... still no support for what I needed though.

 

SDCC looks like another good Z80 cross compiler but the version I tested crashed at times. The current version fixed the crashes but I haven't tried building any of my stuff because I'd need to port the Z88dk libs.

 

I was working on a port of SDCC for the 6809 and actually had a large portion of the code generator completed but other things have taken my time for the last few months... which wasn't a bad thing since it's given me time to think a few things through and see how another 6809 compiler works. I started looking at how GCC for the 6809 does things and I realized it would be better to allocate registers in a different order. Trivial to fix but it *should* result in faster numeric conversions. There were a lot of other things I needed to figure out before going on (PC relative code, system vs user stack, DP addressing...) and I've finally decided how to deal with them. I guess it's time to get busy again.

[+karri]

It has very good support for different 65-series CPU's.

 

--

Karri

Yeah, but how ANSI compatible is it? While I here it's very usable, I thought you did have to program around it's limitations. But I haven't tried it so I don't know. Still no floats I'm guessing.

 

It is ANSI compatible. No floats. But very cool linker that makes allocating code for page swapping easy. It also has a nice set of loadable drivers for joypads, screen i/o and filesystem.

 

And it is cheap - free.

 

--

Karri

[JamesD]

It is ANSI compatible. No floats. But very cool linker that makes allocating code for page swapping easy. It also has a nice set of loadable drivers for joypads, screen i/o and filesystem.

 

And it is cheap - free.

 

--

Karri

Ok, first of all ANSI requires floats so that alone means it's not.

Second, have you run any compatibility tests to verify compatibility like the test suite GCC uses?

I'm guessing no. Those tests are nasty and bring out minor flaws in compilers that can cause some real problems.

 

ANSI isn't just changing calling parameters from K&R format and a few things like that. Certain code must be compiled a certain way.

If ANSI is the final goal and you are close... fine that's cool, but that isn't the same thing as writing some C, testing it natively on a PC, then expecting it to recompile and run as is on a target 6502 machine. I'm not trying to be nasty, its just that I've tried porting code from one compiler to another way too many times where I had to rewrite valid code because of a flaw in the parser or code generator and that's even with commercial compilers.

 

The linker and drivers sound neat. Free is always good and I have checked on the project from time to time so I do know a lot of progress has been made over the years.

 

My comment about lcc65 was because I know it's based on a proven ANSI front end that optimizes intermediate code pretty well even before generating 6502 assembly. In spite of the ANSI front end that still doesn't mean lcc65 is full ANSI because the code generation may not be right... but at least it has a high probability of being ANSI.

[JamesD]

BTW, just because a compiler isn't 100% ANSI doesn't mean it isn't any good.

 

Also, I did some reading on a Oric forum and found that lcc65 or whatever they are using promotes int to 16 bit. While this does follow the standard you do need to be aware of it. If you want to use a byte then use char. This should hold true for any ANSI compiler.

[EricBall]

Several BASICs omitted INT (integer) variables. Even loop counters are stored as FLOAT which goes back to the constant conversion. That alone slowed down many machines.

Yeah, but it also meant you could have non-integer FOR/NEXT loops.

No, most BASICs didn't include support for sprites. I think the Tandy CoCo was the first machine to include an extended BASIC and even then it was an option. People had always used PEEK and POKE until then so nobody dealt with it any other way.

 

After Microsoft created Level III BASIC for the TRS-80 Model 1, Tandy thought it was a good idea and decided to offer it with the CoCo as Extended BASIC. After a few magazines proclaimed the CoCo's Extended BASIC as the best, everyone else offered an enhanced or Extended BASIC.

The Apple ][ had graphics routines built into both BASICs. Integer Basic even had "shape tables" although they were far too slow to use for anything serious.

[danwinslow]

Yeah, but it also meant you could have non-integer FOR/NEXT loops.

 

Well, compared to the incredible general slowdown imposed by only supporting floats, having the ability to directly do float for/next loops is maybe not a bonus, especially considering its easy enough to handle by scaling up integers.

 

CC65, at least the modern one, is a very good compiler. It's ANSI-compliant to the degree that I have never noticed anything not working as I expected it to. James, you may be thinking of the native CC65 compiler as it was released to actually do compiles on the 65xx machines...that one did indeed suffer from numerous limitations and I never considered it as usable for anything serious. A much-improved CC65 nowadays has been hosted on modern hardware as a cross-compiler, and it is very excellent and highly usable to produce ready to run executables for a large number of different 65xx machines.

www.cc65.org

[JamesD]

Nope, I'm thinking of the compiler you are. From the main page you link to:

The datatypes float and double are not available.

The compiler does not support bit fields.

 

While it may be a good compiler, those are both ANSI features.

Bit fields aren't used very much so that's not a big thing but float is pretty common.

double could just be implemented as float at first and most (not all) double usage would work.

<edit>

If double were implemented, float could be represented as double as well.

 

ROM floating point libs could also be used to save RAM.

Edited March 26, 2007 by JamesD

[+karri]

Nope, I'm thinking of the compiler you are. From the main page you link to:

The datatypes float and double are not available.

The compiler does not support bit fields.

 

While it may be a good compiler, those are both ANSI features.

Bit fields aren't used very much so that's not a big thing but float is pretty common.

double could just be implemented as float at first and most (not all) double usage would work.

<edit>

If double were implemented, float could be represented as double as well.

 

ROM floating point libs could also be used to save RAM.

 

For game programming there is no need for floats or doubles. The best thing is to use 16 bit words as mantissa between -1.0 and 1.0. All 3D transformations and other things you usually use floats for can be represented very efficiently in this way. Besides some machines like Atari Lynx has special hardware for accelerating transformations. There is built in 16 by 16 multiplication, division and cumulative summing circuitry.

 

You can even typedef your variable to float if you like it that way.

 

typedef int float;

 

The only problem is that you cannot use decimal points in constants like:

 

float a;

 

a = 0.286;

 

instead something like

 

a = 286 * FRAC_ONE / 1000; /* FRAC_ONE = 16384 */

 

You obviously cannot write a * b for two floats. Instead you need a float multiply like:

 

float fracmul(float a, float b)

{

return (long)(a * b) >> 14;

}

 

The cc65 long is 32 bits so this will produce a correct mantissa multiplication. As the numbers are always between -1.0 and 1.0 there is never a risk for overflows.

 

The smallest value you can represent with this technique is 0.00006.

 

I have used this technique for converting games using floats to compile on the cc65 compiler and I like it.

 

But of course this is not ANSI compatible and it is not even floating point. But it sure is fast

 

Oh, and if you need floats for larger range than -1.0 .. 1.0 you can always treat the second operand as an int.

 

float a = 286 * FRAC_ONE / 1000;

int b = 1500;

 

c = fracmul(a, b);

 

expands to (286 * FRAC_ONE / 1000 * 1500) >> 14 = 429

 

On a calculator 0.286 * 1500 = 429

 

--

Karri

Edited March 27, 2007 by karri

[JamesD]

The point was that it's not an ANSI compiler.

Not that there aren't ways around that.

 

I ported a program from BASIC to C and tried to get it running on Z88dk (common C cross compiler for Z80 machines like the Speccy). It doesn't have floats either and it was a pain. While it was doable, float is just a whole lot easier and more what a lot of software expects.

[djmips]

Nope, I'm thinking of the compiler you are. From the main page you link to:

The datatypes float and double are not available.

The compiler does not support bit fields.

 

While it may be a good compiler, those are both ANSI features.

Bit fields aren't used very much so that's not a big thing but float is pretty common.

double could just be implemented as float at first and most (not all) double usage would work.

<edit>

If double were implemented, float could be represented as double as well.

 

ROM floating point libs could also be used to save RAM.

 

For game programming there is no need for floats or doubles. The best thing is to use 16 bit words as mantissa between -1.0 and 1.0. All 3D transformations and other things you usually use floats for can be represented very efficiently in this way. Besides some machines like Atari Lynx has special hardware for accelerating transformations. There is built in 16 by 16 multiplication, division and cumulative summing circuitry.

 

--

Karri

 

That's all well and good but it's a real pain. Our compiled languages are supposed to make things easier, we shouldn't ahve to do all this work when the compiler could do it for us. I don't propose that floating point is the answer, although it should be an option. I've always though that fixed point should be an native type. The DSP industry addressed this with their own DSP C variant and that work as influenced another variant called Embedded C. http://www.open-std.org/jtc1/sc22/wg14. I think that it wouldn't hurt for a good 6502 compiler to support the Embedded C standard.

 

PDF here -> http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf

[+karri]

The fixed point standard proposal was very interesting. It is basically exactly what I do by hand.

 

I also know that there are people working towards a 6 byte floating point representation in the cc65 compiler but I am not interested in this kind of extensions. The runtime cc65 C-library takes 6400 bytes for Atari Lynx MegaPak I am working with now. I don't know how much floats would add to that. When you take away all the obligatory stuff like screen buffers etc you are left with 39000 bytes for the game itself.

 

I am afraid that doing a float data type could easily add 1k or 2k to the C library runtime size. On the other hand you don't have to use floats in your code so then nothing will change in the runtime either.

 

Lets hope that someone adds both floats and fixed point datatypes.

 

--

Karri

[danwinslow]

Well, I have to say that if I had one thing I had to leave out of a 8 bit compiler, it'd be floats. I understand what you are saying James, but I don't agree. Floats are totally unnecessary for 99.99% of game programming if you have a solid grounding in whats going on. And, I am *not* implying you don't or that people who want floats in their game language are idiots or anything of the sort, just stating something I think is accurate.