[Enh][VM] primitiveApplyToFromTo for the heart of the enumeration of collections?

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

[Enh][VM] primitiveApplyToFromTo for the heart of the enumeration of collections?

Klaus D. Witzel
Attached is #primitiveApplyToFromTo as it compiles and runs using the  
win32 Squeak 3.7.1 build environment here; I'm testing it with the 3.8 and  
3.9 images.

The performance is compared against plain #do: (apples v.s. apples) and  
#to:do: (apples v.s. oranges) further down below.

Compared to #do: with block, #applyTo:from:to: with block is definitively  
faster (smaller hidden constants) and there also is at least one item  
waiting for optimization (and for me having time to do that).

I'd say that the factor can arrive at about 2 (#do: v.s.  
#applyTo:from:to:). But the primitive will not outperform an inlined  
#to:do: this was clear from the beginning. As Jon wrote, the primitive is  
good for "fixing" the standard enumeration methods so they all have (more  
or less) identical performance.

The current implementation is for non-Strings only (as dictated by an  
atCache parameter) but can of course be extended to work with Strings.  
Another item that's missing is returning self from the primitive, this is  
currently handled by falling into the shadow which then returns (and some  
superflous bytecode cycles are burned).

Example method in SequenceableCollection
applyTo: aBlock from: index to: limit
        <primitive: 164>
        [index <= limit] whileTrue:
                [aBlock value: (self basicAt: index).
                 thisContext tempAt: 2 put: index + 1]

The shadow code is exactly what is done by the primitive. As discussed  
ealier,the primitive can be called from #commonSend and from #commonReturn  
and in both cases might decide to exit with primitiveFail.

The overrides for #commonSend and #commonReturn are not attached but if  
you want them ask me.

Any questions?

/Klaus

--------------------

| time array sum |
        array := (1 to: 10565520) collect: [:none | 1].
        Smalltalk garbageCollect.
        time := Time millisecondsToRun: [
                sum := array sum].
        sum.
        time
=> 9093

--------------------

| time array sum |
        array := (1 to: 10565520) collect: [:none | 1].
        Smalltalk garbageCollect.
        time := Time millisecondsToRun: [
                sum := 0.
                array do: [:each | sum := sum + each]].
        sum.
        time
=> 4764

--------------------

| time array sum |
        array := (1 to: 10565520) collect: [:none | 1].
        Smalltalk garbageCollect.
        time := Time millisecondsToRun: [
                sum := 0.
                array applyTo: [:each | sum := sum + each]
                        from: 1 to: array size].
        sum.
        time
=> 3499

--------------------

| time array sum |
        array := (1 to: 10565520) collect: [:none | 1].
        Smalltalk garbageCollect.
        time := Time millisecondsToRun: [
                sum := 0.
                1 to: array size do: [:index | sum := sum + (array at: index)]].
        sum.
        time
=> 2089

--------------------

PrimitiveApplyFromTo-kwl.1.cs (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [Enh][VM] primitiveApplyToFromTo for the heart of the enumeration of collections?

Andreas.Raab
Where is the other half of the changes? What you sent isn't enough to
generate a functioning VM. I'm in particular curious how you've dealt
with the loop inlining and it seems there is some code missing which
does that.

Cheers,
    - Andreas

Klaus D. Witzel wrote:

> Attached is #primitiveApplyToFromTo as it compiles and runs using the
> win32 Squeak 3.7.1 build environment here; I'm testing it with the 3.8
> and 3.9 images.
>
> The performance is compared against plain #do: (apples v.s. apples) and
> #to:do: (apples v.s. oranges) further down below.
>
> Compared to #do: with block, #applyTo:from:to: with block is
> definitively faster (smaller hidden constants) and there also is at
> least one item waiting for optimization (and for me having time to do
> that).
>
> I'd say that the factor can arrive at about 2 (#do: v.s.
> #applyTo:from:to:). But the primitive will not outperform an inlined
> #to:do: this was clear from the beginning. As Jon wrote, the primitive
> is good for "fixing" the standard enumeration methods so they all have
> (more or less) identical performance.
>
> The current implementation is for non-Strings only (as dictated by an
> atCache parameter) but can of course be extended to work with Strings.
> Another item that's missing is returning self from the primitive, this
> is currently handled by falling into the shadow which then returns (and
> some superflous bytecode cycles are burned).
>
> Example method in SequenceableCollection
> applyTo: aBlock from: index to: limit
>     <primitive: 164>
>     [index <= limit] whileTrue:
>         [aBlock value: (self basicAt: index).
>          thisContext tempAt: 2 put: index + 1]
>
> The shadow code is exactly what is done by the primitive. As discussed
> ealier,the primitive can be called from #commonSend and from
> #commonReturn and in both cases might decide to exit with primitiveFail.
>
> The overrides for #commonSend and #commonReturn are not attached but if
> you want them ask me.
>
> Any questions?
>
> /Klaus
>
> --------------------
>
> | time array sum |
>     array := (1 to: 10565520) collect: [:none | 1].
>     Smalltalk garbageCollect.
>     time := Time millisecondsToRun: [
>         sum := array sum].
>     sum.
>     time
> => 9093
>
> --------------------
>
> | time array sum |
>     array := (1 to: 10565520) collect: [:none | 1].
>     Smalltalk garbageCollect.
>     time := Time millisecondsToRun: [
>         sum := 0.
>         array do: [:each | sum := sum + each]].
>     sum.
>     time
> => 4764
>
> --------------------
>
> | time array sum |
>     array := (1 to: 10565520) collect: [:none | 1].
>     Smalltalk garbageCollect.
>     time := Time millisecondsToRun: [
>         sum := 0.
>         array applyTo: [:each | sum := sum + each]
>             from: 1 to: array size].
>     sum.
>     time
> => 3499
>
> --------------------
>
> | time array sum |
>     array := (1 to: 10565520) collect: [:none | 1].
>     Smalltalk garbageCollect.
>     time := Time millisecondsToRun: [
>         sum := 0.
>         1 to: array size do: [:index | sum := sum + (array at: index)]].
>     sum.
>     time
> => 2089
>
> --------------------
>
>
> ------------------------------------------------------------------------
>
>


Reply | Threaded
Open this post in threaded view
|

Re: [Enh][VM] primitiveApplyToFromTo for the heart of the enumeration of collections?

Klaus D. Witzel
In reply to this post by Klaus D. Witzel
The previously missing #returnReceiver case is now solved and the new .cs
posted to

- http://bugs.impara.de/view.php?id=4925

The Mantis report also includes the overrides for #commonSend and
#commonReturn.

Andreas, #commonSend and #commonReturn are the same what I emailed you
last night.

It would be interesting to compare the performance figures for platforms
other than win32.

/Klaus