Christoph Thiede uploaded a new version of Collections to project The Inbox: http://source.squeak.org/inbox/Collections-ct.877.mcz
==================== Summary ====================
Name: Collections-ct.877 Author: ct Time: 17 February 2020, 8:57:49.278239 pm UUID: bf652ba0-43cc-734d-ac03-7a226cc80463 Ancestors: Collections-ul.875
Extends and realigns version of #findFirst: and #findLast:.
Second, optimized version after many helpful comments by Levente (ul). Thank you! Replaces Collections-ct.875.
---
Performance analysis:
#findFirst: - '238 per second. 4.2 milliseconds per run. 0.73956 % GC time.' #findFirst:startingAt: - '1,510 per second. 660 microseconds per run. 1.56 % GC time.' #findFirst:startingAt:ifNone: - '1,210 per second. 828 microseconds per run. 2.06 % GC time.' #findFirst:ifNone: - '214 per second. 4.68 milliseconds per run. 0.65987 % GC time.' #findLast: - '210 per second. 4.76 milliseconds per run. 0.66 % GC time.' #findLast:startingAt: - '1,380 per second. 724 microseconds per run. 1.72 % GC time.' #findLast:startingAt:ifNone: - '1,130 per second. 887 microseconds per run. 2 % GC time.' #findLast:ifNone: - '206 per second. 4.86 milliseconds per run. 0.81967 % GC time.'
Comparing to previous version:
#findFirst: - '193 per second. 5.19 milliseconds per run. 0.5994 % GC time.' (NOW 23.3% faster) #findLast: - '213 per second. 4.69 milliseconds per run. 0.71986 % GC time.' (NOW 1.4% slower) #findLast:startingAt: - '1,360 per second. 736 microseconds per run. 1.72 % GC time.' (NOW 1.4% faster)
Measurements code:
random := Random new. range := 1 to: 256. array := (1 to: 128) collect: [:i | range atRandom: random]. values := (1 to: 4096) collect: [:i | range atRandom: random]. ({ #findFirst: -> [ values do: [:x | array findFirst: [:y | x = y]]]. #findFirst:startingAt: -> [ values pairsDo: [:x :s | array findFirst: [:y | x = y] startingAt: s]]. #findFirst:ifNone: -> [ values do: [:x | array findFirst: [:y | x = y] ifNone: [123456789 sqrt]]]. #findFirst:startingAt:ifNone: -> [ values pairsDo: [:x :s | array findFirst: [:y | x = y] startingAt: s ifNone: [123456789 sqrt]]]. #findLast: -> [ values do: [:x | array findLast: [:y | x = y]]]. #findLast:startingAt: -> [ values pairsDo: [:x :s | array findLast: [:y | x = y] startingAt: s]]. #findLast:ifNone: -> [ values do: [:x | array findLast: [:y | x = y] ifNone: [123456789 sqrt]]]. #findLast:startingAt:ifNone: -> [ values pairsDo: [:x :s | array findLast: [:y | x = y] startingAt: s ifNone: [123456789 sqrt]]]. } select: [:assoc | array respondsTo: assoc key]) collect: [:assoc | assoc key -> assoc value bench] as: Dictionary
=============== Diff against Collections-ul.875 ===============
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 + "Return the index of my first element for which aBlock evaluates as true. If no element is found, return the value of anotherBlock." + + | index | + (index := self findFirst: aBlock) = 0 + ifTrue: [^ anotherBlock value]. + ^ index!
Item was added: + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category 'enumerating') ----- + findFirst: aBlock startingAt: minIndex + "Return the index of my first element with index >= minIndex for which aBlock evaluates as true." + + minIndex to: self size do: [:index | + (aBlock value: (self at: index)) ifTrue: [^index]]. + ^ 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 := self findFirst: aBlock startingAt: minIndex) = 0 + ifTrue: [^ anotherBlock value]. + ^ index!
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 + "Return the index of my last element for which aBlock evaluates as true. If no element is found, return the value of anotherBlock." + + | index | + (index := self findLast: aBlock) = 0 + ifTrue: [^ anotherBlock value]. + ^ index!
Item was changed: ----- Method: SequenceableCollection>>findLast:startingAt: (in category 'enumerating') ----- + findLast: aBlock startingAt: minIndex + "Return the index of my last element with index >= minIndex for which aBlock evaluates as true." - findLast: aBlock startingAt: i - "Return the index of my last element with index >= i for which aBlock evaluates as true."
+ self size to: minIndex by: -1 do: [:index | + (aBlock value: (self at: index)) ifTrue: [^index]]. - | 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 findLast: aBlock startingAt: minIndex) = 0 + ifTrue: [^ anotherBlock value]. + ^ index!
I moved Collections-ct.875 to treated.
Best, Marcel Am 17.02.2020 20:57:58 schrieb commits@source.squeak.org commits@source.squeak.org: Christoph Thiede uploaded a new version of Collections to project The Inbox: http://source.squeak.org/inbox/Collections-ct.877.mcz
==================== Summary ====================
Name: Collections-ct.877 Author: ct Time: 17 February 2020, 8:57:49.278239 pm UUID: bf652ba0-43cc-734d-ac03-7a226cc80463 Ancestors: Collections-ul.875
Extends and realigns version of #findFirst: and #findLast:.
Second, optimized version after many helpful comments by Levente (ul). Thank you! Replaces Collections-ct.875.
---
Performance analysis:
#findFirst: - '238 per second. 4.2 milliseconds per run. 0.73956 % GC time.' #findFirst:startingAt: - '1,510 per second. 660 microseconds per run. 1.56 % GC time.' #findFirst:startingAt:ifNone: - '1,210 per second. 828 microseconds per run. 2.06 % GC time.' #findFirst:ifNone: - '214 per second. 4.68 milliseconds per run. 0.65987 % GC time.' #findLast: - '210 per second. 4.76 milliseconds per run. 0.66 % GC time.' #findLast:startingAt: - '1,380 per second. 724 microseconds per run. 1.72 % GC time.' #findLast:startingAt:ifNone: - '1,130 per second. 887 microseconds per run. 2 % GC time.' #findLast:ifNone: - '206 per second. 4.86 milliseconds per run. 0.81967 % GC time.'
Comparing to previous version:
#findFirst: - '193 per second. 5.19 milliseconds per run. 0.5994 % GC time.' (NOW 23.3% faster) #findLast: - '213 per second. 4.69 milliseconds per run. 0.71986 % GC time.' (NOW 1.4% slower) #findLast:startingAt: - '1,360 per second. 736 microseconds per run. 1.72 % GC time.' (NOW 1.4% faster)
Measurements code:
random := Random new. range := 1 to: 256. array := (1 to: 128) collect: [:i | range atRandom: random]. values := (1 to: 4096) collect: [:i | range atRandom: random].
({ #findFirst: -> [ values do: [:x | array findFirst: [:y | x = y]]]. #findFirst:startingAt: -> [ values pairsDo: [:x :s | array findFirst: [:y | x = y] startingAt: s]]. #findFirst:ifNone: -> [ values do: [:x | array findFirst: [:y | x = y] ifNone: [123456789 sqrt]]]. #findFirst:startingAt:ifNone: -> [ values pairsDo: [:x :s | array findFirst: [:y | x = y] startingAt: s ifNone: [123456789 sqrt]]]. #findLast: -> [ values do: [:x | array findLast: [:y | x = y]]]. #findLast:startingAt: -> [ values pairsDo: [:x :s | array findLast: [:y | x = y] startingAt: s]]. #findLast:ifNone: -> [ values do: [:x | array findLast: [:y | x = y] ifNone: [123456789 sqrt]]]. #findLast:startingAt:ifNone: -> [ values pairsDo: [:x :s | array findLast: [:y | x = y] startingAt: s ifNone: [123456789 sqrt]]]. } select: [:assoc | array respondsTo: assoc key]) collect: [:assoc | assoc key -> assoc value bench] as: Dictionary
=============== Diff against Collections-ul.875 ===============
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) - [(aBlock value: (self at: index)) ifTrue: [^index]]. - ^ 0!
Item was added: + ----- Method: SequenceableCollection>>findFirst:ifNone: (in category 'enumerating') ----- + findFirst: aBlock ifNone: anotherBlock + "Return the index of my first element for which aBlock evaluates as true. If no element is found, return the value of anotherBlock." + + | index | + (index := self findFirst: aBlock) = 0 + ifTrue: [^ anotherBlock value]. + ^ index!
Item was added: + ----- Method: SequenceableCollection>>findFirst:startingAt: (in category 'enumerating') ----- + findFirst: aBlock startingAt: minIndex + "Return the index of my first element with index >= minIndex for which aBlock evaluates as true." + + minIndex to: self size do: [:index | + (aBlock value: (self at: index)) ifTrue: [^index]]. + ^ 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 := self findFirst: aBlock startingAt: minIndex) = 0 + ifTrue: [^ anotherBlock value]. + ^ index!
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 + "Return the index of my last element for which aBlock evaluates as true. If no element is found, return the value of anotherBlock." + + | index | + (index := self findLast: aBlock) = 0 + ifTrue: [^ anotherBlock value]. + ^ index!
Item was changed: ----- Method: SequenceableCollection>>findLast:startingAt: (in category 'enumerating') ----- + findLast: aBlock startingAt: minIndex + "Return the index of my last element with index >= minIndex for which aBlock evaluates as true." - findLast: aBlock startingAt: i - "Return the index of my last element with index >= i for which aBlock evaluates as true."
+ self size to: minIndex by: -1 do: [:index | + (aBlock value: (self at: index)) ifTrue: [^index]]. - | 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 findLast: aBlock startingAt: minIndex) = 0 + ifTrue: [^ anotherBlock value]. + ^ index!
Hi Levente,
would you be fine with this version #findFirst:... and #findLast:... in the Trunk? :-)
Best, Christoph
--- Sent from Squeak Inbox Talk
On 2020-02-18T09:26:12+01:00, marcel.taeumel@hpi.de wrote:
I moved Collections-ct.875 to treated.
Best, Marcel Am 17.02.2020 20:57:58 schrieb commits at source.squeak.org <commits at source.squeak.org>: Christoph Thiede uploaded a new version of Collections to project The Inbox: http://source.squeak.org/inbox/Collections-ct.877.mcz
==================== Summary ====================
Name: Collections-ct.877 Author: ct Time: 17 February 2020, 8:57:49.278239 pm UUID: bf652ba0-43cc-734d-ac03-7a226cc80463 Ancestors: Collections-ul.875
Extends and realigns version of #findFirst: and #findLast:.
Second, optimized version after many helpful comments by Levente (ul). Thank you! Replaces Collections-ct.875.
Performance analysis:
#findFirst: - '238 per second. 4.2 milliseconds per run. 0.73956 % GC time.' #findFirst:startingAt: - '1,510 per second. 660 microseconds per run. 1.56 % GC time.' #findFirst:startingAt:ifNone: - '1,210 per second. 828 microseconds per run. 2.06 % GC time.' #findFirst:ifNone: - '214 per second. 4.68 milliseconds per run. 0.65987 % GC time.' #findLast: - '210 per second. 4.76 milliseconds per run. 0.66 % GC time.' #findLast:startingAt: - '1,380 per second. 724 microseconds per run. 1.72 % GC time.' #findLast:startingAt:ifNone: - '1,130 per second. 887 microseconds per run. 2 % GC time.' #findLast:ifNone: - '206 per second. 4.86 milliseconds per run. 0.81967 % GC time.'
Comparing to previous version:
#findFirst: - '193 per second. 5.19 milliseconds per run. 0.5994 % GC time.' (NOW 23.3% faster) #findLast: - '213 per second. 4.69 milliseconds per run. 0.71986 % GC time.' (NOW 1.4% slower) #findLast:startingAt: - '1,360 per second. 736 microseconds per run. 1.72 % GC time.' (NOW 1.4% faster)
Measurements code:
random := Random new. range := 1 to: 256. array := (1 to: 128) collect: [:i | range atRandom: random]. values := (1 to: 4096) collect: [:i | range atRandom: random].
({ #findFirst: -> [ values do: [:x | array findFirst: [:y | x = y]]]. #findFirst:startingAt: -> [ values pairsDo: [:x :s | array findFirst: [:y | x = y] startingAt: s]]. #findFirst:ifNone: -> [ values do: [:x | array findFirst: [:y | x = y] ifNone: [123456789 sqrt]]]. #findFirst:startingAt:ifNone: -> [ values pairsDo: [:x :s | array findFirst: [:y | x = y] startingAt: s ifNone: [123456789 sqrt]]]. #findLast: -> [ values do: [:x | array findLast: [:y | x = y]]]. #findLast:startingAt: -> [ values pairsDo: [:x :s | array findLast: [:y | x = y] startingAt: s]]. #findLast:ifNone: -> [ values do: [:x | array findLast: [:y | x = y] ifNone: [123456789 sqrt]]]. #findLast:startingAt:ifNone: -> [ values pairsDo: [:x :s | array findLast: [:y | x = y] startingAt: s ifNone: [123456789 sqrt]]]. } select: [:assoc | array respondsTo: assoc key]) collect: [:assoc | assoc key -> assoc value bench] as: Dictionary
=============== Diff against Collections-ul.875 ===============
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)
- [(aBlock value: (self at: index)) ifTrue: [^index]].
- ^ 0!
Item was added:
- ----- Method: SequenceableCollection>>findFirst:ifNone: (in category 'enumerating') -----
- findFirst: aBlock ifNone: anotherBlock
- "Return the index of my first element for which aBlock evaluates as true. If no element is found, return the value of anotherBlock."
- | index |
- (index := self findFirst: aBlock) = 0
- ifTrue: [^ anotherBlock value].
- ^ index!
Item was added:
- ----- Method: SequenceableCollection>>findFirst:startingAt: (in category 'enumerating') -----
- findFirst: aBlock startingAt: minIndex
- "Return the index of my first element with index >= minIndex for which aBlock evaluates as true."
- minIndex to: self size do: [:index |
- (aBlock value: (self at: index)) ifTrue: [^index]].
- ^ 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 := self findFirst: aBlock startingAt: minIndex) = 0
- ifTrue: [^ anotherBlock value].
- ^ index!
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
- "Return the index of my last element for which aBlock evaluates as true. If no element is found, return the value of anotherBlock."
- | index |
- (index := self findLast: aBlock) = 0
- ifTrue: [^ anotherBlock value].
- ^ index!
Item was changed: ----- Method: SequenceableCollection>>findLast:startingAt: (in category 'enumerating') -----
- findLast: aBlock startingAt: minIndex
- "Return the index of my last element with index >= minIndex for which aBlock evaluates as true."
- findLast: aBlock startingAt: i
- "Return the index of my last element with index >= i for which aBlock evaluates as true."
- self size to: minIndex by: -1 do: [:index |
- (aBlock value: (self at: index)) ifTrue: [^index]].
- | 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 findLast: aBlock startingAt: minIndex) = 0
- ifTrue: [^ anotherBlock value].
- ^ index!
squeak-dev@lists.squeakfoundation.org