ACE, optimisation and an old friend

December 29, 2017

In late November I received an email from an old friend: Sean Miller. Sean was a member of the wonderful community that built up around ACE BASIC, a compiler for the Amiga I developed as a labour of love between 1991 and 1996. I’ve written about ACE in this blog before. Sean told me how his use of ACE influenced him over the years. It has been great to get back in contact with him.

I felt honoured and humbled when, on Christmas Eve, Sean released an episode about ACE on the Raising Awesome YouTube channel he and his son have created. In this episode (Retro Amiga Computing – ACE BASIC and Questions2.1 Development):

Sean shows how to use ACE on an Amiga emulator to compile and run a program he wrote more than 20 years ago (Questions).

Retro Computing with ACE

I’ve expressed this in email to Sean, but let me say it publicly: thank you Sean! It means more to me than I can say.

During the video, Sean comments on the progress of the compilation of Questions, notes that there were around 4000 peephole optimisations (see screenshot from video above) and wonders whether I might explain what a peephole optimisation is. I’d be happy to of course. Now you’ve got me started! 🙂

ACE generates assembly code for the beautiful Motorola 68000 microprocessor. Compilation of some ACE language constructs generates sub-optimal assembly code instructions on the first pass. Assembly code is emitted as ACE parses the input source code without any knowledge of the broader context of the program.

Here’s a trivial ACE program:

x%=42
y%=x%*3

This simply stores 42 in the short integer variable x% (the type is denoted by %), multiplies x% by 3 and stores the product in the variable y%. I chose integer over floating point for this example because the generated assembly is more complex and would distract from the explanation. Speaking of distractions…

As an aside, unlike modern Intel, ARM and other processors, the 68000 didn’t have a floating point unit (FPU), so floating point operations were carried out by library code instead of hardware, such as a Motorola Fast Floating Point or IEEE 754 library. As an aside to my aside, the Amiga 500 had a 68000 processor whereas the Amiga 1200 (I owned both eventually) had a 68020. The 68020 could offload floating point instructions (which it did not know how to handle) to a co-processor. The 68040 was the first 68k processor with an on-board FPU. This is a whole topic by itself.

Back to the trivial example ACE program above…

Here’s the 68000 assembly ACE generates for the two line program without any optimisation (i.e. without the -O option):

    move.w  #42,-(sp)
    move.w  (sp)+,-2(a4)
    move.w  -2(a4),-(sp)
    move.w  #3,-(sp)
    move.w  (sp)+,d0
    move.w  (sp)+,d1
    muls    d1,d0
    move.l  d0,-(sp)
    move.l  (sp)+,d0
    move.w  d0,-(sp)
    move.w  (sp)+,-4(a4)

With optimisation we have 6 assembly instructions instead of 11:

    move.w  #42,-2(a4)
    move.w  -2(a4),-(sp)
    move.w  #3,d0
    move.w  (sp)+,d1
    muls    d1,d0
    move.w  d0,-4(a4)

Looking at the first two lines of the 11 unoptimised sequence:

    move.w  #42,-(sp)
    move.w  (sp)+,-2(a4)
lifo_stack1
Example stack operations (source: goo.gl/5EuhjG)

ACE examines this pair in a sliding window, or so-called peephole, onto the emitted instructions and notices that 42 is being pushed to the first-in, last-out stack then immediately popped from the stack and stored into the variable x%’s address, represented by an offset of two from an address stored in the register a4. The peephole optimiser reduces this push-pop pair to a single instruction:

    move.w  #42,-2(a4)

ACE stops short of taking the newly optimised pair:

    move.w  #42,-2(a4)
    move.w  -2(a4),-(sp)

then peephole optimising it and emitting this:

    move.w  #42,-(sp)

The reason is that the programmer has asked for 42 to be stored in the variable x%.

More ideally would have been this sequence:

move.w  #42,-2(a4)
move.w  -2(a4),d0
muls    #3,d0
move.w  d0,-4(a4)

which literally says:

  • move 42 into variable x%’s memory location
  • move the value stored at x%’s memory location into the 68k register d0
  • carry out a signed multiplication of 3 with the contents of register d0, storing the result in d0
  • move the contents of register d0 into variable y%’s memory location

If the constraints relating to use of x% and y% did not exist, the following would be sufficient to yield the product of 42 and 3 in 68k assembly:

