[Openmcl-devel] Re: Hemlock performance investigation
hamlink at comcast.net
Fri Aug 27 01:50:25 UTC 2004
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
The linear operations are being dwarfed by the constant time operations
in this case (it appears), because it's a far bigger constant that it
should be and the O(1) function in question is being called hundreds of
thousands of times.
I will see if I can get any traction in the code to optimize things
tonight. The values in question may not have to be bignums if properly
declared and unboxed, but otherwise the type checking, etc. could
easily eat us alive when called hundreds of thousands of times. I don't
think bignum-compare was ever meant to be super-fast. Anyhow we
shouldn't even bother checking in this particular case.
On Aug 26, 2004, at 6:35 PM, Andrew P. Lentvorski, Jr. wrote:
> On Aug 26, 2004, at 2:39 PM, Gary Byers wrote:
>> characterAtIndex: is supposed to be a primitive, relatively low-cost
>> operation. The FFI callback overhead doesn't seem to be significant;
>> the cost of determining that SELF was an ObjC instance does. When I
>> tried metering this with Shark (a step that still requires trying to
>> look up the lisp functions associated with an address range manually),
>> I saw that the busiest function was CCL::BIGNUM-COMPARE. These calls
>> came from code which compared the address of a possible ObjC pointer
>> to the addresses of known ObjC library data segments (that might
>> contain NSStrings); all of these addresses were represented as
>> integers, and all happened to be bignums.
> Just a side question: What's the O() of that lookup? Compare being
> the busiest function almost always indicates a bad algorithm/data
> If that is a linear lookup, simply changing the data structure which
> holds the known ObjC library data segments to a tree or hash would
> be a big win.
> If that's not possible, then caching the results of previous lookups
> and then validating on a hit (or flushing on a miss) should also get
> a significant gain.
More information about the Openmcl-devel