Erlang Mailing Lists

Author Message

<  Erlang  ~  Tuples vs Lists

dexterslab
Posted: Fri Jul 06, 2007 10:38 am Reply with quote
Joined: 06 Jul 2007 Posts: 5
Hi,

How much more efficient are Tuples over Lists?
Especially for relatively small structures.
Being from a Prolog background I tend to prefer the flexibility and uniformity of code by using just lists and I wonder at what point the deficiency issues overtake the code writing ones.

cheers,
dexter
View user's profile Send private message
alexaandru
Posted: Sat Jul 07, 2007 3:29 pm Reply with quote
Benchmarking Hobbist Joined: 19 Jun 2007 Posts: 18 Location: Oradea, Romania
Since I'm just learning Erlang myself, this question made me curious. Here's how I tried to test this:
Code:
%%% tvsl.erl
%%% Tuple Vs. Lists
-module(tvsl).
-export([test/1, test_list/1, test_tuple/1]).

test_list(0) ->
    ok;
test_list(N) ->
    List = [45 * 89, 48 * 95],
    [_A, _B] = List,
    test_list(N-1).

test_tuple(0) ->
    ok;
test_tuple(N) ->
    Tuple = {45 * 89, 48 * 95},
    {_A, _B} = Tuple,
    test_tuple(N-1).

test(N) ->
    {timer:tc(tvsl,test_list,[N]),
     timer:tc(tvsl,test_tuple,[N])}.


I then tried it with various numbers of iterations:

Quote:
Erlang (BEAM) emulator version 5.5 [source] [async-threads:0] [hipe]

Eshell V5.5 (abort with ^G)
1> tvsl:test(10).
{{13,ok},{8,ok}}
2> tvsl:test(100).
{{25,ok},{12,ok}}
3> tvsl:test(1000).
{{136,ok},{50,ok}}
4> tvsl:test(10000).
{{1708,ok},{531,ok}}
5> tvsl:test(100000).
{{14758,ok},{4496,ok}}


So looks like tuples are winning every day of the week Wink. Then I also tried with HIPE:

Quote:
6> c(tvsl,[native,{hipe,[o3]}]).
{ok,tvsl}
7> tvsl:test(10).
{{12,ok},{8,ok}}
8> tvsl:test(100).
{{13,ok},{8,ok}}
9> tvsl:test(1000).
{{19,ok},{14,ok}}
10> tvsl:test(10000).
{{123,ok},{85,ok}}
11> tvsl:test(100000).
{{1109,ok},{813,ok}}


While the gap between them was drastically reduced, tuples still win. So I guess that {tuples, kicks_ass} Wink

Cheers,
Alex
View user's profile Send private message
francesco
Posted: Sat Jul 07, 2007 8:28 pm Reply with quote
User Joined: 07 Jul 2006 Posts: 249 Location: London
Hi Alex,

Good example. What you have measured is access time. Try doing the same with memory consumption and you should get similar results. Use lists when you have a variable number of Items and use records or tuples for a fixed number of items.

Francesco
View user's profile Send private message Visit poster's website
alexaandru
Posted: Sun Jul 08, 2007 8:44 am Reply with quote
Benchmarking Hobbist Joined: 19 Jun 2007 Posts: 18 Location: Oradea, Romania
Hi Smile,

francesco wrote:
Good example. What you have measured is access time. Try doing the same with memory consumption and you should get similar results.
Thanks Smile. Acually, it's not necessary to test memory consumption at all, thanks to the excellent docs that come with Erlang: http://erlang.org/doc/ -> Efficiency Guide -> Advanced -> Memory:
Quote:
List [size] = 1 words per element + the size of each element
Tuple [size] = 2 words + the size of each element
Have a lovely Sunday everyone,
Alex
View user's profile Send private message
Ulf
Posted: Mon Jul 09, 2007 5:13 pm Reply with quote
User Joined: 04 Sep 2006 Posts: 42 Location: Göteborg
I think a better test is to test different sizes of tuples and lists and see how the access time increase when the lists and tuples increase in size. That's where you spot the real difference between tuples and lists Smile

