[squeak-dev] Optimizing RunArray

karl ramberg karlramberg at gmail.com
Tue Aug 2 19:41:00 UTC 2011


TextMorph>>releaseParagraph is called a lot.
Getting that faster would speed up the feel of the GUI

Karl

On Tue, Aug 2, 2011 at 9:22 PM, Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com> wrote:

> Normal text editing (inserting) follows that path and main RunArray
> operation is #copyReplaceFrom:to:with:
> It seems it could be marginally optimized, but I don't think this
> would be noticed at all.
> Anyway, the operation never appear on a MessageTally (maybe I should
> try again with a huge Text).
>
> TextMorph handleKeyStroke:
>  TextMorphForEditView keyStroke:
>    TextMorph keyStroke:
>      TextMorphForEditView handleInteraction:fromEvent:
>        TextMorph handleInteraction:fromEvent:
>          TextEditor readKeyboard
>            TextEditor dispatchOnCharacter:with:
>              TextEditor normalCharacter:
>            TextEditor zapSelectionWith:
>              NewParagraph replaceFrom:to:with:
>                Text replaceFrom:to:with:
>                  RunArray copyReplaceFrom:to:with:
>
> Nicolas
>
> 2011/8/2 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>:
> > No, I wanted to reuse RunArray for other purposes, that's why the
> > methods weren't optimized.
> > For Text, the major operation is ... Hmm wait, this is really hard to
> > track by just reading code, and debugging it is not that easy !
> >
> > Nicolas
> >
> > 2011/8/2 Bert Freudenberg <bert at freudenbergs.de>:
> >> On 02.08.2011, at 10:17, Nicolas Cellier wrote:
> >>
> >>> I played a bit with RunArray, and found some un-optimized features.
> >>> First, I don't know why RunArray is an ArrayedCollection. It cannot
> >>> #add: but it can #addFirst: and #addLast:.
> >>> It cannot #add:withOccurrences: but it can #addLast:times:. Why
> >>> inventing new selectors for old behaviours ?
> >>
> >> The RunArray selectors may in fact precede the more common ones.
> RunArray's purpose was to make Text operations efficient. I think that's
> still the only actual use of RunArrays. In any case, speeding up Text is a
> good idea, though you might want to check what methods it actually uses.
> >>
> >> - Bert -
> >>
> >>> These operations will cost a realloc it the last value is different,
> >>> so the underlying runs/values could better be an OrderedCollection if
> >>> these operations are used often.
> >>> A RunArray cannot remove at all.
> >>> Very weird collection species, I don't like the implementation too
> much.
> >>>
> >>> Then, #do: loops could be far faster. They rely on ArrayedCollection
> >>> which inlines do: loops with #to:do: and #at:
> >>> But #at: is not that fast. Scanning the runs and counting elements
> >>> would result in a n^2 cost.
> >>> Fortunately there is a cache lastIndex,lastRun,lastOffset to keep a
> cost n.
> >>> Nonetheless, all the tests cost, and the loop is suboptimal.
> >>> Let use see:
> >>>
> >>> version 1:
> >>> RunArray>>fastDo: aBlock
> >>>       runs with: values do: [:r :v |
> >>>               r timesRepeat: [aBlock value: v]].
> >>>
> >>> | tmp |
> >>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]) as: RunArray.
> >>> {
> >>> [ tmp do: [:e |]] bench.
> >>> [ tmp fastDo: [:e |]] bench.
> >>> }
> >>> #('3,220 per second.' '6,290 per second.')
> >>>
> >>> But timesRepeat: is slow, it is unoptimized by the compiler and costs
> >>> a message send.
> >>> I think we should implement BlockClosure>>repeat: and optimize that
> >>> call in Compiler.
> >>> But let's not do it, and rather inline by ourself:
> >>>
> >>> version 2:
> >>>       runs with: values do: [:r :v |
> >>>               1 to: r do: [:i | aBlock value: v]].
> >>>
> >>> | tmp |
> >>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]) as: RunArray.
> >>> {
> >>> [ tmp do: [:e |]] bench.
> >>> [ tmp do2: [:e |]] bench.
> >>> }
> >>> #('3,070 per second.' '25,500 per second.')
> >>>
> >>> We can even inline the with:do: loop itself:
> >>> version 3:
> >>>       1 to: runs size do: [:i |
> >>>               | r v |
> >>>               v := values at: i.
> >>>               r := runs at: i.
> >>>               [( r := r - 1) >= 0]
> >>>                       whileTrue: [aBlock value: v]].
> >>>
> >>> | tmp |
> >>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]) as: RunArray.
> >>> {
> >>> [ tmp do: [:e |]] bench.
> >>> [ tmp do2: [:e |]] bench.
> >>> }
> >>> #('3,370 per second.' '32,200 per second.')
> >>>
> >>> Now the operation I wanted to use was reverseDo: so I implemented:
> >>> RunArray>>fastReverseDo: aBlock
> >>>       | i |
> >>>       i := runs size.
> >>>       [i > 0]
> >>>               whileTrue:
> >>>                       [ | r v |
> >>>                       v := values at: i.
> >>>                       r := runs at: i.
> >>>                       i := i - 1.
> >>>                       [( r := r - 1) >= 0]
> >>>                               whileTrue: [aBlock value: v]].
> >>> | tmp |
> >>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]) as: RunArray.
> >>> {
> >>> [ tmp reverseDo: [:e |]] bench.
> >>> [ tmp reverseDo2: [:e |]] bench.
> >>> }
> >>> #('83.9 per second.' '32,600 per second.')
> >>>
> >>> Ouch! The cache is missing a lot of indices, and our loop turns into a
> n^2 cost.
> >>> I know, premature optimization bla bla bla, but a factor x400 is worth
> >>> some inlining no?
> >>>
> >>> I guess these features are never used.
> >>> By now RunArray is kind of private utility for Text implementation.
> >>> But it could / should be generic.
> >>>
> >>> I also have proposals for count: / select: / collect:. etc...
> >>> It would be to evaluate the block only once per group of values.
> >>> For example
> >>> RunArray>>collect: aBlock
> >>>       "Beware, the block will be evaluated only once per group of
> values."
> >>>       ^(self class runs: (runs collect: aBlock) contents values: values
> >>> copy) coalesce
> >>> But that's controversial, it would make the RunArray behave
> >>> differently if the block has side effects...
> >>>
> >>> | i tmp tmp2 tmp3 |
> >>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]).
> >>> i := 0.
> >>> tmp2 := tmp collect: [:e | i := i + 1].
> >>> i := 0.
> >>> tmp3 := (tmp as: RunArray) collect: [:e | i := i + 1].
> >>> tmp2 = tmp3 asArray
> >>> ==> false
> >>>
> >>> Nicolas
> >>>
> >>
> >>
> >>
> >>
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20110802/641359a3/attachment.htm


More information about the Squeak-dev mailing list