Re: [Monotone-devel] Call for testing: nvm.experiment.no-split-path

[Zack Weinberg]

On 6/27/07, Timothy Brownawell <address@hidden> wrote:
> On Wed, 2007-06-27 at 17:03 -0700, Zack Weinberg wrote:
> > The hybrid_map is for roster_t::nodes, not for dir_t::children.
> > Having O(1) lookup in dir_t::children would definitely help, but I'm
> > not sure a hybrid_map is the right way to do it (to be honest though,
> > I don't know what the right way *is* ... maybe, like, steal the
> > directory htrees from ext3fs).
>
> I tried that, and it actually seemed to slow things down a bit (for
> pull, at least). Probably because we don't actually *do* lookups that
> often, I think mostly we just iterate through everything. So the bigger
> effect is the higher overhead of inserting into the map, since you now
> have two indexes to maintain. Maybe a trie or something would work?

I assume you mean you tried hybrid_maps for the directories?  I'd
believe that we did dfs_iter type walks more often than we did
get_node in normal operation.

To be specific, this is the "htree" I was talking about:
http://www.usenix.org/publications/library/proceedings/als01/full_papers/phillips/phillips_html/index.html
I am inclined to think it wouldn't be better than what we have, but
perhaps it gives ideas...

zw