Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3775 > unrolled thread

the death of optimization compiler

Back to article view | Back to comp.compilers

Contents

  the death of optimization compiler Anton Antimo <anton@safunu.org> - 2026-10-12 18:17 -0300
    Re: the death of optimization compiler anton@mips.complang.tuwien.ac.at - 2026-10-16 10:41 +0000
      Re: the death of optimization compiler tfb <tfb@work.it.out> - 2026-10-16 17:52 +0000
      Re: the death of optimization compiler Stefan Monnier <monnier@iro.umontreal.ca> - 2026-10-16 18:52 -0400
        Re: the death of optimization compiler Derek M Jones <derek@knosof.co.uk> - 2026-10-17 20:42 +0100
      Re: the death of optimization compiler Stefan Monnier <monnier@iro.umontreal.ca> - 2026-10-16 18:47 -0400

#3775 — the death of optimization compiler

I recalled this lecture and these quotes recently when I was looking at
the syntax of the Rust programming language, seeing how the programmer
is to supposed to tell the compiler what is mutable so that the compiler
can in turn handle memory management.  I'm not particularly interested
in memory management, but it seems to be an illustration of how
programmer teams up with machine to solve problems---and how the Lisp
language seems to be a great fit for the job (for the reasons expressed
by Knuth in the quote at end of this post).

So I'm choosing comp.lang.lisp as the follow-up-to newsgroups because I
think this post is more about Lisp than compilers.  But the quotes here
might get the interest of comp.compilers in particular because it's been
many years now and people might want to discuss what has changed, if
anything.

--8<-------------------------------------------------------->8---
  Daniel J. Bernstein in 2015:

    Wikipedia: --- ``By the late 1990s for even performance sensitive
    code, optimizing compilers exceeded the performance of human
    experts.''

  Bernstein: --- ``The experts disagree, and hold the speed records.''

  Mike Pall, LuaJIT author in 2011:

  --- ``If you write an interpreter, [...]  [t]here’s just no way you
  can reasonably expect even the most advanced C compilers to [optimize
  it] on your behalf.''

  Source: ``The death of optimizing compilers'', Daniel J. Bernstein,
  University of Illinois at Chicago, Technische Universiteit Eindhoven,
  lecture from April 16th, 2015.
--8<-------------------------------------------------------->8---

In 1974, Donald Knuth had already remarked:

--8<-------------------------------------------------------->8---
  For 15 years or so I have been trying to think of how to write a
  compiler that really produces top quality code.  For example, most of
  the MIX programs in my books are considerably more efficient than any
  of today’s most visionary compiling schemes would be able to
  produce. [...]  We [...] always [ran] up against the same problem: the
  compiler needs to be in a dialog with the programmer; it needs to know
  properties of the data, and whether certain cases can arise, etc.

  For some reason we all (especially me) had a mental block about
  optimization, namely that we always regarded it as a behind-the-
  scenes activity, [...] which the programmer isn’t supposed to know.
  This veil was first lifted from my eyes in [...] 1973, when I ran
  across a remark by Hoare [...] that, ideally, a language should be
  designed so that an optimizing compiler can describe its optimizations
  in the source language.  Of course!  Why hadn’t I ever thought of it?

  A program-manipulation system is obviously what we’ve been leading up
  to, and I wonder why I never thought of it before.  Of course, the
  idea isn’t original with me; when I told Hoare, he said, “Exactly!”
  and referred me to a recent work by Darlington and Burstall [...]
  which describes a system which removes some recursions from a
  LISP-like language (curiously, without introducing any [go-to]’s)
  [...].  Since LISP programs are easily manipulated as LISP [...]
  objects, there has also been a rather extensive development of similar
  ideas in this domain, notably by Warren Teitelman [...].  The time is
  clearly ripe for program-manipulation systems, and a great deal of
  further work suggests itself.

  Source: ``Structured programming with go to statements,'' Donald
  E. Knuth, ACM Computing Surveys (CSUR) 6.4 (1974): 261--301.
--8<-------------------------------------------------------->8---

It seems to me that telling the compiler what is mutable is a clear
illustration of how a compiler is in dialog with the programmer, just
like declaring a variable's type, with the C ``register'' keyword as
another example.  And Common Lisp with its declare-optimize-speed
directives right at the place where the programmer wishes for compiler
help seems to be another illustration of what Knuth is talking about in
his paper.

So it seems that Knuth and Hoare were indeed insightful in the 70s.

And it's mysterious to me how people always implement a new syntax for
their language when the Lisp syntax is so suitable for program
manipulation as Knuth mentioned.  My hypothesis is that syntax turns out
to be easily implemented, so people always try to leave their mark by
inventing a new one.  Clojure, for example, is a great example of how
sophisticated Java could have been since its inception.  But I guess
Lisp's syntax is not considered pedestrian, right?
[I left this in both groups since it seems an interesting compiler question. -John]

[toc] | [next] | [standalone]

#3776

