[Pharo-project] #at:ifAbsent: for Array(s) could be faster
Here the original implementation, which Array inherits from SequenceableCollection: at: index ifAbsent: exceptionBlock "Answer the element at my position index. If I do not contain an element at index, answer the result of evaluating the argument, exceptionBlock." (index between: 1 and: self size) ifTrue: [^ self at: index]. ^ exceptionBlock value the thing is, that #at: primivite also doing a range checking and fails if index is invalid, so if index is valid, as result we performing a range checking twice instead of just once. Here the simple implementation how to make things faster: fat: index "Primitive. Assumes receiver is indexable. Answer the value of an indexable element in the receiver. Fail if the argument index is not an Integer or is out of bounds. Essential. See Object documentation whatIsAPrimitive. Read the class comment for a discussion about that the fact that the index can be a float." <primitive: 60> ^ #plopp fat: index ifAbsent: aBlock | x | x := (self fat: index). x == #plopp ifTrue: [ ^ aBlock value ]. ^ x And speedup is almost 2 times: [ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 1 ifAbsent: nil ] ] timeToRun 39 [ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 1 ifAbsent: nil ] ] timeToRun 20 Even when index is out of range, it is still much faster: [ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 100 ifAbsent: nil ] ] timeToRun 35 [ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) fat: 100 ifAbsent: nil ] ] timeToRun 24 The problem, of course, that trick with #plopp is a dirty hack. Because if array include an #plopp object as element, it will report as it absent, instead of answering it. There is no way to ensure that any arbitrary object are never included as element in array, so this is no-go for generic replacement. But in controlled environment, when you know that none of arrays which you using with #fat:ifAbsent: will ever include #plopp (or pick your own unique object) it may be a good alternative. -- Best regards, Igor Stasenko.
On Wed, 2 Nov 2011, Igor Stasenko wrote:
Here the original implementation, which Array inherits from SequenceableCollection:
at: index ifAbsent: exceptionBlock "Answer the element at my position index. If I do not contain an element at index, answer the result of evaluating the argument, exceptionBlock."
(index between: 1 and: self size) ifTrue: [^ self at: index]. ^ exceptionBlock value
the thing is, that #at: primivite also doing a range checking and fails if index is invalid, so if index is valid, as result we performing a range checking twice instead of just once.
Here the simple implementation how to make things faster: fat: index "Primitive. Assumes receiver is indexable. Answer the value of an indexable element in the receiver. Fail if the argument index is not an Integer or is out of bounds. Essential. See Object documentation whatIsAPrimitive. Read the class comment for a discussion about that the fact that the index can be a float."
<primitive: 60> ^ #plopp
fat: index ifAbsent: aBlock | x | x := (self fat: index). x == #plopp ifTrue: [ ^ aBlock value ]. ^ x
And speedup is almost 2 times:
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 1 ifAbsent: nil ] ] timeToRun
39
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 1 ifAbsent: nil ] ] timeToRun
20
Even when index is out of range, it is still much faster:
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 100 ifAbsent: nil ] ] timeToRun
35
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) fat: 100 ifAbsent: nil ] ] timeToRun
24
The problem, of course, that trick with #plopp is a dirty hack. Because if array include an #plopp object as element, it will report as it absent, instead of answering it. There is no way to ensure that any arbitrary object are never included as element in array, so this is no-go for generic replacement. But in controlled environment, when you know that none of arrays which you using with #fat:ifAbsent: will ever include #plopp (or pick your own unique object) it may be a good alternative.
I've been thinking about this earlier and there's a much nicer and simpler solution, though it requires vm changes :). The idea is to change primitive 60 to work for 2 parameters too, so #at:ifAbsent: could also use the primitive directly. There were a few changes about #at: recently (mirror prims, cog), so I'm not sure it's still easy to change the primitive. Levente
-- Best regards, Igor Stasenko.
On Wed, Nov 2, 2011 at 11:33 AM, Levente Uzonyi <leves@elte.hu> wrote:
On Wed, 2 Nov 2011, Igor Stasenko wrote:
Here the original implementation, which Array inherits from
SequenceableCollection:
at: index ifAbsent: exceptionBlock "Answer the element at my position index. If I do not contain an element at index, answer the result of evaluating the argument, exceptionBlock."
(index between: 1 and: self size) ifTrue: [^ self at: index]. ^ exceptionBlock value
the thing is, that #at: primivite also doing a range checking and fails if index is invalid, so if index is valid, as result we performing a range checking twice instead of just once.
Here the simple implementation how to make things faster: fat: index "Primitive. Assumes receiver is indexable. Answer the value of an indexable element in the receiver. Fail if the argument index is not an Integer or is out of bounds. Essential. See Object documentation whatIsAPrimitive. Read the class comment for a discussion about that the fact that the index can be a float."
<primitive: 60> ^ #plopp
fat: index ifAbsent: aBlock | x | x := (self fat: index). x == #plopp ifTrue: [ ^ aBlock value ]. ^ x
And speedup is almost 2 times:
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 1 ifAbsent: nil ] ] timeToRun
39
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 1 ifAbsent: nil ] ] timeToRun
20
Even when index is out of range, it is still much faster:
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 100 ifAbsent: nil ] ] timeToRun
35
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) fat: 100 ifAbsent: nil ] ] timeToRun
24
The problem, of course, that trick with #plopp is a dirty hack. Because if array include an #plopp object as element, it will report as it absent, instead of answering it. There is no way to ensure that any arbitrary object are never included as element in array, so this is no-go for generic replacement. But in controlled environment, when you know that none of arrays which you using with #fat:ifAbsent: will ever include #plopp (or pick your own unique object) it may be a good alternative.
I've been thinking about this earlier and there's a much nicer and simpler solution, though it requires vm changes :). The idea is to change primitive 60 to work for 2 parameters too, so #at:ifAbsent: could also use the primitive directly. There were a few changes about #at: recently (mirror prims, cog), so I'm not sure it's still easy to change the primitive.
his is neat, but it wouldn't be an extension to primitive 60 but a new primitive that would ignore its top of stack. primitive 60 can operate with 2 args,when used as a mirror primitive, but then it ignores the receiver. Your usage would ignore the last argument. So choose a primitive number and I'll make it so...
Levente
-- Best regards, Igor Stasenko.
-- best, Eliot
Am I crazy to think that this reflect a language-expressiveness issue? I mean, I can think of a couple of ways around it, like implement #at: code in the #at:ifAbsent routine (which violates DRY), or have an #__unsafe_at:. And it seems like there'd be lots of cases of this, though I could be wrong. And maybe there aren't enough cases of this to matter, but it seems like it should be possible to group methods under a particular set of validations/safety checks. They could require them without performing them. Theoretically, anyway. Heh. On Wed, Nov 2, 2011 at 12:55 PM, Eliot Miranda <eliot.miranda@gmail.com>wrote:
On Wed, Nov 2, 2011 at 11:33 AM, Levente Uzonyi <leves@elte.hu> wrote:
On Wed, 2 Nov 2011, Igor Stasenko wrote:
Here the original implementation, which Array inherits from
SequenceableCollection:
at: index ifAbsent: exceptionBlock "Answer the element at my position index. If I do not contain an element at index, answer the result of evaluating the argument, exceptionBlock."
(index between: 1 and: self size) ifTrue: [^ self at: index]. ^ exceptionBlock value
the thing is, that #at: primivite also doing a range checking and fails if index is invalid, so if index is valid, as result we performing a range checking twice instead of just once.
Here the simple implementation how to make things faster: fat: index "Primitive. Assumes receiver is indexable. Answer the value of an indexable element in the receiver. Fail if the argument index is not an Integer or is out of bounds. Essential. See Object documentation whatIsAPrimitive. Read the class comment for a discussion about that the fact that the index can be a float."
<primitive: 60> ^ #plopp
fat: index ifAbsent: aBlock | x | x := (self fat: index). x == #plopp ifTrue: [ ^ aBlock value ]. ^ x
And speedup is almost 2 times:
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 1 ifAbsent: nil ] ] timeToRun
39
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 1 ifAbsent: nil ] ] timeToRun
20
Even when index is out of range, it is still much faster:
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) at: 100 ifAbsent: nil ] ] timeToRun
35
[ 1000000 timesRepeat: [ #(1 2 4 5 56 67 67) fat: 100 ifAbsent: nil ] ] timeToRun
24
The problem, of course, that trick with #plopp is a dirty hack. Because if array include an #plopp object as element, it will report as it absent, instead of answering it. There is no way to ensure that any arbitrary object are never included as element in array, so this is no-go for generic replacement. But in controlled environment, when you know that none of arrays which you using with #fat:ifAbsent: will ever include #plopp (or pick your own unique object) it may be a good alternative.
I've been thinking about this earlier and there's a much nicer and simpler solution, though it requires vm changes :). The idea is to change primitive 60 to work for 2 parameters too, so #at:ifAbsent: could also use the primitive directly. There were a few changes about #at: recently (mirror prims, cog), so I'm not sure it's still easy to change the primitive.
his is neat, but it wouldn't be an extension to primitive 60 but a new primitive that would ignore its top of stack. primitive 60 can operate with 2 args,when used as a mirror primitive, but then it ignores the receiver. Your usage would ignore the last argument.
So choose a primitive number and I'll make it so...
Levente
-- Best regards, Igor Stasenko.
-- best, Eliot
what if fat would do different nasty trick, like <primitive:60> ^(thisContext callingContext argAt: 2) value ? (make up #callingContext and #argAt:, I just presume there is something like that...) The question is if it would be faster. -- View this message in context: http://forum.world.st/at-ifAbsent-for-Array-s-could-be-faster-tp3980183p3981... Sent from the Pharo Smalltalk mailing list archive at Nabble.com.
participants (5)
-
blake -
Eliot Miranda -
Herby VojÄÃk -
Igor Stasenko -
Levente Uzonyi