Maybe I hack something together when I get home, but I don't have any internet connection in my flat so if someone is faster please post it.
View user's profile Send private message
alexaandru
Posted: Mon Jul 09, 2007 10:14 pm Reply with quote
Benchmarking Hobbist Joined: 19 Jun 2007 Posts: 18 Location: Oradea, Romania
Hello Smile,

Ok, it did sound interesting so I tried it. Learned a good lesson too: never use lists:nth/2 unless..., well, just never Smile

Basically I tested here [H|T] vs. lists:nth/2 vs. element/2. Here we go:
Code:
%%% tvsl2.erl
%%% Tuples vs. Lists, take 2
-module(tvsl2).
-export([test/1, sum/1, sum2/1]).

%% a few handy functions
build(list,Max)  -> lists:seq(1,Max);
build(tuple,Max) -> list_to_tuple(build(list,Max)).

sum(Z) when is_list(Z) ->
    sum_of_list(Z, 1, length(Z), 0);
sum(Z) when is_tuple(Z) ->
    sum_of_tuple(Z, 1, size(Z), 0);
sum(_) ->
    error.

%% a dead ugly way to sum up a list,
%% but similar to the way we sum up the tuple below
sum_of_list(_, Max, Max, Sum)  -> Sum + Max;
sum_of_list(Z, Curr, Max, Sum) ->
    sum_of_list(Z, Curr + 1, Max, Sum + lists:nth(Curr, Z)).

%% is there a better way to sum up (elements of) a tuple,
%% ( besides lists:sum(tuple_to_list/1) ) ?
sum_of_tuple(_, Max, Max, Sum)  -> Sum + Max;
sum_of_tuple(Z, Curr, Max, Sum) ->
    sum_of_tuple(Z, Curr + 1, Max, Sum + element(Curr, Z)).

%% a nice way to sum up a list (besides lists:sum)
sum2([H|T]) ->
    sum2(T, H).

sum2([H|T], Sum) ->
    sum2(T, H + Sum);
sum2([], Sum) ->
    Sum.

test(N) ->
    AList = build(list,N),
    ATuple = build(tuple,N),
    Control =  N * (N + 1) div 2,
    {Time1, Control} = timer:tc(tvsl2,sum2,[AList]),
    {Time2, Control} = timer:tc(tvsl2,sum,[AList]),
    {Time3, Control} = timer:tc(tvsl2,sum,[ATuple]),
    {{sum_list_ht, Time1}, {sum_list_nth, Time2}, {sum_tuple, Time3}}.

and here are the results I got:
Quote:
Erlang (BEAM) emulator version 5.5 [source] [async-threads:0] [hipe]

Eshell V5.5 (abort with ^G)
1> c(tvsl2).
{ok,tvsl2}
2> tvsl2:test(10).
{{sum_list_ht,11},{sum_list_nth,16},{sum_tuple,10}}
3> tvsl2:test(100).
{{sum_list_ht,17},{sum_list_nth,317},{sum_tuple,26}}
4> tvsl2:test(1000).
{{sum_list_ht,97},{sum_list_nth,41980},{sum_tuple,217}}
5> tvsl2:test(10000).
{{sum_list_ht,948},{sum_list_nth,3984675},{sum_tuple,2087}}

So looks like using a (big) list and lists:nth is not the smartest thing to do Smile but performing a similar operation on tuples has very good results. Anyway, this was a fun little experiment Smile

Cheers,
Alex
View user's profile Send private message
dexterslab
Posted: Mon Jul 16, 2007 10:05 am Reply with quote
Joined: 06 Jul 2007 Posts: 5
Hi, Smile

Considering;
List [size] = 1 words per element + the size of each element
Tuple [size] = 2 words + the size of each element

