I must be stupid

Ulf Wiger (AL/EAB) <>
Sat Jul 9 21:21:16 CEST 2005


This is true. The 'lines' contrib at http://jungerl.sourceforge.net
was an attempt to be able to handle very large data structures
with tuple semantics. It uses a tree of tuples, so it has O(logN)
complexity. It will never copy large tuples on update.

On the operation you're trying, nothing in Erlang will beat a list 
though.

Iterating over a tuple is not going to be faster than iterating
over a list, either(*). It's only when you require random access 
that the tuple starts to shine. If the ratio of random access
over updates is high enough, large tuples might be a viable option.

/Uffe

(*) At least not in BEAM. Don't know about HiPE.

> -----Original Message-----
> From: 
> [mailto:]On Behalf Of Håkan Stenholm
> Sent: den 9 juli 2005 21:11
> To: Joel Reymont
> Cc: Erlang Users' List
> Subject: Re: I must be stupid
> 
> 
> Joel Reymont wrote:
> 
> > ....
> >
> > creates just a second without HiPE whereas doing it like 
> this takes I  
> > don't know how much time (stopped after half an hour or so)
> >
> > populate(T, 0) ->
> >     T;
> >
> > populate(T, Size) ->
> >     populate(setelement(Size, T, Size), Size - 1).
> >
> > Is there a simple explanation?
> 
> Yes.
> 
> Updating a tuple _allways_ creates a new copy of the updated 
> tuple [1] - 
> as there is no destructive update.
> 
> Attaching a new element to the head of a list, only allocates 
> memory for 
> that element.
> 
> In other words a size N tuple in populate/2, will allocate memory for 
> N*N elements [2], rather than N elements, as in the 
> populate1/2 call, so 
> things will obviously go much slower.
> 
> [1]: a new copy of the internal pointer array used - the data 
> pointed to 
> will remain unchanged, only one or more tuple pointers will differ in 
> the new tuple.
> [2]: where N*(N-1) elements of the N*N elements, will later 
> be discarded 
> by the garbage collector.
> 
> >
> >     Thanks, Joel
> >
> > -- 
> > http://wagerlabs.com/uptick
> >
> >
> >
> >
> 
> 



More information about the erlang-questions mailing list