bugs in gridfile

[Ulf Wiger]

I have discovered that the gridfile (multi-key access) I posted on
www.erlang.org has some faults in it. The split/merge algorithm was not
correctly implemented, and the next/previous operations do not work
right.

I have fixed the split/merge problem and have figured out how to do the
next/previous. I will post a new version real soon.

If anyone is using the current version, or wants to start now, contact
me for an early copy.


I have also made a RAM-based version, which I will also post. 

It is actually pretty fast:

Rough performance measurements (1000 objects, 3 dimensions) indicate:
- insert: ca 500 us/object
- lookup: ca 250 us/object
- delete: ca 300 us/object
- match:  ca 80 ms matching 100/1000 objs (whole table scanned)
- range_match: ca 3.6 ms for a search matching 20 objects
  -> roughly 150-200 us/(matching object)

The above measurements where taken on an UltraSPARC 1 running
BEAM on Solaris. 
- Each object had a payload of lists:seq(1,100).
- Keys were composed as {1..10,1..10,1..10} and inserted in
pseudo-random order.


The disk-based variant, gridfile.erl, sped up as well when I got the
split/merge to work better.

/Uffe
-- 
Ulf Wiger, Chief Designer AXD 301     <ulf.wiger@REDACTED>
Ericsson Telecom AB                          tfn: +46  8 719 81 95
Varuvägen 9, Älvsjö                          mob: +46 70 519 81 95
S-126 25 Stockholm, Sweden                   fax: +46  8 719 43 44