🚀 go-pugleaf

In article <gUI7zNADfCz1EABV@turnpike.com>
           richard@turnpike.com "Richard Clayton" writes:

> it obviously failed to come across when I wrote before... if sorting is
> taking any time you can actually measure then you're using the wrong
> algorithm or implementing it poorly. You never use a BubbleSort for
> anything (he says, provocatively)

Yep, that's definitely true.  About 18 years ago I wrote a Z-80 assembler
in VAX Basic (VAX Basic was actually a *good* programming language, in
that it was a *very* structured variant of Basic; in the 18,000 lines of
source code, there was not ONE line number[1] nor any GOTOs)

After the first pass, I obviously had to sort the symbol table before the
code generating second pass.  My initial cut of the program used a bubble
sort.  This was OK on trivial examples, but when I got around to
compiling the real program for which I wrote the asssembler (the
firmware for a VDU that managed VT102 emulation as well as Tektronix
4010, and ran out at 32KB of code, with over 14,000 symbols) I found that
the sort was taking almost three HOURS (on a VAX-11/730).

Successive refinements firstly used a Shell sort, and later a variant of
Quicksort; the time was brought successively down firstly to 7 minutes,
and later to seven SECONDS.


[1] Actually, that's a lie: in order to preload some data structures, it
was necessary to use a command that takes info from a DATA statement; the
latter *have* to be numbered.  But otherwise, there were no line numbers.

-- 
Brian {Hamilton Kelly}                                         bhk@dsl.co.uk
      "You're one of the very rare few who can argue ad hominem, ad absurdum
       and ad nauseam simultaneously...worse still it looks like you want to
       carry on ad infinitum..."               WPSM on alt.config 1998/06/27