[Openmcl-devel] Re: Hemlock performance investigation

[Hamilton Link]

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

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.

h

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
> structure.
>
> 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.
>
> -a
>