Re: Compilation Was: Is DEFCONSTANT broken?

Duane Rettig <duane@xxxxxxxxx> writes:

On Jun 25, 1:28 am, p...@xxxxxxxxxxxxxxxxx (Pascal J. Bourguignon)
wrote:
Duane Rettig <du...@xxxxxxxxx> writes:
The problem here is that the whole reason for
compilation is to reduce code complexity, and having these hooks to
break these simplifications goes against the goal of compilation.  

This surprize me.

I thought that the purpose of compilation was foremost to optimize
speed.

No, although that's usually a by-product, and thus the user tends to
make that a goal.

We wouldn't want to merely translate to a different target machine, if
it didn't allow to run faster. There'd be no money in compilers.

So if it's not porting a program from one VM to another, and it's not
for speed, why do we want to compile?


I'm not sure that it reduces code complexity.  For a start, assembler
is harder to read than high level language.

Harder for whom or what? It's certainly easier to read for the
executing machine. And we're not talking about readability, but
complexity. And, by the way, assembler code is not compiled code; it
is also source code which must be assembled in order to execute
directly on a machine. You might consider assembler to be equivalent
to machine code, because you usually have excellent disassembling
tools, which reintroduce the complexities of mnemonic names,
connections between jump instructions and their target labels
(remember, though, that labels don't actually exist in machine code -
they are just instructions which happen to be the target of the jump).

Yes, with plain assemblers and simple enough processors, there's a
quasi bijection between assembler text and binary. But I'm aware of
the difference, only I don't think it's signficative. My bet is that
assembler and binary have a complexity ratio close to 1 (see below).


 Then the compiler may
open code, inline, unroll loops, and implement any other kind of trick
which dilutes abstractions a lot, which I understand as rendering the
code more complex, not less.

Actually, quite the opposite. A loop is more complex than straight-
line code; it has a branch instruction within it, which is well-
understood to create pipeline stalls, unless the hardware has the
added complexity itself to duplicate effort in order to perform branch
prediction. No, the simplest code is the fully-unrolled loop which
executes no branches, but which simply performs the required
instructions. Is it necessarily optimal? No, because code size does
factor into the mix, and so the fact that loops are only unrolled
partially is due to tradeoffs between code complexity and instruction
cache size.


We fight complexity with abstractions. Which is mostly inventing new
levels of source code generating the existing lower level of lisp, VOP
or binary. If adding an abstraction didn't reduce the complexity we
wouldn't do it, we'd keep programming in assembler.

Another way to see it is to consider that a complex object is harder
to compress than a simplier object.

I'd assert that:

1- Program sources are more compressible than program binaries.

2- Compressed sources of a given program are smaller than
compressed binaries of the same program.

Which would tend to show that sources are less complex than binaries.

Let's take a sizable commercial embedded application as example:

text bzip2 -9 Compression ratio
Source (C++) 16435727 1304451 0.079
Binary (x86, stripped) 10587432 3039129 0.287
Complexity ratio (binary/source): 2.330

(I consider coarsely bzip2 -9 to be a majoration of Kolmogorov's
complexity).


--
__Pascal Bourguignon__
.

Relevant Pages

  • Re: Compilation Was: Is DEFCONSTANT broken?
    ... compilation is to reduce code complexity, ... There's money in compilers? ...  And, by the way, assembler code is not compiled code; it ... they are just instructions which happen to be the target of the jump). ...
    (comp.lang.lisp)
  • Compilation Was: Is DEFCONSTANT broken?
    ... break these simplifications goes against the goal of compilation. ... I'm not sure that it reduces code complexity. ... Perhaps you mean that the target virtual machine is usually simplier ...
    (comp.lang.lisp)
  • Re: Compilation Was: Is DEFCONSTANT broken?
    ... compilation is to reduce code complexity, ... break these simplifications goes against the goal of compilation. ... And, by the way, assembler code is not compiled code; ... they are just instructions which happen to be the target of the jump). ...
    (comp.lang.lisp)
  • Re: Compilation Was: Is DEFCONSTANT broken?
    ... break these simplifications goes against the goal of compilation. ... We fight complexity with abstractions. ... instructions. ... level to low level is one of increasing simplicity. ...
    (comp.lang.lisp)
  • Re: object file size is reduced after build
    ... LOC without requiring a great deal of complexity. ... pre-process the source - this saves headaches with comments ... and conditional compilation and stuff; ... and compile for pure code (i.e. no debuggery, ...
    (comp.lang.c)