[DGD] Multi-level map shifter bigmap

[Noah Gibbs]

  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