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

[Zack Weinberg]

On 6/28/07, Nathaniel Smith <address@hidden> wrote:
> You may want to double-check your numbers on a workload you're really
> interested in, like 'pull' -- 'regenerate_caches', unless someone has
> gone and fixed it when I wasn't looking, uses an arbitrary toposort.
> Normally for things like pull we process revisions using our smart
> height-based toposort, which has nice clustering behavior.  This means
> that often (anyone want to measure?) when we want to load a roster,
> its immediate parent is already in the roster cache.

Unfortunately, oprofile is still not working for me (I tried your
suggestion but it didn't help any) and I suspect the server side of a
pull will not appreciate the client running under cachegrind. I'll see
what I can do with boring old gprof...

> Where are these dynamic_cast's coming from?  Roster loading seems like
> a plausible source, since loading a roster requires doing many many
> path lookups, and doing a path lookup requires doing dynamic_cast's on
> the node_t's corresponding to each intermediate directory.  Roster
> writing similarly requires O(tree) dynamic_casts, and poor cache
> behavior for roster writing means that we'll be writing too many full
> rosters (as dirty rosters get evicted, only to later be re-loaded and
> deltafied).

Yeah, it's all path lookup, roster writeout, and deltificiation.

> > 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.
>
> What workloads are you thinking of?  It seems plausible to me that
> they would, but it also seems plausible that things like
> pull or regenerate_rosters are a worst-case, given that they are doing
> whole-roster operations over and over in their inner loop.

Pull, checkout, large updates, merge were what I was thinking of.
unify_rosters, but I don't know what hits that.

> Do you know how much memory we're losing to the hash table as compared
> to a dense vector?  Any idea how it compares to the memory we're
> losing to, say, malloc overhead from the shared_ptr/std::string-happy
> structures that the hash table is storing?  (I have no idea how to
> measure either of these quantities, I wish I did.
> database::roster_size_estimator::operator() is totally awesome.)

Urrr.  No, I don't know myself.  I do know that malloc and free are
the #2 and #3 entries on the regenerate_caches profile (#1 is,
unsurprisingly, Botan::SHA_160::hash, and #4 is our old friend
__dynamic_cast).

> > * We might want to think about packing node IDs better.  I can think
> > of several algorithms of varying degrees of cleverness, but suspect
> > someone else has a better sense of how to do it.
>
> Not sure what you mean here.  Within a database, node_ids are
> perfectly packed -- we use every node_id from 1 up to the current
> maximum.  We might arrange to make the space used by any given roster
> less fragmented, I guess

Yes, that's what I had in mind.

>  -- the obvious way that comes to mind would
> be to process revisions in a clustered-toposorty sort of way so that
> all the additions within one branch of development get adjacent parts
> of the node_id space :-).

I wonder if it might make sense to leave space for future expansion somehow...

> If that's true, you might want to run your
> scripts on a database after doing a local fresh pull, as opposed to a
> regenerate_rosters.

Will try that.

zw