It seems that their time complexity is roughly n and 2n respectively (also supported by the experimental data). This is not as a dramatic of a difference as if it was, let's say; exponential n^2, since "for sufficiently large n: logn < n < nlogn < n^2 < n^3 < 2^n". In fact they are both of complexity class O(n) as constant factors are "small peanuts". Smile
A factor of 2 might be crucial for some applications but with available processing power doubling ever so often it begs the question whether such efficiency gain ought to overtake concerns of generalised code, that is easier to produce, maintain and extend.
Let's not forget that processing power is getting cheaper, man hours don't!
So I still believe that it is a discretionary matter depending on the circumstances, as there are other kinds of efficiency too other the computational one. Cool

cheers,
james

P.S. A factor of 2 is hardly "kick ass" Wink
View user's profile Send private message
alexaandru
Posted: Mon Jul 16, 2007 10:46 am Reply with quote
Benchmarking Hobbist Joined: 19 Jun 2007 Posts: 18 Location: Oradea, Romania
Hi Smile,

You know what? You are absolutely right. n vs. 2n is nowhere near 'kick ass' Smile Learned it the hard way, while struggling with this week's Ruby Quiz (http://rubyquiz.com/quiz131.html). It just showed me how little I know about O(*) and the likes... so I finally took the time to grasp this, and all of the sudden, the difference between lists and tuples seems a lot smaller than the difference between a naive and smart algorythm Smile

I still prefer tuples because of the nice curly brackets though Very Happy

Cheers,
Alex

P.S. Can somebody change my 'tag' from "benchmarking guru" to maybe "benchmarking hobbist"? thank you Smile
There's a long way to 'guru', and in spite of the 10 years of coding practice, looks like I'm at the beginning of the journey. But that's cool. I very much enjoyed getting here, I'm sure I'll enjoy the rest of it as well Smile
View user's profile Send private message
Ulf
Posted: Mon Jul 16, 2007 1:27 pm Reply with quote
User Joined: 04 Sep 2006 Posts: 42 Location: Göteborg
How would you write more general code using lists then tuples in a case where a tuple is good, when you have a fixed number of elements? Example please.

And a factor of N*2 is much if it is totally unnecessary to have N*2

Also, these test ain't the best to show the difference between tuples and list because it's not often you recurse through the elements in a tuple, but rather access a specific field, and there you have a O(1) for tuples and O(n) for lists. (See what happens when you use nth).

It's good for one thing though, showing that even if you only pass through the list one time, the list is still slower then the tuple.

So if you every time want to have the fourth field, this is N in a tuple and N*4 using a list (or rather N*Cool. Now suddenly the list is eight times slower, and many systems where Erlang is used you pass a lot of messages and a lot of stuff is happening, you don't want your code eight times slower just because you want to use lists instead.

And somewhere else you want to access the fifth or sixths element, and now suddenly the lists is 10 and 12 times slower.

When you have a dynamic amount of elements, use lists, but if it is a fixed number of fields, use a tuple (or even better, records which will translate to tuples when compiling).

Sorry, but there is no excuse for not using tuples where a tuple should be used.
View user's profile Send private message
arcatan
Posted: Thu Jul 19, 2007 3:46 pm Reply with quote
Joined: 19 Jul 2007 Posts: 2 Location: Finland
I think there's also a semantic difference. A tuple looks like a list syntactically, but semantically it's more like struct in C. If you want to represent list-like data, use lists. If your data fits into predefined fields, use tuples. In the latter case you might want to use records, of course.
View user's profile Send private message
Ulf
Posted: Thu Jul 19, 2007 5:21 pm Reply with quote
User Joined: 04 Sep 2006 Posts: 42 Location: Göteborg
Yes, you are absolutely right arcatan.

That's what I tried to say as well, not as elegant as you did though Wink
View user's profile Send private message

Display posts from previous:  

All times are GMT
Page 1 of 1
This forum is locked: you cannot post, reply to, or edit topics.

Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum