Re: Thinking assembly?

From: Randall Hyde (randyhyde_at_earthlink.net)
Date: 01/20/04 

Date: Tue, 20 Jan 2004 16:45:30 GMT

"Beth" <BethStone21@hotmail.NOSPICEDHAM.com> wrote in message
news:5G4Pb.25$9b5.0@newsfep3-gui.server.ntli.net...
>
> > Replacing it by an O(n) algorithm in a HLL will give
> > better results than simply reducing the constant factor with
> > assembly.
>
> Without a shadow of a doubt; But, as I mention, replacing it with an
> "O(n)" algorithm in ASM will give even better results again...because
> we can improve _BOTH_ the algorithm _AND_ reduce that constant factor
> as well...

Actually, as someone who actually paid attention in an algorithms
analysis class will tell you (:-)), replacing an O(n**2) algorithm by
an O(n) algorithm may *not* give better results. "n" has to be
sufficiently large and the corresponding constants (hidden by the
Big-Oh notation) need to be reasonable.

One other thing, in Big-Oh notation, any O(n) algorithm is
automatically O(n**2), so when you replace that O(n**2)
algorithm by an O(n) algorithm, it must be the case that the
lower bounds on the original algorithm was really quadratic
in nature (yeah, that's a nit-pick, but as long as we're splitting
hairs here).

The truth is, the "better algorithms prove assembly isn't useful"
argument is almost always a red herring. If someone is capable
of finding that lower-term algorithm in a HLL, they're equally
capable of it in assembly. The truth is, if someone is using a
bad algorithm, then chances are pretty good they're going to
use that same bad algorithm no matter what language they
choose. The argument that "I don't have to even consider
assembly because all I've got to do is find a better algorithm"
evades the fact that there might not *be* a better algorithm
(in the sense that you can reduce the polynomial/whatever
associated with the algorithm).

Another problem with the "Big-Oh proof that assembly
isn't useful" is the fact that Big-Oh notation completely ignores
the constant. I don't know about the rest of the world, but
a 10x performance improvement is pretty significant to me.
This, in fact, often allows the use of a poorer, but easier to
understand and maintain, algorithm rather than a better, but
complex and difficult to maintain algorithm.
Cheers,
Randy Hyde

Relevant Pages

  • Re: stl skipping algorithms
    ... Super Giraffe wrote: ... because another part of my code was improved by replacing an ... element-wise copy with the std::copy algorithm. ... and it could be dangerous sitting under them as they fly ...
    (microsoft.public.vc.stl)
  • Re: How long to trust 3DES
    ... time so we can make a logical business decision about replacing the ... algorithm. ... Any comments or advice would be welcome. ...
    (sci.crypt)
  • Re: about PE-header
    ... That's kind of the definition of a HLL and how they usually work: ... you provide it some "algorithm" by which to do this and it ... _MUST_ be made "safe" for any and all situations that the HLL tools ... And this is, in a sense, _why_ HLL compilers can be beaten by ASM ...
    (comp.lang.asm.x86)
  • Re: about PE-header
    ... That's kind of the definition of a HLL and how they usually work: ... you provide it some "algorithm" by which to do this and it ... _MUST_ be made "safe" for any and all situations that the HLL tools ... And this is, in a sense, _why_ HLL compilers can be beaten by ASM ...
    (alt.lang.asm)
  • 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. ...
    (alt.lang.asm)