[Openmcl-devel] Re: Hemlock performance investigation

[Andrew P. Lentvorski, Jr.]

On Aug 26, 2004, at 6:50 PM, Hamilton Link wrote:

> I bet bignum-compare is effectively constant time on the bignums in 
> question (it's presumably linear in the size of the bignums otherwise, 
> in the worst case, as it would probably have to be, but we're talking 
> about addresses).

Whoa.  Back up.

I wasn't impugning the bignum compare.  I was questioning the number of 
times it is called.

Calling *anything* hundreds of thousands of times feels like something 
is very wrong.  Having written a VLSI polygon editor, I can assure you 
that *very* few of my functions get called 100,000+ times.  And that 
program can actually manipulate 100,000+ objects at interactive speed.

At 1 GHz, even executing a primitive assembly language operation 
1,000,000 times will take 1ms.  If there are 100 assembly instructions 
per call (probably a pretty aggressive estimate), that's .1 seconds--a 
noticeable and annoying delay in user interactive terms.  This is a 
rough, back-of-the-envelope engineering estimate, but it does hint that 
attacking constant factors of speedup probably won't solve the problem.

This feels like there is some O(n^2) algorithm where there should only 
be O(log n).  A quick profile of the number of times each function is 
called and from where will probably tell you what the offending 
function is.

-a