I need an index-based access to elements of a fixed-size array-like
structure. Number of elements is expected to be about several
thousands.
What would be more efficient: to create an array (using the "array"
module) or to build a huge tuple and use erlang:element?
Thanks.
PS I suspect the latter, but how does erlang:element scale on tuples
of such size?
--
Dimitry Golubovsky
Anywhere on the Web
Please share results when you do!
On Aug 25, 2008, at 3:40 PM, Dimitry Golubovsky wrote:
> What would be more efficient: to create an array (using the "array"
> module) or to build a huge tuple and use erlang:element?
> [...]
> PS I suspect the latter, but how does erlang:element scale on tuples
> of such size?
If nobody did it before, then I'll do (not earlier than tonight anyway ;)
I just believe someone already came across such a common task.
Thank you.
On 8/25/08, Joel Reymont <joe...@gmail.com> wrote:
> Why not profile and find out?
>
> Please share results when you do!
--
> Joel,
>
> If nobody did it before, then I'll do (not earlier than tonight
> anyway ;)
Here, check out the performance of fixed-size vs extensible array set
op.
Astounding!
---
Mac OSX Leopard 10.5.4
Mac Pro 2x2.8Ghz Quad-Core Intel Xeon, 14Gb 800Mhz DDR2 FB-DIMM
Erlang (BEAM) emulator version 5.6.3 [source] [64-bit] [smp:8] [async-
threads:0] [kernel-poll:false]
%% 10K elements
14> arr:test().
Fixed-size array: get: 1256ns, set: 6667ns
Extensible array: get: 1255ns, set: 22ns
Tuple: get: 659ns, set: 6ns
ok
%% 1 million
15> arr:test(1000000).
Fixed-size array: get: 121881ns, set: 777067ns
Extensible array: get: 120026ns, set: 35ns
Tuple: get: 66288ns, set: 40ns
ok
---
-module(arr).
-compile([export_all]).
data1(N) ->
%% size implies fixed-size array
%% but lets be explicit
array:new([{size, N}, {default, 0}, {fixed, true}]).
data2(N) ->
%% extensible array
array:new([{size, N}, {default, 0}, {fixed, false}]).
data3(N) ->
erlang:make_tuple(N, 0).
array_set(Array, I, Value) ->
%% array indexing starts at 0
array:set(I - 1, Value, Array).
tuple_set(Tuple, I, Value) ->
%% tuple indexing starts at 1
setelement(I, Tuple, Value).
array_get(Array, I) ->
array:get(I - 1, Array).
tuple_get(Tuple, I) ->
element(I, Tuple).
get(_, _, 0) ->
ok;
get(Fun, Data, N) ->
Fun(Data, N),
get(Fun, Data, N - 1).
set(_, _, 0) ->
ok;
set(Fun, Data, N) ->
Data1 = Fun(Data, N, N),
set(Fun, Data1, N - 1).
test() ->
test(10000).
test(N) ->
%% fixed-size array
{G1, _} = timer:tc(arr, get, [{arr, array_get}, data1(N), N]),
{S1, _} = timer:tc(arr, set, [{arr, array_set}, data1(N), N]),
%% extensible array
{G2, _} = timer:tc(arr, get, [{arr, array_get}, data2(N), N]),
{S2, _} = timer:tc(arr, set, [{arr, array_get}, data2(N), N]),
%% tuple
{G3, _} = timer:tc(arr, get, [{arr, tuple_get}, data3(N), N]),
{S3, _} = timer:tc(arr, set, [{arr, tuple_get}, data3(N), N]),
%% results
io:format("Fixed-size array: get: ~8wns, set: ~8wns~n", [G1 , S1]),
io:format("Extensible array: get: ~8wns, set: ~8wns~n", [G2 , S2]),
io:format("Tuple: get: ~8wns, set: ~8wns~n", [G3 , S3]),
ok.
http://www.wagerlabs.com/blog/2008/08/optimizing-erlang-a-death-match-of-arrays-vs-tuples.html#more
One of the differences is that I'm using the populated data structure
for get operations instead of an empty one.
Times are in microseconds as Serge Aleynikov kindly pointed out.
Thanks, Joel
Just wondering why set operations are so much faster (except for fixed
size arrays)?
The result of applying *set operations is not consumed, is it? What if
you try to do anything with it (after it is returned from timer:tc)?
Could this be some internal laziness, so only function application
thunks are indeed formed, but since results are never consumed, it
does not expand any further? Or is it some optimization of the same
kind, that the compiler sees unconsumed result, and does not really
compile anything? Or even something at JIT level?
Or am I missing anything ? ;)
Thanks.
On 8/25/08, Joel Reymont <joe...@gmail.com> wrote:
>
> 14> arr:test().
> Fixed-size array: get: 1256ns, set: 6667ns
> Extensible array: get: 1255ns, set: 22ns
> Tuple: get: 659ns, set: 6ns
> ok
>
> %% 1 million
>
> 15> arr:test(1000000).
> Fixed-size array: get: 121881ns, set: 777067ns
> Extensible array: get: 120026ns, set: 35ns
> Tuple: get: 66288ns, set: 40ns
> ok
> The result of applying *set operations is not consumed, is it? What if
> you try to do anything with it (after it is returned from timer:tc)?
The result of a set operation _is_ consumed on every iteration, it's
used to prime the subsequent one.
The result of every get operation is thrown away, though!
I updated the blog post to state that the times are in microseconds.
%% 10,000 elements
11> arr:test().
Fixed-size array: get: 3364mc, set: 6941mc
Extensible array: get: 1mc, set: 23mc
Tuple: get: 625mc, set: 209628mc
Tree: get: 47700mc, set: 4305mc
ok
%% 100,000 elements
4> arr:test(100000).
Fixed-size array: get: 39017mc, set: 73636mc
Extensible array: get: 2mc, set: 36mc
Tuple: get: 6290mc, set: 24495846mc
Tree: get: 619615mc, set: 52691mc
ok
[1] http://www.wagerlabs.com/blog/2008/08/optimizing-erlang-a-death-match-of-arrays-vs-tuples.html#more
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
> You have typo in your code. Set on tuple can't be as fast as your
> measure :)
> You do get on Extensible array and tuple instead of set and you call
> this
> inside set cycle which remove data structure away.
I updated my blog post to remove the typo and re-ran the benchmarks.
Interesting benchmark. I tried compiling the array API natively and
got pretty decent improvements, especially for the array set
operations (approx 40% better). .
Colm
If it's the case of write-once, read-many, you could prepare the
data in a list, do list_to_tuple, and then use the tuple for reading.
But I'd only do that myself as a last resort, to maximize speed.
> PS I suspect the latter, but how does erlang:element scale on tuples
> of such size?
Just reading elements using erlang:element(N, Tuple) is as fast as
it can possibly get - simply a pointer addition and a load. And tuples
can be pretty huge. Try e.g. erlang:make_tuple(10000000,0)) - that's
10 million elements. But updating big tuples (copying N words) is much
too inefficient; hence the array module, which tries to provide a good
balance between read and write access times.
/Richard