[MUD-Dev] Naming and Directories?

[Mark Gritter]

Ola Fosheim =?iso-8859-1?Q?Gr=F8stad?= writes:
> 
> Mark Gritter wrote:
> > 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.)
> 
> Uhm... But a hashtable would only access like... 3-5 cachelines?  (I
> don't think trees and tries qualifies as random-access structures
> either)  The benefit of the binary tree is that it is efficient to
> traverse... So we agree, we need to know what the datastructure is going
> to be used for. For instance, if you want to display a sorted "all
> players" list then a binary tree (or a balancing variant) would do ok.
> *shrug*
> 

True, hash tables are generally good.  The main difference is, as you say,
whether you're interested in just exact lookups, or also sorted lists,
prefixes, etc.

<GEEK mode='os/architecture'>
There's actually a solution for handling "prefix" lookups that gets used
(well, discussed, anyway) in handling TLB misses.  Say you have various page 
sizes, and aren't sure which size to use when looking in your inverted page 
table.  Just duplicate the entry for each of the possible prefixes.  So in 
terms of our discussion, add 'Mark', 'Mar', 'Ma', and 'M' to the hash table, 
stopping when there's a conflict with another name.
</GEEK>

> > 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;
> > };
> 
> sizeof(struct node) == 36... Maybe it would be better if one clustered
> those variables whose bytes are most likely to be accessed? ;^)
> 

Doh!  I was aiming for sizeof(struct node) == 32, but forgot the object
pointer...  plus, you'd have to throw it out and start over for a new
pointer size.  Your idea seems better, with those considerations.

Mark Gritter
mgritter at cs.stanford.edu


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