What did you do, replace their sequential search of the symbol
table with a hash or an AVL tree???
I've always been a big fan of insertion sorts for such things -
then I can use a binary search. But I don't think that was the
main reason my assembler was so much faster. Univac's assembler
was heavily I/O-bound; it must have been doing a lot of passes,
or was keeping too much stuff on disk. The binary had 40 overlays
or so. Mine consisted of 4 phases, with one overlay each for the
second, third and fourth phases. The first phase read the source
file and expanded macros, the second one read the expanded code and
built the symbol table, the third read the expanded code again and
generated the listing, object code, and cross-reference data, and
the fourth sorted and printed the cross-reference data.
If I was assembling a program from a card deck, the first pass
worked directly from the card input without reading it into a
disk file first. You could hear the card reader stutter or pause
at each macro. The second phase ran in about the time it took the
card reader motor to time out and shut down, at which point the
printer fired up and started cranking out the listing.
This was on the Univac 9300, although I used the same principles
when I wrote my OS/3 assembler. Rumour has it that Univac's OS/3
assembler was a hacked version of IBM's DOS/360 assembler, whose
source code somebody found in the trunk of a car. Another rumour
states that IBM wanted it found.
