[cfe-dev] Adding indexing support to Clangd

[Manuel Klimek via cfe-dev]

On Thu, Aug 10, 2017 at 5:57 PM Doug Schaefer via cfe-dev <
cfe-dev at lists.llvm.org> wrote:

> > -----Original Message-----
> > From: Dr D. Chisnall [mailto:dc552 at hermes.cam.ac.uk] On Behalf Of David
> > Chisnall
> > Sent: Thursday, August 10, 2017 6:10 AM
> > To: Marc-André Laperle <marc-andre.laperle at ericsson.com>
> > Cc: via cfe-dev <cfe-dev at lists.llvm.org>; zeratul976 at hotmail.com; Doug
> > Schaefer <dschaefer at blackberry.com>
> > Subject: Re: [cfe-dev] Adding indexing support to Clangd
> >
> > On 8 Aug 2017, at 18:52, Marc-André Laperle via cfe-dev <cfe-
> > dev at lists.llvm.org> wrote:
> > >
> > > --ClangdIndexStorage--
> > > malloc-like interface that allocates/frees data blocks of variable
> sizes on
> > disk. The blocks can contain ints, shorts, strings, pointers (i.e. file
> offsets),
> > etc. The data is cached in 4K pieces so that local and repeated accesses
> are all
> > done quickly, in memory.
> > > Clangd mallocs and writes its index model objects using this.
> > >
> > > --BTree--
> > > A pretty classic BTree implementation. Used to speed up lookup (symbol
> > names, file names). It allocates its nodes using ClangdIndexStorage
> therefore
> > it is stored on disk. Keys are actually records in ClangdIndexStorage so
> you
> > can really think of the BTree as a collection of sorted pointers (sorted
> > according to a provided comparator).
> >
> > This sounds very like bdb.  Is there a reason that we’re reimplementing a
> > large chunk of bdb, rather than just using it (or using something like
> sqlite for
> > the index storage)?
>
> It looks like Marc-Andre is following our work on the Eclipse CDT indexer.
> We found databases to be just too slow.


That is somewhat surprising. Which db's did you benchmark against?


> Also, forcing the C++ language model to fit into a bunch of tables or
> key/value pairs just didn't make that much sense in the end. The data is
> very complex.
>
> Instead it's better to think of this as a big graph data structure that
> just happens to be backed by memory mapped file store. Clients generally
> deal directly with pointers into that data structure and follow pointers in
> the graph. The BTrees help speed up that navigation at various nodes in the
> graph. It's super fast.
>
> Doug.
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20170811/52445a79/attachment.html>