Uploaded image for project: 'Erlang/OTP'
  1. Erlang/OTP
  2. ERL-1216

Performance degradation in lists:mapfoldl

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 23.0, 22.3
    • Fix Version/s: 23
    • Component/s: compiler
    • Labels:
      None

      Description

      In versions OTP-22 and 23.0-rc2 some cases lists:mapfoldl provides bad performance comparing with otp-21.

       

      Probably this is causes by suboptimal stack allocation.

       

      Sample code:

       

       

      lists:mapfoldl(fun(K,Dict) -> {1,dict:store(K,1,Dict)} end,
        dict:new(),
        lists:seq(1, 166666))
       end 
      

       

      21.3.8.3: Time: 615437
      22.3: Time: 5405957
      23.0-rc2: Time: 5569684

       

      OTP-21 asm code:

       

      {function, mapfoldl, 3, 5}.
        {label,4}.
          {line,[{location,"slow.erl",10}]}.
          {func_info,{atom,slow},{atom,mapfoldl},3}.
        {label,5}.
          {test,is_nonempty_list,{f,6},[{x,2}]}.
          {allocate,2,3}.
          {get_list,{x,2},{x,3},{y,1}}.
          {move,{x,0},{x,2}}.
          {move,{x,2},{y,0}}.
          {move,{x,3},{x,0}}.
          {line,[{location,"slow.erl",11}]}.
          {call_fun,2}.
          {test,is_tuple,{f,8},[{x,0}]}.
          {test,test_arity,{f,8},[{x,0},2]}.
          {get_tuple_element,{x,0},1,{x,1}}.
          {move,{y,1},{x,2}}.
          {get_tuple_element,{x,0},0,{y,1}}.
          {move,{y,0},{x,0}}.
          {trim,1,1}.
          {line,[{location,"slow.erl",12}]}.
          {call,3,{f,5}}.
          {test,is_tuple,{f,7},[{x,0}]}.
          {test,test_arity,{f,7},[{x,0},2]}.
          {test_heap,5,1}.
          {get_tuple_element,{x,0},0,{x,1}}.
          {get_tuple_element,{x,0},1,{x,2}}.
          {put_list,{y,0},{x,1},{x,1}}.
          {put_tuple,2,{x,0}}.
          {put,{x,1}}.
          {put,{x,2}}.
          {deallocate,1}.
          return.
        {label,6}.
          {test,is_nil,{f,4},[{x,2}]}.
          {test,is_function2,{f,4},[{x,0},{integer,2}]}.
          {test_heap,3,2}.
          {put_tuple,2,{x,0}}.
          {put,nil}.
          {put,{x,1}}.
          return.
        {label,7}.
          {line,[{location,"slow.erl",12}]}.
          {badmatch,{x,0}}.
        {label,8}.
          {line,[{location,"slow.erl",11}]}.
          {badmatch,{x,0}}.
      

       

       

      OTP-22 asm code:

       

      {function, mapfoldl, 3, 5}.
        {label,4}.
          {line,[{location,"slow.erl",10}]}.
          {func_info,{atom,slow},{atom,mapfoldl},3}.
        {label,5}.
          {test,is_nonempty_list,{f,6},[{x,2}]}.
          {allocate,3,3}.
          {init,{y,0}}.
          {move,{x,0},{y,2}}.
          {get_list,{x,2},{x,0},{y,1}}.
          {move,{y,2},{x,2}}.
          {line,[{location,"slow.erl",11}]}.
          {call_fun,2}.
          {move,{x,0},{y,0}}.
          {test,is_tuple,{f,7},[{x,0}]}.
          {test,test_arity,{f,7},[{x,0},2]}.
          {get_tuple_element,{y,0},1,{x,1}}.
          {move,{y,1},{x,2}}.
          {move,{y,2},{x,0}}.
          {kill,{y,1}}.
          {kill,{y,2}}.
          {line,[{location,"slow.erl",12}]}.
          {call,3,{f,5}}.
          {'%',{type_info,{x,0},{tuple,2,#{{integer,1} => list}}}}.
          {test_heap,5,1}.
          {get_tuple_element,{y,0},0,{x,1}}.
          {get_tuple_element,{x,0},0,{x,2}}.
          {get_tuple_element,{x,0},1,{x,0}}.
          {put_list,{x,1},{x,2},{x,1}}.
          {put_tuple2,{x,0},{list,[{x,1},{x,0}]}}.
          {deallocate,3}.
          return.
        {label,6}.
          {test,is_nil,{f,4},[{x,2}]}.
          {test,is_function2,{f,4},[{x,0},{integer,2}]}.
          {test_heap,3,2}.
          {put_tuple2,{x,0},{list,[nil,{x,1}]}}.
          return.
        {label,7}.
          {line,[{location,"slow.erl",11}]}.
          {badmatch,{y,0}}.

       

       

       

      Small discussion:

      https://erlang.org/pipermail/erlang-questions/2020-March/099367.html

       

       

        Attachments

          Activity

            People

            Assignee:
            bjorn Björn Gustavsson
            Reporter:
            alexey.antipov Alexey Antipov
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Dates

              Created:
              Updated:
              Resolved: