Re: What micros do you actually hate to work with?

On Sat, 14 Oct 2006 15:04:33 GMT, "Wilco Dijkstra"
<Wilco_dot_Dijkstra@xxxxxxxxxxxx> wrote:

"Jonathan Kirwan" <jkirwan@xxxxxxxxxxxxxx> wrote in message
news:jgb0j2dd1et08fsn4dusucvhlbp6pv5hpa@xxxxxxxxxx
On Fri, 13 Oct 2006 21:36:12 GMT, "Wilco Dijkstra"
<Wilco_dot_Dijkstra@xxxxxxxxxxxx> wrote:

By the way, I'd like you to follow up on my question regarding the
following exchange. Since you had professional experiences here, I'd
like to hear what you say:

In my last job I worked on a compiler for 10 years, and in that time
its performance improved by 50% and its codesize by 30%.
I would call that a good improvement rate, especially considering
the compiler was pretty good to start with.

What precisely do you attribute these changes to? At least, what are
the few more important changes?

Some of the large improvements were loop unrolling, inlining, and
library optimizations (floating point emulation, memcpy etc). A
smart calling standard helped too - I quickly got rid of frame
pointers and other unnecessary baggage like compiler
temporaries choking up the registers.

But those together amount to less than a quarter of the total gain.
Most of the improvements came from concentrating on very low
level optimizations and fine tuning every bit of the compiler. This
was possible by continuous benchmarking to ensure progress.

I did a lot of staring at compiler output of actual customer code to
spot cases where the compiler could improve. By focusing on
things that matter (ie. real world code) it was possible to identify
the weak spots and fix them. In most of these cases simple
optimizations were all that was needed, for example expression
simplifications, peepholes or tuning of a particular optimization.

I have done a lot of comparisons with the competition. Almost
invariably they concentrate on high-level optimizations and can
do interesting stuff that I could only dream of. However we
still won due to using the instruction set more efficiently and so
emitting fewer instructions in the end. For a comparison, GCC
still hasn't beaten our 10 year old compiler, despite a huge
amount of effort and using the latest advances (fashion?) in
compiler technology.

Using the instruction set efficiently appears to be the key. If you
teach the compiler to use instructions with writeback, conditional
execution, select the more esoteric instructions like wide or
narrow multiplies, etc then you end up with code that is as good
as assembler written by an expert. I've been surprised more
than once by the way the compiler combines several simple
optimizations and ends up with amazing code.

To give a small example - byte wise strcmp:

while (t0 = *p++, t1 = *q++, t0 >= 1 && t0 == t1);

translates to the following optimal ARM code:

loop
LDRB t0, [p],#1
LDRB t1, [q],#1
CMP t0,#1
CMPCS t0,t1
BEQ loop

This is a feature called conditionalized comparisons. Compares
can be conditionally executed just like all other instructions on ARM
to avoid branches.

I remember noticing this when scanning a manual.

The compiler can combine several comparisons
like this with varying conditions and && or || combinations. It's a trick
few assembly programmers know, let alone use...

But some of us would, of course, notice and use at times.

As another example, ARM has multiple load and store instructions
which are often used to save & restore registers at function entry
and exit. You also may have to adjust the stack pointer. Rather than
using 4 instructions it is often possible to push a few extra registers
thus needing only 2 instructions. This kind of trick makes the code
that deals with this extremely complex as it needs to handle many
special cases, but it helps a lot as functions are small on average.

Understood. Special cases are exactly where a human can excel, at
least pretty often.

So there you are. Probably not what you wanted to hear... Compiler
design is not about sexy new optimizations, it's just plain good old
engineering, implementing a huge amount of smart tricks and taking
care of every single detail while at the same time understanding
what matters most in the big picture. Very challenging but rewarding!

Actually, this was a lovely discussion. Some of the above is what I'm
quite used to seeing in compilers. Some makes me a little interested
in looking more at ARM, again.

Have you taken a look at the ADSP-21xx processors? They allow special
case packing (you mention "many special cases" and the ADSP-21xx has a
bevy of such things) of up to three instructions in a single word. I
will often promote calculations or moves many tens or hundreds of
instructions behind where they are actually needed, in order to
achieve high density. I'd love to show you a few examples for you to
think on how you'd manage them in a C compiler. Frankly, I don't
doubt it could largely be done -- but it would be fun to discuss
exactly how. This would definitely include trace scheduling to move
calculations above branch edges, for example.

Thanks for the time. Much appreciated. I will pose to you this
example:

unsigned int gcd (unsigned int a, unsigned int b)
{
if (a == 0 && b == 0)
b= 1;
else if (b == 0)
b= a;
else if (a != 0)
while (a != b)
if (a < b)
b -= a;
else
a -= b;
return b;
}

I think Walter will remember this one.

You can easily deduce the boundary conditions this routine is required
to handle from a cursory examination of the code, so I won't write a
spec for it. None needed.

I have taken the time on the x86 to run this through quite a number of
compilers and _none_ of them can 'see' the topology change that a good
assembly programmer can, in writing this for the x86.

I have never written a single line of ARM assembly code and I am
completely unfamiliar with the instruction set, except from a very
general overview point of view, but I might be able to try my hand at
it just the same with something smaller like this. It will take me
some work to get familiar and, probably, I will miss some details you
will then remind me about. Perhaps you might consider popping this
through your compiler (or another one, as you like) and then also
telling me what you personally can "see" here as some alternative ways
of looking at it.

I honestly only know where this takes me with the x86, so I'm at a
disadvantage in the sense that I do NOT know how this plays elsewhere
and it certainly may toss me some surprises, too. You know compiler
technology better than I do, as well. I'm just a lowly application
programmer. But the process is always interesting for me to see
unfold.

I don't mean any of this as some kind of C vs assembly challenge, but
only as a learning experience for all. No matter how this plays out,
it does NOT reflect on either. It's just interesting, that's all.

Jon
.

Relevant Pages

  • Re: Migrating ARM9E codebase to ARM11
    ... > optimizations done using hand-coding, only the control code is left to ... You should then consider upgrading to a newer compiler. ... wish to target might be faster than the assembler optimised for the 9E. ... I do not believe that the ARM ARM for architecture version 6 has been ...
    (comp.sys.arm)
  • Re: Interesting article by Randall Hyde
    ... > assembler is that the assembler should generate _exactly_ what I ... any assembler that did optimizations would have to offer you ... But advanced programmers should be able to take advantage of compiler ... As a RL programmer I expect no such thing. ...
    (comp.lang.asm.x86)
  • Re: What micros do you actually hate to work with?
    ... the compiler was pretty good to start with. ... level optimizations and fine tuning every bit of the compiler. ... emitting fewer instructions in the end. ... can be conditionally executed just like all other instructions on ARM ...
    (comp.arch.embedded)
  • Re: Can you write code directly in CIL ???
    ... >>> single IL instruction translates to x assembly level instructions where x is ... > method and it's compiler generated IL method. ... >> The JIT probably does all the processor specific optimizations. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Some clarification on "Pre-Parsers" and other bits
    ... which is then feed to a assembler. ... To do decent optimizations, the ... compiler will work on an abstract representation of the source program ... anyway for a decent amount of it's optimizations. ...
    (alt.lang.asm)