The Inbox: Collections-ct.875.mcz

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

The Inbox: Collections-ct.875.mcz

commits-2
A new version of Collections was added to project The Inbox:
http://source.squeak.org/inbox/Collections-ct.875.mcz

==================== Summary ====================

Name: Collections-ct.875
Author: ct
Time: 16 February 2020, 3:32:23.116 pm
UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
Ancestors: Collections-topa.873

Extends and realigns version of #findFirst: and #findLast:.

=============== Diff against Collections-topa.873 ===============

Item was changed:
  ----- Method: SequenceableCollection>>findFirst: (in category 'enumerating') -----
  findFirst: aBlock
- "Return the index of my first element for which aBlock evaluates as true."
 
+ ^ self findFirst: aBlock startingAt: 1!
- | index |
- index := 0.
- [(index := index + 1) <= self size] whileTrue:
- [(aBlock value: (self at: index)) ifTrue: [^index]].
- ^ 0!

Item was added:
+ ----- Method: SequenceableCollection>>findFirst:ifNone: (in category 'enumerating') -----
+ findFirst: aBlock ifNone: anotherBlock
+
+ ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!

Item was added:
+ ----- Method: SequenceableCollection>>findFirst:startingAt: (in category 'enumerating') -----
+ findFirst: aBlock startingAt: minIndex
+
+ ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!

Item was added:
+ ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in category 'enumerating') -----
+ findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
+ "Return the index of my first element with index >= minIndex for which aBlock evaluates as true. If no element is found, return the value of anotherBlock."
+
+ | index |
+ index := minIndex - 1.
+ [(index := index + 1) <= self size] whileTrue:
+ [(aBlock value: (self at: index)) ifTrue: [^index]].
+ ^ anotherBlock value!

Item was changed:
  ----- Method: SequenceableCollection>>findLast: (in category 'enumerating') -----
  findLast: aBlock
- "Return the index of my last element for which aBlock evaluates as true."
 
+ ^ self findLast: aBlock startingAt: 1!
- | index |
- index := self size + 1.
- [(index := index - 1) >= 1] whileTrue:
- [(aBlock value: (self at: index)) ifTrue: [^index]].
- ^ 0!

Item was added:
+ ----- Method: SequenceableCollection>>findLast:ifNone: (in category 'enumerating') -----
+ findLast: aBlock ifNone: anotherBlock
+
+ ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!

Item was changed:
  ----- Method: SequenceableCollection>>findLast:startingAt: (in category 'enumerating') -----
+ findLast: aBlock startingAt: minIndex
- findLast: aBlock startingAt: i
- "Return the index of my last element with index >= i for which aBlock evaluates as true."
 
+ ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
- | index |
- index := self size + 1.
- [(index := index - 1) >= i] whileTrue:
- [(aBlock value: (self at: index)) ifTrue: [^index]].
- ^ 0!

Item was added:
+ ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in category 'enumerating') -----
+ findLast: aBlock startingAt: minIndex ifNone: anotherBlock
+ "Return the index of my last element with index >= minIndex for which aBlock evaluates as true.  If no element is found, return the value of anotherBlock."
+
+ | index |
+ index := self size + 1.
+ [(index := index - 1) >= minIndex] whileTrue:
+ [(aBlock value: (self at: index)) ifTrue: [^index]].
+ ^ anotherBlock value!


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Levente Uzonyi
Hi Christoph,

I suggest keeping the all method comments, and measuring the performance
impact of the rewrite.

Levente

On Sun, 16 Feb 2020, [hidden email] wrote:

> A new version of Collections was added to project The Inbox:
> http://source.squeak.org/inbox/Collections-ct.875.mcz
>
> ==================== Summary ====================
>
> Name: Collections-ct.875
> Author: ct
> Time: 16 February 2020, 3:32:23.116 pm
> UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
> Ancestors: Collections-topa.873
>
> Extends and realigns version of #findFirst: and #findLast:.
>
> =============== Diff against Collections-topa.873 ===============
>
> Item was changed:
>  ----- Method: SequenceableCollection>>findFirst: (in category 'enumerating') -----
>  findFirst: aBlock
> - "Return the index of my first element for which aBlock evaluates as true."
>
> + ^ self findFirst: aBlock startingAt: 1!
> - | index |
> - index := 0.
> - [(index := index + 1) <= self size] whileTrue:
> - [(aBlock value: (self at: index)) ifTrue: [^index]].
> - ^ 0!
>
> Item was added:
> + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category 'enumerating') -----
> + findFirst: aBlock ifNone: anotherBlock
> +
> + ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!
>
> Item was added:
> + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category 'enumerating') -----
> + findFirst: aBlock startingAt: minIndex
> +
> + ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!
>
> Item was added:
> + ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in category 'enumerating') -----
> + findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
> + "Return the index of my first element with index >= minIndex for which aBlock evaluates as true. If no element is found, return the value of anotherBlock."
> +
> + | index |
> + index := minIndex - 1.
> + [(index := index + 1) <= self size] whileTrue:
> + [(aBlock value: (self at: index)) ifTrue: [^index]].
> + ^ anotherBlock value!
>
> Item was changed:
>  ----- Method: SequenceableCollection>>findLast: (in category 'enumerating') -----
>  findLast: aBlock
> - "Return the index of my last element for which aBlock evaluates as true."
>
> + ^ self findLast: aBlock startingAt: 1!
> - | index |
> - index := self size + 1.
> - [(index := index - 1) >= 1] whileTrue:
> - [(aBlock value: (self at: index)) ifTrue: [^index]].
> - ^ 0!
>
> Item was added:
> + ----- Method: SequenceableCollection>>findLast:ifNone: (in category 'enumerating') -----
> + findLast: aBlock ifNone: anotherBlock
> +
> + ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!
>
> Item was changed:
>  ----- Method: SequenceableCollection>>findLast:startingAt: (in category 'enumerating') -----
> + findLast: aBlock startingAt: minIndex
> - findLast: aBlock startingAt: i
> - "Return the index of my last element with index >= i for which aBlock evaluates as true."
>
> + ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
> - | index |
> - index := self size + 1.
> - [(index := index - 1) >= i] whileTrue:
> - [(aBlock value: (self at: index)) ifTrue: [^index]].
> - ^ 0!
>
> Item was added:
> + ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in category 'enumerating') -----
> + findLast: aBlock startingAt: minIndex ifNone: anotherBlock
> + "Return the index of my last element with index >= minIndex for which aBlock evaluates as true.  If no element is found, return the value of anotherBlock."
> +
> + | index |
> + index := self size + 1.
> + [(index := index - 1) >= minIndex] whileTrue:
> + [(aBlock value: (self at: index)) ifTrue: [^index]].
> + ^ anotherBlock value!

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Levente Uzonyi
And one more thing: These method resemble #indexOf:* methods, so I think
#ifAbsent: is a better choice than #ifNone:.

Levente

On Sun, 16 Feb 2020, Levente Uzonyi wrote:

