Re: [Monotone-devel] some observations about roster node IDs

[Nathaniel Smith]

On Thu, Jun 28, 2007 at 09:35:51PM -0500, Timothy Brownawell wrote:
> On Thu, 2007-06-28 at 15:07 -0700, Zack Weinberg wrote:
> > Performance testing on the file_path/split_path changes led me to
> > thinking about node_id lookups.  Some things I've noticed:
> > 
> > regenerate_caches (on a monotone database) spends nearly seven percent
> > of runtime in dynamic_cast<> implementation, going from node_t to
> > dir_t and/or file_t.
> 
> Make node_t hold everything and an "enum Type {FILE, DIR};", and then
> file_t and dir_t can be inlineable wrapper classes?

The original roster code actually did this -- well, without the
wrapper classes.  It's really one of those "C++ sucks, it doesn't have
enough features" things, you can either use dynamic_cast stuff and
have proper (static) type-checking on field accesses, or use enum
stuff and have proper (static) warnings if you have left something out
of your switch statement.  Or use boost's discriminated union type,
which is theoretically perfect and pure torture on the programmer.

Wrapper classes (or checked accessors generally) might be a least-bad
solution.

In the original code this also cut down on malloc's, because if your
node_t is a POD, then you can just store it in the node_id->node_t
table directly, and then have directory nodes refer to their children
by node_id rather than direct pointers.  (Parent->child traversal
then involves an indirection through the node_id->node_t table.)  I
don't know if this matters, though I have some vague intuition that
extra mallocs are worse than extra hashtable lookups.

> > We are currently doing node ID lookups with a hybrid_map, which is
> > both a STL map (i.e. red-black tree) and a hashtable.  Lookups do not
> > show up in my profiles, but I suspect they would for other workloads.
> 
> The lookup just uses the hashtable, so it really shouldn't show up until
> everything else is sped up a lot. The map is only there to provide
> ordered iteration (for eg roster_merge.cc, which does parallel iteration
> on rosters).

Possibly those few places that need sorted items should just call
sort?

This is all micro-optimization, though, which is doubly-pointless if
we're not seeing table operations in the profiles.

-- Nathaniel

-- 
"The problem...is that sets have a very limited range of
activities -- they can't carry pianos, for example, nor drink
beer."