Improvements to the Xerox Alto Mandelbrot drop runtime from 1 hour to 9 minutes
righto.com
righto.com
The key, if you read Thacker's original design paper, is that screen refresh rate was 2/3 of the bus bandwidth. This was considered absurd: why so much resource devoted to I/O (many machines in those days still had channel controllers, a design which has implicitly returned).
These old tidbits are fun because they make you think about different design tradeoffs. I love the line in K&R (IIRC -- is it still in there?) where they explain that the standard library is required (and say, including the quotes "you mean I have to call a function to do I/O?"). And the implicit defense in the 801 paper (the original RISC paper) that yes, the compiler really could do a good job.
Ah, same as the Sinclair ZX81 fast mode for the same reasons. The ZX80 was always running in fast mode and displayed the screen only if no program was running. Old times.
I guess I had always assumed this was about memory bandwidth, but this Alto article raises the possibility that the CPU may have been doing double duty (probably for cost reasons and not flexibility).
And this documentation says it was "four times as fast", which is probably too much of a difference for just memory bandwidth: http://www.worldofspectrum.org/ZX81BasicProgramming/chap13.h...
I wonder if the implementation is as simple as just swapping the priorities of user code and display code.
The algorithm was, roughly, to render 16x16 pixels at random in the scene. If the variance in colors was low, you're done. If it's high, you cut it in half (kd-tree). Pick a region at random and a random 16x16 pixels and render them. If it's low variance you're good, otherwise split. Eventually things like a wall would have maybe 4 regions describing it, though taking up a large portion of the final image. You repeat this random selection and rendering continuously. There was also a way to merge regions should the scene change and they have a similar color though I've forgotten the details.
It was quite fast on commodity hardware from 2004/2005.
In my experience, if you are familiar with RTL level synthesis of hardware then microprogramming isn't a huge leap (to me they feel very similar).
But for testing I absolutely prefer to use a low-end machine. I used to have a SparcStation 20 at home (it died a few years ago, though), and I loved that machine for that precise reason. (Also: Big-endian vs. Little-endian issues) Damn, that beast was SLOW. Not just slow: It only had 64 MB of RAM, and I had removed the hard drive because it was way too loud, so the entire thing ran over the network. Swapping over a half-duplex 10MBit line makes you really think about memory usage. ;-)
Chuck, people have been saying that since punch-card days.
And here I am, cutting out strings from my program to make it fit under the 1MB barrier for my bootloader-to-SRAM to be happy :)
It's an interesting world. Closed and not entirely relevant to most developers.
https://groups.google.com/forum/#!forum/mechanical-sympathy
I understand maybe a third of it, but what I do get is high quality.
Beyond that, I've found the biggest throughput gains and/or latency decreases by implementing the right threading or lack of threading, locking or lock-free implementations, and then tuning, profiling and optimizing things just right for the target hardware.
That's just a little sentence, but it's an amazingly hard topic. There are not many resources about this out there beyond just looking at high performance systems, regardless of language. The innodb storage engine is a fun project with some interesting locking, and I like reading about the things the kernel does.
There is also the option to get the generated machine code, here is a recent example with the Oracle JDK about SIMD programming in Java.
http://prestodb.rocks/code/simd/
Finally, note that just like many programming languages, Java enjoys multiple implementations, each with its own JIT.
I don't understand that logic, coming from somebody who has a restored Xerox Alto and wrote a Mandelbrot generator in BCPL for it "to learn how to use the Alto's bitmapped display, not make the fastest Mandelbrot set".
I also expect this guy will get source code for the 'simple' things such as an OR instruction or a fixed-width multiplication instruction within a few weeks.
Edit: I’ve been browsing http://bitsavers.trailing-edge.com/pdf/xerox/alto/Alto_Hardw....
There apparently are only 16 basic micro-instructions (”The ALU function field controls the SN74181 ALU. This device can do a total of 48 arithmetic and logical operations, most of which are relatively useless. The 4-bit field is mapped by a PROM into the 16 most useful functions”), and OR is one of them:
ALUF FIELD FUNCTION
0 BUS (A)
1 T (B)
2 BUS OR T* (A+B)
3 BUS AND T (AB)
4 BUS XOR T (A XOR B)
5 BUS + I* (A PLUS I)
6 BUS - I* (A MINUS I)
7 BUS + T (A PLUS B)
1OB BUS - T (A MINUS B)
11B BUS - T - 1 (A MINUS B MINUS I)
12B BUS + T + 1* (A PLUS B PLUS I)
13B BUS + SKIP* (A PLUS I)
14B BUS.T* (AND) (AB)
15B BUS AND NOT T (A & NOT B)
16B-17B UNDEFINED
”For the most part, since the Alto is such a simple machine, writing Alto microcode is a straightforward exercise in rule-following”
that shouldn’t be too hard, provided that there is a free spot for writing the microcode instruction, or that you can find an instruction to give up in exchange for a simple OR.
Edit 2: that PDF also describes the way you do an OR, so that apparently was the way to go:
”To "or" together the contents of ACO and ACI; results ACO:
COM 1.1
AND 1,0
ADC 1,0ContrAlto was very helpful while getting the real Alto running, and I also use it for developing software such as the Mandelbrot. I wrote a guide to getting started with ContrAlto: http://www.righto.com/2016/10/simulating-xerox-alto-with-con...
http://xeroxalto.computerhistory.org/_cd8_/alto/.index.html
http://xeroxalto.computerhistory.org/_cd8_/alto/.mu.run!2.ht...
but I don't know if there's any way to transfer it from a disk image to an actual Alto disk?
This task management is entirely orthogonal to the 16 tasks that are running at the microcode level to refresh the display and handle I/O devices.
There are the 16 basic ALU micro-instructions, but these are combined with 8 different bus sources and two sets of "special functions" to make fairly complex micro-instructions. The special functions are a bit crazy and also totally change meaning depending on which hardware task is running.
Control flow in microcode is pretty wacky. Each micro-instruction contains the address of the next micro-instruction, so it's like a goto in every instruction with instructions randomly scattered through memory. Additionally, branches are done by the hardware setting bits in the address based on conditions, so you end up with basically a computed goto. Finally, branches happen the instruction after the condition. So even just following the control flow of microcode is hard.
Another fun thing with microcode is that to read memory you write the address to the memory address register. Then you need to wait two microinstructions before you can read or write the memory value.
If you want to take a look at the Alto's microcode: http://bitsavers.trailing-edge.com/pdf/xerox/alto/microcode/...
If you do have the microcode for AND, and a RAM board to store custom microcode, creating an OR instruction shouldn't be insanely hard, though, even without an assembler (finding a spot to put it without losing another instruction may be impossible, though, and that could mean a fairly large rewrite of your OS and applications)
Also, branch delay slots (https://en.wikipedia.org/wiki/Delay_slot#Branch_delay_slots) apparently predate RISC.
G17: L_ ACDEST AND T, TASK, :SHIFT;
...the problem is that that's in the middle of the decode (there's a computed jump into this lot from the line labelled DIS1:). So you could change the AND insn to do OR instead, trivially (use "OR" here where the line says "AND"), but you probably wanted to keep AND. So you'd need to at least add enough of your own decode to be able to put the insn somewhere else. And as you say that looks like the real problem: http://users.rcn.com/crfriend/museum/doco/DG/Nova/base-instr... suggests that given 16 bit instructions and the format they've used there isn't much space left. The best you could do would be to steal some of the 'io instruction' space and have it operate on fixed accumulator registers the way MUL and DIV do.
(The decode is remarkably confusing even knowing what it's supposed to be doing; there seems to be a lot of implicitly jumping to entries in decode tables based on bits of the instruction...)
!17,20,GETAD,G1,G2,G3,G4,G5,G6,G7,G10,G11,G12,G13,G14,G15,G16,G17;
DIS0: L←T←IR←MD;
DIS1: T←ACSOURCE, :GETAD;
GETAD: T←0, :DOINS; PAGE 0
G1: T←PC -1, :DOINS; RELATIVE
G2: T←AC2, :DOINS; AC2 RELATIVE
...
G17: L←ACDEST AND T, TASK, :SHIFT;
Further instruction decoding is done with the IDISP and ACSOURCE special microcode functions, which do more complex decoding (based on multiple bit combinations) resulting in similar dispatches. So the branch to :DOINS or :SHIFT will do a second dispatch, based on the earlier ACSOURCE.(See page 30 of the hardware manual for details.)
It would be interesting to see some code that exercise more parts of the system, beyond the Mandelbrot generator.
About coding style - I guess this is tabs-vs-spaces territory - but is there a particular reason why you only indent blocks in the loops, not in the procedure/functions (like under main)?
I also wonder a bit about some of the magic constants - like 30705 - is there an overhead to use variables in BCPL (eg: indirect de-reference, no automatic in-lining by the compiler)?
Finally, how about procedure call overhead? Granted, the Mandelbrot generator is rather simple (shifts and other tricks notwithstanding) - so I can see why it makes sense to keep it all in a single procedure - but what does a call/ret look like on the Alto? (eg: in simplified assembler, in terms of stack-push, registers etc)?
Coding style: I tried to match the style of the existing Alto files, which starts functions at the left margin and then indents by 3 (!) spaces from there. e.g. http://xeroxalto.computerhistory.org/Pixel/IFS/Sources/.IfsM...
Magic constants: I'm lazy so it's easier to leave them inline when I'm hacking on code. I don't know if there's runtime overhead.
BCPL procedure call overhead: kind of nasty. There's no stack support in the instruction set, just jump-and-link. So a called procedure first calls a subroutine "getframe" that sets up the stack frame (very similar to a C stack frame). Then a second subroutine "moveargs" moves the call arguments into the stack frame. At the end of the procedure call, a third subroutine call cleans up and does the return.
Thank you! It's interesting to see how similar this code is to assembly code calling OS procedures, after declaring them external - I've recently been playing (again) with assembly for the win64 arch, and one sample program (a mish-mash of example code available for nasm, fasm and "go" assembler - is rather similar IMNHO - note this just displays a window, no loading of (image) files):
; Assemble and link with:
; nasm -f win64 .\hello-nasm.asm
; golink .\hello-nasm.obj \
; Kernel32.dll User32.dll /entry:WinMain
global WinMain
extern ExitProcess
extern MessageBoxA
section '.text'
WinMain:
sub rsp,8*5 ; reserve stack for API use and make
; stack dqword aligned
xor rcx, rcx ; uType = MB_OK
lea rdx, [szCaption] ; LPCSTR lpCaption
lea r8, [szTitle] ; LPCSTR lpText
xor r9d, r9d ; hWnd = HWND_DESKTOP
call MessageBoxA
mov ecx,eax
call ExitProcess
section '.rdata'
szTitle: db 'Hello, Title!', 0
szCaption: db 'Hello, World!', 0
nasm: http://www.nasm.us/ go linker (and assembler): http://godevtool.com/ (not to be confused with Google's "golang" Go programming language and tools.
http://bitsavers.trailing-edge.com/pdf/xerox/alto/Alto_Hardw...
You do get a speedup by just disabling the screen too on both the C64 and C128, though, as with the display on the VIC hogs a lot of memory bus cycles. That's a bit more similar to the situation on the Alto, except instead of different "hardware threads" they are separate chips and the VIC just has the ability to take control of the bus whenever it needs memory access.
The actual physical PDP-8 we had never had a printer hooked up, so actually drawing the thing would have been impossible, other than using the blinkenlights to render a line at a time.
It would be good if it was updated every so often, it probably wouldn't kill the speed too much.
Anytime I see a slightly-curious headline with only 0-3 comments, I know it's going to be good.
There's some kind of velocity factor in the position ranking, so a story that quickly gets a bunch of votes will have a high rank and few comments. But the comments are likely to come as the link sits there for a while.