> Hi Christoph,
>
> I suggest keeping the all method comments, and measuring the performance
> impact of the rewrite.
>
> Levente
>
> On Sun, 16 Feb 2020, [hidden email] wrote:
>
>> A new version of Collections was added to project The Inbox:
>> http://source.squeak.org/inbox/Collections-ct.875.mcz
>>
>> ==================== Summary ====================
>>
>> Name: Collections-ct.875
>> Author: ct
>> Time: 16 February 2020, 3:32:23.116 pm
>> UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
>> Ancestors: Collections-topa.873
>>
>> Extends and realigns version of #findFirst: and #findLast:.
>>
>> =============== Diff against Collections-topa.873 ===============
>>
>> Item was changed:
>>  ----- Method: SequenceableCollection>>findFirst: (in category
> 'enumerating') -----
>>  findFirst: aBlock
>> - "Return the index of my first element for which aBlock evaluates as
> true."
>>
>> + ^ self findFirst: aBlock startingAt: 1!
>> - | index |
>> - index := 0.
>> - [(index := index + 1) <= self size] whileTrue:
>> - [(aBlock value: (self at: index)) ifTrue: [^index]].
>> - ^ 0!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category
> 'enumerating') -----
>> + findFirst: aBlock ifNone: anotherBlock
>> +
>> + ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category
> 'enumerating') -----
>> + findFirst: aBlock startingAt: minIndex
>> +
>> + ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in
> category 'enumerating') -----
>> + findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
>> + "Return the index of my first element with index >= minIndex for
> which aBlock evaluates as true. If no element is found, return the value of
> anotherBlock."
>> +
>> + | index |
>> + index := minIndex - 1.
>> + [(index := index + 1) <= self size] whileTrue:
>> + [(aBlock value: (self at: index)) ifTrue: [^index]].
>> + ^ anotherBlock value!
>>
>> Item was changed:
>>  ----- Method: SequenceableCollection>>findLast: (in category
> 'enumerating') -----
>>  findLast: aBlock
>> - "Return the index of my last element for which aBlock evaluates as
> true."
>>
>> + ^ self findLast: aBlock startingAt: 1!
>> - | index |
>> - index := self size + 1.
>> - [(index := index - 1) >= 1] whileTrue:
>> - [(aBlock value: (self at: index)) ifTrue: [^index]].
>> - ^ 0!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findLast:ifNone: (in category
> 'enumerating') -----
>> + findLast: aBlock ifNone: anotherBlock
>> +
>> + ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!
>>
>> Item was changed:
>>  ----- Method: SequenceableCollection>>findLast:startingAt: (in category
> 'enumerating') -----
>> + findLast: aBlock startingAt: minIndex
>> - findLast: aBlock startingAt: i
>> - "Return the index of my last element with index >= i for which aBlock
> evaluates as true."
>>
>> + ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
>> - | index |
>> - index := self size + 1.
>> - [(index := index - 1) >= i] whileTrue:
>> - [(aBlock value: (self at: index)) ifTrue: [^index]].
>> - ^ 0!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in
> category 'enumerating') -----
>> + findLast: aBlock startingAt: minIndex ifNone: anotherBlock
>> + "Return the index of my last element with index >= minIndex for which
> aBlock evaluates as true.  If no element is found, return the value of
> anotherBlock."
>> +
>> + | index |
>> + index := self size + 1.
>> + [(index := index - 1) >= minIndex] whileTrue:
>> + [(aBlock value: (self at: index)) ifTrue: [^index]].
>> + ^ anotherBlock value!
>
>

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Christoph Thiede

Hi Levente,


thanks for the suggestions.


And one more thing: These method resemble #indexOf:* methods, so I think #ifAbsent: is a better choice than #ifNone:.


Agreed :-)

I suggest keeping the all method comments

Personally, I see little value in documenting a one-liner. Documentation is useful for explaining and optimized method that does not provide the typical Smalltalk readability. Plus, they all need to be maintained ...

measuring the performance impact of the rewrite.

What is the critical point here?
Of course, the stack will be a little higher, but the asymptotic cost does not change. We only evaluate anotherBlock at the end instead of returning 0.

Please do not misunderstand me: I honor optimizing critical Smalltalk methods, but I always strive to avoid premature optimization.
Should we maybe establish to practice to store such benchmarks somewhere in the trunk so that not every willing contributor needs to write them again?

Best,
Christoph


Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
Gesendet: Sonntag, 16. Februar 2020 22:47:10
An: The general-purpose Squeak developers list
Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz
 
And one more thing: These method resemble #indexOf:* methods, so I think
#ifAbsent: is a better choice than #ifNone:.

Levente

On Sun, 16 Feb 2020, Levente Uzonyi wrote:

> Hi Christoph,
>
> I suggest keeping the all method comments, and measuring the performance
> impact of the rewrite.
>
> Levente
>
> On Sun, 16 Feb 2020, [hidden email] wrote:
>
>> A new version of Collections was added to project The Inbox:
>> http://source.squeak.org/inbox/Collections-ct.875.mcz
>>
>> ==================== Summary ====================
>>
>> Name: Collections-ct.875
>> Author: ct
>> Time: 16 February 2020, 3:32:23.116 pm
>> UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
>> Ancestors: Collections-topa.873
>>
>> Extends and realigns version of #findFirst: and #findLast:.
>>
>> =============== Diff against Collections-topa.873 ===============
>>
>> Item was changed:
>>  ----- Method: SequenceableCollection>>findFirst: (in category
> 'enumerating') -----
>>  findFirst: aBlock
>> -     "Return the index of my first element for which aBlock evaluates as
> true."
>>
>> +     ^ self findFirst: aBlock startingAt: 1!
>> -     | index |
>> -     index := 0.
>> -     [(index := index + 1) <= self size] whileTrue:
>> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
>> -     ^ 0!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category
> 'enumerating') -----
>> + findFirst: aBlock ifNone: anotherBlock
>> +
>> +     ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category
> 'enumerating') -----
>> + findFirst: aBlock startingAt: minIndex
>> +
>> +     ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in
> category 'enumerating') -----
>> + findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
>> +     "Return the index of my first element with index >= minIndex for
> which aBlock evaluates as true. If no element is found, return the value of
> anotherBlock."
>> +
>> +     | index |
>> +     index := minIndex - 1.
>> +     [(index := index + 1) <= self size] whileTrue:
>> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
>> +     ^ anotherBlock value!
>>
>> Item was changed:
>>  ----- Method: SequenceableCollection>>findLast: (in category
> 'enumerating') -----
>>  findLast: aBlock
>> -     "Return the index of my last element for which aBlock evaluates as
> true."
>>
>> +     ^ self findLast: aBlock startingAt: 1!
>> -     | index |
>> -     index := self size + 1.
>> -     [(index := index - 1) >= 1] whileTrue:
>> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
>> -     ^ 0!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findLast:ifNone: (in category
> 'enumerating') -----
>> + findLast: aBlock ifNone: anotherBlock
>> +
>> +     ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!
>>
>> Item was changed:
>>  ----- Method: SequenceableCollection>>findLast:startingAt: (in category
> 'enumerating') -----
>> + findLast: aBlock startingAt: minIndex
>> - findLast: aBlock startingAt: i
>> -     "Return the index of my last element with index >= i for which aBlock
> evaluates as true."
>>
>> +     ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
>> -     | index |
>> -     index := self size + 1.
>> -     [(index := index - 1) >= i] whileTrue:
>> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
>> -     ^ 0!
>>
>> Item was added:
>> + ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in
> category 'enumerating') -----
>> + findLast: aBlock startingAt: minIndex ifNone: anotherBlock
>> +     "Return the index of my last element with index >= minIndex for which
> aBlock evaluates as true.  If no element is found, return the value of
> anotherBlock."
>> +
>> +     | index |
>> +     index := self size + 1.
>> +     [(index := index - 1) >= minIndex] whileTrue:
>> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
>> +     ^ anotherBlock value!
>
>



Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Levente Uzonyi
Hi Christoph,

