Subject: Do Faster Computers Imply Slower Code?

From: Shlomi Fish <[email-masked]>
Date: Fri, 31 May 2002 19:15:41 +0300 (IDT)

I had a discussion with two distinguished haifuxers the other day, about
whether the fact that computers are becoming faster, has a negative impact
on the algorithms that people use inside their code. It is a well accepted
fact that some newer programs cannot be effectively run on slower
computers. And the questions that has to be raised is whether it is a
necessary result of implementing all the features, or that it has a
deliberately sub-optimal code.

The first stable version of Freecell Solver was slower by an order of 50
than the second one. Still, it ran fast enough on my computer (a Pentium
166) and so I thought I did everything fine. Many of the programmers that
work on different projects, are not more experienced than I was at that
point, and so may code a lot of inefficient code, and leave it at that
because it still runs fast enough on their iron.

I also remember a program I wrote when I worked on Smart-Link, that
managed a couple of driver configuration files as something that was
inherently not designed well. I had a dialog with several fields and each
field became apparent in one or more places in the files. What I did, was
that whenever the apply button was pressed, I went over all the changes,
and for each change I read the relevant file, and wrote it again, while
modifying the relevant line. It worked well enough for local hard-drives,
but took a noticable amount of time when working accessing LAN
volumes.

I thought of a better design (keeping a collection of changes that are
processed concurrently, or doubly-linked lists of the files' lines or
both), shortly after I wrote the original code, but was not assigned to
refactor it before I left.

Maybe I can think of more places where I wrote inherently broken code like
that. One of the reasons I like Perl is that it reduces the risk of
writing bad code like that considerably, due to its strong support of data
structures and similar mechanisms.

Regards,

	Shlomi Fish

There is no IGLU Cabal! The IGLU Cabal "Content Management Software" can
only run in reasonable speed on a machine the scope of an SGI Origin 2000
super-computer, which the IGLU Cabalists could not afford to buy.

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: OmerM <[email-masked]>
Date: Fri, 31 May 2002 20:03:26 +0300

> deliberately sub-optimal code.

The question is whether the fact that programs tend to be slower
is a problem on itself, or is a sympthom of a more interesting 
trend in software development.

More and more people are turning to scripting languages in those days.
Code maintainability and ease of development gain more priority than 
raw speed in majority of projects these days.

Maybe we should take it for granted that if code is not developed to 
be a speedster, it will be slower these days due to change in conceptions
about what a good code is?

> structures and similar mechanisms.

Let me tell a story from my trenches:)

I had got a project to maintain and to improve. Its performance was good, 
however it was stated as inacceptable. The speed had had to be raised.

After consulting profiler ( Rational Quantify ) I had performed following 
optimisations:
   
    Elliminated object copying in all but 2 places - in input and in output.
    All object processing was done on const references ( which are isomorphic
    to pointers for sake of discussion ).

    Changed data structure to be lineary aligned in memory instead of being
    dynamicly layed out. That caused object comparision to perform much
    faster.

Overall performance gain was almost thrice. No algorithm tuning was involved.
Although Jon Bently tells that algorithm tuning is the key for optimisation 
and for writing high performance code, my practice makes me agree with Chen:
Most of the algorithms we are using today are already good.
The devil is still in the details.

---

From: Shlomi Fish <[email-masked]>
Date: Sat, 1 Jun 2002 02:57:51 +0300 (IDT)

> about what a good code is?

My point was that given the choice of a language, many programmers will
use sub-optimal algorithms or techniques, that will make the programs
slower. I'm not talking about making the code slower due to modularity or
ease of development. I'm talking about "brain-dead" or erroneous design.

> The devil is still in the details.

Maybe I should have phrased myself better. I'd like to discuss the
overhaul program's design, including various programming language specific
details.

Regards,

	Shlomi Fish

> >
> > Regards,
> >
> > 	Shlomi Fish
>
>
> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

---

From: "Nadav Har'El" <[email-masked]>
Date: Sat, 1 Jun 2002 19:34:50 +0300

> deliberately sub-optimal code.

