[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-core-devel
Subject:    Re: khtml performance analisys
From:       Lars Knoll <lars () trolltech ! com>
Date:       2000-08-07 7:38:47
[Download RAW message or body]

On Sun, 06 Aug 2000, Waldo Bastian wrote:
> On Sun, 06 Aug 2000, Dima Rogozin wrote:
> > I also noticed that absolute majority of calls to the method use single
> > character strings. From total 325.427 calls to the method only 18.954
> > calls had s.length() > 1.  Does composing on single character strings
> > still make sense?
> >
> >From what I remember, khtml fills lines character by character. Assuming
> > that
>
> width(string[1..n]) = width(string[1..n-1]) + width(string[n]). This fails
> when you need to compose characters. Which sucks because that kills
> performance, we now do basically:
> for(i=1 to n)
>    width += width(string[i])
>
> which is O(n) and we should actually do
>
> for(i=1 to n)
>    width = width(string[1..i])
>
> which is O(n^2)
>
> At least the code in void RenderText::calcMinMaxWidth() still makes the
> above assumption. Not sure what the actual layout code uses these days.

That's why I would like to store already composed strings in the tree, and do 
the composition in the tokenizer/parser. At least we do it only once then, 
and we can keep the O(n) version of calculating width.

Cheers,
Lars

[prev in list] [next in list] [prev in thread] [next in thread]