TextMorph>>releaseParagraph is called a lot.<div>Getting that faster would speed up the feel of the GUI<br><div><br></div><div>Karl<br><br><div class="gmail_quote">On Tue, Aug 2, 2011 at 9:22 PM, Nicolas Cellier <span dir="ltr"><<a href="mailto:nicolas.cellier.aka.nice@gmail.com">nicolas.cellier.aka.nice@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Normal text editing (inserting) follows that path and main RunArray<br>
operation is #copyReplaceFrom:to:with:<br>
It seems it could be marginally optimized, but I don't think this<br>
would be noticed at all.<br>
Anyway, the operation never appear on a MessageTally (maybe I should<br>
try again with a huge Text).<br>
<br>
TextMorph handleKeyStroke:<br>
TextMorphForEditView keyStroke:<br>
TextMorph keyStroke:<br>
TextMorphForEditView handleInteraction:fromEvent:<br>
TextMorph handleInteraction:fromEvent:<br>
TextEditor readKeyboard<br>
TextEditor dispatchOnCharacter:with:<br>
TextEditor normalCharacter:<br>
TextEditor zapSelectionWith:<br>
NewParagraph replaceFrom:to:with:<br>
Text replaceFrom:to:with:<br>
RunArray copyReplaceFrom:to:with:<br>
<div class="im"><br>
Nicolas<br>
<br>
2011/8/2 Nicolas Cellier <<a href="mailto:nicolas.cellier.aka.nice@gmail.com">nicolas.cellier.aka.nice@gmail.com</a>>:<br>
</div><div><div></div><div class="h5">> No, I wanted to reuse RunArray for other purposes, that's why the<br>
> methods weren't optimized.<br>
> For Text, the major operation is ... Hmm wait, this is really hard to<br>
> track by just reading code, and debugging it is not that easy !<br>
><br>
> Nicolas<br>
><br>
> 2011/8/2 Bert Freudenberg <<a href="mailto:bert@freudenbergs.de">bert@freudenbergs.de</a>>:<br>
>> On 02.08.2011, at 10:17, Nicolas Cellier wrote:<br>
>><br>
>>> I played a bit with RunArray, and found some un-optimized features.<br>
>>> First, I don't know why RunArray is an ArrayedCollection. It cannot<br>
>>> #add: but it can #addFirst: and #addLast:.<br>
>>> It cannot #add:withOccurrences: but it can #addLast:times:. Why<br>
>>> inventing new selectors for old behaviours ?<br>
>><br>
>> 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.<br>
>><br>
>> - Bert -<br>
>><br>
>>> These operations will cost a realloc it the last value is different,<br>
>>> so the underlying runs/values could better be an OrderedCollection if<br>
>>> these operations are used often.<br>
>>> A RunArray cannot remove at all.<br>
>>> Very weird collection species, I don't like the implementation too much.<br>
>>><br>
>>> Then, #do: loops could be far faster. They rely on ArrayedCollection<br>
>>> which inlines do: loops with #to:do: and #at:<br>
>>> But #at: is not that fast. Scanning the runs and counting elements<br>
>>> would result in a n^2 cost.<br>
>>> Fortunately there is a cache lastIndex,lastRun,lastOffset to keep a cost n.<br>
>>> Nonetheless, all the tests cost, and the loop is suboptimal.<br>
>>> Let use see:<br>
>>><br>
>>> version 1:<br>
>>> RunArray>>fastDo: aBlock<br>
>>> runs with: values do: [:r :v |<br>
>>> r timesRepeat: [aBlock value: v]].<br>
>>><br>
>>> | tmp |<br>
>>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]) as: RunArray.<br>
>>> {<br>
>>> [ tmp do: [:e |]] bench.<br>
>>> [ tmp fastDo: [:e |]] bench.<br>
>>> }<br>
>>> #('3,220 per second.' '6,290 per second.')<br>
>>><br>
>>> But timesRepeat: is slow, it is unoptimized by the compiler and costs<br>
>>> a message send.<br>
>>> I think we should implement BlockClosure>>repeat: and optimize that<br>
>>> call in Compiler.<br>
>>> But let's not do it, and rather inline by ourself:<br>
>>><br>
>>> version 2:<br>
>>> runs with: values do: [:r :v |<br>
>>> 1 to: r do: [:i | aBlock value: v]].<br>
>>><br>
>>> | tmp |<br>
>>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]) as: RunArray.<br>
>>> {<br>
>>> [ tmp do: [:e |]] bench.<br>
>>> [ tmp do2: [:e |]] bench.<br>
>>> }<br>
>>> #('3,070 per second.' '25,500 per second.')<br>
>>><br>
>>> We can even inline the with:do: loop itself:<br>
>>> version 3:<br>
>>> 1 to: runs size do: [:i |<br>
>>> | r v |<br>
>>> v := values at: i.<br>
>>> r := runs at: i.<br>
>>> [( r := r - 1) >= 0]<br>
>>> whileTrue: [aBlock value: v]].<br>
>>><br>
>>> | tmp |<br>
>>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]) as: RunArray.<br>
>>> {<br>
>>> [ tmp do: [:e |]] bench.<br>
>>> [ tmp do2: [:e |]] bench.<br>
>>> }<br>
>>> #('3,370 per second.' '32,200 per second.')<br>
>>><br>
>>> Now the operation I wanted to use was reverseDo: so I implemented:<br>
>>> RunArray>>fastReverseDo: aBlock<br>
>>> | i |<br>
>>> i := runs size.<br>
>>> [i > 0]<br>
>>> whileTrue:<br>
>>> [ | r v |<br>
>>> v := values at: i.<br>
>>> r := runs at: i.<br>
>>> i := i - 1.<br>
>>> [( r := r - 1) >= 0]<br>
>>> whileTrue: [aBlock value: v]].<br>
>>> | tmp |<br>
>>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]) as: RunArray.<br>
>>> {<br>
>>> [ tmp reverseDo: [:e |]] bench.<br>
>>> [ tmp reverseDo2: [:e |]] bench.<br>
>>> }<br>
>>> #('83.9 per second.' '32,600 per second.')<br>
>>><br>
>>> Ouch! The cache is missing a lot of indices, and our loop turns into a n^2 cost.<br>
>>> I know, premature optimization bla bla bla, but a factor x400 is worth<br>
>>> some inlining no?<br>
>>><br>
>>> I guess these features are never used.<br>
>>> By now RunArray is kind of private utility for Text implementation.<br>
>>> But it could / should be generic.<br>
>>><br>
>>> I also have proposals for count: / select: / collect:. etc...<br>
>>> It would be to evaluate the block only once per group of values.<br>
>>> For example<br>
>>> RunArray>>collect: aBlock<br>
>>> "Beware, the block will be evaluated only once per group of values."<br>
>>> ^(self class runs: (runs collect: aBlock) contents values: values<br>
>>> copy) coalesce<br>
>>> But that's controversial, it would make the RunArray behave<br>
>>> differently if the block has side effects...<br>
>>><br>
>>> | i tmp tmp2 tmp3 |<br>
>>> tmp := ((Array new: 1000) collect: [:e | 4 atRandom]).<br>
>>> i := 0.<br>
>>> tmp2 := tmp collect: [:e | i := i + 1].<br>
>>> i := 0.<br>
>>> tmp3 := (tmp as: RunArray) collect: [:e | i := i + 1].<br>
>>> tmp2 = tmp3 asArray<br>
>>> ==> false<br>
>>><br>
>>> Nicolas<br>
>>><br>
>><br>
>><br>
>><br>
>><br>
><br>
<br>
</div></div></blockquote></div><br></div></div>