move.w  #42,d0
muls    #3,d0

Notice that the 4 instructions after the multiplication (muls) in the unoptimised sequence are optimised during more than one pass over the assembly code to a single instruction that stores the product into y%, from this:

    move.l  d0,-(sp)
    move.l  (sp)+,d0
    move.w  d0,-(sp)
    move.w  (sp)+,-4(a4)

to this:

    move.w  d0,-4(a4)

So, ACE does better with this than the instruction sequence before the multiplication.

There are other simple optimisations carried out when the -O option is used, relating to numeric negation, but this example illustrates the key aspects.

Bernd Brandes later wrote a more powerful optimiser for ACE, the SuperOptimiser, that built upon this simple peephole optimisation approach.

Every instruction the processor doesn’t have to execute means fewer CPU cycles, so a run-time speed up. This matters a lot for example, when such instructions are part of a loop that iterates many times.

To revisit ACE’s code generation and optimisation implementation, I downloaded and Vidar Hokstad’s improvements to the ACE source (on GitHub) for compilation under Linux. I compiled that on my Mac OS X laptop and used it to generate 68k assembly code. Vidar contacted me several years ago to say that he was engaging in “software archaeology” (that made me feel a bit old, even then) with the ACE source code. I appreciate Vidar’s efforts. He sorted out some compilation problems under the GNU C compiler (gcc) that I would have had to otherwise.

It’s interesting to look at the Intel assembly generated by gcc for a similar C code fragment. The following would have to be embedded in a function:

int x,y;
x=42;
y=x*3;

The gcc compiler generates this sequence:

    movl    $0, -4(%rbp)
    movl    $42, -8(%rbp)
    imull   $3, -8(%rbp), %ecx
    movl    %ecx, -12(%rbp)

As with the ACE generated 68k assembly, only the relevant part is shown. There’s additional code generated just to start up and shut down a program (by gcc, ACE or any other compiler). The Intel assembly generated here is a bit better than the optimised 68k code ACE generated (4 vs 6 lines) although surprisingly, not very much better.

When I wrote ACE in the 90s, all components were written either in C or 68000 assembly and I went straight from an implicit parse tree to assembly code generation. These days I tend to use ANTLR or similar tools for lexical analysis (converting character streams to tokens) and parsing (checking against language grammar). I have yet to use The LLVM Compiler Infrastructure for language development, but that’s on my list too.

Creating an intermediate representation (such as abstract syntax trees) before code generation, provides additional opportunities for optimisation, something I’ve been exploring in recent times. I’ll write more about that in another post.

To be honest, the more I think and write about this topic again, the more I want to.

Thanks again Sean.

Mr & Mrs JW: I have some questions…

October 3, 2017

In recent months, I’ve noticed more of you in pairs with portable pamphlet displays, congregating mostly around public transport interchanges, train stations, busy street corners, and near the occasional university in Adelaide.

Are we special or is the picture more or less the same elsewhere?

Is the Apocalypse impending? Wasn’t it supposed to happen in the mid-70s? Where’s the evidence that it will ever happen? Please don’t say “it’s in the Bible”. That doesn’t count as evidence. Telling me to “have faith” doesn’t help either. I prefer not to pretend to know things I don’t know, especially for no apparent reason and certainly not about things that could profoundly affect my life, in spite of Pascal’s Wager.

Why do you think it’s reasonable that Joseph Rutherford in the early 1930s declared that only 144,000 would make it to heaven once the total number of JWs exceeded that number?

Isn’t that just a little bit convenient?

Do you think you’re one of those 144,000?

If not, what makes you OK with the idea that millions of you will be resurrected bodily, zombie-like (from Jehovah’s Witness to Jehovah’s Zombie?) to live in “paradise” (no, not Paradise, the Adelaide suburb, although that is close to a major bus interchange) built upon the 7 billion human corpses of the Apocalypse, assuming the rest of us haven’t become followers by then. Unlikely!

And why exactly is it that every other species on Earth must pay for the sins of humankind with their future? Why the heck does it always have to be about us? What makes you think we’re so special? That we have a soul? Evidence?

But that’s your mission now, isn’t it? To get yourself and the rest of us through the Apocalypse and into this paradise on earth depicted by the Watch Tower publications you hand out.

