[DGD] Multi-level map shifter bigmap

[Noah Gibbs]

  On the face of it, this design sounds good.  I suspect you can get into situations with strongly unbalanced lists (very deep list compared to total number of nodes) by inserting in very specific orders, but most balanced-tree schemes have this property.  Overall, this sounds like a good solid data structure design, and like it would have good average-case/amortized performance in most situations.

--- On Fri, 6/6/08, Shentino <shentino at gmail.com> wrote:

> From: Shentino <shentino at gmail.com>
> Subject: Re: [DGD] Multi-level map shifter bigmap
> To: noah_gibbs at yahoo.com, "All about Dworkin's Game Driver" <dgd at dworkin.nl>
> Date: Friday, June 6, 2008, 3:52 PM
> 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
> >
> ___________________________________________
> https://mail.dworkin.nl/mailman/listinfo/dgd