Implementing tables - advice wanted

[Dan Gudmundsson]

I have worked on a "large" integer "array" imp.
Faster than gb_trees but not an O(1) access time, it still is a tree.

For 4500000 objects  total millisecs/micros per op.
Module		gb_trees	    ga	
--------------------------------------
insert		  alot         9155/ 2.0347
lookup         6419/ 1.4265    2689/ 0.5977
update        19065/ 4.2368    8679/ 1.9288
from_list      2560/ 0.5689     766/ 0.1702
to_list         967/ 0.2151     243/ 0.0542
from_orddict   2560/ 0.5690    1084/ 0.2411
to_orddict      995/ 0.2213    1884/ 0.4188
map            4554/ 1.0122    1788/ 0.3974
keymap         4704/ 1.0454    2287/ 0.5083
foldl          1806/ 0.4014    1204/ 0.2677
keyfoldl       1700/ 0.3779    1825/ 0.4057
foldr          1622/ 0.3606    1318/ 0.2929

/Dan

-------------- next part --------------
A non-text attachment was scrubbed...
Name: ga.erl
Type: application/octet-stream
Size: 21656 bytes
Desc: ga.erl
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20060619/db99dbf9/attachment.obj>
-------------- next part --------------

Richard Carlsson writes:
 > Joe Armstrong (AL/EAB) wrote:
 > > Erlang really really really (^100) needs tables.
 > 
 > Allow me to disagree somewhat. Erlang already has good tables,
 > both using hashing (dict) and binary trees (gb_trees). The
 > syntactic convenience of a built-in table/dictionary type is
 > really a minor thing. (Not that I would oppose having such a
 > notation, but I really don't think it is critical in any way.)
 > The main advantage would be psychological, I think: a standard
 > one-size-fits-all dictionary type makes it easier for people to
 > start using them in public interfaces, and not just internally.
 > 
 > What I _do_ miss now and then (and when I need them, I have to
 > jump through several hoops to get them) is indexable tables
 > (i.e., arrays) with O(1) access time and a _small_ constant
 > factor, and no copying of the stored data.
 > 
 > If I remember correctly, the experiment with a "vector" data
 > type (which used destructive update internally, with some
 > penalty for accessing older versions of the data) was killed
 > by bad interaction with the garbage collector, leading to
 > rotten performance. Have things changed enough in the GC by
 > now for this to become worth a new attempt?
 > 
 > 	/Richard