On 6/27/07, Timothy Brownawell <[EMAIL PROTECTED]> 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
_______________________________________________
Monotone-devel mailing list
[email protected]
http://lists.nongnu.org/mailman/listinfo/monotone-devel
