Re: Intro to Programming w/ Machine Language

From: Randall Hyde (randyhyde_at_earthlink.net)
Date: 02/27/05


Date: Sun, 27 Feb 2005 07:18:16 GMT


"Randy Howard" <randyhoward@FOOverizonBAR.net> wrote in message
news:MPG.1c8aef4f4ed697ed98a0d3@news.verizon.net...
> In article <KU9Ud.6507$MY6.5143@newsread1.news.pas.earthlink.net>,
> randyhyde@earthlink.net says...
> > O(x) complexity is irrelevant.
>
> Based upon your previous posts, I found this pretty surprising.
>
> > Again, the important issue for our discussion is whether you're
> > wasting your end user's time.
>
> If n is sufficiently large, the O(n) complexity obviously matters.

You missed the whole point.
When people use asymptotic performance predictions as an
excuse to not bother with optimization, the battle is already lost.
The bottom line is that, except for a few well-known algorithms,
it generally isn't *possible* to substitute an algorithm with better
asymptotic complexity for the ones found in typical programs.
For example, where's the O(n) or O( n lgn ) algorithm that's
going to make the browser run so much faster? In most real
world applications, such algorithms don't exist. Therefore, the
constant is all you've got to play with.

>
> > If you are, and a different algorithm (even more complex and
> > slightly less maintainable) make the program *twice* as fast
> > (same big-Oh), it's probably worth it.
>
> That's a pretty nasty constant, but ok.

Around this particular newsgroup, it's pretty easy to find
constants like 5x and 10x. Doesn't happen all the time, mind
you, but it does happen. Coming up with a factor of two isn't
all that difficult to do.

> Anytime you can cut the
> time in half, you're on the right track, provided you don't
> introduce new bugs, or negatively impact portability (provided
> that portability is a product requirement).

Keep in mind, the point isn't to "cut the time in half." Rather,
the point is *not* to write the code in such a manner that it
runs at *half* the speed it ought to. If you're worrying about
speeding up your code to make it run twice as fast, you've
already lost the battle.

>
> Microsoft's memcmp() implementation is so bad on large memory
> blocks that I've been replacing it with one of my own for
> years, and that's usually only good for about 40% best case,
> and that depends greatly upon how often you use it. In data
> integrity stress test software, it gets worked pretty hard.
> In a typical application, nobody ever knows.

You've made one of the classic mistakes of optimization metrics:
measuring a single function's performance. Attempting to improve
the performance of a system by speeding up the individual functions
is rarely successful. Or, at least, you don't get *that* much of a boost.
This is the main reason you hear so many people claiming that their
software just can't be sped up -- they've tried to speed up their
software after the fact and typically got a 10-25% boost, and
automatically assumed that they were writing good code all along
(and optimization just wasn't worth the effort). It's the same argument
people use in the good old "assembly vs. HLL" religous wars.

The problem, however, is that good performance is not achieved
at a microscopic level. It's obtained at the macroscopic level.
You get good performance by writing an entire *system* with
an eye to providing good performance, not by trying to hack in
the performance later on. This is why assembly programmers
tend to produce faster code than HLL compilers -- because they
write the entire app in assembly, thinking in assembly. If you write
the code in a HLL and "hand compile" each HLL function into
assembly after the fact, I'd be surprised to find that your code
ran any faster at all than that produced by the HLL. The trick
to writing fast code is to "grok" the whole project and design it
to be efficient from the very beginning.

>
> > Conversely, if you're not wasting your end-users time at
> > all, changing from O(n^2) to O(n) isn't worth the effort to
> > make the change to your code.
>
> Depends again upon what the upper limit on n can be. Just
> because they aren't hitting it today with their 1MB of
> data doesn't mean that 3 years from now they won't be
> ripping their hair out.

Unless, of course, there is no better algorithm (in an
asymptotic case). People throw this concept around
like you can take out one algorithm and easily replace
it with a faster one when necessary. In practice, most
programs are already operating at O(n) (or even O(1))
and they are still too slow.

>
> BTW, if we really wanted to stop wasting end-users time,
> we'd turn off all the eye candy in the GUI. :-)

And we'd turn off all the virus protection, spam blocking,
and other modern tools that eat so much of the CPU's
resourcs.
Cheers,
Randy Hyde



Relevant Pages

  • Re: Intro to Programming w/ Machine Language
    ... > Based upon your previous posts, I found this pretty surprising. ... > If n is sufficiently large, the Ocomplexity obviously matters. ... where's the Oor Oalgorithm that's ... people use in the good old "assembly vs. HLL" religous wars. ...
    (comp.programming)
  • Re: FUD about CGD and GBDE
    ... >government has approved the use of AES with 256 bit keys for very ... that stress on the algorithm and maintain 256 bits of margin. ... I don't seriously think that either of CGD or GBDE will be broken ... The first reason is that it adds complexity. ...
    (freebsd-hackers)
  • Re: Hooray: the Church of Scotland shows the way
    ... If you are simply pointing out the limitations of algorithmic machines then I agree completely. ... any Turing machine could print out the solution to a non-computable problem if that solution were part of the machine's algorithm. ... Given the complexity of the universe it doesn't seem unlikely that the solutions to all manner of non-computable problems have been physically realised in some form and lie there waiting for us to latch on to them somehow. ... Whilst it's true that fundamental physics are essentially algorithmic in nature, ...
    (uk.religion.christian)
  • Re: ALFREDO RIZZI - 21-st Century Breakthrough - AKS algorithm (primality test) is O log
    ... You have to read the number into memory! ... a paper where a present a new algorithm ... Input time does not matter. ... May I suggest that you read a book on complexity analysis? ...
    (sci.crypt)
  • Re: Predicting the Future and Kolmogorov Complexity
    ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ... cannot be algorithmically random. ...
    (talk.origins)