[PATCH 02 of 22] radixlink: introduce a new data structure
Yuya Nishihara
yuya at tcha.org
Tue Jun 6 11:53:09 EDT 2017
On Sun, 4 Jun 2017 16:59:14 -0700, Jun Wu wrote:
> # HG changeset patch
> # User Jun Wu <quark at fb.com>
> # Date 1496536858 25200
> # Sat Jun 03 17:40:58 2017 -0700
> # Node ID e8e8d713e4b774f6894ee65723e7fdc12bf8a101
> # Parent 5c3500de0a229d8aa08058bccec531d8a85b90d9
> # Available At https://bitbucket.org/quark-zju/hg-draft
> # hg pull https://bitbucket.org/quark-zju/hg-draft -r e8e8d713e4b7
> radixlink: introduce a new data structure
I just had a look at _get() and _splitleafentry() code paths. The idea
generally looks good to me. I have random thoughts on both data structure and
API. Some are just nitpick and some are crazy.
> +class radixlink(object):
> + """multimap. keys are variable-length bytes, values are lists of uint32s.
Do we really need to support variable-length key? IIUC, that's the main reason
why both radix-entry and leaf-entry have link-offset field.
> + O(len(key)) lookup and insertion.
> +
> + A "radixlink" consists of 2 logical parts: index, and link. "index" is a
> + base16 radix tree with pointers to link. "link" stores linked lists.
> +
> + The actual implementation mixes the above 2 parts into 1 buffer for
> + simplicity and easy transaction handling. The format of the buffer is:
> +
> + radixlink := header + entry-list
> + header := source-of-truth-size (4B)
> + entry-list := radix-entry | entry-list + entry
> + entry := index-entry | link-entry
> + index-entry := radix-entry | leaf-entry
> + radix-entry := '\0' * 4 + link-offset (4B) + index-offset (4B) * 16
> + leaf-entry := key-length (4B) + link-offset (4B) + key + padding
> + link-entry := next-link-offset (4B) + value (4B)
> +
> + leaf-entry's key-length cannot be 0, and is at least len(radix-entry)
> + long so it can be converted to radix-entry in-place later.
Nit: I slightly prefer "link-entry := value + next-link-offset" for consistency
with the other entries.
Crazy idea: If we can have some restrictions on the key format (e.g. fixed
length, maximum length, etc.), maybe we could shrink the minimum size of the
entry and embed a few values onto leaf-entry.
radix-entry := index-offset * 16
leaf-entry := link-offset + b16-key-length (1byte)
+ number-of-inline-value (1byte) + b8-key + padding
padding := inline-value (4byte) * (as much as possible)
link-entry := link-offset + value
Suppose our data structure is at least 8-byte aligned, we have 3bits from LSB
which can be (ab)used as flags (as glibc malloc does.)
*-entry := *-offset (29bits) + flags (3bits) + ...
flags := { RADIX (0), LEAF (1), LINK (2) }
> + def __len__(self):
> + """raw buffer length, could be used to do "isdirty" check"""
> + return len(self._data)
API: This would be confusing with the length of the entries since it supports
__getitem__(). I prefer more explicit name, e.g. rawsize().
> + def _get(self, key):
> + """lookup a key, return the value list, or an empty array"""
> + ioff = self.headersize
> + bkey = _tob16(key)
Future API: we'll need to support odd-length key in order to replace
revlog._partialmatch().
> + def insert(self, key, value):
(not yet reviewed)
> + def _followindex(self, offset, b16list, b16offset, splitleaf=False):
> + """follow an index-entry at offset
> +
> + For a radix-entry, lookup b16list[b16offset], and return new pointers.
> + For a leaf-entry, check the remaining of b16list.
> +
> + If splitleaf is True, split a leaf-entry where b16list does not match.
> + Useful for adding new index-entries.
> +
> + return (nextoffset, b16offset, poffset) or raise. poffset is the offset
Nit: maybe "or raise" would be outdated?
> + of nextoffset. Useful for being rewritten to newly added index-entry.
> + """
> + data = self._data
> + klen = self.keylen.unpack_from(self._data, offset)[0]
> + koff = offset + self.keylen.size + self.linkoffset.size
> + if klen > 0: # leaf entry
> + if data[koff:koff + klen] == b16list[b16offset:]:
> + return (offset, len(b16list) + 1, 0)
> + if not splitleaf:
> + return (0, b16offset, 0)
> + self._splitleafentry(offset)
> + # radix entry
> + klen = self.keylen.unpack_from(self._data, offset)[0]
> + assert klen == 0
Nit: Some comment would be helpful to understand why we re-read and assert klen.
> + def _splitleafentry(self, offset):
> + """split leaf-entry into a radix-entry and another leaf-entry
> +
> + return offset of the new leaf entry.
> + """
> + data = self._data
> + klen = self.keylen.unpack_from(data, offset)[0]
> + assert klen > 0 # must be a leaf
> +
> + koff = offset + self.keylen.size
> + loff = self.linkoffset.unpack_from(data, koff)[0]
> + koff += self.linkoffset.size
> + key = data[koff:koff + klen]
> +
> + # create a new leaf entry
> + newoffset = self._appendleafentry(key[1:], loff)
> +
> + # rewrite entry to radix in-place
> + radixbuf = bytearray(self.radixentrysize)
> + self.indexoffset.pack_into(radixbuf, self.linkoffset.size +
> + self.keylen.size + key[0] *
> + self.indexoffset.size, newoffset)
> + data[offset:offset + len(radixbuf)] = radixbuf
> + return newoffset
Nit: Since we dropped support for Python 2.6, maybe we could use memoryview to
simulate pointer arithmetic.
> +# dumpradixlink need some struct.Struct definitions from pure
> +from mercurial.pure import radixlink as pureradixlink
[...]
> +def dumpradixlink(rl, fout):
> + """dump radixlink content in a human-readable way"""
> + p = pureradixlink.radixlink
> + data = rl.data
> + linkoffsets = set()
> + descs = {} # {offset: entry-desc}
> + tovisit = [(p.headersize, 'index')] # [(offset, 'index' | 'link')]
> + visited = set([0])
> + while tovisit:
> + offset, type = tovisit.pop()
> + if offset in visited:
> + continue
> + visited.add(offset)
> + if type == 'link':
> + nextloff, value = p.linkentry.unpack_from(data, offset)
> + desc = 'link%5d | value %d' % (nextloff, value)
> + if nextloff:
> + tovisit.append((nextloff, 'link'))
> + elif type == 'index':
> + koff = offset
> + klen = p.keylen.unpack_from(data, koff)[0]
> + koff += p.keylen.size
> + loff = p.linkoffset.unpack_from(data, koff)[0]
> + linkoffsets.add(loff)
> + koff += p.linkoffset.size
> + desc = 'link%5d | ' % loff
> + tovisit.append((loff, 'link'))
> + if klen > 0:
> + key = data[koff:koff + klen]
> + desc += 'leaf %r' % list(bytearray(key))
> + else:
> + desc += 'radix'
> + for i in xrange(16):
> + v = p.indexoffset.unpack_from(
> + data, koff + i * p.indexoffset.size)[0]
> + if v > 0:
> + desc += ' %d: %d' % (i, v)
> + tovisit.append((v, 'index'))
> + descs[offset] = desc
> + for offset, desc in sorted(descs.items()):
> + fout.write('%5d | %s\n' % (offset, desc))
> + fout.flush()
Nit: I believe we'll soon need "hg debugradixlink" command. How about splitting
the module into core radixlink + pure impl + cext impl?
More information about the Mercurial-devel
mailing list