[rescue] Mozilla Firefox

[Charles Shannon Hendrix]

Fri, 23 Apr 2004 @ 10:03 -0400, Joshua Boyd said:

> On Thu, Apr 22, 2004 at 05:10:00PM -0400, Charles Shannon Hendrix wrote:
> 
> > Although... some OO techniques are pretty easy in C.  In fact, with just
> > a few changes, C could do about 90% of what is worthwhile in C++.
> 
> Or better yet, probably a higher still percent of what is worthwhile in
> ObjC.  :)
>  
> > Worse, I've seen professors try to alleviate this by putting O(n)
> > notation on top of object code, which is blindly stupid.  O(n) isn't
> > always accurate even at the level of C.  All bets are off on the highly
> > overloaded reality of Java or C++.
> 
> Err, why isn't O notation acurate at the level of C?  I wasn't aware
> that it was ever non-applicable.

First of all, I didn't way it was not accurate.  I said it was not
always accurate.

But onward:

O(n) analysis assumes that the operations you count are relatively
uniform in cost, which is frequently not true.  Most of the time it
still works out, but not always.

It's a rough guide on the syntax and math you see in the program code,
not what it gets translated into.

It also places a heavy emphasis on loops rather than what is in them.
Sometimes that is a very good guide, sometimes it is a terrible guide.

Just because something has fewer loops doesn't mean that it will run
faster.

Modern CPUs are often optimized specifically for the worst case, and
improving the algorithm in some cases, particularly if you are looking a
bit too low level, might actually hurt performance.

What if that inner loop you remove just happened to be keeping the
pipeline from stalling?  Or maybe you are on an older Alpha, and your
improved algorithm, tickles a barrier-trap problem.

There are some CPUs that might run an algorithm faster if it is written
backwards.  

So O(n) is a good thing, as long as you don't trust it more than you do
a stopwatch and a code profiler.


-- 
shannon "AT" widomaker.com -- ["The trade of governing has always been
monopolized by the most ignorant and the most rascally individuals of
mankind.  -- Thomas Paine"]