[DGD] Multi-level map shifter bigmap

[Shentino]

Well, here's how it works:

split:

When a node, at any level, gets too big, I split it in two by
appending a new node linked list style and with the same parent, and
then transfer half of the fat node's keyspace to the new node.

Then, since the parent just got fatter, I repeat the balance check on it.

merge:

If a node gets too small, and it's not the root node, I combine it
with one of its neighbors.  Since the parent of the node that was
absorbed got thinner, I repeat teh check on it.

If the root node gets too fat, I "nest" by creating a new root node
before splitting the old fat one.

If the root node has its two children merged down to one, I "denest"
by moving the only child back into root position.

Invariants:

All siblings are arranged in a prev<-this->next linked list, at various levels
All siblings have the same level
The keyspace of a node is a subset of the keyspace range of a supernode.
The root is a single node and encompasses all.

That's how I balance.

I was able to get it working quite well...once...but then I managed to
screw something up while I was adding iterator capability :P.


On 6/6/08, Noah Gibbs <noah_gibbs at yahoo.com> wrote:
>  This kind of thing can definitely work well.  What you're doing here has a lot in common with, for instance, balanced tree data structures like red-black trees or splay trees.  You're just changing it around noticeably because DGD has somewhat different performance characteristics (specifically in terms of memory allocation and interpreted code) than the environments of origin of those data structures.  Though an adaptation of any of them might work well for what you're doing.
>
>  You could also look into balanced heaps, Fibonacci heaps and skip lists, all of what *also* solve similar problems.  Which is best under DGD depends on a lot of performance information I don't know offhand, and how you adapt your implementation to DGD's slightly variant code and memory-allocation speeds.  However, basing your data structure on one of these existing ones might help you be sure that your basic design is correct.  What you describe sounds like it could be done well, but you haven't really given us enough information about how you accumulate and split chunks, and that's where all the magic happens.  Fibonacci heaps, for instance, are made or broken by whether they get that part right.  Splay trees are defined by their approach to it.  Your own approach will be good or bad depending on how you do it.
>
> --- On Fri, 6/6/08, Shentino <shentino at gmail.com> wrote:
>
> > From: Shentino <shentino at gmail.com>
> > Subject: [DGD] Multi-level map shifter bigmap
> > To: "All about Dworkin's Game Driver" <dgd at dworkin.nl>
> > Date: Friday, June 6, 2008, 2:07 PM
> > I've recently been working on what I hope to be the be
> > all and end all
> > of types, the bigmap.
> >
> > Homebrew, it's structured as a successively layered
> > partitioned
> > keyspace with balancing.
> >
> > The bottom nodes contain the actual mapping(s) with the
> > keys->values,
> > while higher level nodes use similiar mappings to index
> > their
> > subnodes.
> >
> > On insertion or deletion, after I put the keys in or out of
> > the
> > bottom, I run up to do a balance check to move nodes back
> > and forth as
> > needed by splits and merges.
> >
> > I guess you could call it a layered linked list with a top
> > level all
> > encompassing root directory.
> >
> > Does anyone have any ideas or notice any weaknesses in this
> > scheme?
> >
> > Two problems I seem to be having
> >
> > 1.  Merges and splits require range operations on mappings,
> > and
> > massive slowdowns.  Anything besides tuning to balance out
> > layer count
> > vs driver-side O(1) operations?
> >
> > 2.  It keeps crashing...invariant violations aplenty
> > everytime I run
> > node->fsck() ;).  Anything wrong with the design itself
> > or am I just a
> > sloppy coder?
> > ___________________________________________
> > https://mail.dworkin.nl/mailman/listinfo/dgd
>
>
>
> ___________________________________________
> https://mail.dworkin.nl/mailman/listinfo/dgd
>