[cfe-dev] RFC: Symbol index for Clangd design proposal

Kirill Bobyrev via cfe-dev cfe-dev at lists.llvm.org
Tue Jul 17 22:43:09 PDT 2018

Hi Dean,

Thank you very much for the suggestion! Having an index which can be
searched and compacted at the same time would undoubtedly be amazing. We
would certainly consider it and think about how this could fit into the

Right now, however, I think we should focus on immutable index model. The
most building blocks (searching/query routine) are unlikely to change in
the future, so we would like to start with these. The plan is to implement
an immutable index and rebuild it once in a while and to get an idea of
whether it is a performance bottleneck or not. Once everything is in place
and we could get an idea of what parts of interaction with symbol index
cause performance overhead, we can start optimizing and changing these

As Eric and Marc-Andre mentioned before, we are looking into efficient
index building, too, and I think both problems are connected and I think we
should investigate possible solutions.

Kind regards,
Kirill Bobyrev

On Tue, Jul 17, 2018 at 6:19 AM Dean Michael Berris <dean.berris at gmail.com>

> Hi Kirill,
> Thanks for posting this!
> I wondered while reading the proposal whether you've considered the
> model used by Bigtable [0] where you can have "compactions" or
> re-indexing in an incremental manner. You can then do the trigraph
> indexing be done quickly, and maintain different versions of the
> trigraph indexes that can be concurrently searched while compactions
> are happening in the background as new changes are committed through
> the LSP API. This will always be a trade-off, but merging the trigraph
> indices can happen independently without resorting to mutating the
> actual index.
> Cheers
> [0] https://ai.google/research/pubs/pub27898
> On Mon, Jul 16, 2018 at 8:04 PM Kirill Bobyrev via cfe-dev
> <cfe-dev at lists.llvm.org> wrote:
> >
> > Dear LLVM Community,
> >
> > over the past few weeks, we (Google C++ Language Tools Team) have been
> working on the efficient symbol index proposal for Clangd. The goal is to
> improve overall Clangd performance by reducing the latency of different
> kinds of symbol search queries, such as the ones used for code completion.
> The plan is to follow the proposed design and replace existing
> implementation by the end of September.
> >
> > We are happy to get feedback and comments on the proposal: suggestions
> are welcome!
> >
> > The link to design document:
> https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiGmJ2jL1UwV91Kyx11gOI/edit?usp=sharing
> >
> > Kind regards,
> > Kirill Bobyrev
> > _______________________________________________
> > cfe-dev mailing list
> > cfe-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
> --
> Dean
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20180718/b2d507b0/attachment.html>

More information about the cfe-dev mailing list