Live data from Hacker News

BBC BASIC raytracer in 432 characters

mastodon.me.uk

31–40 of 96 posts

Re: BBC BASIC raytracer in 432 characters

#32
a thing that puzzles me is how https://bbcmic.ro/?t=9ctpk is only 4× faster in emulation (about 30 seconds per scan line and so on the order of 2 hours for the whole image)

i'm running this on a ryzen 5 3500u at 2400 megahertz. the acorn electron which supposedly takes 8 hours and 40 minutes is a 1 megahertz 6502 when running from ram, roughly, 262144 instructions per second. at 2 ipc one core of the ryzen should be about 4800 mips. if the emulation slowdown is 10× (10 host instructions to emulate one guest instruction), which is typical for naïve interpretation, it should be about 1000× faster on this laptop as on the original hardware

(possibly the basic is in rom and so it's closer to 524288 instructions per second)

emulation through qemu-like dynamic code generation should cut the 10× slowdown to 3×, so it should be 3000× faster than the original hardware

where did that factor of 1000 go? not the javascript engine, surely?

incidentally there is a rocket-ship button underneath the output screen image labeled 'send to beebjit' which runs the program in about a second

Re: BBC BASIC raytracer in 432 characters

#33
post #32

a thing that puzzles me is how https://bbcmic.ro/?t=9ctpk is only 4× faster in emulation (about 30 seconds per scan line and so on the order of 2 hours for the whole image) i'm running this on a ryzen 5 3500u at 2400 megahertz. the acorn electron which supposedly takes 8 hours and 40 minutes is a 1 megahertz 6502 when running from ram, roughly, 262144 instructions per second. at 2 ipc one core of the ryzen should be…

If the emulator is entirely cycle correct for the entire system (including the video system, which is usually the most expensive to emulate, not the CPU), then the speedup on modern computers will be much less than just comparing the clock frequencies.

Consider that each chip of a home computer system (CPU, 1..2 IO/timer chips, audio, video, ...) needs to do 'emulation work' for each 1 or 2 MHz clock cycle which can add up to quite a number of host computer instructions (dozens to hundreds).

If each chip emulator just takes around 10..20 host system clock cycles to emulate one emulator clock cycle, then you are already looking at around 100 host system clock cycles per emulated clock cycle for the entire home computer (in reality it's probably worse).

Such 'vertically sliced' emulation code is also full of conditional branches which put a heavy burden on the host CPU branch predictor.

...and that's how a theoretical 1000x speedup suddenly becomes a 10x speedup, it's not the CPU emulation (this is usually cheap) but the rest of the emulated system which can be expensive.

Different emulators use all sorts of tricks and shortcuts, but usually with tradeoffs like less precise emulation, or less 'compartmentalized' code.

PS: case in point this is just the top-level per-cycle function in my C64 emulator, which in turn calls per-cycle-functions in each of the chip emulators (which may each be just as much code):

https://github.com/floooh/chips/blob/9a7f6d659b5d1bbf72bc8d0...

I'm trying to strike a balance between 'purity' (e.g. an entire emulated system can be 'plugged together' by wiring together chip emulators, just like one would build a real 8-bit computer on a breadboard), while still being fast enough to comfortably run in realtime even in browsers (https://floooh.github.io/tiny8bit/c64.html).

It's definitely possible to implement a faster cycle-correct C64 emulator with a less 'pure' architecture, but it's quite hard to do meaningful optimizations while keeping that same 'virtual breadboard' architecture.

...considering all the code that runs per cycle it's actually amazing how fast modern CPUs are :)

Re: BBC BASIC raytracer in 432 characters

#34
post #26

https://www.pouet.net/prod.php?which=78045 Incredible raytraced demo in 256 bytes.

https://www.pouet.net/prod.php?which=53871

https://www.youtube.com/watch?v=36BPql6Nl_U

Incredible raytraced demo in 128 bytes. (An underwater journey through a Menger-sponge fractal)

Re: BBC BASIC raytracer in 432 characters

#35

Can anybody provide de-obfuscated/minified source so those of us who understand the principle (tracing rays of light around a scene) can understand the maths?

here's my attempt

    10 REMĀĘĆĞ$Č*Ēĉ!ăě-ĕ'ď
       rem dithering table in comment above consulted by GCOL line?
       rem raytracer from https://bbcmic.ro/?t=9ctpk by https://mastodon.me.uk/@coprolite9000
       rem deobfuscated and possibly broken by kragen javier sitaker (untested)
    20 MODE 1
       VDU 5
    30 FOR N = 8 TO 247         : rem loop over rows (n) and columns (m) of pixels
          FOR M = 0 TO 319
    40       X = 0              : rem three-dimensional vector
             Y = -.1
             Z = 3

             U = (M - 159.5)/160    : rem xform screen coords to direction vector
             V = (N - 127.5)/160

             W = 1/SQR(U*U + V*V + 1) : rem normalize direction vector
             U = U * W
             V = V * W

             I = SGN U    : rem derive coordinate of sphere center (i, i, 1)?
             G = 1

    50          E = X - I : rem beginning of do-while loop
                F = Y - I
                P = U*E + V*F - W*Z
                D = P*P - E*E - F*F - Z*Z + 1
                IF D 
i'm interested to hear what i got wrong

see also https://news.ycombinator.com/item?id=39026517 and https://news.ycombinator.com/item?id=39026495

Re: BBC BASIC raytracer in 432 characters

#36
post #14

Ok, this is probably a dumb question: I get that the code traces the rays for this scene, obviously — but where is the scene, then? That is, where is the “data” (as opposed to the algorithm) that says “there’s a sphere at coordinates x,y,z with radius r, and here’s the other one, and here’s the checkerboard plane”?

W=1/SQR(U*U+V*V+1) This makes a sphere. It gets multiplied by two coordinates to make spheres at different places, U and V.

i think this is incorrect, i think that's computing the z component of the initial direction vector of the ray being traced

if you change the initialization of i from sgn u to 1.2 * sgn u you will get an image with the spheres a little further apart

Re: BBC BASIC raytracer in 432 characters

#37
post #19

Earlier quoted context omitted.

thanks! i didn't see that link. but i think the 432 bytes leaves the line numbers out, so it should actually be 448 bytes

I guess that's a philosophical question. In most home computer BASIC interpreters, the source code (including line numbers) never exists as text in memory or on tape/disk, only as binary tokens. The only place where the original input text exists is a small line buffer which gets translated into binary token form when pressing Enter/Return. The LIST command translates the token form back into human readable text. And…

sure, you might want to count the tokenized representation instead of the printed representation, so maybe the real number is something smaller than 432, but it contains the line numbers too. you definitely don't want to count the 432 bytes of printed representation and leave out the 16 bytes of line numbers because the program won't run without them

Re: BBC BASIC raytracer in 432 characters

#38
post #26

https://www.pouet.net/prod.php?which=78045 Incredible raytraced demo in 256 bytes.

last year i wrote a tetris in arm assembly https://asciinema.org/a/622461 and was pleased to get it down below 1024 bytes

then i looked and rrrola's 4is256 https://www.pouet.net/prod.php?which=29286 is a working tetris in under 256 bytes, and it's better than mine because it has colors and scoring. i could blame a little bit of inflation on arm being 32-bit rather than 16-bit, but not 4×

Re: BBC BASIC raytracer in 432 characters

#39
post #20

Earlier quoted context omitted.

BBC BASIC is surprisingly efficient for an interpreted language. It kind of had to be, running on processors that slow.

all the basics i used on processors that slow were surprisingly inefficient, even for an interpreted languages i thought they had to be, running on processors with that little memory. though later on i learned about forth, which is surprisingly efficient for an interpreted language a more likely explanation is that sophie wilson was just a better hacker than bill gates and paul allen

Yeah, BBC BASIC is really good. Both the language design and the implementation.

I loved it at the time, and the more I think back on it the more impressed I am. Like it had a very decent suite of floating-point routines, which if I remember right were very performant. In a 32KB ROM!

Re: BBC BASIC raytracer in 432 characters

#40
post #32

a thing that puzzles me is how https://bbcmic.ro/?t=9ctpk is only 4× faster in emulation (about 30 seconds per scan line and so on the order of 2 hours for the whole image) i'm running this on a ryzen 5 3500u at 2400 megahertz. the acorn electron which supposedly takes 8 hours and 40 minutes is a 1 megahertz 6502 when running from ram, roughly, 262144 instructions per second. at 2 ipc one core of the ryzen should be…

If the emulator is entirely cycle correct for the entire system (including the video system, which is usually the most expensive to emulate, not the CPU), then the speedup on modern computers will be much less than just comparing the clock frequencies. Consider that each chip of a home computer system (CPU, 1..2 IO/timer chips, audio, video, ...) needs to do 'emulation work' for each 1 or 2 MHz clock cycle which can…

that's an excellent point, i hadn't considered that they might be running this program in basic on a cycle-correct emulator of the bbc micro. thank you very much for explaining
Post reply on HN