Isn’t that at least a little bit creepy?

What will happen in Paradise? What will our newly resurrected bodies be sustained by? All other species will be dead, won’t they, or are some going to be bodily resurrected too just so they can be consumed again? Will we get to worship your genocidal god for eternity? If so, we’ll need to be sustained for eternity so we’ll need food for eternity.

I hope we find strong evidence for life on other worlds. Not because we will be able to communicate within reasonable timeframes, but so that the Copernican revolution continues on its logical trajectory toward deposing us from our delusion of central importance in the universe. We can be important to one another and create meaning in our lives without being favoured by gods. Watch Pale Blue Dot! It always comes back to that.

How is it that you don’t see that in the marketplace of religions, yours is just as manufactured as the rest? We create gods in our own image not the other way around!

What evidence do you have that around 1915, your religion was “selected” by Jesus to be the one true religion? Has no-one else declared such a status for their religion?

And don’t get me started on shunning, your theological allergy to blood transfusions, or allegations of child sexual abuse in your chosen church? It’s not just the Catholics and Anglicans anymore who are under the spotlight.

I’ve engaged in civil conversation with JWs when they’ve knocked on our door, especially when a child has been in attendance, so they at least hear a different viewpoint. But door knocks are infrequent and I feel the need to engage in street epistemology with JWs (or Mormons or …) where I find them.

I don’t particularly enjoy debate or conflict, but I like dogmatic thinking less.

I wrote this post after hearing a compelling interview with Lloyd Evans, an ex Jehovah’s Witness, on The Thinking Atheist podcast.

Questionable church websites: prayer by email?

September 17, 2017

I passed by a school and associated church-next-door while out walking in an Adelaide suburb yesterday. They had a web address on their signage so I navigated there in my phone’s browser to get an idea of their theology. Not too fundamentalist. Probably not too different from the sort of liberal theology I grew up with. Probably a nice bunch of people and a caring community.

But I did a double-take when I saw this:

img_1721

Intrigued, I clicked “Request Prayer”.

what_would_like_pray

they asked. Hmm. So, I felt compelled to reply:

email2g

Seriously, I know that (the Christian) God is supposed to forgive all sins, but a missing personal pronoun and an unnecessary capitalisation? Blasphemy!

Anyway, I’ve at least made the suggestion that direct email communication with the almighty might be a Good Thing. We’ll see what comes of it. Not much I suspect.

The church in question has my email address (what the heck, so does the rest of the Internet it seems).

However, after clicking Submit, I did get this response page:

img_1720

Naturally, I have a question… You know what’s coming, don’t you?

My question is this: who has my submission been received by, exactly? 🙂

As you might imagine, I have not received an email response yet (from a god or a parishioner concerned for my soul) and I suspect I won’t. After all, it was not actually a prayer request, more like web site feedback, if a little cheeky. It should be taken as gentle satire of course, something to reflect upon.

There is a serious point to be made here though. If gods really wanted to communicate with us, they could choose to do so clearly and distinctly. Sagan (as always) captures the essence of this for me:

Our posturings, our imagined self-importance, the delusion that we have some privileged position in the Universe, are challenged by this point of pale light. Our planet is a lonely speck in the great enveloping cosmic dark. In our obscurity, in all this vastness, there is no hint that help will come from elsewhere to save us from ourselves. Carl Sagan, Pale Blue Dot (source)

 

15 years since the kindest, wisest, sanest of us died

August 17, 2017

It’s hard to believe that 15 years have passed since Mum died and as I’ve said before:

She was the kindest, wisest, sanest of us all. But she’s gone.

and

…she is still in my thoughts at some point of every day. I try to recapture the sound of her voice, her facial expressions, kind, caring, at times whimsical. And yes, I still miss her. The sense of loss reduces over time, but doesn’t leave. Not that I want it to entirely.

Karen and I have taken to lighting a candle on August 17 near the end of the day as a symbolic gesture, a focus of meditation.

 

Nova Interruptus

June 23, 2017

nova_interruptus

I like to call this wide field (12 x 8 degrees) image, taken with a Canon 1100D (ISO 100, f2.0 100mm), nova interruptus. 🙂

The red arrow points to ASASSN-17gk (shown in inset), an 11th magnitude nova in Centaurus I observed on May 21. It also shows the trail left by a passenger airliner as it moved from top left to lower right during the one minute exposure, with tree-tops at bottom.

