| Author |
Message |
|
| Guest |
 Posted: Thu Sep 07, 2006 8:00 pm |
 |
|
|
Guest
|
I am trying to implement a 2d map in erlang where
dynamic elements will be traversing it via reference.
I have no other way to get the "locations" into memory
other than using a large array, explicitly for
reading.
The bottom "terrain" layer is what the static array
represents. Putting this in memory consists of reading
from a text file in the example format:
{ % map tuple start
{ % row start
{ID,{a1,a2}}, % column
...
}, % row end
...
} % map tuple end
Question: read it into memory as a large tuple or
list?
I have heard of a "binary" format in erlang that is
used for this kind of read-without-copy on large
amounts of data. I assume that I should read out a map
export then convert it to binary, then read it
cheaply. I haven't located a good usage tutorial for
the binary format and could use a guide if this is the
preferred method.
What do I do when I want to operate on a similarly
sized dynamic layer that I want to read/write to?
Tuple or List or Binary or something else?
The idea of each "location" being a process might be a
good idea for dynamic layers, but not for the base
terrain layer, which has no behaviors IMO.
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Thu Sep 07, 2006 9:00 pm |
|
|
|
Guest
|
On 07/09/06, Jeff Crane <jefcrane@yahoo.com (jefcrane@yahoo.com)> wrote:Quote: I am trying to implement a 2d map in erlang where
dynamic elements will be traversing it via reference.
I have no other way to get the "locations" into memory
other than using a large array, explicitly for
reading.
Umm...I don't quite understand your data structure but have you looked at ets? It is for storing tuples. You can then lookup rows/cells using either a key or a match pattern.
http://www.erlang.org/doc/doc-5.5.1/lib/stdlib-1.14.1/doc/html/ets.html
Quote: I have heard of a "binary" format in erlang that is
used for this kind of read-without-copy on large
amounts of data.
Have you seen this?
http://www.erlang.org/doc/doc-5.5.1/doc/programming_examples/bit_syntax.html#4
Binaries larger than 64 bytes (I think) are referenced to and not copied on read. Binaries smaller than 64 bytes are copied when exchanged between processes.
cheers
Chandru
Post recived from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Thu Sep 07, 2006 10:14 pm |
|
|
|
Guest
|
Jeff Crane wrote:
>I am trying to implement a 2d map in erlang where
>dynamic elements will be traversing it via reference.
>I have no other way to get the "locations" into memory
>other than using a large array, explicitly for
>reading.
>
>The bottom "terrain" layer is what the static array
>represents. Putting this in memory consists of reading
>from a text file in the example format:
>{ % map tuple start
> { % row start
> {ID,{a1,a2}}, % column
> ...
> }, % row end
> ...
>} % map tuple end
>
>Question: read it into memory as a large tuple or
>list?
>
>I have heard of a "binary" format in erlang that is
>used for this kind of read-without-copy on large
>amounts of data. I assume that I should read out a map
>export then convert it to binary, then read it
>cheaply. I haven't located a good usage tutorial for
>the binary format and could use a guide if this is the
>preferred method.
>
>
There are a number of fairly obvious choices to implement a 2D array (to
for example be able to do efficient random access):
* use a tuple of terms - this is probably the fastest way[1] to do
random access (based on a positional index) in a fixed size array.
O(1) read, O(N) update cost.
1: tuple reads have the same speed as reading from the head of a list.
* use a binary - similar to using a tuple, but may be somewhat more
complicated to access, but has the benefit to be able to store small
elements (< 1 word length) compactly.
Building new binaries (doing updates) may be costly.
* ets tables have reasonably fast reads and writes and may also be a
good way to model spares arrays. The drawback (mainly for fast reads) is
that ets reads are several times slower than tuple accesses.
Note: ets tables do destructive updates which introduce non-functional
state concerns - the same ets table can't be passed to two functions,
both which write in the ets tables without introducing execution
dependencies between the two, they may for example break if run in parallel.
Note: ets tables are only visible on a single erlang node - this may
introduce additional work if they need to be distribute on several
machines. Some of the above issues can be fixed by using mnesia or
another transactional database.
* various kinds of trees (e.g. binary ones) can be used - but read /
write times for small trees are not noticeably better than ets tables
and probably worse when the tree grows large - due to the log(N) factor
(ets is O(1)).
Note: trees suffer none of the issues mentioned in the notes for ets
tables - this also makes it very simple to implement an undo function,
simply keep a number of old trees around, only log(N) elements will
differ between each write update, so storage will be = LevesOfUndo * log(N).
I would therefore recommend using tuples or binaries for fixed sized
read only arrays, and trees or ets tables for more dynamic "arrays",
depending on your needs and your likelihood of wanting to turn the ets
table into a real database like mnesia.
>What do I do when I want to operate on a similarly
>sized dynamic layer that I want to read/write to?
>
>Tuple or List or Binary or something else?
>
>The idea of each "location" being a process might be a
>good idea for dynamic layers, but not for the base
>terrain layer, which has no behaviors IMO.
>
>
>
>
>
>__________________________________________________
>Do You Yahoo!?
>Tired of spam? Yahoo! Mail has the best spam protection around
>http://mail.yahoo.com
>_______________________________________________
>erlang-questions mailing list
>erlang-questions@erlang.org
>http://www.erlang.org/mailman/listinfo/erlang-questions
>
>
>
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Sep 11, 2006 6:00 am |
|
|
|
Guest
|
Jeff Crane wrote:
> What do I do when I want to operate on a similarly
> sized dynamic layer that I want to read/write to?
A while ago, Dan Gudmundsson posted an array datatype implementation
to the list. Since then, I and Dan have been rewriting it with the
intention of eventually making it a standard library component. Here
is a preview; the interface should be pretty stable now:
http://user.it.uu.se/~richardc/array/
It still uses a tree structure, but since it uses indices from 0 to N
instead of arbitrary keys, it can be quite a lot more efficient in both
time and space than gb_trees or dicts.
/Richard
PS. I tried to post this to the list with the code as an attachment
just before the weekend, but apparently, it was eaten by a grue.
--
"Having users is like optimization: the wise course is to delay it."
-- Paul Graham
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| uffe |
| Posted: Mon Sep 11, 2006 7:38 am |
|
|
|
User
Joined: 02 Mar 2005
Posts: 365
Location: Sweden
|
Den 2006-09-11 07:58:04 skrev Richard Carlsson <richardc@it.uu.se>:
> A while ago, Dan Gudmundsson posted an array datatype implementation
> to the list. Since then, I and Dan have been rewriting it with the
> intention of eventually making it a standard library component. Here
> is a preview; the interface should be pretty stable now:
>
> http://user.it.uu.se/~richardc/array/
>
> It still uses a tree structure, but since it uses indices from 0 to N
> instead of arbitrary keys, it can be quite a lot more efficient in both
> time and space than gb_trees or dicts.
This looks awfully similar to the 'lines' module in jungerl.
Could you describe the main differences?
BR,
Ulf W
--
Ulf Wiger
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
  
