[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