Re: Comparisons and Benchmarking

Ray <>
Wed, 04 Nov 2009 10:10:38 -0800

          From comp.compilers

Related articles
[4 earlier articles]
Re: Comparisons and Benchmarking (Paul Biggar) (2009-10-20)
Re: Comparisons and Benchmarking (Isaac Gouy) (2009-10-20)
Re: Comparisons and Benchmarking (Tom Crick) (2009-10-20)
Re: Comparisons and Benchmarking (Philip Herron) (2009-10-21)
Re: Comparisons and Benchmarking (2009-10-21)
Re: Comparisons and Benchmarking (George Neuner) (2009-10-21)
Re: Comparisons and Benchmarking (Ray) (2009-11-04)
Re: Comparisons and Benchmarking (bartc) (2009-11-05)
| List of all articles for this month |

From: Ray <>
Newsgroups: comp.compilers
Date: Wed, 04 Nov 2009 10:10:38 -0800
Organization: Doubtful
References: 09-10-01609-10-021 09-10-026
Keywords: code, benchmarks
Posted-Date: 05 Nov 2009 15:18:08 EST

> [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.


Post a followup to this message

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