MUD-Dev
mailing list archive
[ Other Periods
| Other mailing lists
| Search
]
Date:
[ Previous
| Next
]
Thread:
[ Previous
| Next
]
Index:
[ Author
| Date
| Thread
]
Re: [MUD-Dev] Naming and Directories?
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#cs,stanford.edu
_______________________________________________
MUD-Dev maillist - MUD-Dev#kanga,nu
http://www.kanga.nu/lists/listinfo/mud-dev
- Thread context:
- Re: [MUD-Dev] Naming and Directories?, (continued)
- Re: [MUD-Dev] Naming and Directories?,
Mark Gritter mark#erdos,Stanford.EDU, Tue 16 Mar 1999, 13:46 GMT
- Re: [MUD-Dev] Naming and Directories?,
Jon A. Lambert jlsysinc#ix,netcom.com, Wed 17 Mar 1999, 00:54 GMT
- Re: [MUD-Dev] Naming and Directories?,
Hans-Henrik Staerfeldt hhs#cbs,dtu.dk, Wed 17 Mar 1999, 02:48 GMT
- Re: [MUD-Dev] Naming and Directories?,
Ola Fosheim Grøstad olag#ifi,uio.no, Wed 17 Mar 1999, 08:43 GMT
- Re: [MUD-Dev] Naming and Directories?,
Jon A. Lambert jlsysinc#ix,netcom.com, Thu 18 Mar 1999, 07:44 GMT
[ Other Periods
| Other mailing lists
| Search
]