This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1773

revlog: use named attributes on revlog index entries
AcceptedPublic

Authored by indygreg on Dec 26 2017, 7:36 PM.

Details

Reviewers
durin42
Group Reviewers
hg-reviewers
Summary

Now that we're using a dedicated type for index entries everywhere,
we can access fields in them by name instead of integer offset.

This change has a significant impact on performance on the Firefox
repository. (Values are from before refactor, parent commit, this
commit.)

$ HGMODULEPOLICY=c hg perfrevset '::tip'
! wall 0.755869 comb 0.750000 user 0.750000 sys 0.000000 (best of 13)
! wall 1.011107 comb 1.010000 user 1.010000 sys 0.000000 (best of 10)
! wall 0.864906 comb 0.860000 user 0.860000 sys 0.000000 (best of 11)

$ HGMODULEPOLICY=py hg perfrevset '::tip'
! wall 1.366281 comb 1.360000 user 1.360000 sys 0.000000 (best of 7)
! wall 1.860068 comb 1.860000 user 1.860000 sys 0.000000 (best of 5)
! wall 1.672432 comb 1.680000 user 1.670000 sys 0.010000 (best of 6)

And with PyPy:

! wall 0.163141 comb 0.160000 user 0.160000 sys 0.000000 (best of 56)
! wall 0.154325 comb 0.160000 user 0.160000 sys 0.000000 (best of 54)
! wall 0.155534 comb 0.160000 user 0.160000 sys 0.000000 (best of 53)

The C extension is ~15% slower than before the refactor. This is a
bit unfortunate. That is a bit steep price to pay for more readable
code and the establishment of a formal interface for index entries.

However, all is not lost! Because we're now using a custom type and
conforming to a yet-to-be-formally-defined interface, there's nothing
preventing us from implementing a backed-by-C custom type for revlog
entries. This type could lazily resolve PyObject instances, which
should result in a massive performance boost for operations that
don't need to access all fields of the index entry. This is easier
done *after* we drop all uses of tuples and their API for referring
to index entries.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

indygreg created this revision.Dec 26 2017, 7:36 PM
yuja added a subscriber: yuja.Dec 28 2017, 9:04 AM

Because we're now using a custom type and conforming to
a yet-to-be-formally-defined interface, there's nothing
preventing us from implementing a backed-by-C custom type
for revlog entries.

Not reviewed the series yet, but can't we just start with a custom type
backed by C so we don't have to import back IndexV1Entry from Python?

indygreg added a comment.Dec 28 2017, 1:56 PM
In D1773#30283, @yuja wrote:

Not reviewed the series yet, but can't we just start with a custom type
backed by C so we don't have to import back IndexV1Entry from Python?

That's possible. I do have a work-in-progress patch to the C code to implement such a type.

However, it is quite large and I suspect it will take a bit more effort to finish it. The end result of this series gets us into a state where the C type can be swapped in with minimal effort. I have a soft preference for implementing the type in C as a follow-up. But I can refactor the series if wanted. Or someone can review this series without accepting it and I'll add the C type later.

yuja added a comment.Jan 5 2018, 12:43 AM

However, it is quite large and I suspect it will take a bit more effort to finish it.

Isn't that something like dirstateTupleType? If we had a native type, we wouldn't
need D1767, D1768, and probably D1769. If it can get rid of refcounting business,
reviewing this series will be much fun.

indygreg edited the summary of this revision. (Show Details)Jan 6 2018, 3:26 AM
durin42 added a subscriber: durin42.Jan 10 2018, 5:53 PM
In D1773#30628, @yuja wrote:

However, it is quite large and I suspect it will take a bit more effort to finish it.

Isn't that something like dirstateTupleType? If we had a native type, we wouldn't
need D1767, D1768, and probably D1769. If it can get rid of refcounting business,
reviewing this series will be much fun.

I don't feel strongly about the approach. My bias is to land this whole series as-is. The "lazy struct" should be fairly easily done as a followup.

The refcounting of the type looks okay to me.

durin42 accepted this revision.Jan 10 2018, 5:54 PM
This revision is now accepted and ready to land.Jan 10 2018, 5:54 PM

