[DGD] Multi-level map shifter bigmap

[Shentino]

I just found another bug...turns out when I was merging a thin node
with another one with a different parent, I screw up the parent's and
uncle's low and high key markers.

Back to the drawing board...I need to write an explicit node
"migration" function so that my uncle can adopt me.

I've rewritten this sucker multiple times and no matter how many times
I've done so, testing always finds "just one more special case" where
it doesn't work.

On 6/6/08, Noah Gibbs <noah_gibbs at yahoo.com> wrote:
>   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
>
>
>
> ___________________________________________
> https://mail.dworkin.nl/mailman/listinfo/dgd
>