On Sun, 16 Feb 2020, Thiede, Christoph wrote:

>
> Hi Levente,
>
>
> thanks for the suggestions.
>
>
> > And one more thing: These method resemble #indexOf:* methods, so I think #ifAbsent: is a better choice than #ifNone:.
>
>
> Agreed :-)
>
> > I suggest keeping the all method comments
>
> Personally, I see little value in documenting a one-liner. Documentation is useful for explaining and optimized method that does not provide the typical Smalltalk readability. Plus, they all need to be maintained ...
If one sees #findLast: being sent somewhere, and one doesn't know what it
does, with your changes, it means looking up the implementors three times
to get to the actual implementation and comment.

>
> > measuring the performance impact of the rewrite.
>
> What is the critical point here?
> Of course, the stack will be a little higher, but the asymptotic cost does not change. We only evaluate anotherBlock at the end instead of returning 0.

Two things I saw and you didn't mention are block creation and
introduction of non-jittable comparison.

>
> Please do not misunderstand me: I honor optimizing critical Smalltalk methods, but I always strive to avoid premature optimization.

In my opinion, generic library methods like these should be optimized by
definition.

Calling premature optimization means that you assume that if these methods
were written in a more optimal way, then their complexity and/or
legibility would be worse.
Have a look at #indexOf:*, and you'll see that's not the case.

> Should we maybe establish to practice to store such benchmarks somewhere in the trunk so that not every willing contributor needs to write them again?

I think methods like these don't change often enough (presumably they
never change) to justify storing benchmarks for them.


Levente

>
> Best,
> Christoph
>
> _________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> Gesendet: Sonntag, 16. Februar 2020 22:47:10
> An: The general-purpose Squeak developers list
> Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> And one more thing: These method resemble #indexOf:* methods, so I think
> #ifAbsent: is a better choice than #ifNone:.
>
> Levente
>
> On Sun, 16 Feb 2020, Levente Uzonyi wrote:
>
> > Hi Christoph,
> >
> > I suggest keeping the all method comments, and measuring the performance
> > impact of the rewrite.
> >
> > Levente
> >
> > On Sun, 16 Feb 2020, [hidden email] wrote:
> >
> >> A new version of Collections was added to project The Inbox:
> >> http://source.squeak.org/inbox/Collections-ct.875.mcz
> >>
> >> ==================== Summary ====================
> >>
> >> Name: Collections-ct.875
> >> Author: ct
> >> Time: 16 February 2020, 3:32:23.116 pm
> >> UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
> >> Ancestors: Collections-topa.873
> >>
> >> Extends and realigns version of #findFirst: and #findLast:.
> >>
> >> =============== Diff against Collections-topa.873 ===============
> >>
> >> Item was changed:
> >>  ----- Method: SequenceableCollection>>findFirst: (in category
> > 'enumerating') -----
> >>  findFirst: aBlock
> >> -     "Return the index of my first element for which aBlock evaluates as
> > true."
> >>
> >> +     ^ self findFirst: aBlock startingAt: 1!
> >> -     | index |
> >> -     index := 0.
> >> -     [(index := index + 1) <= self size] whileTrue:
> >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> -     ^ 0!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category
> > 'enumerating') -----
> >> + findFirst: aBlock ifNone: anotherBlock
> >> +
> >> +     ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category
> > 'enumerating') -----
> >> + findFirst: aBlock startingAt: minIndex
> >> +
> >> +     ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in
> > category 'enumerating') -----
> >> + findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
> >> +     "Return the index of my first element with index >= minIndex for
> > which aBlock evaluates as true. If no element is found, return the value of
> > anotherBlock."
> >> +
> >> +     | index |
> >> +     index := minIndex - 1.
> >> +     [(index := index + 1) <= self size] whileTrue:
> >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> +     ^ anotherBlock value!
> >>
> >> Item was changed:
> >>  ----- Method: SequenceableCollection>>findLast: (in category
> > 'enumerating') -----
> >>  findLast: aBlock
> >> -     "Return the index of my last element for which aBlock evaluates as
> > true."
> >>
> >> +     ^ self findLast: aBlock startingAt: 1!
> >> -     | index |
> >> -     index := self size + 1.
> >> -     [(index := index - 1) >= 1] whileTrue:
> >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> -     ^ 0!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findLast:ifNone: (in category
> > 'enumerating') -----
> >> + findLast: aBlock ifNone: anotherBlock
> >> +
> >> +     ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!
> >>
> >> Item was changed:
> >>  ----- Method: SequenceableCollection>>findLast:startingAt: (in category
> > 'enumerating') -----
> >> + findLast: aBlock startingAt: minIndex
> >> - findLast: aBlock startingAt: i
> >> -     "Return the index of my last element with index >= i for which aBlock
> > evaluates as true."
> >>
> >> +     ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
> >> -     | index |
> >> -     index := self size + 1.
> >> -     [(index := index - 1) >= i] whileTrue:
> >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> -     ^ 0!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in
> > category 'enumerating') -----
> >> + findLast: aBlock startingAt: minIndex ifNone: anotherBlock
> >> +     "Return the index of my last element with index >= minIndex for which
> > aBlock evaluates as true.  If no element is found, return the value of
> > anotherBlock."
> >> +
> >> +     | index |
> >> +     index := self size + 1.
> >> +     [(index := index - 1) >= minIndex] whileTrue:
> >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> +     ^ anotherBlock value!
> >
> >
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Christoph Thiede

Hi Levente,


alright, I'll try to measure and optimize them again.


Two things I saw and you didn't mention are block creation


You mean that "ifNone: [0]"? One could replace it with "ifNone: 0" to avoid duplication.

and introduction of non-jittable comparison.

What are you referring to?

Best,
Christoph


Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
Gesendet: Montag, 17. Februar 2020 01:00:11
An: The general-purpose Squeak developers list
Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz
 
Hi Christoph,

On Sun, 16 Feb 2020, Thiede, Christoph wrote:

>
> Hi Levente,
>
>
> thanks for the suggestions.
>
>
> > And one more thing: These method resemble #indexOf:* methods, so I think #ifAbsent: is a better choice than #ifNone:.
>
>
> Agreed :-)
>
> > I suggest keeping the all method comments
>
> Personally, I see little value in documenting a one-liner. Documentation is useful for explaining and optimized method that does not provide the typical Smalltalk readability. Plus, they all need to be maintained ...

If one sees #findLast: being sent somewhere, and one doesn't know what it
does, with your changes, it means looking up the implementors three times
to get to the actual implementation and comment.

>
> > measuring the performance impact of the rewrite.
>
> What is the critical point here?
> Of course, the stack will be a little higher, but the asymptotic cost does not change. We only evaluate anotherBlock at the end instead of returning 0.

Two things I saw and you didn't mention are block creation and
introduction of non-jittable comparison.

>
> Please do not misunderstand me: I honor optimizing critical Smalltalk methods, but I always strive to avoid premature optimization.

In my opinion, generic library methods like these should be optimized by
definition.

Calling premature optimization means that you assume that if these methods
were written in a more optimal way, then their complexity and/or
legibility would be worse.
Have a look at #indexOf:*, and you'll see that's not the case.

> Should we maybe establish to practice to store such benchmarks somewhere in the trunk so that not every willing contributor needs to write them again?

I think methods like these don't change often enough (presumably they
never change) to justify storing benchmarks for them.


Levente

