[erlang-questions] foldl vs foldr and ++

[Hynek Vychodil]

You are right. I should realize it myself instead guessing. Compiler
has to do something really smart there. Strange thing happen when I
copied lists:foldl and lists:foldr implementation inside benchmark
module and compile native. It is far (more than twice) slower than
BEAM.

On Thu, May 10, 2012 at 11:08 AM, Ulf Wiger <ulf@REDACTED> wrote:
>
> Try this benchmark program with, e.g. L = lists:seq(1,100000).
>
> -module(lr).
> -export([l/1, r/1, x/1, foldr/3]).
>
>
> l(L) ->
>    timer:tc(lists, foldl, [fun erlang:'+'/2, 0, L]).
>
> r(L) ->
>    timer:tc(lists, foldr, [fun erlang:'+'/2, 0, L]).
>
> x(L) ->
>    timer:tc(?MODULE, foldr, [fun erlang:'+'/2, 0, L]).
>
> foldr(F, Acc, L) -> lists:foldl(F, Acc, lists:reverse(L, [])).
>
>
> lists:foldl/3 and lists:foldr/3 run a fairly even race, whereas lr:foldr/3 is consistenty slower.
>
> BR,
> Ulf W
>
> On 10 May 2012, at 10:53, Hynek Vychodil wrote:
>
>> When I see foldr implementation I wonder why it is not simple
>>
>> foldr(F, Acc, L) -> foldl(F, Acc, lists:reverse(L, [])).
>>
>> There should be less memory consumption. lists:reverse is BIF which I
>> believe consume less memory than stack frame per each list element
>> what current foldr implementation do. It should be faster and both
>> accepts only proper lists. Only difference which I can found current
>> implementation consumes memory on stack but above implementation would
>> consume heap and affect GC behavior. Current foldr implementation
>> would make sense in Haskell but I don't understand its reason in
>> Erlang.
>>
>> On Thu, May 10, 2012 at 10:26 AM, Robert Virding
>> <robert.virding@REDACTED> wrote:
>>> The documentation is referring to the *implementation* of the foldl/foldr functions, foldl uses a tail-recursive function while foldr cannot do that. The difference in speed comes from what you do inside the fold function. As others have pointed out the efficiency of ++ depends solely on its left argument.
>>>
>>> Robert
>>>
>>> ----- Original Message -----
>>>> Aha I just looked at my own explanation and realized it made no
>>>> sense. Of course the slow one is slow for exactly the reason I
>>>> expected. Sorry for the waste, but thank you for the clear
>>>> complexity analysis.
>>>>
>>>> Andrew Ledvina
>>>>
>>>> On May 9, 2012, at 2:57 PM, "Richard O'Keefe" <ok@REDACTED>
>>>> wrote:
>>>>
>>>>>
>>>>> On 10/05/2012, at 7:00 AM, Andrew Ledvina wrote:
>>>>>
>>>>>> Okay, so I was profiling something and it led me to write this:
>>>>>>
>>>>>> from_left(X) ->
>>>>>>   lists:foldl(fun(Y,R) -> R ++ [{Y+1,Y*2}] end, [], X).
>>>>>>
>>>>>> from_right(X) ->
>>>>>>   lists:foldr(fun(Y,R) -> [{Y+1,Y*2}] ++ R end, [], X).
>>>>>
>>>>> Immediate reaction:  from_left/1 is going to be atrociously slow.
>>>>>
>>>>>> My understanding is that foldl is preferred over foldr because it
>>>>>> is tail recursive.
>>>>>
>>>>> ***other things being equal***
>>>>>
>>>>> In this case, they are not.  It should be clear that from_right/1
>>>>> is
>>>>> O(|X|) because it does O(1) work per element of X, while
>>>>> from_left/1 is O(|X|**2) because it does O(|R|) work per element of
>>>>> X, and R grows from empty to 2|X|-2 elements long.
>>>>>
>>>>> Write [{Y+1,Y*2} || Y <- X] and let the compiler worry about the
>>>>> best way to do it.
>>>>>
>>>>>> I was also to understand that putting the accumulator on the
>>>>>> left-hand-side of the ++ operation is super bad. So, the
>>>>>> following results were a bit of a surprise at first:
>>>>>
>>>>> If you understood that long++short is more expensive than
>>>>> short++long,
>>>>> you should NOT have been surprised by your result.
>>>>>
>>>>>
>>>> _______________________________________________
>>>> erlang-questions mailing list
>>>> erlang-questions@REDACTED
>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>>
>> --
>> Hynek Vychodil
>> Chief Scientists
>>
>> GoodData
>> náměstí 28. října 1104/17, 602 00, Brno - Černá Pole
>> Office:   +420 530 50 7704
>> E-mail:  hynek@REDACTED
>> Web:     www.gooddata.com
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
>
> Ulf Wiger, Co-founder & Developer Advocate, Feuerlabs Inc.
> http://feuerlabs.com
>
>
>



-- 
Hynek Vychodil
Chief Scientists

GoodData
náměstí 28. října 1104/17, 602 00, Brno - Černá Pole
Office:   +420 530 50 7704
E-mail:  hynek@REDACTED
Web:     www.gooddata.com