A contest to reduce code size

[WillisBlackburn]

I'd like my BASIC interpreter (see previous post) to fit into 8K but after working on it for a few days, I've only managed to reduce it by about 100 bytes. I need to eliminate another 280.

I'm considering offering a bounty for patches that save space. It would mostly be for fun, with the bounty giving people a reason to spend a few minutes looking at the code rather than just scrolling past.

Questions:

• Worth doing or a waste of time?
• What's a bounty level that would motivate people without costing me a fortune? A dollar per byte saved? Two? More?! A sliding scale?
• Should I forget it and just use AI?

If you have any ideas about how to save space, don't tell me, wait for the contest.

[Martin_H]

I don't think a cash bounty is required for this kind of project. People might help you for an honorable mention.

[drogon]

WillisBlackburn wrote:

I'd like my BASIC interpreter (see previous post) to fit into 8K but after working on it for a few days, I've only managed to reduce it by about 100 bytes. I need to eliminate another 280.

I'm considering offering a bounty for patches that save space. It would mostly be for fun, with the bounty giving people a reason to spend a few minutes looking at the code rather than just scrolling past.

Questions:

• Worth doing or a waste of time?
• What's a bounty level that would motivate people without costing me a fortune? A dollar per byte saved? Two? More?! A sliding scale?
• Should I forget it and just use AI?

If you have any ideas about how to save space, don't tell me, wait for the contest.

Tricky as everyone here has their own opinion (and more).. Here are mine:

Based on writing my own Basics; very (very) few people will be interested, paid or not.

But I've never seen a bounty system for a 6502 thing, so who knows.

Saving code bytes? Why bother. No-one (see below) has minimal 6502 systems now. Some are even making memory management units to add more memory because 64K is just not enough...