>
> Best,
> Christoph
>
> _________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> Gesendet: Sonntag, 16. Februar 2020 22:47:10
> An: The general-purpose Squeak developers list
> Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> And one more thing: These method resemble #indexOf:* methods, so I think
> #ifAbsent: is a better choice than #ifNone:.
>
> Levente
>
> On Sun, 16 Feb 2020, Levente Uzonyi wrote:
>
> > Hi Christoph,
> >
> > I suggest keeping the all method comments, and measuring the performance
> > impact of the rewrite.
> >
> > Levente
> >
> > On Sun, 16 Feb 2020, [hidden email] wrote:
> >
> >> A new version of Collections was added to project The Inbox:
> >> http://source.squeak.org/inbox/Collections-ct.875.mcz
> >>
> >> ==================== Summary ====================
> >>
> >> Name: Collections-ct.875
> >> Author: ct
> >> Time: 16 February 2020, 3:32:23.116 pm
> >> UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
> >> Ancestors: Collections-topa.873
> >>
> >> Extends and realigns version of #findFirst: and #findLast:.
> >>
> >> =============== Diff against Collections-topa.873 ===============
> >>
> >> Item was changed:
> >>  ----- Method: SequenceableCollection>>findFirst: (in category
> > 'enumerating') -----
> >>  findFirst: aBlock
> >> -     "Return the index of my first element for which aBlock evaluates as
> > true."
> >>
> >> +     ^ self findFirst: aBlock startingAt: 1!
> >> -     | index |
> >> -     index := 0.
> >> -     [(index := index + 1) <= self size] whileTrue:
> >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> -     ^ 0!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category
> > 'enumerating') -----
> >> + findFirst: aBlock ifNone: anotherBlock
> >> +
> >> +     ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category
> > 'enumerating') -----
> >> + findFirst: aBlock startingAt: minIndex
> >> +
> >> +     ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in
> > category 'enumerating') -----
> >> + findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
> >> +     "Return the index of my first element with index >= minIndex for
> > which aBlock evaluates as true. If no element is found, return the value of
> > anotherBlock."
> >> +
> >> +     | index |
> >> +     index := minIndex - 1.
> >> +     [(index := index + 1) <= self size] whileTrue:
> >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> +     ^ anotherBlock value!
> >>
> >> Item was changed:
> >>  ----- Method: SequenceableCollection>>findLast: (in category
> > 'enumerating') -----
> >>  findLast: aBlock
> >> -     "Return the index of my last element for which aBlock evaluates as
> > true."
> >>
> >> +     ^ self findLast: aBlock startingAt: 1!
> >> -     | index |
> >> -     index := self size + 1.
> >> -     [(index := index - 1) >= 1] whileTrue:
> >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> -     ^ 0!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findLast:ifNone: (in category
> > 'enumerating') -----
> >> + findLast: aBlock ifNone: anotherBlock
> >> +
> >> +     ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!
> >>
> >> Item was changed:
> >>  ----- Method: SequenceableCollection>>findLast:startingAt: (in category
> > 'enumerating') -----
> >> + findLast: aBlock startingAt: minIndex
> >> - findLast: aBlock startingAt: i
> >> -     "Return the index of my last element with index >= i for which aBlock
> > evaluates as true."
> >>
> >> +     ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
> >> -     | index |
> >> -     index := self size + 1.
> >> -     [(index := index - 1) >= i] whileTrue:
> >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> -     ^ 0!
> >>
> >> Item was added:
> >> + ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in
> > category 'enumerating') -----
> >> + findLast: aBlock startingAt: minIndex ifNone: anotherBlock
> >> +     "Return the index of my last element with index >= minIndex for which
> > aBlock evaluates as true.  If no element is found, return the value of
> > anotherBlock."
> >> +
> >> +     | index |
> >> +     index := self size + 1.
> >> +     [(index := index - 1) >= minIndex] whileTrue:
> >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> >> +     ^ anotherBlock value!
> >
> >
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Levente Uzonyi
Hi Christoph,

On Mon, 17 Feb 2020, Thiede, Christoph wrote:

>
> Hi Levente,
>
>
> alright, I'll try to measure and optimize them again.
>
>
> > Two things I saw and you didn't mention are block creation
>
>
> You mean that "ifNone: [0]"? One could replace it with "ifNone: 0" to avoid duplication.
That's a possible way, but there's an even better one: put the actual
implementation into #findFirst:startingAt:, and let
#findFirst:startingAt:ifAbsent: use it. Just like how it's done in the
#indexOf:* methods.

>
> > and introduction of non-jittable comparison.
>
> What are you referring to?

The current Spur VM makes x >= 1 about 1.5x faster than x >= y, because it
has more type information available.

Another possible optimization in #findFirst: is to store #size in a
temporary instead of accessing it in each iteration.

Levente