Anton Antimo <anton@safunu.org> writes:
>In 1974, Donald Knuth had already remarked:
>
>--8<-------------------------------------------------------->8---
>  For 15 years or so I have been trying to think of how to write a
>  compiler that really produces top quality code.  For example, most of
>  the MIX programs in my books are considerably more efficient than any
>  of today���s most visionary compiling schemes would be able to
>  produce. [...]  We [...] always [ran] up against the same problem: the
>  compiler needs to be in a dialog with the programmer; it needs to know
>  properties of the data, and whether certain cases can arise, etc.
>
>  For some reason we all (especially me) had a mental block about
>  optimization, namely that we always regarded it as a behind-the-
>  scenes activity, [...] which the programmer isn���t supposed to know.
>  This veil was first lifted from my eyes in [...] 1973, when I ran
>  across a remark by Hoare [...] that, ideally, a language should be
>  designed so that an optimizing compiler can describe its optimizations
>  in the source language.  Of course!  Why hadn���t I ever thought of it?
>
>  A program-manipulation system is obviously what we���ve been leading up
>  to, and I wonder why I never thought of it before.  Of course, the
>  idea isn't original with me; when I told Hoare, he said, ``Exactly!''
>  and referred me to a recent work by Darlington and Burstall [...]
>  which describes a system which removes some recursions from a
>  LISP-like language (curiously, without introducing any [go-to]���s)
>  [...].  Since LISP programs are easily manipulated as LISP [...]
>  objects, there has also been a rather extensive development of similar
>  ideas in this domain, notably by Warren Teitelman [...].  The time is
>  clearly ripe for program-manipulation systems, and a great deal of
>  further work suggests itself.
>
>  Source: ``Structured programming with go to statements,'' Donald
>  E. Knuth, ACM Computing Surveys (CSUR) 6.4 (1974): 261--301.
>--8<-------------------------------------------------------->8---

This reminds me the research project CIP (Computer-Aided,
Intuition-Guided Programming): They designed a wide-spectrum language
CIP-L (described in LNCS 183, published 1985) and a program
transformation system CIP-S (described in LNCS 292, published 1987).
The idea was that you write a specification in CIP-L, and then tell
CIP-S to perform various transformation steps, that eventually result
in an executable and efficient program.

This idea looked interesting, amd I looked in the books, but did not
find them inspiring apart from the basic idea.  And apparently the
idea has not taken the world by storm, not even in the research world
(according to Springer there are 63 citations of LNCS 183 and 45 of
LNCS 292).

It seems that we prefer to write executable programs from the start,
and either optimize them by applying transformations manually, or
fully automatic (using an optimizing compiler), not
semi-automatically.  I guess one of the problems of the idea of
semi-automatic transformations is that the transformations are no
longer applicable after changes due to changes in requirements.  So
you either want to apply the changes to the transformed program (and
when you transform it manually, and treat the transformed program as
the new source, you can easily apply changes to the transformed
program), or you want fully automatic transformation, even if you only
get a best-effort result.

>It seems to me that telling the compiler what is mutable is a clear
>illustration of how a compiler is in dialog with the programmer, just
>like declaring a variable's type, with the C ``register'' keyword as
>another example.

It's actually a monolog.  You might consider that error messages from
a compiler turn it into a dialog, but that's not how programming in
most languages works (including Lisp, while Rust may be the exception
that proves the rule).

But that should not distract from the idea that one should be able to
express the optimized code in the source language.  And in many
respects C (not the standardized subset) gives us that.  E.g., we can
search for the index of the smallest element in an array by writing it
in the common subset of Java and C:

  for (i=0, best=0; i<n; i++)
    if (a[i]<a[best])
      best=i;
  return best;

or by using pointer arithmetics, which is not in Java.

  for (p=a, bestp=a, endp=a+n; p<endp; p++)
    if (*p < *bestp)
      bestp = p;
  return bestp-a;

For the two versions gcc-10 -O3 produces the following code for RV64GC
for the loop body of this code:

Java-compliant      pointer arithmetics
#a0=best    a3=a[i] #a1=endp   a4=*p
#a1=n       a4=i    #a2=bestp  a5=p
#a2=a[best] a5=a+i  #a3=*bestp
L4: ld   a3,0(a5)   L4: ld   a4,0(a5)
    addi a5,a5,8
    bge  a3,a2,L3       bge  a4,a3,L3
    mv   a0,a4          mv   a2,a5
    mv   a2,a3          mv   a3,a4
L3: addi a4,a4,1    L3: addi a5,a5,8
    bne  a4,a1,L4       bltu a5,a1,L4

The actual instruction that is optimized away by using pointer
arithmetics is the second-to-last instruction of the Java-compliant
version and it corresponds to the "i++".  In the Java-compliant
version, the compiler introduces an induction variable in register a5
that has the same value as p has in the pointer arithmetics version.
For many loops over arrays, the compiler can then optimize the index
away with induction-variable elimination, but in this case it does
not.  So here we have a case where we can express an optimization in C
source code that the compiler does not optimize by itself.

