| Author |
Message |
< Erlang ~ Tuples vs Lists |
| dexterslab |
Posted: Fri Jul 06, 2007 10:38 am |
|
|
|
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 |
|
|
| Back to top |
|
| alexaandru |
Posted: Sat Jul 07, 2007 3:29 pm |
|
|
|
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 . 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}
Cheers,
Alex |
|
|
| Back to top |
|
| francesco |
Posted: Sat Jul 07, 2007 8:28 pm |
|
|
|
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 |
|
|
| Back to top |
|
| alexaandru |
Posted: Sun Jul 08, 2007 8:44 am |
|
|
|
Benchmarking Hobbist
Joined: 19 Jun 2007
Posts: 18
Location: Oradea, Romania
|
Hi ,
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 . 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 |
|
|
| Back to top |
|
| Ulf |
Posted: Mon Jul 09, 2007 5:13 pm |
|
|
|
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
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. |
|
|
| Back to top |
|
| alexaandru |
Posted: Mon Jul 09, 2007 10:14 pm |
|
|
|
Benchmarking Hobbist
Joined: 19 Jun 2007
Posts: 18
Location: Oradea, Romania
|
Hello ,
Ok, it did sound interesting so I tried it. Learned a good lesson too: never use lists:nth/2 unless..., well, just never
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 but performing a similar operation on tuples has very good results. Anyway, this was a fun little experiment
Cheers,
Alex |
|
|
| Back to top |
|
| dexterslab |
Posted: Mon Jul 16, 2007 10:05 am |
|
|
|
Joined: 06 Jul 2007
Posts: 5
|
Hi,
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".
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.
cheers,
james
P.S. A factor of 2 is hardly "kick ass"  |
|
|
| Back to top |
|
| alexaandru |
Posted: Mon Jul 16, 2007 10:46 am |
|
|
|
Benchmarking Hobbist
Joined: 19 Jun 2007
Posts: 18
Location: Oradea, Romania
|
Hi ,
You know what? You are absolutely right. n vs. 2n is nowhere near 'kick ass' 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
I still prefer tuples because of the nice curly brackets though
Cheers,
Alex
P.S. Can somebody change my 'tag' from "benchmarking guru" to maybe "benchmarking hobbist"? thank you
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  |
|
|
| Back to top |
|
| Ulf |
Posted: Mon Jul 16, 2007 1:27 pm |
|
|
|
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* . 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. |
|
|
| Back to top |
|
| arcatan |
Posted: Thu Jul 19, 2007 3:46 pm |
|
|
|
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. |
|
|
| Back to top |
|
| Ulf |
Posted: Thu Jul 19, 2007 5:21 pm |
|
|
|
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  |
|
|
| Back to top |
|
|
|
All times are GMT
|
|
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
|
|
|