>
> Best,
> Christoph
>
> _________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> Gesendet: Montag, 17. Februar 2020 01:00:11
> An: The general-purpose Squeak developers list
> Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> Hi Christoph,
>
> On Sun, 16 Feb 2020, Thiede, Christoph wrote:
>
> >
> > Hi Levente,
> >
> >
> > thanks for the suggestions.
> >
> >
> > > And one more thing: These method resemble #indexOf:* methods, so I think #ifAbsent: is a better choice than #ifNone:.
> >
> >
> > Agreed :-)
> >
> > > I suggest keeping the all method comments
> >
> > Personally, I see little value in documenting a one-liner. Documentation is useful for explaining and optimized method that does not provide the typical Smalltalk readability. Plus, they all need to be maintained ...
>
> If one sees #findLast: being sent somewhere, and one doesn't know what it
> does, with your changes, it means looking up the implementors three times
> to get to the actual implementation and comment.
>
> >
> > > measuring the performance impact of the rewrite.
> >
> > What is the critical point here?
> > Of course, the stack will be a little higher, but the asymptotic cost does not change. We only evaluate anotherBlock at the end instead of returning 0.
>
> Two things I saw and you didn't mention are block creation and
> introduction of non-jittable comparison.
>
> >
> > Please do not misunderstand me: I honor optimizing critical Smalltalk methods, but I always strive to avoid premature optimization.
>
> In my opinion, generic library methods like these should be optimized by
> definition.
>
> Calling premature optimization means that you assume that if these methods
> were written in a more optimal way, then their complexity and/or
> legibility would be worse.
> Have a look at #indexOf:*, and you'll see that's not the case.
>
> > Should we maybe establish to practice to store such benchmarks somewhere in the trunk so that not every willing contributor needs to write them again?
>
> I think methods like these don't change often enough (presumably they
> never change) to justify storing benchmarks for them.
>
>
> Levente
>
> >
> > Best,
> > Christoph
> >
> >________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> _
> > Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> > Gesendet: Sonntag, 16. Februar 2020 22:47:10
> > An: The general-purpose Squeak developers list
> > Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> > And one more thing: These method resemble #indexOf:* methods, so I think
> > #ifAbsent: is a better choice than #ifNone:.
> >
> > Levente
> >
> > On Sun, 16 Feb 2020, Levente Uzonyi wrote:
> >
> > > Hi Christoph,
> > >
> > > I suggest keeping the all method comments, and measuring the performance
> > > impact of the rewrite.
> > >
> > > Levente
> > >
> > > On Sun, 16 Feb 2020, [hidden email] wrote:
> > >
> > >> A new version of Collections was added to project The Inbox:
> > >> http://source.squeak.org/inbox/Collections-ct.875.mcz
> > >>
> > >> ==================== Summary ====================
> > >>
> > >> Name: Collections-ct.875
> > >> Author: ct
> > >> Time: 16 February 2020, 3:32:23.116 pm
> > >> UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
> > >> Ancestors: Collections-topa.873
> > >>
> > >> Extends and realigns version of #findFirst: and #findLast:.
> > >>
> > >> =============== Diff against Collections-topa.873 ===============
> > >>
> > >> Item was changed:
> > >>  ----- Method: SequenceableCollection>>findFirst: (in category
> > > 'enumerating') -----
> > >>  findFirst: aBlock
> > >> -     "Return the index of my first element for which aBlock evaluates as
> > > true."
> > >>
> > >> +     ^ self findFirst: aBlock startingAt: 1!
> > >> -     | index |
> > >> -     index := 0.
> > >> -     [(index := index + 1) <= self size] whileTrue:
> > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> -     ^ 0!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category
> > > 'enumerating') -----
> > >> + findFirst: aBlock ifNone: anotherBlock
> > >> +
> > >> +     ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category
> > > 'enumerating') -----
> > >> + findFirst: aBlock startingAt: minIndex
> > >> +
> > >> +     ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in
> > > category 'enumerating') -----
> > >> + findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
> > >> +     "Return the index of my first element with index >= minIndex for
> > > which aBlock evaluates as true. If no element is found, return the value of
> > > anotherBlock."
> > >> +
> > >> +     | index |
> > >> +     index := minIndex - 1.
> > >> +     [(index := index + 1) <= self size] whileTrue:
> > >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> +     ^ anotherBlock value!
> > >>
> > >> Item was changed:
> > >>  ----- Method: SequenceableCollection>>findLast: (in category
> > > 'enumerating') -----
> > >>  findLast: aBlock
> > >> -     "Return the index of my last element for which aBlock evaluates as
> > > true."
> > >>
> > >> +     ^ self findLast: aBlock startingAt: 1!
> > >> -     | index |
> > >> -     index := self size + 1.
> > >> -     [(index := index - 1) >= 1] whileTrue:
> > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> -     ^ 0!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findLast:ifNone: (in category
> > > 'enumerating') -----
> > >> + findLast: aBlock ifNone: anotherBlock
> > >> +
> > >> +     ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!
> > >>
> > >> Item was changed:
> > >>  ----- Method: SequenceableCollection>>findLast:startingAt: (in category
> > > 'enumerating') -----
> > >> + findLast: aBlock startingAt: minIndex
> > >> - findLast: aBlock startingAt: i
> > >> -     "Return the index of my last element with index >= i for which aBlock
> > > evaluates as true."
> > >>
> > >> +     ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
> > >> -     | index |
> > >> -     index := self size + 1.
> > >> -     [(index := index - 1) >= i] whileTrue:
> > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> -     ^ 0!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in
> > > category 'enumerating') -----
> > >> + findLast: aBlock startingAt: minIndex ifNone: anotherBlock
> > >> +     "Return the index of my last element with index >= minIndex for which
> > > aBlock evaluates as true.  If no element is found, return the value of
> > > anotherBlock."
> > >> +
> > >> +     | index |
> > >> +     index := self size + 1.
> > >> +     [(index := index - 1) >= minIndex] whileTrue:
> > >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> +     ^ anotherBlock value!
> > >
> > >
> >
> >
> >
>
>

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Christoph Thiede

The current Spur VM makes x >= 1 about 1.5x faster than x >= y, because it has more type information available.


Wow, this is interesting.
However, I found out it is even faster to use #to:do: (4.2 ms vs. 5.19 ms). I will send this soon to the inbox.

Just one other question before: I just discovered that we have #detect:ifNone: and also #find:ifNone: and #findBinary:ifNone:. #ifAbsent: rather appears to go with #at:, i. e. lookup operations, whereas #ifNone: goes with search operations. Are you still sure that we shouldn't name the thing #findFirst:ifNone:?

Best,
Christoph


Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
Gesendet: Montag, 17. Februar 2020 15:10:10
An: The general-purpose Squeak developers list
Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz
 
Hi Christoph,

On Mon, 17 Feb 2020, Thiede, Christoph wrote:

>
> Hi Levente,
>
>
> alright, I'll try to measure and optimize them again.
>
>
> > Two things I saw and you didn't mention are block creation
>
>
> You mean that "ifNone: [0]"? One could replace it with "ifNone: 0" to avoid duplication.

That's a possible way, but there's an even better one: put the actual
implementation into #findFirst:startingAt:, and let
#findFirst:startingAt:ifAbsent: use it. Just like how it's done in the
#indexOf:* methods.

>
> > and introduction of non-jittable comparison.
>
> What are you referring to?

The current Spur VM makes x >= 1 about 1.5x faster than x >= y, because it
has more type information available.

Another possible optimization in #findFirst: is to store #size in a
temporary instead of accessing it in each iteration.

Levente

