[Vm-dev] Re: [Pharo-project] #at:ifAbsent: for Array(s) could be faster

Eliot Miranda eliot.miranda at gmail.com
Wed Nov 2 20:23:33 UTC 2011


On Wed, Nov 2, 2011 at 1:15 PM, Igor Stasenko <siguctua at gmail.com> wrote:

>
> On 2 November 2011 20:55, Eliot Miranda <eliot.miranda at gmail.com> wrote:
> >
> >
> >
> > On Wed, Nov 2, 2011 at 11:33 AM, Levente Uzonyi <leves at 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...
>
> Of course i was thinking about changing VM too. But i am uncertain if
> it worth doing so, because maybe this is too low reward for putting
> effort in it.
>
> But if we going to make new prim , here's what i'd like to have
>  - use proper prim error code(s) to distinguish between cases:
>   - a receiver is not indexable/variable object
>   - an index is integer, but points outside of array's range
>   - an object passed as index is non-integer
>

I agree.  I was going to brag that the Cog VM already has this implemented
but the error code returned for a non-indexable receiver is wrong.  It
should be #'bad receiver' but the prim always answers #'bad index'.  I'll
fix this.  Primitive error codes and relevant usage in primitives still
need to be ported to the standard VM though.


> this is to eliminate code which tries to guess what is really happen:
>
> <primitive: 60>
> index isInteger ifTrue:
>                [self class isVariable
>                        ifTrue: [self errorSubscriptBounds: index]
>                        ifFalse: [self errorNotIndexable]].
>        index isNumber
>                ifTrue: [^self at: index asInteger]
>                ifFalse: [self errorNonIntegerIndex]
>
>
> Btw, this is an example of how much more flexibility we could earn, if
> we could rewrite basic prims to count (and use) arguments from bottom
> of stack (receiver) instead from top,
> so primitives could be used in more flexible manner.
>
>
> --
> Best regards,
> Igor Stasenko.
>



-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20111102/ee8dc637/attachment-0001.htm


More information about the Vm-dev mailing list