[erlang-questions] Coming Back (maybe improving lists:reverse/1)

Ivan Carmenates Garcia <>
Thu Oct 8 00:49:56 CEST 2015


Nice.

 

So in order of balance between memory and speed is the best ways as it is?. Okay, sounds good to me, also Joe was saying something that I like some kind about algorithms optimizations, because I am a little bit hard about it, but for example in this little framework I am doing for myself and the community if they like of course there are parts in which maybe I think some algorithms could be better but if it works and it does quite well, i.e. if in my computer with one millions of iterations in one process this is important because each user will have one process for its own, it take 21 seconds to perform and in a core i3 with 2 GB of single channel memory it take 9 seconds, then in a real server with 64 cores and super memory it will take none milliseconds to perform so, in the future machines will be better each time and maybe we don’t have to be so extreme about performance.

That gives me a little more of hope lol.

 

Best regards,

Ivan (son of Gilberio)

 

From: Erik Søe Sørensen [mailto:] 
Sent: Wednesday, October 7, 2015 3:21 PM
To: Ivan Carmenates Garcia
Subject: Re: [erlang-questions] Coming Back (maybe improving lists:reverse/1)

 

Hi Ivan -

 

Erlang is using singly linked lists for obvious(?) reasons:

If you have a list L, then you can both prepend an element X and prepend an element Y in constant time:

  [X|L], [Y|L]

getting two new lists.

 

This approach is compact, a standard approach for functional languages, and performs quite well.

Let's do the math - the cost of building a list of length N using both approaches:

- Using doubly linked lists:

  Allocate and populate 3*N memory words. The end result uses 3*N words.

- Using singly linked lists:

  Allocate and populate 2*N memory words, then doing it again - a total cost of 4*N. The end result uses 2*N words.

(I here assume that the list objects have no header; afaik this is true in the Erlang VM.)

 

So using doubly linked lists - the semantic difference aside - costs only about 25% less, even using your approach, while using 50% more memory for the end result.

And that 25% figure is the best case - what also needs to be taken into consideration is that performance would suffer in other places, in those operations where that extra bit of yours would have to be tested.

 

Believe it or not, these simple cons lists are hard to beat; that's why they are still around after more than 50 years. :-)

 

/Erik

 

 

2015-10-07 20:39 GMT+02:00 Ivan Carmenates Garcia < <mailto:> >:

I fellows, I was down for a while, connection payment problems, lol. So I am back, and I have a few ideas I would like to share. Also my cowboy extension framework is marching very nice, I had dedicate some time to it in this offline days.

 

My thoughts, when I was doing some algorithms for the framework, I found some questions I would like to share because for example, when working with lists module, and doing some recursive functions, it is usually a problem that we need to do lists:reverse at the end of the algorism to get the data in the right order.

 

So I can imagine Erlang implement lists using double linked lists for obvious purposes, I haven’t see the source code so I am just guessing here, so for example when doing length you must spend one O(N) to transverse the list, one O(1) for each element to count them and one final O(1) to return the list. So when using lists:reverse/1 it takes four times what lengths does, so I can play guess, and just that, that you are using indeed a double linked list so you spend one O(n) to transverse the list, three O(1), which is an O(1) in total of course I am just counting the operations as well, to swap the preview and next pointers for each node so the list will be in the reverse order and other O(1) to return the new list which is a pointer of course to the old list just reversed.

 

So guessing that it is what you do, how bad could be instead of doing that just make list have one bit more of size in memory by saying the order it have. So when you use lists:reverse/1 is just changing that bit to true and when iterating the list instead of using the next function use preview function and viseversa. The problem will be that you must spend one more O(1) for each element when iterating to choose what function is executed depending on the reverse bit. I just did a little simple erlang example to prove my point, of course it is just for demonstration purposes not for real implementation.   

 

-module(mylists).

 

-compile(export_all).

 

-type mylists_ref() :: erlang:ref().

 

-spec new(list()) -> mylists_ref().

new(List)->

    Ref = erlang:make_ref(),

    erlang:put({Ref, first}, erlang:hd(List)),

    store_list(List, Ref),

    Ref.

 

store_list([A], Ref) ->

    erlang:put({Ref, final}, A);

store_list([A,B | _] = [_ | Rest], Ref) ->

    erlang:put({Ref, A, next}, B),

    erlang:put({Ref, B, preview}, A),

    store_list(Rest, Ref).

       

-spec next(mylists_ref()) -> Element :: any().

next(MyListRef) ->

    case erlang:get({MyListRef, cursor}) of

        undefined ->

            Element =

                case erlang:get({MyListRef, reversed}) of

                    true ->

                        erlang:get({MyListRef, final});

                    undefined ->

                        erlang:get({MyListRef, first})

                end,

                erlang:put({MyListRef, cursor}, Element),

                Element;

        Element ->

            NewElement =

                case erlang:get({MyListRef, reversed}) of

                    true ->

                        erlang:get({MyListRef, Element, preview});

                    undefined ->

                        erlang:get({MyListRef, Element, next})

                end,

                case NewElement of

                    undefined ->

                        undefined;

                    Next ->

                        erlang:put({MyListRef, cursor}, Next),

                        Next

                end

        end.

 

reset(MyListRef) ->

    erlang:erase({MyListRef, cursor}).

 

 

-spec reverse(mylists_ref()) -> MyReverseListRef :: mylists_ref().

reverse(MyListRef) -> 

    reset(MyListRef),

    case erlang:get({MyListRef, reversed}) of

        undefined ->

            erlang:put({MyListRef, reversed}, true);

        true ->

            erlang:erase({MyListRef, reversed})

    end,

    ok.

 

test() ->

    MyListRef = mylists:new([1,2,3,4]),

    FirstElem = mylists:next(MyListRef),

    mylists:reverse(MyListRef),

    LastElem = mylists:next(MyListRef),

    {FirstElem, LastElem}.

 

Cheers,

Ivan (son of Gilberio).


_______________________________________________
erlang-questions mailing list
 <mailto:> 
http://erlang.org/mailman/listinfo/erlang-questions

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20151007/c208c866/attachment.html>


More information about the erlang-questions mailing list