Revision Contents
Changeset List

PathPackages
Mmercurial/revlog.py (56 lines)

Diff 4634

mercurial/revlog.py

except KeyError: except KeyError:
# pure python cache lookup failed # pure python cache lookup failed
n = self._nodecache n = self._nodecache
i = self.index i = self.index
p = self._nodepos p = self._nodepos
if p is None: if p is None:
p = len(i) - 2 p = len(i) - 2
for r in xrange(p, -1, -1): for r in xrange(p, -1, -1):
v = i[r][7] v = i[r].node
n[v] = r n[v] = r
if v == node: if v == node:
self._nodepos = r - 1 self._nodepos = r - 1
return r return r
if node == wdirid: if node == wdirid:
raise error.WdirUnsupported raise error.WdirUnsupported
raise LookupError(node, self.indexfile, _('no node')) raise LookupError(node, self.indexfile, _('no node'))
# Accessors for index entries. # Accessors for index entries.
# First tuple entry is 8 bytes. First 6 bytes are offset. Last 2 bytes # First tuple entry is 8 bytes. First 6 bytes are offset. Last 2 bytes
# are flags. # are flags.
def start(self, rev): def start(self, rev):
return int(self.index[rev][0] >> 16) return int(self.index[rev].offsetflags >> 16)
def flags(self, rev): def flags(self, rev):
return self.index[rev][0] & 0xFFFF return self.index[rev].offsetflags & 0xFFFF
def length(self, rev): def length(self, rev):
return self.index[rev][1] return self.index[rev].chunklength
def rawsize(self, rev): def rawsize(self, rev):
"""return the length of the uncompressed text for a given revision""" """return the length of the uncompressed text for a given revision"""
l = self.index[rev][2] l = self.index[rev].rawlength
if l >= 0: if l >= 0:
return l return l
t = self.revision(rev, raw=True) t = self.revision(rev, raw=True)
return len(t) return len(t)
def size(self, rev): def size(self, rev):
"""length of non-raw text (processed by a "read" flag processor)""" """length of non-raw text (processed by a "read" flag processor)"""
# fast path: if no "read" flag processor could change the content, # fast path: if no "read" flag processor could change the content,
# size is rawsize. note: ELLIPSIS is known to not change the content. # size is rawsize. note: ELLIPSIS is known to not change the content.
flags = self.flags(rev) flags = self.flags(rev)
if flags & (REVIDX_KNOWN_FLAGS ^ REVIDX_ELLIPSIS) == 0: if flags & (REVIDX_KNOWN_FLAGS ^ REVIDX_ELLIPSIS) == 0:
return self.rawsize(rev) return self.rawsize(rev)
return len(self.revision(rev, raw=False)) return len(self.revision(rev, raw=False))
def chainbase(self, rev): def chainbase(self, rev):
base = self._chainbasecache.get(rev) base = self._chainbasecache.get(rev)
if base is not None: if base is not None:
return base return base
index = self.index index = self.index
base = index[rev][3] base = index[rev].baserev
while base != rev: while base != rev:
rev = base rev = base
base = index[rev][3] base = index[rev].baserev
self._chainbasecache[rev] = base self._chainbasecache[rev] = base
return base return base
def linkrev(self, rev): def linkrev(self, rev):
return self.index[rev][4] return self.index[rev].linkrev
def parentrevs(self, rev): def parentrevs(self, rev):
try: try:
entry = self.index[rev] entry = self.index[rev]
except IndexError: except IndexError:
if rev == wdirrev: if rev == wdirrev:
raise error.WdirUnsupported raise error.WdirUnsupported
raise raise
return entry[5], entry[6] return entry.p1rev, entry.p2rev
def node(self, rev): def node(self, rev):
try: try:
return self.index[rev][7] return self.index[rev].node
except IndexError: except IndexError:
if rev == wdirrev: if rev == wdirrev:
raise error.WdirUnsupported raise error.WdirUnsupported
raise raise
# Derived from index values. # Derived from index values.
def end(self, rev): def end(self, rev):
return self.start(rev) + self.length(rev) return self.start(rev) + self.length(rev)
def parents(self, node): def parents(self, node):
i = self.index i = self.index
d = i[self.rev(node)] d = i[self.rev(node)]
return i[d[5]][7], i[d[6]][7] # map revisions to nodes inline return i[d.p1rev].node, i[d.p2rev].node # map revisions to nodes inline
def chainlen(self, rev): def chainlen(self, rev):
return self._chaininfo(rev)[0] return self._chaininfo(rev)[0]
def _chaininfo(self, rev): def _chaininfo(self, rev):
chaininfocache = self._chaininfocache chaininfocache = self._chaininfocache
if rev in chaininfocache: if rev in chaininfocache:
return chaininfocache[rev] return chaininfocache[rev]
index = self.index index = self.index
generaldelta = self._generaldelta generaldelta = self._generaldelta
iterrev = rev iterrev = rev
e = index[iterrev] e = index[iterrev]
clen = 0 clen = 0
compresseddeltalen = 0 compresseddeltalen = 0
while iterrev != e[3]: while iterrev != e.baserev:
clen += 1 clen += 1
compresseddeltalen += e[1] compresseddeltalen += e.chunklength
if generaldelta: if generaldelta:
iterrev = e[3] iterrev = e.baserev
else: else:
iterrev -= 1 iterrev -= 1
if iterrev in chaininfocache: if iterrev in chaininfocache:
t = chaininfocache[iterrev] t = chaininfocache[iterrev]
clen += t[0] clen += t[0]
compresseddeltalen += t[1] compresseddeltalen += t[1]
break break
e = index[iterrev] e = index[iterrev]
else: else:
# Add text length of base since decompressing that also takes # Add text length of base since decompressing that also takes
# work. For cache hits the length is already included. # work. For cache hits the length is already included.
compresseddeltalen += e[1] compresseddeltalen += e.chunklength
r = (clen, compresseddeltalen) r = (clen, compresseddeltalen)
chaininfocache[rev] = r chaininfocache[rev] = r
return r return r
def _deltachain(self, rev, stoprev=None): def _deltachain(self, rev, stoprev=None):
"""Obtain the delta chain for a revision. """Obtain the delta chain for a revision.
``stoprev`` specifies a revision to stop at. If not specified, we ``stoprev`` specifies a revision to stop at. If not specified, we
chain = [] chain = []
# Alias to prevent attribute lookup in tight loop. # Alias to prevent attribute lookup in tight loop.
index = self.index index = self.index
generaldelta = self._generaldelta generaldelta = self._generaldelta
iterrev = rev iterrev = rev
e = index[iterrev] e = index[iterrev]
while iterrev != e[3] and iterrev != stoprev: while iterrev != e.baserev and iterrev != stoprev:
chain.append(iterrev) chain.append(iterrev)
if generaldelta: if generaldelta:
iterrev = e[3] iterrev = e.baserev
else: else:
iterrev -= 1 iterrev -= 1
e = index[iterrev] e = index[iterrev]
if iterrev == stoprev: if iterrev == stoprev:
stopped = True stopped = True
else: else:
chain.append(iterrev) chain.append(iterrev)
if not count: if not count:
return [nullrev] return [nullrev]
# we won't iter over filtered rev so nobody is a head at start # we won't iter over filtered rev so nobody is a head at start
ishead = [0] * (count + 1) ishead = [0] * (count + 1)
index = self.index index = self.index
for r in self: for r in self:
ishead[r] = 1 # I may be an head ishead[r] = 1 # I may be an head
e = index[r] e = index[r]
ishead[e[5]] = ishead[e[6]] = 0 # my parent are not ishead[e.p1rev] = ishead[e.p2rev] = 0 # my parent are not
return [r for r, val in enumerate(ishead) if val] return [r for r, val in enumerate(ishead) if val]
def heads(self, start=None, stop=None): def heads(self, start=None, stop=None):
"""return the list of all nodes that have no children """return the list of all nodes that have no children
if start is specified, only heads that are descendants of if start is specified, only heads that are descendants of
start will be returned start will be returned
if stop is specified, it will consider all the revs from stop if stop is specified, it will consider all the revs from stop
if id in self._pcache: if id in self._pcache:
return self._pcache[id] return self._pcache[id]
if len(id) < 40: if len(id) < 40:
try: try:
# hex(node)[:...] # hex(node)[:...]
l = len(id) // 2 # grab an even number of digits l = len(id) // 2 # grab an even number of digits
prefix = bin(id[:l * 2]) prefix = bin(id[:l * 2])
nl = [e[7] for e in self.index if e[7].startswith(prefix)] nl = [e.node for e in self.index if e.node.startswith(prefix)]
nl = [n for n in nl if hex(n).startswith(id) and nl = [n for n in nl if hex(n).startswith(id) and
self.hasnode(n)] self.hasnode(n)]
if len(nl) > 0: if len(nl) > 0:
if len(nl) == 1 and not maybewdir: if len(nl) == 1 and not maybewdir:
self._pcache[id] = nl[0] self._pcache[id] = nl[0]
return nl[0] return nl[0]
raise LookupError(id, self.indexfile, raise LookupError(id, self.indexfile,
_('ambiguous identifier')) _('ambiguous identifier'))
Callers will need to call ``self.start(rev)`` and ``self.length(rev)`` Callers will need to call ``self.start(rev)`` and ``self.length(rev)``
to determine where each revision's data begins and ends. to determine where each revision's data begins and ends.
""" """
# Inlined self.start(startrev) & self.end(endrev) for perf reasons # Inlined self.start(startrev) & self.end(endrev) for perf reasons
# (functions are expensive). # (functions are expensive).
index = self.index index = self.index
istart = index[startrev] istart = index[startrev]
start = int(istart[0] >> 16) start = int(istart.offsetflags >> 16)
if startrev == endrev: if startrev == endrev:
end = start + istart[1] end = start + istart.chunklength
else: else:
iend = index[endrev] iend = index[endrev]
end = int(iend[0] >> 16) + iend[1] end = int(iend.offsetflags >> 16) + iend.chunklength
if self._inline: if self._inline:
start += (startrev + 1) * self._io.size start += (startrev + 1) * self._io.size
end += (endrev + 1) * self._io.size end += (endrev + 1) * self._io.size
length = end - start length = end - start
return start, self._getsegment(start, length, df=df) return start, self._getsegment(start, length, df=df)
return l return l
def _chunkclear(self): def _chunkclear(self):
"""Clear the raw chunk cache.""" """Clear the raw chunk cache."""
self._chunkcache = (0, '') self._chunkcache = (0, '')
def deltaparent(self, rev): def deltaparent(self, rev):
"""return deltaparent of the given revision""" """return deltaparent of the given revision"""
base = self.index[rev][3] base = self.index[rev].baserev
if base == rev: if base == rev:
return nullrev return nullrev
elif self._generaldelta: elif self._generaldelta:
return base return base
else: else:
return rev - 1 return rev - 1
def revdiff(self, rev1, rev2): def revdiff(self, rev1, rev2):
self.DELTAREUSESAMEREVS) self.DELTAREUSESAMEREVS)
index = self.index index = self.index
for rev in self: for rev in self:
entry = index[rev] entry = index[rev]
# Some classes override linkrev to take filtered revs into # Some classes override linkrev to take filtered revs into
# account. Use raw entry from index. # account. Use raw entry from index.
flags = entry[0] & 0xffff flags = entry.offsetflags & 0xffff
linkrev = entry[4] linkrev = entry.linkrev
p1 = index[entry[5]][7] p1 = index[entry.p1rev].node
p2 = index[entry[6]][7] p2 = index[entry.p2rev].node
node = entry[7] node = entry.node
# (Possibly) reuse the delta from the revlog if allowed and # (Possibly) reuse the delta from the revlog if allowed and
# the revlog chunk is a delta. # the revlog chunk is a delta.
cachedelta = None cachedelta = None
rawtext = None rawtext = None
if populatecachedelta: if populatecachedelta:
dp = self.deltaparent(rev) dp = self.deltaparent(rev)
if dp != nullrev: if dp != nullrev: