RFC: bitmap storage for hidden
pierre-yves.david at ens-lyon.org
Tue Sep 6 13:06:52 EDT 2016
On 08/31/2016 10:53 PM, Durham Goode wrote:
> One of the performance costs that affects every command is the
> computehidden function (which computes what commits are hidden based on
> a combination of obsmarkers, bookmarks, workingcopy, phases, and tags).
> At Facebook this function alone can add 300ms to every command a user
> runs (depending on a variety of factors).
Do you have the details on where that time is going? There might be
small steps to take in existing code to speed thing up before
introducing a new concept.
For example, We could have a similar bitmap to know if a changeset is
affected by obsolescence markers, that would cut the whole obsstore
parsing out + hash checking out of the equation with minimum impact. The
bitmap would also be significant more stable (you never stop being
affected unless the obsstore is stripped) which would make it easier to
> I've begun work on a storage structure for this information, so we don't
> need to recompute it during every read command. Before I go through the
> work to polish it enough to send it upstream, I want to run it by people
> for comments.
> The idea is basically:
> - Have a file that acts as a bitmap, where a changelog rev number maps
> to a particular bit, and if that bit is set then the node is considered
> hidden. computehidden will return a class that uses this to answer
> filteredrevs.__contains__ calls.
> - When something is changed that would affect visibility (bookmark edit,
> phase change, obsmarker creation, dirstate movement, tag edit), that
> code is responsible for calling hidden.updatevisibilty(repo,
> affectednodes) which reports which nodes are touched by the edit (like
> the old bookmark node and the new bookmark node), and updatevisibility()
> does the minimal calculation of visibility changes and propagates those
> changes to the node ancestors as required.
Could we move that at a level lower and use this for the whole filter
infrastructure? There is a lot of logic around incremental update and
The idea of having some even system to detect change and triggers
various processing seems useful but we should probably also tight it up
at a lower level than just high level operation. There is multiple other
place that could use this kind of data, having some kind of "journal of
transaction event" seems something useful. Having it a the transaction
level would also help a bit with the daunting idea of having 3rd party
code in extension play nice with it.
> - The file would be stored in .hg/cache/hidden, and would only be 122kb
> per million commits, so we'd just use the normal copy + atomic rename
> strategy for transactionality (i.e. transaction.addfilegenerator)
We cannot just use transaction here, visibility is affected by operation
done outside a transaction (eg: working copy parent update).
> - In theory the file would always be up-to-date, but we can put some
> metadata at the front of the file to allow verifying the repo hasn't
> changed significantly out from under it (recording tip, working copy
> parents, obsmarker file timestamp, etc). If the repo has changed, or if
> the bitmap doesn't yet exist, it can be trivially calculated using
> hidden.updatevisibility(repo.revs('not public()')) in a manner similar
> to how it works today.
Given that old client can touch repository, we cannot guarantee it will
always be up to date unless we bump the repository format (something
that will eventually happen "one day"). In the mean time we need some
cache invalidation key. Invalidation key for the whole hiddenset wont be
trivial. That make another argument to start with caching at simpler
point in the pipe.
> Notable issues:
> - A number of places treat filteredrevs as a set, and do things like
> 'myset - repo.filteredrevs'. With a bitmap this doesn't work, so we
> need to translate it to '(r for r in myset if r not in
> repo.filteredrevs)'. Which is probably a better O() anyway since it
> won't be affected by the size of filteredrevs.
I'm pretty sure Python have optimized enough set operations than the
complexity of the existing code is fine. You proposal will probably be
significantly slower. We should look into having efficient operation
with set instead.
> - filteredrevs is currently a frozen set. Editing the bitmap will have
> to be done in a way where the edits only become visible when the
> 'frozen' set is invalidated. So we maintain the existing behavior.
Moving to mutable object for this is a bit scary. They might escape in
various places and are used in various keys. We should probably stick to
immutable object for now and see if having mutable one is worth is as a
> Follow up ideas:
> - Once this ships as a cache, it might be possible to progress it to
> not-a-cache, such that we could define visibility in other terms. For
> instance, we could allow hiding/reviving commits without obsolescence
> markers in non-evolve repos. This is a bit more of a long term thought,
> but might be worth brainstorming about.
I'm a bit confused by this part. The current code for hidden computable
is already independent from obsolescence and extensible. Did you checked
out the current code?
More information about the Mercurial-devel