|
| Heinrich |
| Posted: Mon Sep 11, 2006 7:47 am |
|
|
|
Joined: 11 Aug 2006
Posts: 4
Location: Midrand, South Africa
|
I tinkered around with a similar design a while ago.
In the end I built some tests to compare different approaches. If you
only need to read elements, you can probably get away with a tuple of
tuples, or a large binary with some indexing logic. If you need to do
writes too things change drastically.
I wrote a binary based read only test and an ets based one. The binary
outperformed the ets table by a factor of 3. However when writes were
done, the ets solution outperformed the binary one by a factor of about
10 and also used less memory.
I did not test a binary vs tuple solution tho. The drawback of the
binary solution is that you have to know the size of your data element
in bytes for the logic to work.
Consider this: If you use a tuple based solution you have some options
on how you partition it.
Say you have a 10x10 array. You could store it as a single tuple with
100 elements and use I=(Row*10+Col) to get the correct index for
element(I,Map).
You could also make it a tuple of 10 row tuples so that the access
becomes element(Col,element(Row,Map))
But why stop there, why not break it up further into regions for a
quad-tree type structure?
If you break it up fine enough you will end up with something that looks
almost like an ets table where each element has the form {{X,Y},Data}.
So in the end ets will probably give you the most bang for your buck.
-]-[
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Sep 11, 2006 8:20 am |
|
|
|
Guest
|
Ulf Wiger wrote:
> This looks awfully similar to the 'lines' module in jungerl.
> Could you describe the main differences?
Noticeably faster, according to Dan's measurements.
(I haven't looked at the code for the lines module myself.)
/Richard
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Sep 11, 2006 8:57 am |
|
|
|
Guest
|
Heinrich Venter wrote:
> If you need to do writes too things change drastically.
Of course - and the whole point of the array.erl implementation
is to support writes (and have a good balance between writes and
lookups). For lookup only, you probably can't beat a big, flat
tuple, but that does not scale when it comes to writing. We want
to have reasonably efficient arrays of many millons of elements.
> However when writes were
> done, the ets solution outperformed the binary one by a factor of about
> 10 and also used less memory.
Well, binaries are not really a candidate for random-access writing,
(even when you have fixed, known sizes for the elements), since it
involves an awful amount of copying.
> Consider this: If you use a tuple based solution you have some options
> on how you partition it.
> Say you have a 10x10 array. You could store it as a single tuple with
> 100 elements and use I=(Row*10+Col) to get the correct index for
> element(I,Map).
> You could also make it a tuple of 10 row tuples so that the access
> becomes element(Col,element(Row,Map))
> But why stop there, why not break it up further into regions for a
> quad-tree type structure?
> If you break it up fine enough you will end up with something that looks
> almost like an ets table where each element has the form {{X,Y},Data}.
> So in the end ets will probably give you the most bang for your buck.
First, we do not try to optimize for extremely sparse arrays (in which
case quad trees or plain binary trees would perform well - and we
already have decent binary trees), but for fairly densely populated
ones. Second, in order to get fast operations, you have to have as few
and as cheap tests as possible, and a regular layout like the one we use
(nested N-tuples, where N=10 has been measured to be a good choice)
simply gives us the fastest code - about 2-3 times faster than gb_trees.
(On the other hand, you can only use nonnegative integers as keys!)
Ets tables would not be faster if they were implemented in Erlang,
instead of in C, and functional arrays have a couple of important
properties that ets tables do not have:
- No copying when reading/writing data. Ets tables always copy
the data in and out of the table (except for large binaries),
and is thus not suitable for storing things like large lists
or tree structures.
- They are _functional_, not destructive, so they can be used in
places where you want to keep older versions of the array around
(e.g., in an "undo"-list). With ets tables, you overwrite the old
version of the data. Also, since the arrays are tree-based, keeping
several "copies" around does not cost a lot space-wise.
/Richard
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| uwiger |
| Posted: Mon Sep 11, 2006 11:03 am |
|
|
|
User
Joined: 03 Jul 2006
Posts: 604
Location: Sweden
|
Richard Carlsson wrote:
>
> Ulf Wiger wrote:
> > This looks awfully similar to the 'lines' module in jungerl.
> > Could you describe the main differences?
>
> Noticeably faster, according to Dan's measurements.
> (I haven't looked at the code for the lines module myself.)
Hmm, yes, a 'replace' takes about 15 us in lines.erl compared
to ca 8 us in array.erl, and for 'get', the numbers were 7/13.
Interestingly, 'from_list' (measured on a list of 1000 elements)
was noticeably faster in lines.erl than in array.erl. I think
this is because I have an optimized function for creating a large
tree, rather than growing the tree as I go. The figures were
238 us for 'lines' and 626 us for 'array'.
But here's the main difference (now that I've spend more than
15 seconds looking at array.erl): The 'lines' module supports
insert() and delete(), whereas array.erl doesn't.
While it would have been possible to optimize lines.erl
slightly for nth() and replace() (not quite reaching the
speed of array.erl, but closing the gap somewhat) by using
tuples instead of lists as leafs, this would make append(),
insert() and delete() quite less appealing.
BR,
Ulf W
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| uwiger |
| Posted: Mon Sep 11, 2006 11:44 am |
|
|
|
User
Joined: 03 Jul 2006
Posts: 604
Location: Sweden
|
I wrote:
> Hmm, yes, a 'replace' takes about 15 us in lines.erl compared
> to ca 8 us in array.erl, and for 'get', the numbers were 7/13.
Sorry, that should have been 13/7 (i.e. in favour of array.erl)
Sorry 'bout that.
BR,
Ulf W
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Sep 11, 2006 11:47 am |
|
|
|
Guest
|
Richard Carlsson wrote:
> Ets tables would not be faster if they were implemented in Erlang,
> instead of in C
>
Could you say have you seen an implementation of arrays using Erlang
ports? If yes, how they fast?
Best regards,
Nick.
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Sep 11, 2006 12:24 pm |
|
|
|
Guest
|
Nick Linker wrote:
> Could you say have you seen an implementation of arrays using Erlang
> ports? If yes, how they fast?
That would probably only be useful for storing integers and atoms,
otherwise you would have the same copy-in/out problem as ets tables.
And, of course, there would be some overhead for message passing.
It doesn't feel like a worthwhile exercise to implement it.
/Richard
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Sep 11, 2006 4:54 pm |
|
|
|
Guest
|
Can anyone post example usage for the Array
implementation?
I'd like to see proper usage.
%% yes I imported the array module, after compiling
test() ->
MyArr = array:new(0,0),
array:push(1,4,MyArr).
This is about as far as I got.
How do you identify individual arrays? New doesnt
always return me a value. How do I push a value into
the array? Does it dynamically resize? I cannot
determine the answers to these questions by looking at
the code/trying test args.
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Mon Sep 11, 2006 6:34 pm |
|
|
|
Guest
|
Jeff Crane wrote:
> Can anyone post example usage for the Array
> implementation?
>
> I'd like to see proper usage.
>
> %% yes I imported the array module, after compiling
> test() ->
> MyArr = array:new(0,0),
> array:push(1,4,MyArr).
>
> This is about as far as I got.
'push' is not an exported function, so don't even try to
use it. It's just a help function that works on lists.
Rule number one: if it's not exported and not documented,
then it doesn't exist.
On the other hand, there _is_ a heap of unit testing code
inside the module, with plenty of usage examples.
> How do you identify individual arrays?
What do you mean by "identify"?
> New doesnt always return me a value.
That sounds awfully strange. Do you mean that the 'new'
function loops forever? Can you show an example?
> How do I push a value into the array?
Use the 'set' function. I will probably add some
extra functions such as 'append' later.
> Does it dynamically resize?
Yes.
> I cannot determine the answers to these questions by looking at
> the code/trying test args.
Did you not see the html documentation
(http://user.it.uu.se/~richardc/array/array.html)?
/Richard
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
| uwiger |
| Posted: Mon Sep 11, 2006 7:03 pm |
|
|
|
User
Joined: 03 Jul 2006
Posts: 604
Location: Sweden
|
The array.erl module implements a functional data structure.
It doesn't work like ets.
array:set(I, Value, Array) returns a new Array with
index I set to Value, for example.
This is the same as for gb_trees, dict, queue, and,
well, lists.
BR,
Ulf W
> -----Original Message-----
> From: erlang-questions-bounces@erlang.org
> [mailto:erlang-questions-bounces@erlang.org] On Behalf Of Jeff Crane
> Sent: den 11 september 2006 18:52
> To: erlang-questions@erlang.org
> Subject: Re: [erlang-questions] 2D Map Arrays
>
> Can anyone post example usage for the Array implementation?
>
> I'd like to see proper usage.
>
> %% yes I imported the array module, after compiling
> test() ->
> MyArr = array:new(0,0),
> array:push(1,4,MyArr).
>
> This is about as far as I got.
>
> How do you identify individual arrays? New doesnt always
> return me a value. How do I push a value into the array? Does
> it dynamically resize? I cannot determine the answers to
> these questions by looking at the code/trying test args.
>
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam? Yahoo! Mail has the best spam protection
> around http://mail.yahoo.com
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@erlang.org
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
erlang-questions@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Post recived from mailinglist |
|
|
| Back to top |
|
|
|
All times are GMT
Page 1 of 2
Goto page 1, 2 Next
|
|
|
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
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