>
> Best,
> Christoph
>
> _________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> Gesendet: Montag, 17. Februar 2020 01:00:11
> An: The general-purpose Squeak developers list
> Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> Hi Christoph,
>
> On Sun, 16 Feb 2020, Thiede, Christoph wrote:
>
> >
> > Hi Levente,
> >
> >
> > thanks for the suggestions.
> >
> >
> > > And one more thing: These method resemble #indexOf:* methods, so I think #ifAbsent: is a better choice than #ifNone:.
> >
> >
> > Agreed :-)
> >
> > > I suggest keeping the all method comments
> >
> > Personally, I see little value in documenting a one-liner. Documentation is useful for explaining and optimized method that does not provide the typical Smalltalk readability. Plus, they all need to be maintained ...
>
> If one sees #findLast: being sent somewhere, and one doesn't know what it
> does, with your changes, it means looking up the implementors three times
> to get to the actual implementation and comment.
>
> >
> > > measuring the performance impact of the rewrite.
> >
> > What is the critical point here?
> > Of course, the stack will be a little higher, but the asymptotic cost does not change. We only evaluate anotherBlock at the end instead of returning 0.
>
> Two things I saw and you didn't mention are block creation and
> introduction of non-jittable comparison.
>
> >
> > Please do not misunderstand me: I honor optimizing critical Smalltalk methods, but I always strive to avoid premature optimization.
>
> In my opinion, generic library methods like these should be optimized by
> definition.
>
> Calling premature optimization means that you assume that if these methods
> were written in a more optimal way, then their complexity and/or
> legibility would be worse.
> Have a look at #indexOf:*, and you'll see that's not the case.
>
> > Should we maybe establish to practice to store such benchmarks somewhere in the trunk so that not every willing contributor needs to write them again?
>
> I think methods like these don't change often enough (presumably they
> never change) to justify storing benchmarks for them.
>
>
> Levente
>
> >
> > Best,
> > Christoph
> >
> >________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> _
> > Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> > Gesendet: Sonntag, 16. Februar 2020 22:47:10
> > An: The general-purpose Squeak developers list
> > Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> > And one more thing: These method resemble #indexOf:* methods, so I think
> > #ifAbsent: is a better choice than #ifNone:.
> >
> > Levente
> >
> > On Sun, 16 Feb 2020, Levente Uzonyi wrote:
> >
> > > Hi Christoph,
> > >
> > > I suggest keeping the all method comments, and measuring the performance
> > > impact of the rewrite.
> > >
> > > Levente
> > >
> > > On Sun, 16 Feb 2020, [hidden email] wrote:
> > >
> > >> A new version of Collections was added to project The Inbox:
> > >> http://source.squeak.org/inbox/Collections-ct.875.mcz
> > >>
> > >> ==================== Summary ====================
> > >>
> > >> Name: Collections-ct.875
> > >> Author: ct
> > >> Time: 16 February 2020, 3:32:23.116 pm
> > >> UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
> > >> Ancestors: Collections-topa.873
> > >>
> > >> Extends and realigns version of #findFirst: and #findLast:.
> > >>
> > >> =============== Diff against Collections-topa.873 ===============
> > >>
> > >> Item was changed:
> > >>  ----- Method: SequenceableCollection>>findFirst: (in category
> > > 'enumerating') -----
> > >>  findFirst: aBlock
> > >> -     "Return the index of my first element for which aBlock evaluates as
> > > true."
> > >>
> > >> +     ^ self findFirst: aBlock startingAt: 1!
> > >> -     | index |
> > >> -     index := 0.
> > >> -     [(index := index + 1) <= self size] whileTrue:
> > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> -     ^ 0!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category
> > > 'enumerating') -----
> > >> + findFirst: aBlock ifNone: anotherBlock
> > >> +
> > >> +     ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category
> > > 'enumerating') -----
> > >> + findFirst: aBlock startingAt: minIndex
> > >> +
> > >> +     ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in
> > > category 'enumerating') -----
> > >> + findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
> > >> +     "Return the index of my first element with index >= minIndex for
> > > which aBlock evaluates as true. If no element is found, return the value of
> > > anotherBlock."
> > >> +
> > >> +     | index |
> > >> +     index := minIndex - 1.
> > >> +     [(index := index + 1) <= self size] whileTrue:
> > >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> +     ^ anotherBlock value!
> > >>
> > >> Item was changed:
> > >>  ----- Method: SequenceableCollection>>findLast: (in category
> > > 'enumerating') -----
> > >>  findLast: aBlock
> > >> -     "Return the index of my last element for which aBlock evaluates as
> > > true."
> > >>
> > >> +     ^ self findLast: aBlock startingAt: 1!
> > >> -     | index |
> > >> -     index := self size + 1.
> > >> -     [(index := index - 1) >= 1] whileTrue:
> > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> -     ^ 0!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findLast:ifNone: (in category
> > > 'enumerating') -----
> > >> + findLast: aBlock ifNone: anotherBlock
> > >> +
> > >> +     ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!
> > >>
> > >> Item was changed:
> > >>  ----- Method: SequenceableCollection>>findLast:startingAt: (in category
> > > 'enumerating') -----
> > >> + findLast: aBlock startingAt: minIndex
> > >> - findLast: aBlock startingAt: i
> > >> -     "Return the index of my last element with index >= i for which aBlock
> > > evaluates as true."
> > >>
> > >> +     ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
> > >> -     | index |
> > >> -     index := self size + 1.
> > >> -     [(index := index - 1) >= i] whileTrue:
> > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> -     ^ 0!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in
> > > category 'enumerating') -----
> > >> + findLast: aBlock startingAt: minIndex ifNone: anotherBlock
> > >> +     "Return the index of my last element with index >= minIndex for which
> > > aBlock evaluates as true.  If no element is found, return the value of
> > > anotherBlock."
> > >> +
> > >> +     | index |
> > >> +     index := self size + 1.
> > >> +     [(index := index - 1) >= minIndex] whileTrue:
> > >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> +     ^ anotherBlock value!
> > >
> > >
> >
> >
> >
>
>


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

timrowledge
In reply to this post by Christoph Thiede


> On 2020-02-17, at 2:36 AM, Thiede, Christoph <[hidden email]> wrote:
>
> You mean that "ifNone: [0]"? One could replace it with "ifNone: 0" to avoid duplication.

Please don't. This is ugly beyond any level of acceptability

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful random insult:- On permanent leave of absence from his senses.



Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Christoph Thiede

Don't worry, I never really liked it myself 😊


Von: Squeak-dev <[hidden email]> im Auftrag von tim Rowledge <[hidden email]>
Gesendet: Montag, 17. Februar 2020 19:32:03
An: The general-purpose Squeak developers list
Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz
 


> On 2020-02-17, at 2:36 AM, Thiede, Christoph <[hidden email]> wrote:
>
> You mean that "ifNone: [0]"? One could replace it with "ifNone: 0" to avoid duplication.

Please don't. This is ugly beyond any level of acceptability

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful random insult:- On permanent leave of absence from his senses.





Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Nicolas Cellier
In reply to this post by Christoph Thiede


Le lun. 17 févr. 2020 à 19:14, Thiede, Christoph <[hidden email]> a écrit :

The current Spur VM makes x >= 1 about 1.5x faster than x >= y, because it has more type information available.


Wow, this is interesting.
However, I found out it is even faster to use #to:do: (4.2 ms vs. 5.19 ms). I will send this soon to the inbox.

Just one other question before: I just discovered that we have #detect:ifNone: and also #find:ifNone: and #findBinary:ifNone:. #ifAbsent: rather appears to go with #at:, i. e. lookup operations, whereas #ifNone: goes with search operations. Are you still sure that we shouldn't name the thing #findFirst:ifNone:?

I think that you are right

indexOf: anElement ifAbsent: ... is like at: aKey ifAbsent: ... (anElement is absent).

But when we provide a predicate, we might prefer ifNone: (none matches the predicate)

Best,
Christoph


Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
Gesendet: Montag, 17. Februar 2020 15:10:10
An: The general-purpose Squeak developers list
Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz
 
Hi Christoph,

On Mon, 17 Feb 2020, Thiede, Christoph wrote:

>
> Hi Levente,
>
>
> alright, I'll try to measure and optimize them again.
>
>
> > Two things I saw and you didn't mention are block creation
>
>
> You mean that "ifNone: [0]"? One could replace it with "ifNone: 0" to avoid duplication.

That's a possible way, but there's an even better one: put the actual
implementation into #findFirst:startingAt:, and let
#findFirst:startingAt:ifAbsent: use it. Just like how it's done in the
#indexOf:* methods.

>
> > and introduction of non-jittable comparison.
>
> What are you referring to?

The current Spur VM makes x >= 1 about 1.5x faster than x >= y, because it
has more type information available.

Another possible optimization in #findFirst: is to store #size in a
temporary instead of accessing it in each iteration.

Levente

