[MUD-Dev] Naming and Directories?

[Mark Gritter]

Ola Fosheim =?iso-8859-1?Q?Gr=F8stad?= writes:
> 
> "Jon A. Lambert" wrote:
> > But you have changed your requirements above from speed to memory. 
> > No fair. ;)
> 
> fragmented memory access == slow => memory == speed
> 

True.  But almost _any_ large-scale random-access data structure is gonna
have bad memory locality, so in general, the fewer accesses, the better. 
I and a couple of my research group members were talking about this, this
afternoon.

Although a trie could easily use 10x or more memory than a binary tree,
the number of cache lines you're accessing is likely to be much smaller
during a lookup, and that's generally a big win.  (Assuming you have enough
memory so you don't have to page, of course.)

The "natural" binary tree repesentation

struct node {
  char *key;
  struct node *left, *right;
}

suffers from having to access _two_ cache lines per node: one for the
node itself and one to compare the key.  A trie only accesses the cache
line containing the next-node pointer, so the large nodes don't hurt...
in the short term.

Binary-tree cache behavior could be improved significantly by limiting the 
key length and adding some space overhead to the node:

struct node {
  char key[24];
  struct node *left, *right;
};

If your processor has 32-byte entries in its first-level cache, this will
probably be faster due to accessing only a single cache line per node.
I'd guess (without running a test) that not being able to share nodes
in a cache line isn't enough of a win to favor the former case.

The interesting question is what effect tries and the various flavors of
binary trees have on second-level cache behavior, and that's a lot harder
to model.  Modern architectures make everything so complicated.  :(

I'll agree that we're pretty much all blowing smoke without a specific
application/dataset in mind, Ola.  :)

Mark Gritter
mgritter at cs.stanford.edu


_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev