[erlang-patches] Add lists:init/1 - got tired of implementing it

Robert Virding <>
Sun Apr 28 04:57:16 CEST 2013


But it creates more garbage so it will cause the collector to run more often, which costs.

Robert

----- Original Message -----
> From: "Fred Hebert" <>
> 
> Ah yeah, the version that reverses twice is more likely to be fast
> due
> to the fact that lists:reverse/1 calls lists:reverse/2, which is now
> a
> NIF. Thus the traversal and building is gonna be made in C rather
> than
> in Erlang. Testing with a 'homemade' lists:reverse/2 tends to bring
> things back to the more expected N vs. 2N for traversals.
> 
> Regards,
> Fred.
> 
> On 04/26, Hans Svensson wrote:
> > You are absolutely right about the 'badarg', it is better to have a
> > consistent failure!
> > 
> > However on performance, the suggested implementation is somewhat
> > surprisingly the best option (I admit, I did measure before writing
> > the patch ;-) ) For lists up to 3000 elements, it is on average
> > ~x1.8 faster than a (tail-)recursive implementation!
> > 
> > So a better version would probably be:
> > init([]) -> error(badarg);
> > init(List = [_ | _]) ->
> >   lists:reverse(tl(lists:reverse(List)));
> > init(_) -> error(badarg).
> > 
> > /Hans
> > 
> > On 2013-04-25 18:18, Fred Hebert wrote:
> > >I don't think there's any benefit in tail-recursion when you're
> > >rebuilding an entirely new list. Given the limited number of
> > >arguments,
> > >the list you're creating by not being tail-recursive is in all
> > >points
> > >similar to the one you would have to maintain on the stack through
> > >tail
> > >recursions. Maybe a bit larger, but given you don't have to trash
> > >it,
> > >you're likely to avoid GC costs by doing it that way.
> > >
> > >See
> > >http://erlang.2086793.n4.nabble.com/Efficiency-of-a-list-construction-td3538122.html#a3538379
> > >and
> > >http://ferd.ca/erlang-s-tail-recursion-is-not-a-silver-bullet.html
> > >for more information.
> > >
> > >What I would worry about in my implementation is adding a clause
> > >of 'init([]) -> error(badarg)' to be consequent in failures with
> > >the rest
> > >of the lists module, and not get a 'function_clause' error there
> > >when
> > >someone passes in an empty list.
> > >
> > >On 04/25, Yurii Rashkovskii wrote:
> > >>What about non-tail-recursiveness, though?
> > >>
> > >>
> > >>On Thu, Apr 25, 2013 at 8:54 AM, Fred Hebert <>
> > >>wrote:
> > >>
> > >>>Sounds to me like it would have been better implemented as
> > >>>something like:
> > >>>
> > >>>init([_]) -> [];
> > >>>init([H|T]) -> [H|init(T)].
> > >>>
> > >>>As this would avoid re-building the list twice, once on each
> > >>>reversal.
> > >>>
> > >>>Regards,
> > >>>Fred.
> > >>>
> > >>>
> > >>>On Thu, Apr 25, 2013 at 11:12 AM, Hans Svensson
> > >>><> wrote:
> > >>>
> > >>>>Hi,
> > >>>>
> > >>>>Yesterday I implemented, for the umpteenth time, the
> > >>>>init-function. (I
> > >>>>guess being taught Haskell at one point could be blamed partly
> > >>>>for the
> > >>>>coding style requiring this function...) It is a trivial
> > >>>>function that I
> > >>>>think should be part of the standard lists module. This patch
> > >>>>adds the
> > >>>>function, tests in lists_SUITE, and documentation of the
> > >>>>function.
> > >>>>
> > >>>>The implementation is trivial: reverse(tl(reverse(List))).
> > >>>>
> > >>>>If I've missed some religious reason for not having this
> > >>>>function feel
> > >>>>free to drop the patch ;-)
> > >>>>
> > >>>>Cheers,
> > >>>>Hans
> > >>>>
> > >>>>git fetch
> > >>>>git://github.com/hanssv/otp.**git<http://github.com/hanssv/otp.git>add_init_to_lists
> > >>>>
> > >>>>https://github.com/hanssv/otp/**compare/erlang:maint...add_**
> > >>>>init_to_lists<https://github.com/hanssv/otp/compare/erlang:maint...add_init_to_lists>
> > >>>>https://github.com/hanssv/otp/**compare/erlang:maint...add_**
> > >>>>init_to_lists.patch<https://github.com/hanssv/otp/compare/erlang:maint...add_init_to_lists.patch>
> > >>>>______________________________**_________________
> > >>>>erlang-patches mailing list
> > >>>>
> > >>>>http://erlang.org/mailman/**listinfo/erlang-patches<http://erlang.org/mailman/listinfo/erlang-patches>
> > >>>>
> > >>>
> > >>>_______________________________________________
> > >>>erlang-patches mailing list
> > >>>
> > >>>http://erlang.org/mailman/listinfo/erlang-patches
> > >>>
> > >>>
> > >>_______________________________________________
> > >>erlang-patches mailing list
> > >>
> > >>http://erlang.org/mailman/listinfo/erlang-patches
> > >_______________________________________________
> > >erlang-patches mailing list
> > >
> > >http://erlang.org/mailman/listinfo/erlang-patches
> > 
> _______________________________________________
> erlang-patches mailing list
> 
> http://erlang.org/mailman/listinfo/erlang-patches
> 


More information about the erlang-patches mailing list