As for minimal - my own TinyBasic SBC has just 4K of RAM and 4K of ROM (Technically a lie, but that's how it works). I played code-golf with it for weeks to save a few bytes here and there just to add in a new feature. It was worth it for me, but external interest in it? I know of just one other who got it going on their system.

So how about this - rather than make it an 8K Basic (that's been done thanks MS), make it a well featured and fast 12K (or 16K) Basic.

Would I ever use it? Nope. I have my own and BBC Basic - why should I struggle with a microsoft-esque Basic when I have BBC Basic?

Would it be worth it as a personal project? Absolutely. Go for it.

[BigEd]

For fame and glory - as noted, an honourable mention.

Which is to say, I wouldn't expect a bounty to work too well.

[barrym95838]

I have done it for Scot and Kevin and Charlie here in the past, but the optimizations I found for them were very "local", and I think for me to be able to tackle a job worthy of an "honorable mention" would require a level of attention that I can't provide at the moment, especially since I don't do well trying to expand macros in my head. There are a number of individuals on this forum who are more qualified than I, so I think that your request has merit. 8KB is a large playground, so I'm quite sure there are several nuggets lying in there, waiting for someone to find them.

[BigEd]

I'd agree - there's a good chance the 8k target can be met. Make it an exciting joint effort, perhaps?

[WillisBlackburn]

drogon wrote:

Saving code bytes? Why bother. No-one (see below) has minimal 6502 systems now. Some are even making memory management units to add more memory because 64K is just not enough...

On one hand, you're right, but on the other, if we're just going to say, why bother, everyone has 128K or more now, then isn't the next step, why bother with the 6502 at all, there are CPUs available for less than a dollar that you can just program in C without having to deal with managing space in zero page or hand-optimizing your floating point code or any of the other inconveniences that come with programming the 6502. The whole point of fitting it in 8K is the challenge of fitting it in 8K. Fitting a floating-point BASIC into 12K or 16K isn't challenging at all.

[jgharston]

WillisBlackburn wrote:

If you have any ideas about how to save space, don't tell me, wait for the contest.

Is there any stuff your Basic is doing that the OS should be doing instead? Eg, instead of:
loop:
LDA kbdstatus
BPL loop
LDA kbddata
you should be doing:
JSR MOS_RDCH

Instead of:
LDX posnX
LDY posnY
JSR calc_40YplusX
STA (ptr),Y
you should be doing:
JSR MOS_WRCH

[jgharston]

Code: Select all

start_message:  .byte "VC83 BASIC "
.include "version.inc"
                .byte " <> "
start_length = * - start_message

free_message:   .byte " BYTES FREE"
free_length = * - free_message

initialize:
        jsr     initialize_target
        ldax    #start_message
        ldy     #start_length
        jsr     write

You might find zero-terminated string printing more efficient, saving all those pairs of bytes setting the length of the string. If you put all your internal strings in one block, as long as it is less than 256 bytes long all you need to do is call your message printing routine with the offset to the message. Eg:
message_base:
start_message: .byte "VC83 BASIC ",0
free_message: .byte " BYTES FREE",0
ready_message: .byte "READY",nl,cr.0
abort_message: .byte nl,cr,"ABORT",nl,cr,0

...
ldx #start_message-message_base
jsr message_print
...
ldx #abort_message-message_base
jsr message_print
...
etc.
message_print:
LDA message_base,X:BEQ rts
JSR charout:INX:BNE message_print

[jgharston]

You've got lots of bits like this:

Code: Select all

load_fp1:
        ldx     #FP1
        bne     load_fp
load_fp0:
        ldx     #FP0

You could do:
load_fp1:
ldx #FP1
equb $2C ; BIT xxxx, skip next instruction
load_fp0:
ldx #FP0
This is a common trick to save bytes by executing an instruction that uses the skipped instruction as its operand instead of branching around it. You just have to ensure the instruction doesn't inadvertantly result in something that accesses unsafe memory. The above would be executed as BIT $xxA2 with xx being whatever FP0 is.

[jgharston]

Do you need ROUND() ? It's typically done by the programmer with INT(x+0.5) rather than the interpreter.

[WillisBlackburn]

jgharston wrote:

Do you need ROUND() ? It's typically done by the programmer with INT(x+0.5) rather than the interpreter.

That sounds like an easy win, thanks for pointing that out!

I've also been thinking I could just get rid of `install_exception_handler`. It's there because I wanted a way to handle exceptions that would also work for tests and thought this was clever; it sets things up so that the "exception handler" is the code following the call to `install_exception_handler`. But while that's really handy for tests because it enables the function wrapper in c_wrappers.s to handle any exceptions that the code under test raises, for the actual interpreter there's only ever one exception handler, the one in the main loop.

I'm aware of the `BIT` trick, but I haven't actually used it because I don't know what platforms this will run on so can't guarantee that the `BIT` memory access will be harmless.

Your comments about printing the VC83 banner raise the question of what it really means to be an 8K BASIC. The banner-printing code is in the ONCE segment, which in the Apple II version shares space with the BSS segment. It runs when the program starts but is quickly overwritten by program data. So it doesn't take space away from user programs, *but* it's a solution that is only available if the interpreter loads from disk. If it's in an 8K ROM (e.g., an Atari cartridge) then it still has to fit in the ROM. My feeling is that 8K has to mean "fits on an 8K ROM" but the Apple II is kind of a special case because the Language Card ROM is actually RAM that is initialized by the program itself, so it can print the banner during the loading process and not load that code into the LC.

Obviously this is all really obscure, pedantic stuff, but I think the whole point of projects like this is to revel in the details. "Just get it done" is for the day job.

[jgharston]

Ah, I did get confused at one point thinking the code was squeezing into an 8K ROM, then comments talking about overwriting after executing....

[jgharston]

This reminds me that I have some code that has to fit in a 16K ROM, but is actually copied to RAM to be executed. The issue is the code is about 18.5K but must live in the 16K ROM. I've been trying to find some simple quick decompression code to expand it on fetching it to RAM. Most of the code I've looked at are good with text or pictures, but not code; or are very heavyweight and the additional overhead of the decompressor takes the code back up to more than 16K again!

[gilhad]

Just an idea, not sure, if good, but ...:
would it be possible to "export" the code to some basic form (just instructions and labels, no comments or formating or so) (or maybe disassemble it, so local loops would not have different loop label, just jump 10 bytes back or so) and have a modern PC (big RAM, big speed) try to find identical sequences of lines and then replace them with JSR calls? How much lines is minimum to save some space (if the same sequence save just one byte per call and is found 10 times, then it is 10 bytes)?

It would need human discretion, but let machines find possible place by brutal force