Re: Comparisons and Benchmarking

> [At the level of C and C++, if the various languages don't produce
> programs that are all O(the same) something is seriously peculiar. I
> could imagine, e.g., perl and awk might be different if you use their
> built in hhash tables and your data hashes a lot better in one than in
> the other, but if all your loops and such are explicit, how could the
> performance be different by more than a constant factor? -John]


Some folk take a very liberal view of what "Optimizing" means, and
do things like memoizing the results of functions which can be proven
side-effect free or lifting iterative additions or multiplications
out of a loop and replacing them with partial evaluation forms,
sigma forms, equation products, multiplications or exponentiations.


In cases where memoization cuts duplicated branching recursive
calls, or the last operation gets lifted out of a loop and the
loop itself disappears (both of which can happen to, eg,
naive implementations of exponentiation), this changes not just
the constant factors, but also the order of the computation.


I know of at least a couple of compilers where you can write
programs that look like they ought to take exponential time and
discover that they run in constant time or linear time due to
such tricks.


                                              Bear

Return to the comp.compilers page.
Search the comp.compilers archives again.