[Openmcl-devel] Re: Hemlock performance investigation
Andrew P. Lentvorski, Jr.
bsder at mail.allcaps.org
Fri Aug 27 01:46:28 EDT 2004
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
More information about the Openmcl-devel