>
> Best,
> Christoph
>
> _________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> Gesendet: Montag, 17. Februar 2020 01:00:11
> An: The general-purpose Squeak developers list
> Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> Hi Christoph,
>
> On Sun, 16 Feb 2020, Thiede, Christoph wrote:
>
> >
> > Hi Levente,
> >
> >
> > thanks for the suggestions.
> >
> >
> > > And one more thing: These method resemble #indexOf:* methods, so I think #ifAbsent: is a better choice than #ifNone:.
> >
> >
> > Agreed :-)
> >
> > > I suggest keeping the all method comments
> >
> > Personally, I see little value in documenting a one-liner. Documentation is useful for explaining and optimized method that does not provide the typical Smalltalk readability. Plus, they all need to be maintained ...
>
> If one sees #findLast: being sent somewhere, and one doesn't know what it
> does, with your changes, it means looking up the implementors three times
> to get to the actual implementation and comment.
>
> >
> > > measuring the performance impact of the rewrite.
> >
> > What is the critical point here?
> > Of course, the stack will be a little higher, but the asymptotic cost does not change. We only evaluate anotherBlock at the end instead of returning 0.
>
> Two things I saw and you didn't mention are block creation and
> introduction of non-jittable comparison.
>
> >
> > Please do not misunderstand me: I honor optimizing critical Smalltalk methods, but I always strive to avoid premature optimization.
>
> In my opinion, generic library methods like these should be optimized by
> definition.
>
> Calling premature optimization means that you assume that if these methods
> were written in a more optimal way, then their complexity and/or
> legibility would be worse.
> Have a look at #indexOf:*, and you'll see that's not the case.
>
> > Should we maybe establish to practice to store such benchmarks somewhere in the trunk so that not every willing contributor needs to write them again?
>
> I think methods like these don't change often enough (presumably they
> never change) to justify storing benchmarks for them.
>
>
> Levente
>
> >
> > Best,
> > Christoph
> >
> >________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> _
> > Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> > Gesendet: Sonntag, 16. Februar 2020 22:47:10
> > An: The general-purpose Squeak developers list
> > Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> > And one more thing: These method resemble #indexOf:* methods, so I think
> > #ifAbsent: is a better choice than #ifNone:.
> >
> > Levente
> >
> > On Sun, 16 Feb 2020, Levente Uzonyi wrote:
> >
> > > Hi Christoph,
> > >
> > > I suggest keeping the all method comments, and measuring the performance
> > > impact of the rewrite.
> > >
> > > Levente
> > >
> > > On Sun, 16 Feb 2020, [hidden email] wrote:
> > >
> > >> A new version of Collections was added to project The Inbox:
> > >> http://source.squeak.org/inbox/Collections-ct.875.mcz
> > >>
> > >> ==================== Summary ====================
> > >>
> > >> Name: Collections-ct.875
> > >> Author: ct
> > >> Time: 16 February 2020, 3:32:23.116 pm
> > >> UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
> > >> Ancestors: Collections-topa.873
> > >>
> > >> Extends and realigns version of #findFirst: and #findLast:.
> > >>
> > >> =============== Diff against Collections-topa.873 ===============
> > >>
> > >> Item was changed:
> > >>  ----- Method: SequenceableCollection>>findFirst: (in category
> > > 'enumerating') -----
> > >>  findFirst: aBlock
> > >> -     "Return the index of my first element for which aBlock evaluates as
> > > true."
> > >>
> > >> +     ^ self findFirst: aBlock startingAt: 1!
> > >> -     | index |
> > >> -     index := 0.
> > >> -     [(index := index + 1) <= self size] whileTrue:
> > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> -     ^ 0!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category
> > > 'enumerating') -----
> > >> + findFirst: aBlock ifNone: anotherBlock
> > >> +
> > >> +     ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category
> > > 'enumerating') -----
> > >> + findFirst: aBlock startingAt: minIndex
> > >> +
> > >> +     ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in
> > > category 'enumerating') -----
> > >> + findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
> > >> +     "Return the index of my first element with index >= minIndex for
> > > which aBlock evaluates as true. If no element is found, return the value of
> > > anotherBlock."
> > >> +
> > >> +     | index |
> > >> +     index := minIndex - 1.
> > >> +     [(index := index + 1) <= self size] whileTrue:
> > >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> +     ^ anotherBlock value!
> > >>
> > >> Item was changed:
> > >>  ----- Method: SequenceableCollection>>findLast: (in category
> > > 'enumerating') -----
> > >>  findLast: aBlock
> > >> -     "Return the index of my last element for which aBlock evaluates as
> > > true."
> > >>
> > >> +     ^ self findLast: aBlock startingAt: 1!
> > >> -     | index |
> > >> -     index := self size + 1.
> > >> -     [(index := index - 1) >= 1] whileTrue:
> > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> -     ^ 0!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findLast:ifNone: (in category
> > > 'enumerating') -----
> > >> + findLast: aBlock ifNone: anotherBlock
> > >> +
> > >> +     ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!
> > >>
> > >> Item was changed:
> > >>  ----- Method: SequenceableCollection>>findLast:startingAt: (in category
> > > 'enumerating') -----
> > >> + findLast: aBlock startingAt: minIndex
> > >> - findLast: aBlock startingAt: i
> > >> -     "Return the index of my last element with index >= i for which aBlock
> > > evaluates as true."
> > >>
> > >> +     ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
> > >> -     | index |
> > >> -     index := self size + 1.
> > >> -     [(index := index - 1) >= i] whileTrue:
> > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> -     ^ 0!
> > >>
> > >> Item was added:
> > >> + ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in
> > > category 'enumerating') -----
> > >> + findLast: aBlock startingAt: minIndex ifNone: anotherBlock
> > >> +     "Return the index of my last element with index >= minIndex for which
> > > aBlock evaluates as true.  If no element is found, return the value of
> > > anotherBlock."
> > >> +
> > >> +     | index |
> > >> +     index := self size + 1.
> > >> +     [(index := index - 1) >= minIndex] whileTrue:
> > >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > >> +     ^ anotherBlock value!
> > >
> > >
> >
> >
> >
>
>



Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ct.875.mcz

Levente Uzonyi
In reply to this post by Christoph Thiede
Hi Christoph,

On Mon, 17 Feb 2020, Thiede, Christoph wrote:

>
> > The current Spur VM makes x >= 1 about 1.5x faster than x >= y, because it has more type information available.
>
>
> Wow, this is interesting.
> However, I found out it is even faster to use #to:do: (4.2 ms vs. 5.19 ms). I will send this soon to the inbox.
>
> Just one other question before: I just discovered that we have #detect:ifNone: and also #find:ifNone: and #findBinary:ifNone:. #ifAbsent: rather appears to go with #at:, i. e. lookup operations, whereas #ifNone: goes with
> search operations. Are you still sure that we shouldn't name the thing #findFirst:ifNone:?

I don't have #find:ifNone: in my image. SequenceableCollection
understands #detect:ifNone:, #findBinary:ifNone:, and
#findBinaryIndex:ifNone:.
If you search for *ifNone: and *ifAbsent:, you'll find that the latter is
more common, but seeing the number of implementors of these methods, I
suppose it boils down to personal preference.


Levente