ASASSN-17gk visual band

The signal to noise ratio wasn’t high enough to get a good value and error for the nova’s magnitude via DSLR photometry, so I didn’t submit an observation. The light curve at left shows observations made by others and the polynomial fit below highlights the rough shape of the light curve.

ASASSN-17gk visual polyfit

Alto creator Charles P. Thacker dies

June 23, 2017

The influential American engineer Charles P. Thacker died on June 19, aged 74.

Thacker designed the Alto personal computer at Xerox PARC in the 1970s which influenced development of the Mac after Steve Jobs saw it during a visit to PARC.

He also contributed to the development of Ethernet, Tablet PCs, and laser printers.

The computer scientist Butler Lampson, one of Thacker’s colleagues at Xerox PARC and later at Microsoft has spoken about his ability to see what was important and his breadth of coverage:

He could do everything from circuit design all the way through hardware architecture and programming and user-interface design.

The Association for Computing Machinery and IEEE Computer Society recently honoured Charles P. Thacker with the Eckert-Mauchly Award.

HD 148703

June 12, 2017

A request for observations by astronomers at the University of Wroclaw in Poland was announced by AAVSO on June 8.

The bright (magnitude 4.23 V) long period eclipsing binary HD 148703 (aka N Sco, HR 6143) is expected to undergo primary and secondary eclipses on June 11 and 14 each lasting around 20 hours.

The brightness and requested precision of 0.01 or better makes this an ideal candidate for wide field DSLR photometry.

I’ve taken pre-eclipse images but cloud prevented me from imaging the primary eclipse. I’ll take further images over the next few days, hoping to record the secondary eclipse.

Questionable church signs #2

May 11, 2017

Another church sign, same non-fundamentalist denomination, one month later:

So, there exists at least one Christian not opposed to marriage equality.

Hmm…

Fairly uncontroversial given the likely diversity of theological views in such a congregation.

I appreciate that this is an attempt to counter the opinions of those of a more conservative persuasion, but it’s not a terribly strong message.

The essential problem is that it suggests a house divided and says little about what Christianity has to offer to the problem.

How can inter-faith dialogue even at the highest level recognise world views that are fundamentally incompatible and in principle, immune to revision? The truth is it really matters what billions of human beings believe and why they believe it.
(Sam Harris, Letter to a Christian Nation)

 

Questionable church signs #1

May 9, 2017

An Adelaide church sign recently caught my attention:

I’ve omitted the border because I’m not interested in pointing to a particular congregation.

While cute, what struck me about the words is that it illustrates how we are able to create gods in our own image.

Is it really such a leap to go from this to considering the Ten Commandments or the golden rule as the possible product of a human community rather than divine inspiration?

Wouldn’t it be more effective just to point people to Carl Sagan’s Pale Blue Dot on YouTube?

Roy & I

March 11, 2017

Roy Austen (1953-2017), a former colleague, died a few days ago on March 5.

A friend recently told me that Roy had been diagnosed with cancer in January, although he had actually been unwell for months before then.

Not long after the diagnosis, Roy set up a GoFundMe page for medical expenses and for the ongoing care of his son, in preparation for the inevitable.

I really did mean to get in contact, but I got busy and Roy died before I did. At least there was still the fund…

Roy’s main line of work and his passion was photography, but that’s not how we got to know one another.

I bought my first Windows (3.1) PC from his family business, KM Computers.

Then, awhile later, he offered me a job and became my boss…

By the end of 1995 I was in search of my next job after 5 years at the University of Tasmania (UTAS) in Launceston as a computer systems officer then a junior academic in the Department of Applied Computing. A lot of university contracts weren’t being renewed around that time.

Luckily for me, Roy had recently started Vision Internet, one of a small but growing number of competing Internet Service Providers (ISPs) in Tasmania. It was a small business arising from KM Computers at a time when Internet access was still dial-up, ISDN/ISDL was the fastest you could hope for (128 Kbps), but most people just had a dial-up modem, giving up to around 56 Kbps, less in practice. Vision Internet started in Launceston but quickly added points of presence in other parts of the state, including an Internet Cafe.

