Arrays vs tuples / lists

Ulf Wiger (AL/EAB) <>
Tue May 18 14:11:57 CEST 2004


I'm inclined to agree with Erik.
BTW, I enclosed the benchmark program, so feel free to 
modify it and re-run it at will.  ;-)

/Uffe

> -----Original Message-----
> From: 
> [mailto:]On Behalf Of Erik Stenman
> Sent: den 18 maj 2004 14:10
> To: 
> Cc: 'Thomas Johnsson'; 'Ulf Wiger'
> Subject: RE: Arrays vs tuples / lists
> 
> 
> Actually the pattern matching is slightly faster, 
> because it is inline expanded while the call to hd
> require a function call (in the current implementation).
> 
>    He states boldly without actually benchmariking on 
>    the latest implementation.
>  But it seems to be true in  V5.2.3.3.
> 
> Erik 
> 
> > -----Original Message-----
> > From:  
> > [mailto:] On Behalf Of 
> > Thomas Johnsson
> > Sent: Tuesday,18 May, 2004 13:06
> > To: Ulf Wiger
> > Cc: 
> > Subject: Re: Arrays vs tuples / lists
> > 
> > Hi,
> > thanks for doing the benchmarking for me.
> > One note: the ets lookup is done with
> >    [X] = ets:lookup(Tab, Pos),
> > which involves a pattern matching on the lhs, that has a cost.
> > Could you re-run it on the same box, with
> >     X = head(ets:lookup(Tab, Pos)),
> > 
> > or some such? Head must do a similar check, but presumably it 
> > is cheaper.
> > 
> > -- Thomas
> > 
> > >
> > > Ok, that was perhaps a bit too terse, but I was sitting with an 
> > > impatient baby in my lap (she hasn't quite grasped the beauty of 
> > > Erlang yet, but I'm working on it.)
> > >
> > > test:tup(Iterations, DataSize) runs a tight loop accessing 
> > objects via 
> > > element/2 in a tuple with 10,000 elements.
> > >
> > > test:ets/2 does the same thing, but with an ets set 
> > containing 10,000 
> > > objects.
> > >
> > > Due to the very limited precision of erlang:now() on my 
> > windows box, I 
> > > ran 1,000 iterations where I accessed all 10,000 objects each 
> > > iterations.
> > >
> > > As you can see, tuple accesses are independent of data 
> size, as the 
> > > data already resides on the process heap. With ets, there 
> is always 
> > > copying, so as the object size increases, so does the cost of a 
> > > lookup.
> > >
> > > Even with the smallest type of payload (an atom), element/2 
> > is nearly 
> > > an order of magnitude faster than ets:lookup/2.
> > >
> > > Note, this is only read access. As soon as you start using
> > > setelement/3 on a tuple of size 10,000, the picture shifts rather 
> > > dramatically.
> > >
> > > /Uffe
> > >
> > >
> > > On Mon, 17 May 2004 21:14:11 +0200, Ulf Wiger 
> > <> wrote:
> > >
> > >> On Mon, 17 May 2004 18:13:01 +0200 (CEST), Thomas Johnsson 
> > >> <> wrote:
> > >>
> > >>>>
> > >>>> As long as you only look up stuff in large tuples, 
> > access is very 
> > >>>> fast and O(1).
> > >>>
> > >>> Splendid! Presumably it is faster than an ets table 
> > lookup with an 
> > >>> integer as key; by how much, roughly?
> > >>>
> > >>> -- Thomas
> > >>>
> > >>
> > >> Well, it's reasonably easy to measure (at least on 
> UNIX...) (I've 
> > >> enclosed a small test program, and a test run on a 3GHz XP box.)
> > >>
> > >> /Uffe
> > >>
> > >> Erlang (BEAM) emulator version 5.3 [threads:0]
> > >>
> > >> Eshell V5.3  (abort with ^G)
> > >> 1> cd("c:/cygwin/home/foo/erl").
> > >> c:/cygwin/home/foo/erl
> > >> ok
> > >> 2> c(test).
> > >> {ok,test}
> > >> 3> test:tup(1000,small).
> > >> {625000,ok}
> > >> 4> test:tup(1000,medium).
> > >> {609000,ok}
> > >> 5> test:tup(1000,big).
> > >> {609000,ok}
> > >> 6> test:ets(1000,small).
> > >> {4156000,ok}
> > >> 7> test:ets(1000,medium).
> > >> {8718000,ok}
> > >> 8> test:ets(1000,big).
> > >> {138594000,ok}
> > >> 9> test:empty(1000).
> > >> {531000,ok}
> > >> 10>
> > >>
> > >
> > >
> > >
> > > --
> > > Ulf Wiger
> > >
> > >
> > 
> > 
> 



More information about the erlang-questions mailing list