RogerBW's Blog

Quicksort in Postscript 30 January 2022

I think this is the closest I've come to writing a Cthulhu Mythos document: if you don't know what's going on, it's harmless, but with a little knowledge it can be mildly disturbing…

So I was in a bad mood and wanted a programming problem. I've never implemented quicksort before (I tend to use languages that have sorting functions built in). And I was already thinking backwards. So I implemented this in PostScript from the algorithm description on Wikipedia, to see how much work it would be. Answer, really not very much at all.

The public entry point: define the dict entry that serves as an anchor for the array (I suspect there's a better way of doing this), and kick off the top-level sort.

/quicksort { % [ a c b ] -> [ a b c ]
    1 dict begin
    /arr exch def
    0 arr length 1 sub quicksort.main
    arr
    end
} bind def

The main routine: make sure there's something there to sort, generate a partition, and quicksort each subpart. (It's dead handy that full stops are valid characters in a PostScript name, so I can put all my specialised routines into their own namespace. For full OO I'd shove them into their own dict, but I don't think that really generates any major advantages – and it would need an equivalent of self or this which would probably have to be based on where plus an object-local name.)

/quicksort.main { % lo hi -> (null)
    3 dict begin
    /hi exch def
    /lo exch def
    /xit false def
    lo 0 lt {
        /xit true def
    } if
    hi 0 lt {
        /xit true def
    } if
    lo hi ge {
        /xit true def
    } if
    xit not {
        /p quicksort.partition def
        lo p quicksort.main
        p 1 add hi quicksort.main
    } if
    end
} bind def

The partitioning routine (this is Hoare's original version): pick the middle value in the part of the array we're looking at, then walk inwards from both ends, swapping entries if they're out of relative order.

/quicksort.partition {
    3 dict begin
    /pivot arr hi lo add 2 idiv get def
    /i lo 1 sub def
    /j hi 1 add def
    {
        {
            /i i 1 add def
            arr i get pivot ge {
                exit
            } if
        } loop
        {
            /j j 1 sub def
            arr j get pivot le {
                exit
            } if
        } loop
        i j ge {
            j
            exit
        } if
        i j quicksort.swap
    } loop
    end
} bind def

Finally, swap two array entries by index.

/quicksort.swap {
    2 dict begin
    /bi exch def
    /ai exch def
    arr ai get
    arr bi get
    arr exch ai exch put
    arr exch bi exch put
    end
} bind def

Probably this could be done with fewer variables, but it works nicely on GhostScript. Beware: PostScript arrays can be heterogeneous, and if the things in the array you ask to sort aren't comparable (e.g. a number versus a string) it will fail.

If this is of actual use to you… well, it probably shouldn't be.


  1. Posted by Owen Smith at 06:51pm on 30 January 2022

    These days all sort algorithms are sub optimal. Things like quicksort and anything else recommended in textbooks from the 1980s are all designed on the assumption that the comparisons are the expensive bit, which they were then. But these says comparisons in fast cached CPUs are virtually free, and the expensive bit now is accessing external RAM which takes several thousand cycles. Keeping things in cache matters, but there has been no new research on how to do better sorting and instead we just throw faster hardware at it. In the absence of better research, doing everything as an external merge sort wouldn't be a bad start since that assumes all data is read from and written to tape.

  2. Posted by Random Visitor at 12:07am on 31 January 2022

    "Mathematical Illustrations: A Manual of Geometry and PostScript" warns against opening a dictionary in your recursing routine and recursing while it's still open, as you're prone to run out of dictstack.

  3. Posted by RogerBW at 10:46am on 31 January 2022

    Welcome, Mx Visitor, or may I call you Random?

    I agree that that's a valid consideration, but I think Casselman's priority is not necessarily a universal one; it's twenty-five years later, and we don't always need to save every byte. Which is a justification for "I was too lazy to do it".

    To remove the per-function dicts, which is only really worth doing in quicksort.main, would mean moving more to the stack. (Casselman's approach is to use a dict but stuff its values onto the stack and end it before entering the recursive parts, and I may well do that in a future diversion.)

  4. Posted by Random Visitor at 05:41pm on 02 February 2022

    I really do hate "Mx". The default in English is still masculine if unknown, and making like snowflakes where everything just has to be special... we can't all ride the short bus, you know.

    Owen makes a valid point in that there could be more research into relative costs beyond the rather crude abstraction we're using for algorithm complexity. I recall Poul-Henning Kamp mentioning that reshuffling the storage pattern helped more tree-traversal access stay in cache, yielding a nice speed-up for Varnish.

    I wonder whether merge sort makes a good starting point, though presumably with suitable (implicit or explicit) prefaulting you could do a lot. No idea how that would translate to a PostScript interpreter. But key-based access is bound to be slower and bulkier than stack-based access so even if dictstacks have become bigger, relying on stacks of dicts rather than the parameter stack likely is still a bit of a drag. So, next PostScript-nerdery session might have to see some benchmarking done. I presume you did test the implementation. What's the size of the largest list you sorted?

    Of course, a toy implementation written for the benefit of the programmer rather than for solving problems need not consider efficiency. But just saying "well it's been 25 years" and let the abundance of hardware compensate just as much means that you're expecting less performance, relatively speaking, out of current hardware than out of old hardware.

    You'd be in good company, though. I get about the same (un)usability experience out of a webmodern browser on a modern OS on modern-ish hardware as I got out of 25 year old hardware with a 20 year old OS and matching webbrowser. Yes, it can do things now it couldn't do back then, but it doesn't really add much in usability, getting shit done, or any other metric beyond "gee this thing is almost as nice as a TV to look at". Well, I didn't get into computing to cultivate my inner couch potato.

    There's also that PostScript is ment to run on printers, and they tend to lag a little behind the state of the art in computing resources, when not trying very hard to go backward in terms of capabilities.

  5. Posted by RogerBW at 06:12pm on 02 February 2022

    That's nice. I "really do hate" people who use fake names and email addresses so that I can't add them to an auto-pass list but have to approve their comments by hand each time.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1