[Openmcl-devel] Re: Hemlock performance investigation

[Gary Byers]

On Thu, 26 Aug 2004, 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).
>
> 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
>

And there shouldn't be nearly as many entries in the list of cfstring
sections as there are[*], in the typical case, and a linear search would
almost always be faster than anything more clever would be.  The whole
rationale for looking at cfstring sections is to be consistent about
things like:

? #?NSFontAttributeName
#<NS-CF-STRING "NSFont" (#xA2DDC6A8)>


The typical situation in the current implementation finds "too many"
constant data sections, all in the #xa0000000-#xb0000000 address
range.  You might eventually find (if user or 3rd-party libraries that
have interesting data sections get loaded) that some data sections are
loaded outside this range, but I think that you'd get a lot of mileage
out of comparing the pointer to the lowest data section address and
not searching at all if it was below that address.

If you wanted to try speeding up the current code a bit (staying out
of BIGNUM-COMPARE), you could store the data section limits as MACPTRs
and treat the address that way as well.  If there are functions for
comparing MACPTRs' addresses, I've forgotten what they're called, but
the compiler can be persuaded to inline the arithmetic on things that're
known to be 32-bit addresses:

(defun p< (p1 p2)
  (< (the (unsigned-byte 32) (%ptr-to-int p1))
     (the (unsigned-byte 32) (%ptr-to-int p2))))

and likewise for other comparison operators.


[*] I believe that the canonical name of the segment used to store
static/constant NSStrings changed between Jaguar and Panther (or at
least between the gcc/linker versions used to build the standard ObjC
libraries.)  The function FIND-CFSTING-SECTIONS is currently collecting
all sections named "__const" in all data segments in all libraries; I
think that it's likely that many of these libraries contain static/constant
data but less likely that they contain static/constant NSStrings, so
this function could probably be a bit more selective.