My experience (watching my designs and programs, and those of people around me)
tells me that what you describe as sub-optimal code arises from 4 factors:

1. One of the most annoying factor is the latest hypes in software development
   like C++, design patterns, extreme programming, and things like that
   (please don't get me wrong, I'm not against these things - I just have a few
   gripes against them).  People who read books that subscribe to these hypes
   (or who listen to managers that do) learn that the most important thing is
   some sort of philosophical "extendibility" (whether this really allows
   someone to extend the program is many times in doubt), not giving a rat's
   ass on whether this creates in the process 70 layers of classes, virtual
   functions, and who-knows-what every time you want assign to some variable.
   Stuff like templates and other features of C++ cause huge code size as
   well as slow run time.

2. No Optimization: Knuth tells us "premature optimization is the root of
   all evil". Indeed, common wisdom (or hype, see #1 above) tells us that
   only 20% of the code takes up 80% of the run time, so only that 20% should
   be optimized, *after* the code is done. What happens in reality is that
   many programmers don't do any optimization: when they need an algorithm,
   they just pick one that works (without thinking too much which), perhaps
   the first thing they think about from some library (see #3). Since
   computers are now faster, they never go back to optimize it: they don't
   care that some operation that should have taken a millisecond takes a
   100 miliseconds, and they don't care that their program is unusable on huge
   inputs (that is a common thing in Windows, or at least used to - I haven't
   touched Windows in almost two years) and unscalable when you want to
   repeat this "short" operation hundreds of times.

3. Overuse of Libraries: Use of libraries (e.g., C++'s STL) is (and should be)
   encouraged (see also #1, hype). However, this causes many programmers to
   become careless when they use libraries. They use dozens of features from
   a huge library without thinking twice on the impact this has on the code
   size and run time of the program. Worse, when a feature one needs is not
   readily available in the library some programmers tend to use something
   close that *is* available in the library, even at some performace cost:
   for example C++'s STL maps vs. hashes.
   Libraries, also, tend to be very general to accomodate all the users'
   needs, causing code bloat and also slowness (even code-bloat can cause
   slowness on its own, because of modern processors' limited instruction
   cache).

4. Scripting: It is obvious why adding a scripting language to some project,
   and then writing some of the project's code in a scripting language can,
   in addition to the obvious advantages, cause the code to be slower and
   in some cases bigger.

> because it still runs fast enough on their iron.

Yes, this is my #2 above.

-- 
Nadav Har'El                        |      Saturday, Jun 1 2002, 22 Sivan 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Anyone who quotes me in their sig is an
http://nadav.harel.org.il           |idiot. -- Rusty Russell.

---

From: Shlomi Fish <[email-masked]>
Date: Sat, 1 Jun 2002 21:44:19 +0300 (IDT)

>    Stuff like templates and other features of C++ cause huge code size as

It is possible that the code should be modular, but by no means
over-engineered. I did not really encounter a code that was as beastly as
you describe, but it probably would cause it to be bloated.

>    repeat this "short" operation hundreds of times.

That was my point to begin with. The question is how can we educate
programmers to avoid doing it?

>    in addition to the obvious advantages, cause the code to be slower and

Scripting languages should be used with care. I don't really see using
scripting languages as a problem on its own. Sure, a CPU-intensive Perl
script would run as slow as hell on a 8088 processor, but then again I
think most C programs run slowly on CP/M computers. Sometimes, a script
would run almost as quickly as a C program. You usually have to optimize
only certain key places with C code to get an optimal run time.

Regards,

	Shlomi Fish

---

From: Tzafrir Cohen <[email-masked]>
Date: Sat, 1 Jun 2002 21:53:06 +0300 (IDT)

On Sat, 1 Jun 2002, Shlomi Fish wrote:

> > tells me that what you describeas sub-optimal code arises from 4 factors:
> >

Look at a number of recent cross-platform programs:

* abiword
* mozilla
* OpenOffice

The latter two take extra time to load and considerable place to compile
(espcially OpenOffice).

Mozilla has a good excuse, because it really spans across many platforms
(windows, mac, linux, many unixes, to begin with, and there are a number
of other ports). OpenOffice currently has less ports (win32, a number of
unix system, mac OSX)and much more code. It is definitly a beast in terms
of code size.

IIRC abiword runs generally on the same platforms as OpenOffice, but loads
much faster.

Displaimer: I don't know very well the code of nither of the three
projects.

-- 
Tzafrir Cohen
mailto:[email-masked]
http://www.technion.ac.il/~tzafrir

---

From: Oleg Goldshmidt <[email-masked]>
Date: 02 Jun 2002 09:02:12 +0300

OmerM <[email-masked]> writes:

> Overall performance gain was almost thrice. 

Which means, I assume, that you had a very strict limit on the
performance of the application, and you were just above the limit, and
now you are just below. One situation where it is often the case is
interactive applications, where computing something in 1.5 seconds is
acceptable, but in 4.5 seconds isn't.

Otherwise, you should not have bothered about a factor of three... ;-)

> No algorithm tuning was involved.  Although Jon Bently tells that
> algorithm tuning is the key for optimisation and for writing high
> performance code, my practice makes me agree with Chen: Most of the
> algorithms we are using today are already good.

I 'd say you are relly lucky. My experience differs.

> The devil is still in the details.

When you are trying to squeeze another 20% (or 200%) out of the code,
you are probably right. When you need orders of magnitude, look at
your algorithms and data structures - details will not give you a
_real_ (tm) performance boost.

-- 
Oleg Goldshmidt | [email-masked] 
"A sense of the fundamental decencies is parceled out unequally at birth."

---

From: Oleg Goldshmidt <[email-masked]>
Date: 02 Jun 2002 09:10:00 +0300

Shlomi Fish <[email-masked]> writes:

> I had a discussion with two distinguished haifuxers the other day,
> about whether the fact that computers are becoming faster, has a
> negative impact on the algorithms that people use inside their
> code. It is a well accepted fact that some newer programs cannot be
> effectively run on slower computers.

One side of it is that nowadays people routinely write and run
programs that are too heavy for older computers. For instance, I
witnessed myself the transition from extensive research into advanced
algorithms, approximation techniques, and numerical methods to
straightforward heavy simulations (in science and finance) which
happened simply because now such simulations are feasible even on a
"PC". Simpler, more generic and straightforward algorithms tend to be
developed faster, with fewer mistakes, and are usually more generic,
flexible and extendable than highly optimized, custom ones.

---

From: OmerM <[email-masked]>
Date: Sun, 2 Jun 2002 10:08:22 +0300

On Sunday 02 June 2002 09:02, Oleg Goldshmidt wrote:
> >     Elliminated object copying in all but 2 places - in input and in
> > output. All object processing was done on const references ( which are
> > isomorphic to pointers for sake of discussion ).
> >
> >     Changed data structure to be lineary aligned in memory instead of
> > being dynamicly layed out. That caused object comparision to perform much
> > faster.
> >

Your assumptions are right.
It was a hard real-time code with wall-clock execution limits :(.

---

From: "Nadav Har'El" <[email-masked]>
Date: Sun, 2 Jun 2002 12:15:55 +0300

> programs that are too heavy for older computers. For instance, I

Yes. An interesting paper about the problems people faced on older
computers with very limited memories and slow CPUs is M. D. McIlroy's
"Development of a Spelling List", http://www.cs.dartmouth.edu/~doug/spell.ps.gz

This paper was published in 1982 (IEEE Trans. on Communications) and
describes how the UNIX "spell" works. Many of the design choices that
you'll find there where dictated by the wish of "spell" to be a quick
and take little (in our standards) memory.

A programmer today might have forgone all this (interesting) waste of time
and use STL (for example) to hold the data structures. This might make
spellchecking a 5500 word document take 2 seconds and 2MB of memory
instead of 0.2 seconds and 200KB of memory, perfectly acceptable now
but not at the time when McIlroy wrote his spell-checker, when checking
that 5500 word document using his algorithms took as much as 65 seconds on
his PDP11/70 and put a real strain on its memory (which was as little
as 64 KB of memory, if I remember correctly; This was a 1975 machine with a
22-bit memory management limited to 4MB, see
http://www.village.org/pdp11/faq.pages/11model.html and
http://www.psych.usyd.edu.au/pdp-11/11_70.html).

-- 
Nadav Har'El                        |        Sunday, Jun 2 2002, 22 Sivan 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |A Life? Cool! Where can I download one of
http://nadav.harel.org.il           |those from?

---

From: Shlomi Fish <[email-masked]>
Date: Sun, 2 Jun 2002 13:56:48 +0300 (IDT)

> flexible and extendable than highly optimized, custom ones.

Isn't it possible to write APIs that would abstract some of that
functionality away? Making the simulations faster, but just as
straightforward to program. In the Freecell solving world, there is a
friendly competition among Freecell solver coders in which they (including
me) try to make their solvers better solvers for range of deals. This is
one case where you can't rely on the speed of the computer to save you,
because a comparable solver would still run faster.

Do you think we will always find certain tasks that will require more
computing power than we have? Examples I can think of at present:

1. Calculating the Air Thrust on Airplanes at Sub-Sonic Speeds. (a very
heavy task)

2. Choice of a programming language dictates more power. Slashdot runs on
5 pretty spiffy servers, because it is written in Perl, and uses an SQL
database.

3. Solving a Range of Games.

4. Chess Playing a la Deep Blue. But I heard that Sony Playstation 3 would
have more power than it.

5. Other Heavy Simulations - Orna can testify that at Raphael they have a
cluster of Linux workstations, and they still need to run some jobs
overnight.

6. Searching a lot of information - Google has a farm of several
thousands computers.

7. More generally - being able to sustain a large amount of load.

Regards,

	Shlomi Fish

---

From: Omer Musaev <[email-masked]>
Date: Sun, 2 Jun 2002 14:18:44 +0300

On Sunday 02 June 2002 13:56, Shlomi Fish wrote:
> functionality away?

I guess it is possible:)

However, a process of abstracting out that functionality in favor 
of readability/clearness is not trivial.

As a certain ( not the only, and IMHO not the prefferred on most 
of hackers-il members ) way to manage that process, I can recall
"Policy based Design", 

The application of Policy based Design is described nicely in 
MC++D cp.1 (http://www.aw.com/samplechapter/0201704315.pdf)

The quintessence of Policy based Design is that clear separation is
held between needed functionality and existing functionality. As
long as there are multiple ways to get needed functionality from
entities that provide existing functionality, a policy is defined.

> computing power than we have? Examples I can think of at present:

Yes, IMHO there will always be such tasks.

> 	Shlomi Fish
[40 lines of junk deleted]

---

From: "Nadav Har'El" <[email-masked]>
Date: Sun, 2 Jun 2002 14:39:38 +0300

> MC++D cp.1 (http://www.aw.com/samplechapter/0201704315.pdf)

I feel really silly to ask this, but what book is this chapter a part of?

-- 
Nadav Har'El                        |        Sunday, Jun 2 2002, 22 Sivan 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Can Microsoft make a product that doesn't
http://nadav.harel.org.il           |suck? Yes, a vacuum cleaner!

---

From: OmerM <[email-masked]>
Date: Sun, 2 Jun 2002 15:15:54 +0300

> I feel really silly to ask this, but what book is this chapter a part of?

Oops. MC++D == "Modern C++ Design" by Andrei Alexandrescu.

---

From: Oleg Goldshmidt <[email-masked]>
Date: 02 Jun 2002 20:52:20 +0300

> Isn't it possible to write APIs that would abstract some of that

What has it got to do with API? I was referring to the underlying
algorithms.

> computing power than we have? Examples I can think of at present:

To add to your list: finance, hydrodynamics (you mentioned some
problems involving that, but there are many more), cosmology,
climate models, (thermo)nuclear bombs (now that many countries -
albeit not all - signed the Comprehensive Test Ban Treaty), et
caetera, et caetera...