[Openmcl-devel] Re: Hemlock performance investigation

[Hamilton Link]

Back-of-the-envelope is fine, but I am profiling and tracking the total 
time spent within various functions and the number of times they're 
called.

character-at-index is being called across the whole file on every 
keystroke. Opening a file, it looks like it's being called about 34 
times per character in the file (which is a little odd), but then it 
settles down to scanning across the entire file once every keystroke. 
At 4.5e-5 s per call, in a 5000-character file, this makes about a .25 
second delay per keystroke and the bulk of the delay per, and adds up 
to tens of seconds in the course of typing a couple of lines, so it's 
where most of the time is going.

Is this wrong? possibly the scope or frequency of repeated scanning (by 
ObjC, not by anyone in lisp -- there are only two callers of this 
function in the lisp side and they don't call it very often) could be 
reduced, for example if we're using begin/end editing messages 
improperly. Everyone is free to look into it.

h

On Aug 26, 2004, at 11:46 PM, Andrew P. Lentvorski, Jr. wrote:

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