[squeak-dev] Collection's #fold: vs #reduce:

Eliot Miranda eliot.miranda at gmail.com
Tue Nov 2 19:25:18 UTC 2010


On Tue, Nov 2, 2010 at 11:50 AM, Eliot Miranda <eliot.miranda at gmail.com>wrote:

>
>
> On Tue, Nov 2, 2010 at 11:31 AM, Levente Uzonyi <leves at elte.hu> wrote:
>
>> On Tue, 2 Nov 2010, Eliot Miranda wrote:
>>
>>  Hi Levente,
>>>
>>> On Tue, Nov 2, 2010 at 10:16 AM, Levente Uzonyi <leves at elte.hu> wrote:
>>>
>>>  Hi,
>>>>
>>>> we have these two methods which do exactly the same thing. #reduce: was
>>>> added by Andreas during the developement of Squeak 4.1. #fold was added
>>>> by
>>>> Eliot for Cog VMMaker compatibility. One of them is superfluous. I can
>>>> image
>>>> the following solutions:
>>>>
>>>> 1) Replace senders of #fold: in VMMaker to use #reduce:, and remove
>>>> #fold:
>>>> from the image.
>>>>
>>>> 2) Replace #fold:'s implementation to self reduce: aBlock. I benchmarked
>>>> the two methods and #reduce: is a bit faster on CogVM. There's no
>>>> difference
>>>> on SqueakVM.
>>>>
>>>>
>>> I noticed the same thing.  I prefer the fold: implementation so I'm
>>> bummed
>>> it's slightly slower ;)  Personally I like fold: as a name (it's shorter
>>> and
>>>
>>
>> The difference is about 1%, but it's reproducible. And yes, the
>> implementation of #fold: is a bit nicer. :)
>
>
> The difference is due to the instantiation "Object new", and instantiation
> is slow on the current Cog because I haven't implemented the instantiation
> primitives in machine code, and this limitation is hopefully temporary.  So
> you might leave it be.  However, changing the code to use {} for teh
> instantiation speeds things up markedly:
>
> Collection>>newFold: binaryBlock
> | firstValue nextValue |
> firstValue := nextValue := {}.
>  self do:
> [:each |
> nextValue := firstValue == nextValue
>  ifTrue: [each]
> ifFalse: [binaryBlock value: nextValue value: each]].
>  ^nextValue == firstValue
> ifTrue: [self errorEmptyCollection]
> ifFalse: [nextValue]
>
> | c r |
> c := #('if' 'it' 'is' 'to' 'be' 'it' 'is' 'up' 'to' 'me').
> { Time millisecondsToRun: [1 to: 1000000 do: [:i| c fold: [:a :b | a, ' ',
> b]]].
>  Time millisecondsToRun: [1 to: 1000000 do: [:i| c newFold: [:a :b | a, '
> ', b]]].
> Time millisecondsToRun: [1 to: 1000000 do: [:i| c reduce: [:a :b | a, ' ',
> b]]] }
>  #(5076 5008 5052)
>
>
> | c |
> c := #('if').
> { Time millisecondsToRun: [1 to: 1000000 do: [:i| c fold: [:a :b | a, ' ',
> b]]].
>    Time millisecondsToRun: [1 to: 1000000 do: [:i| c newFold: [:a :b | a, '
> ', b]]].
>    Time millisecondsToRun: [1 to: 1000000 do: [:i| c reduce: [:a :b | a, '
> ', b]]] }
>  #(247 226 220)
>
>
> (N.B.  the above are rough measurements!!).
>
> So how about changing fold: to replace Object new with {} and keep it?
>

And of course one can consider using thisContext instead of Object new or
{}, since thisContext has to be instantiated anyway for the closure in
fold:, and so results in less memory pressure.  This needs careful
measurement; you have the test bed set up for that; my workspace hacks are
showing too much variability to distinguish.

This is too ugly to contemplate, but at first blush it seems faster:

fold: binaryBlock
"Evaluate the block with the first two elements of the receiver,
 then with the result of the first evaluation and the next element,
 and so on.  Answer the result of the final evaluation. If the receiver
 is empty, raise an error. If the receiver has a single element, answer
 that element."
"#('if' 'it' 'is' 'to' 'be' 'it' 'is' 'up' 'to' 'me') fold: [:a :b | a, ' ',
b]"

| firstValue nextValue |
firstValue := nextValue := "something that can't be in the receiver"
[:each |
nextValue := firstValue == nextValue
ifTrue: [each]
ifFalse: [binaryBlock value: nextValue value: each]].
self do: firstValue.
^nextValue == firstValue
ifTrue: [self errorEmptyCollection]
ifFalse: [nextValue]



>
>
>> Eliot
>
>
>>
>>  more cuddly) and since we don't have map: (we have collect:) I don't find
>>> the need to use reduce: compelling.  But that's my preference.  I won't
>>> object if you replace fold: with reduce:/  I do note that Gilad used
>>> fold:
>>> in Newspeak.
>>>
>>> What do you prefer?
>>>
>>
>> I prefer the second option, because both names are widely used, but some
>> people are only aware of the one which their previously used languages have.
>> So this way we can avoid questions like "Why isn't there a
>> method for folding in Squeak?".
>>
>>
>> Levente
>>
>>
>>
>>> What do others prefer?
>>>
>>> I know, choices, choices :)
>>>
>>> best
>>> Eliot
>>>
>>>
>>>
>>>
>>>>
>>>> Cheers,
>>>> Levente
>>>>
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20101102/cdfa6c1a/attachment.htm


More information about the Squeak-dev mailing list