Subject: RE: [hackers-il] Summary of a Bash Lecture

From: Chen Shapira <[email-masked]>
Date: Wed, 15 Nov 2000 13:10:34 +0200

> The urban legend (I don't know if it's true either) was that it caused
> a space probe (unmanned) to crash.
> At least, that's the way Tim Peters tells it.

Van der-Linden verifies its authenticity in "Deep C Secrets"

BTW. Is there any knowledge about a theoretical limit of how well a language
can be optimised "by design"?

Meaning: a program written in c can be optimised for speed until it takes x
seconds to run and no farther, while the same program in pascal can be
optimised until it takes y seconds to run and no farther, where x!=y?

Considering that everything is turing complete it sounds improbable, but I
suppose C can be better optimised than perl by knowing types on compile
time, so there are language design limits. What about using OO language -
does that affect speed?

Thanks,
Chen.

---

From: Moshe Zadka <[email-masked]>
Date: Wed, 15 Nov 2000 14:28:24 +0200 (IST)

> can be optimised "by design"?

Depends on what you mean, you'll probably get into
halting-problem-equivalent problem pretty soon.

> time, so there are language design limits. What about using OO language -

If you give me an oracle which answers the halting problem, I can probably
optimize rograms in any language the same. OTOH, without such an oracle, 
any optimizer works by heuristics, so what you're asking has litle
theoreticalmeanning. Also, consider the fact that "optimization" is not
well defined. If you have two programs, one that runs faster on input "a",
and one that runs faster on input "b", which one is optimal? What about
different configurations (say, some algorithms wouild cause thrashing if
there is too litle memory).

--
Moshe Zadka <[email-masked]> -- 95855124
http://advogato.org/person/moshez

---

From: "Nadav Har'El" <[email-masked]>
Date: Wed, 15 Nov 2000 15:20:56 +0200

> optimised until it takes y seconds to run and no farther, where x!=y?

The "obvious" answer is that all languages can be optimized the same: if the
optimizer is smart enough, and given a program in C that can somehow be run
faster if written in Fortran, then the super-smart optimizer can convert the
program to Fortran as its first step.

But in real life, this is not so simple. Consider the following zsh script:

let i=0
CMD="let i++"

if [[ `date` = "never" ]]
then
        CMD="let i+=2"
fi

for j in a b c
do
        eval $CMD
done
print $i

This can be optimized (if the optimizer is smart enough) to
if [[ `date` = "never" ]]
then
        print 6
else
	print 3
fi

But if you realise that date can never return "never" (sounds like a James
Bond movie...), then it can be further optimized to
print 3

This looks like a contrived example, and it is, but it shows a point: a
smart enough optimizer can take code in Zsh, Perl, C++, or whatever, and
optimize it into the best possible assembly-language code (i.e., that no
other code that does the same thing runs faster). But how do you define
"doing the same thing"? Instead of running the "date" program, the shell
compiler/optimizer could call ctime() directly. But what if the installed
date program has some strange side-effects (e.g., changing the access time
of the file "/bin/date"!) that the program relies on? Maybe the whole point
of the above program was to be a "touch -a /bin/date" clone, and the "let i=.."
stuff, not the `date` stuff, needs to be optimized out?

The problem is that different languages let you do pretty high-level things
that each has dozens of implications and/or side-effects, so keeping all these
side-effects may mean we can't do any optimization at all...

As another example, consider a Tcl/Tk program (I hope you know what I'm
talking about). In Tcl/Tk, the callbacks of widgets are written in the
interpreted language Tcl; Because of this fact you (the programmer) can
change widget bindings on the fly, and other crazy stuff like that. And
all this interpreting is slow. It is obvious that it is possible to write
a different program in (say) C/Xlib, that does exactly the same thing, but
quicker, but making this transformation (also known as "optimization" - the
distinction between a "compiler" and "optimizer" in this context is a little
fuzzy) is nearly impossible in practice... Also, does this C/Xlib really does
the *same* thing? The Tcl/Tk program might be able to read widget bindings
from a user's script file, and the C/Xlib will not... So it's not exactly the
same thing - who decides if this optimization is a good enough approximation?

-- 
Nadav Har'El                        |  Wednesday, Nov 15 2000, 17 Heshvan 5761
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Willpower: The ability to eat only one
http://nadav.harel.org.il           |salted peanut.