In 1995 while still at UTAS, I had helped Roy out by writing a basic customer time accounting program in C that read utmp/wtmp logs and generated simple output when someone else had difficulty doing so.

By 1996, Roy needed a programmer and system administrator and I needed a job. Before accepting Roy’s job offer, I was up front with him that I would probably want to do something different after about 18 months. That happened with Karen and I moving to Adelaide in 1997 where I spent 10 years with Motorola. That move was more difficult than I expected, and at least as hard as Karen knew it would be. In the end, it was a good move.

Ironically, UTAS asked me to come back for some occasional part-time tutoring soon after I started working for Roy, which may have been less economical than if they’d just renewed my contract!

Vision Internet was good while it lasted. To be honest, for the first few months, I couldn’t believe I was being paid to write C  (and Perl) code, something I enjoyed doing anyway. 🙂

The compact machine room doubled as my office for the first year or so before we moved down the road to a more spacious building; not as cushy as my office at UTAS. I actually didn’t mind the machine room too much. A terminal with function key accessible “virtual consoles”, the vi editor, command-line shell, a C compiler, and a Perl interpreter kept me pretty happy. Roy was fine with me working from home occasionally as time went by too. He expected me to keep things rolling and solve problems as quickly as possible, but he was good to me and we got along pretty well.

There were only about half a dozen people working at Vision Internet, fewer early on. Everyone pitched in. Roy and I didn’t always see eye to eye though. For example, at one point we disagreed about who should have super-user privileges; more than I would have liked for a brief time. 🙂

I experienced a number of things during my time with Roy at Vision Internet and learned lessons from some:

  • Early mobile phones were fairly bulky. 🙂 Roy gave me my first mobile before I started in the job. Of course, this meant he could contact me whenever. He didn’t abuse that though. A former UTAS colleague took one look at the phone hanging off my belt and declared amusingly: “wanker phone”. 🙂 Even worse when a larger battery was added! Still, I appreciated Roy giving me my first mobile.
  • You can’t always spend time doing what you want in a job, even one you mostly like, unless you’re very lucky. I guess I already knew that from being a nurse in the 80s. I had no real interest in sysadmin tasks like applying security patches to BSD Unix kernels, maintaining backups, chasing hackers, worrying about what dodgy things people might be doing with our systems or customer sales, credit card transactions, help desk (shades of The IT Crowd: “is your modem plugged in?”). I mostly wanted to design, code, and test software. Still do. That’s largely why I told Roy I thought I’d want to move on after about 18 months. Having said that, a fair amount of my time was spent writing software in the form of a suite of customer time usage programs, each prefixed with tu, written in C and Perl. We also eventually sold tu to another local ISP.
  • The practical difference between code that uses a search-based processing algorithm over a linear data structure that runs in polynomial vs logarithmic time – O(n^2) vs O(n log n). This matters a lot as the number of customer records (n) increases when your task is to write a program that processes customer time usage once per day and obviously before the next day starts. To simplify: given a processing time of a second per customer, n≈300 can mean the difference between a run that takes a day instead of an hour. You can make incremental changes to the processing time per customer (t), but eventually you’ll hit a point where n is too large, e.g. when n=1000 and t is 0.1 seconds. Anyway, I don’t recall what our n and t were, but we hit such a limit with a tu program. When I realised what was going on and fixed it, Roy was delighted and relieved. I was pretty happy too and thanked my computer science education, in particular, the discipline of computational complexity.

Before I left to go work at Motorola, I made sure Roy wasn’t going to be left without someone in my role. This gave one of my former UTAS students (Craig Madden) the opportunity he needed to break into the industry; it turned out well for Roy and Vision too.

At the height of Vision Internet, I remember occasional staff gatherings at Roy’s. He was a good host and I think he mostly enjoyed that period, despite the worry that must’ve accompanied running a business. He was generally optimistic and trusted those he employed. He had his moments, like the rest of us, when he was unhappy or angry, but mostly, he was a good guy to be around.

If I could do so, I’d tell him this:

Roy, I’m really sorry you’re gone and that I didn’t make the time to get in contact. In recent years, I should have told you how much I appreciated the opportunity you gave me a long time ago. Upon reflection, after time spent together at Vision and elsewhere, I think we would have used the word “friend” (now distorted by social media) to describe our relationship, not just “colleague”, even if we didn’t say so. I should have told you that too.