>
> Best,
> Christoph
>
> _________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> Gesendet: Montag, 17. Februar 2020 15:10:10
> An: The general-purpose Squeak developers list
> Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> Hi Christoph,
>
> On Mon, 17 Feb 2020, Thiede, Christoph wrote:
>
> >
> > Hi Levente,
> >
> >
> > alright, I'll try to measure and optimize them again.
> >
> >
> > > Two things I saw and you didn't mention are block creation
> >
> >
> > You mean that "ifNone: [0]"? One could replace it with "ifNone: 0" to avoid duplication.
>
> That's a possible way, but there's an even better one: put the actual
> implementation into #findFirst:startingAt:, and let
> #findFirst:startingAt:ifAbsent: use it. Just like how it's done in the
> #indexOf:* methods.
>
> >
> > > and introduction of non-jittable comparison.
> >
> > What are you referring to?
>
> The current Spur VM makes x >= 1 about 1.5x faster than x >= y, because it
> has more type information available.
>
> Another possible optimization in #findFirst: is to store #size in a
> temporary instead of accessing it in each iteration.
>
> Levente
>
> >
> > Best,
> > Christoph
> >
> >________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> _
> > Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> > Gesendet: Montag, 17. Februar 2020 01:00:11
> > An: The general-purpose Squeak developers list
> > Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> > Hi Christoph,
> >
> > On Sun, 16 Feb 2020, Thiede, Christoph wrote:
> >
> > >
> > > Hi Levente,
> > >
> > >
> > > thanks for the suggestions.
> > >
> > >
> > > > And one more thing: These method resemble #indexOf:* methods, so I think #ifAbsent: is a better choice than #ifNone:.
> > >
> > >
> > > Agreed :-)
> > >
> > > > I suggest keeping the all method comments
> > >
> > > Personally, I see little value in documenting a one-liner. Documentation is useful for explaining and optimized method that does not provide the typical Smalltalk readability. Plus, they all need to be maintained ...
> >
> > If one sees #findLast: being sent somewhere, and one doesn't know what it
> > does, with your changes, it means looking up the implementors three times
> > to get to the actual implementation and comment.
> >
> > >
> > > > measuring the performance impact of the rewrite.
> > >
> > > What is the critical point here?
> > > Of course, the stack will be a little higher, but the asymptotic cost does not change. We only evaluate anotherBlock at the end instead of returning 0.
> >
> > Two things I saw and you didn't mention are block creation and
> > introduction of non-jittable comparison.
> >
> > >
> > > Please do not misunderstand me: I honor optimizing critical Smalltalk methods, but I always strive to avoid premature optimization.
> >
> > In my opinion, generic library methods like these should be optimized by
> > definition.
> >
> > Calling premature optimization means that you assume that if these methods
> > were written in a more optimal way, then their complexity and/or
> > legibility would be worse.
> > Have a look at #indexOf:*, and you'll see that's not the case.
> >
> > > Should we maybe establish to practice to store such benchmarks somewhere in the trunk so that not every willing contributor needs to write them again?
> >
> > I think methods like these don't change often enough (presumably they
> > never change) to justify storing benchmarks for them.
> >
> >
> > Levente
> >
> > >
> > > Best,
> > > Christoph
> > >
> >>_______________________________________________________________________________________________________________________________________________________________________________________________________________________________
> _
> > _
> > > Von: Squeak-dev <[hidden email]> im Auftrag von Levente Uzonyi <[hidden email]>
> > > Gesendet: Sonntag, 16. Februar 2020 22:47:10
> > > An: The general-purpose Squeak developers list
> > > Betreff: Re: [squeak-dev] The Inbox: Collections-ct.875.mcz  
> > > And one more thing: These method resemble #indexOf:* methods, so I think
> > > #ifAbsent: is a better choice than #ifNone:.
> > >
> > > Levente
> > >
> > > On Sun, 16 Feb 2020, Levente Uzonyi wrote:
> > >
> > > > Hi Christoph,
> > > >
> > > > I suggest keeping the all method comments, and measuring the performance
> > > > impact of the rewrite.
> > > >
> > > > Levente
> > > >
> > > > On Sun, 16 Feb 2020, [hidden email] wrote:
> > > >
> > > >> A new version of Collections was added to project The Inbox:
> > > >> http://source.squeak.org/inbox/Collections-ct.875.mcz
> > > >>
> > > >> ==================== Summary ====================
> > > >>
> > > >> Name: Collections-ct.875
> > > >> Author: ct
> > > >> Time: 16 February 2020, 3:32:23.116 pm
> > > >> UUID: 61ea773b-1408-c040-a712-09238ee6fe2f
> > > >> Ancestors: Collections-topa.873
> > > >>
> > > >> Extends and realigns version of #findFirst: and #findLast:.
> > > >>
> > > >> =============== Diff against Collections-topa.873 ===============
> > > >>
> > > >> Item was changed:
> > > >>  ----- Method: SequenceableCollection>>findFirst: (in category
> > > > 'enumerating') -----
> > > >>  findFirst: aBlock
> > > >> -     "Return the index of my first element for which aBlock evaluates as
> > > > true."
> > > >>
> > > >> +     ^ self findFirst: aBlock startingAt: 1!
> > > >> -     | index |
> > > >> -     index := 0.
> > > >> -     [(index := index + 1) <= self size] whileTrue:
> > > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > > >> -     ^ 0!
> > > >>
> > > >> Item was added:
> > > >> + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category
> > > > 'enumerating') -----
> > > >> + findFirst: aBlock ifNone: anotherBlock
> > > >> +
> > > >> +     ^ self findFirst: aBlock startingAt: 1 ifNone: anotherBlock!
> > > >>
> > > >> Item was added:
> > > >> + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category
> > > > 'enumerating') -----
> > > >> + findFirst: aBlock startingAt: minIndex
> > > >> +
> > > >> +     ^ self findFirst: aBlock startingAt: minIndex ifNone: [0]!
> > > >>
> > > >> Item was added:
> > > >> + ----- Method: SequenceableCollection>>findFirst:startingAt:ifNone: (in
> > > > category 'enumerating') -----
> > > >> + findFirst: aBlock startingAt: minIndex ifNone: anotherBlock
> > > >> +     "Return the index of my first element with index >= minIndex for
> > > > which aBlock evaluates as true. If no element is found, return the value of
> > > > anotherBlock."
> > > >> +
> > > >> +     | index |
> > > >> +     index := minIndex - 1.
> > > >> +     [(index := index + 1) <= self size] whileTrue:
> > > >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > > >> +     ^ anotherBlock value!
> > > >>
> > > >> Item was changed:
> > > >>  ----- Method: SequenceableCollection>>findLast: (in category
> > > > 'enumerating') -----
> > > >>  findLast: aBlock
> > > >> -     "Return the index of my last element for which aBlock evaluates as
> > > > true."
> > > >>
> > > >> +     ^ self findLast: aBlock startingAt: 1!
> > > >> -     | index |
> > > >> -     index := self size + 1.
> > > >> -     [(index := index - 1) >= 1] whileTrue:
> > > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > > >> -     ^ 0!
> > > >>
> > > >> Item was added:
> > > >> + ----- Method: SequenceableCollection>>findLast:ifNone: (in category
> > > > 'enumerating') -----
> > > >> + findLast: aBlock ifNone: anotherBlock
> > > >> +
> > > >> +     ^ self findLast: aBlock startingAt: 1 ifNone: anotherBlock!
> > > >>
> > > >> Item was changed:
> > > >>  ----- Method: SequenceableCollection>>findLast:startingAt: (in category
> > > > 'enumerating') -----
> > > >> + findLast: aBlock startingAt: minIndex
> > > >> - findLast: aBlock startingAt: i
> > > >> -     "Return the index of my last element with index >= i for which aBlock
> > > > evaluates as true."
> > > >>
> > > >> +     ^ self findLast: aBlock startingAt: minIndex ifNone: [0]!
> > > >> -     | index |
> > > >> -     index := self size + 1.
> > > >> -     [(index := index - 1) >= i] whileTrue:
> > > >> -             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > > >> -     ^ 0!
> > > >>
> > > >> Item was added:
> > > >> + ----- Method: SequenceableCollection>>findLast:startingAt:ifNone: (in
> > > > category 'enumerating') -----
> > > >> + findLast: aBlock startingAt: minIndex ifNone: anotherBlock
> > > >> +     "Return the index of my last element with index >= minIndex for which
> > > > aBlock evaluates as true.  If no element is found, return the value of
> > > > anotherBlock."
> > > >> +
> > > >> +     | index |
> > > >> +     index := self size + 1.
> > > >> +     [(index := index - 1) >= minIndex] whileTrue:
> > > >> +             [(aBlock value: (self at: index)) ifTrue: [^index]].
> > > >> +     ^ anotherBlock value!
> > > >
> > > >
> > >
> > >
> > >
> >
> >
>
>