[squeak-dev] The Trunk: Collections-nice.582.mcz

Eliot Miranda eliot.miranda at gmail.com
Sun Sep 21 19:41:33 UTC 2014


Hi Levente,

On Sat, Sep 20, 2014 at 6:50 PM, Levente Uzonyi <leves at elte.hu> wrote:

> Hi Eliot,
>
> On Sat, 20 Sep 2014, Eliot Miranda wrote:
>
>  Hi Levente,
>>
>> On Sat, Sep 20, 2014 at 8:24 AM, Levente Uzonyi <leves at elte.hu> wrote:
>>       Cool. I think the spaceship operator for strings should use
>> #compare:with:collated: to save a comparison in the most common case.
>>
>>       The performance of symbols would be close to dyadic blocks, if it
>> were cheap and easy to create a block on the fly.
>>
>>
>> I don't know what cheap enough in this case is but Spur is over 5 times
>> faster at creating blocks than the existing Cog V3 VM:
>>
>
> I meant compiling a sortblock, which can be passed to #sort: or #sorted:.
> It seems to be too expensive to be used by default:
>
> [ Compiler evaluate: ('[ :a :b | a {1} {2} b {1} ]' format: { #abs. #< })
> ] bench. '3,560 per second.'
>

ah, of course!  Now I understand.

If we drop down to the bytecode level, in this case using my MethodMassage
bytecode (dis)assembler we can up the performance considerably.  First the
baseline on my machine (in Spur):

[ Compiler evaluate: ('[ :a :b | a {1} {2} b {1} ]' format: { #abs. #< }) ]
bench 11,800 per second.

(c.f. [ Compiler evaluate: ('[ :a :b | a {1} {2} b {1} ]' format: { #abs.
#< }) ] bench 10409.9 per second. Cog)

Now using the assembler, where it is easy to construct the message sequence
you want.  Since the assembler answers a method we need to evaluate it to
produce the closure:

[nil
withArgs: #()
executeMethod:
(AssemblerMethod new
methodClass: UndefinedObject;
pushClosureCopyNumCopiedValues: 0 numArgs: 2 blockSize: 'L1';
pushTemporaryVariable: 0;
send: #abs;
pushTemporaryVariable: 1;
send: #abs;
send: #<;
blockReturnTop;
label: 'L1';
methodReturnTop;
yourself) assemble] bench '27,100 per second.'

So it's more than twice as fast but at ~ 36 microseconds per block creation
it may well be too expensive.


| c d |
> c := (1 to: 20) collect: [:i | 1000000 atRandom-500000].
> d := c copy.
> {
> [ d copyFrom: c ] bench.
> [ d copyFrom: c; sort: [:a :b | a abs < b abs] ] bench.
> [ d copyFrom: c; sort: (Compiler evaluate: ('[ :a :b | a {1} {2} b {1} ]'
> format: { #abs. #< })) ] bench.
> }.
> #('9,720,000 per second.' '125,000 per second.' '7,310 per second.')
>
> But there could be a special message which compiles an optimized block.
> Something like
>
> #(-1 0 1 2) sort: #abs ascending compiled
>
> where #compiled returns the block [ :a :b | a abs < b abs ].
> It could be useful when the collection is large enough:
>
> | c d |
> c := (1 to: 200000) collect: [:i | 1000000 atRandom-500000].
> d := c copy.
> {
> [ d copyFrom: c ] bench.
> [ d copyFrom: c; sort: [:a :b | a abs < b abs] ] bench.
> [ d copyFrom: c; sort: (Compiler evaluate: ('[ :a :b | a {1} {2} b {1} ]'
> format: { #abs. #< })) ] bench.
> }.
> #('1,390 per second.' '3.38 per second.' '3.58 per second.')
>
>
> Levente
>
> P.S.: The numbers below are impressive. :)
>
>
>
>>
>> [1 to: 1,000,000,000 do: [:i| [nil class]]] timeToRun
>>
>> Spur: 5,950ms
>> Cog: 31,951ms
>>
>> 31951 / 5950.0                 5.37
>> 5950 - 31951 / 319.51    -81.4%
>>
>> So ignoring the loop overhead, Spur creates a block in less than 6
>> nanoseconds on a 2.2GHz MBP Core i7.
>>
>>
>> A slightly more realistic example which creates a new home context for
>> every block created is
>>
>>
>> [1 to: 10,000,000 do: [:i| [[nil class]] value. [[nil class]] value.
>> [[nil class]] value. [[nil class]] value. [[nil class]] value. [[nil
>> class]] value. [[nil class]] value. [[nil class]] value. [[nil class]]
>> value. [[nil class]] value.]] timeToRun
>>
>> Spur: 2,568ms
>> Cog: 11,601ms
>>
>> 11601 / 2568.0 4.51752336448598
>> 2568 - 11601 / 116.01 -77.8639772433411
>>
>> So here Spur creates two closures and a context in 2.568 / 100,000,000 =
>> 26 nsecs, compared to 160 for Cog V3.
>>
>>       Levente
>>
>>       On Fri, 19 Sep 2014, commits at source.squeak.org wrote:
>>
>>             Nicolas Cellier uploaded a new version of Collections to
>> project The Trunk:
>>             http://source.squeak.org/trunk/Collections-nice.582.mcz
>>
>>             ==================== Summary ====================
>>
>>             Name: Collections-nice.582
>>             Author: nice
>>             Time: 19 September 2014, 10:22:13.338 pm
>>             UUID: 52a598f1-224e-4649-a95f-4e78547b5ed5
>>             Ancestors: Collections-nice.581
>>
>>             Port TAG-SortFunctions of Travis Griggs from Cincom public
>> store - version (11,tgriggs)
>>
>>             Note that no collation policy were used for String.
>>             The spaceship operator <=> is also required in Kernel-Numbers.
>>
>>             See also the blog http://objology.blogspot.fr/
>> 2010/11/tag-sortfunctions.html
>>             and http://objology.blogspot.fr/2010/11/tag-sortfunctions-
>> redux.html
>>
>>             Note about the cost of these sort functions:
>>             as shown by this mini-bench on cog, using a Symbol costs a
>> bit more (perform:) than a block activation, and monadic block a bit more
>> than dyadic one because activated twice more, but
>>             it seems acceptable to me with regard to the great
>> simplification and expressiveness of code :
>>
>>             | collec1 collec2 collec3 |
>>             collec1 := (1 to: 200000) collect: [:i | 1000000
>> atRandom-500000].
>>             collec2 := collec1 copy.
>>             collec3 := collec1 copy.
>>             {
>>             [collec1 sort: [:a :b | a abs < b abs]] timeToRun.
>>             [collec2 sort: [:e | e abs] ascending] timeToRun.
>>             [collec3 sort: #abs ascending] timeToRun.
>>             }
>>             #(345 532 912)
>>
>>
>>
>>
>>
>> --
>> best,Eliot
>>
>>
>
>
>


-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20140921/825a3e4c/attachment.htm


More information about the Squeak-dev mailing list