"register" also used to be about that, too, but for a long time
(certainly with gcc), I have considered every auto variable going into
a register unless its address is taken or the compiler runs out of
registers.  But that's certainly the part of compilation where the
source code has the least influence on the object code, but I don't
see how this is avoidable given the differences between machines.
Maybe by providing register priority numbers (lower-numbered variables
are preferred in register allocation to higher-numbered ones) and
register classes (caller-saved, callee-saved; others); e.g. in

register("caller-saved"(92),"callee-saved"(328)) x;

the variable x would be considered for allocation to a caller-saved
register, and would not get it if all caller-saved registers are
allocated to variables with a lower number; in that case, it would be
allocated to a callee-saved register if there are any left when all
<328 have been allocated.  Or something like that.

Another case where C does not allow to optimize the code at the
source-code level is SIMD instructions.  GCC and clang support the GNU
C vector extensions
<https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html>, but these
extensions are limited and don't allow programmers to express all
operations supported by SIMD instruction sets nor all instructions
generated (when you are lucky) by auto-vectorization.  So I have
written loops like

    for (j = ncities-SIMD_SIZE; (long)j >= (long)i; j -= SIMD_SIZE) {
      [...]
      for (k=0; k<SIMD_SIZE; k++)
        if (dist[k]<closedist[k]) {
          closedist[k]=dist[k];
          closeidx[k] = baseidx[k]+j;
        }

... in the hope that one of the compilers actually turns the inner
loop into a few SIMD instructions.  Some actually do, with certain
flags, but I think that this is a very unsatisfactory way to tell the
compiler how it should optimize.

Concerning Lisp, my impression is that it is typically more removed
from the machine than C, but I dimly remember reading about a Scheme
implementation that uses a dialect/subset of Scheme that is closer to
the machine.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#3777

<anton@mips.complang.tuwien.ac.at> wrote:
>
> It's actually a monolog.  You might consider that error messages from
> a compiler turn it into a dialog, but that's not how programming in
> most languages works (including Lisp, while Rust may be the exception
> that proves the rule).
>

I've spent an awful lot of time incrementally modifying programs in
response to optimization notes from CL compilers: 'you didn't tell me
enough about this so I[*] couldn't infer a useful thing'; 'OK, here is some
more information', or 'OK, let me adjust how I expressed that'.

[*] Tragically, I probably now have to say that yes, I understand there is
no 'I' talking there.

--
tfeb.org/computer/

[toc] | [prev] | [next] | [standalone]

#3778

anton@mips.complang.tuwien.ac.at [2026-10-16 10:41:59] wrote:
> It seems that we prefer to write executable programs from the start,
> and either optimize them by applying transformations manually, or
> fully automatic (using an optimizing compiler), not
> semi-automatically.  I guess one of the problems of the idea of
> semi-automatic transformations is that the transformations are no
> longer applicable after changes due to changes in requirements.  So
> you either want to apply the changes to the transformed program (and
> when you transform it manually, and treat the transformed program as
> the new source, you can easily apply changes to the transformed
> program), or you want fully automatic transformation, even if you only
> get a best-effort result.

I often think about what it is that I want from my compilers.

For 99% of my code, the compiler does a good enough job, but for the
remaining case, I often would like to be able to state some specific
property which I'd like to get, but often it's hard to state it clearly
in terms of the source code in a way that will still make sense further
down the compilation stages.


=== Stefan

[toc] | [prev] | [next] | [standalone]

#3781

Stefan,

> For 99% of my code, the compiler does a good enough job, but for the
> remaining case, I often would like to be able to state some specific
> property which I'd like to get, but often it's hard to state it clearly
> in terms of the source code in a way that will still make sense further
> down the compilation stages.

I think that programming language could become a build time option
https://shape-of-code.com/2026/10/11/programming-language-choice-is-becoming-a-build-option/

Why not specify language constructs specific to your case
and modify the compiler to map these to the appropriate
optimised form?

Ok, at the moment, even with coding agents, this still requires
a decent chunk of work.

This time next year, it might on the way to being the norm.

--
Derek M. Jones           Evidence-based software engineering
blog:https://shape-of-code.com
[This reminds me of the extensible languages like EL/1 and IMP72 that were
popular in the 1970s.  They ended up being unusable because every program
was in a different language. -John]

[toc] | [prev] | [next] | [standalone]

#3779

anton@mips.complang.tuwien.ac.at [2026-10-16 10:41:59] wrote:
> This reminds me the research project CIP (Computer-Aided,
> Intuition-Guided Programming): They designed a wide-spectrum language
> CIP-L (described in LNCS 183, published 1985) and a program
> transformation system CIP-S (described in LNCS 292, published 1987).
> The idea was that you write a specification in CIP-L, and then tell
> CIP-S to perform various transformation steps, that eventually result
> in an executable and efficient program.
>
> This idea looked interesting, amd I looked in the books, but did not
> find them inspiring apart from the basic idea.  And apparently the
> idea has not taken the world by storm, not even in the research world
> (according to Springer there are 63 citations of LNCS 183 and 45 of
> LNCS 292).

Thanks, I didn't know about that project.

A modern take on a similar idea might be

    https://rise-lang.org/

They claim to be able to generate very efficient parallel numerical code
from a high-level source in a pure functional language.


=== Stefan

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web