<div><div>Hello.</div><div> </div><div>Just 2 cents from my USR experience:</div><div>1. USRs in some cases different for entities that are the same in C++. Namely it takes into account constness of by-value fuction arguments where C++ Front-End ignores them.</div><div>"int foo(const int);" and "int foo(int);" are declarations for the same function in AST, but will have different USRs.</div><div> </div><div>2. Also be careful with USRs and preprocessor macros: in my experience if macro is #undef'ed it looses its USR because USR generation relies on PreprocessingRecord which clears info upon #undef.</div><div> </div><div>Note: My experience is with Clang 4.0 and earlier, so maybe this is fixed already.</div><div> </div><div>Regards,</div><div>Serge Preis</div></div><div> </div><div> </div><div> </div><div>11.08.2017, 23:17, "Alex L via cfe-dev" <cfe-dev@lists.llvm.org>:</div><blockquote type="cite"><div> <div> <div>On 11 August 2017 at 17:09, Doug Schaefer via cfe-dev <span><<a target="_blank" href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>></span> wrote:<blockquote style="margin:0 0 0 0.8ex;border-left:1px #ccc solid;padding-left:1ex;"><div lang="EN-US" link="blue" vlink="purple"><div><p><span style="font-family:calibri,sans-serif;font-size:11pt;">Sorry gang, Outlook isn’t treating this thread very well. I’ll have to top post my response.</span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;">The CDT indexer and database were written in 2005 so the data is long gone and we’re talking about different database technologies anyway. All I remember was it was slower by multiple orders of magnitude on writes. And that stopped my investigation right there. At the time I was trying to get a full index of the Firefox source down from an hour to a few minutes and incremental indexing times down to less than a second (thanks to the header caching). The DB was taking me in the other direction.</span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;">I’m just not sure architecting for simple lookups is the right approach. Just consider probably the most common use case for clangd, content assist. Given an offset into the file, determine the context/scope of the content and a prefix. You then need to find all matches for that prefix. That’s by no means a simple lookup given all the declarations, type hierarchies, scope hierarchies in play in that context. Finding references is another good one that also requires scope analysis to make sure you’re actually returning references to that exact definition and not just something that happens to have the same name. The CDT index has links back and forth between these things.</span></p><p> </p></div></div></blockquote><div> </div><div>Clang shouldn't query by name when looking up references, instead USRs should be used. The USRs deal with scopes correctly (Hence the U in USR). </div><div> </div><blockquote style="margin:0 0 0 0.8ex;border-left:1px #ccc solid;padding-left:1ex;"><div lang="EN-US" link="blue" vlink="purple"><div><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;">Again, I’m just relaying my experience haven built one of these things before. And it was a long time ago. All avenues are worth exploring.</span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;">Doug.</span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4pt;"><div><div style="border:none;border-top:solid #e1e1e1 1pt;padding:3pt 0in 0in 0in;"><p><strong><span style="font-family:calibri,sans-serif;font-size:11pt;">From:</span></strong><span style="font-family:calibri,sans-serif;font-size:11pt;"> Manuel Klimek [mailto:<a target="_blank" href="mailto:klimek@google.com">klimek@google.com</a>]<br /><strong>Sent:</strong> Friday, August 11, 2017 10:59 AM</span></p><div><div><br /><strong>To:</strong> Doug Schaefer <<a target="_blank" href="mailto:dschaefer@blackberry.com">dschaefer@blackberry.com</a>>; David Chisnall <<a target="_blank" href="mailto:David.Chisnall@cl.cam.ac.uk">David.Chisnall@cl.cam.ac.uk</a>>; Marc-André Laperle <<a target="_blank" href="mailto:marc-andre.laperle@ericsson.com">marc-andre.laperle@ericsson.com</a>><br /><strong>Cc:</strong> via cfe-dev <<a target="_blank" href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>><br /><strong>Subject:</strong> Re: [cfe-dev] Adding indexing support to Clangd</div></div><p> </p></div></div><div><div><p> </p><div><div><div><p>On Fri, Aug 11, 2017 at 4:50 PM Doug Schaefer <<a target="_blank" href="mailto:dschaefer@blackberry.com">dschaefer@blackberry.com</a>> wrote:</p></div><blockquote style="border:none;border-left:solid #cccccc 1pt;padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in;"><div><div><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4pt;"><div><div style="border:none;border-top:solid #e1e1e1 1pt;padding:3pt 0in 0in 0in;"><p><strong><span style="font-family:calibri,sans-serif;font-size:11pt;">From:</span></strong><span style="font-family:calibri,sans-serif;font-size:11pt;"> Manuel Klimek [mailto:<a target="_blank" href="mailto:klimek@google.com">klimek@google.com</a>]<br /><strong>Sent:</strong> Friday, August 11, 2017 4:54 AM<br /><strong>To:</strong> Doug Schaefer <<a target="_blank" href="mailto:dschaefer@blackberry.com">dschaefer@blackberry.com</a>>; David Chisnall <<a target="_blank" href="mailto:David.Chisnall@cl.cam.ac.uk">David.Chisnall@cl.cam.ac.uk</a>>; Marc-André Laperle <<a target="_blank" href="mailto:marc-andre.laperle@ericsson.com">marc-andre.laperle@ericsson.com</a>><br /><strong>Cc:</strong> via cfe-dev <<a target="_blank" href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>></span></p></div></div></div></div></div><div><div><div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4pt;"><div><div style="border:none;border-top:solid #e1e1e1 1pt;padding:3pt 0in 0in 0in;"><p><br /><span style="font-family:calibri,sans-serif;font-size:11pt;"><strong>Subject:</strong> Re: [cfe-dev] Adding indexing support to Clangd</span></p></div></div></div></div></div><div><div><div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4pt;"><div><div><div><p>On Thu, Aug 10, 2017 at 5:57 PM Doug Schaefer via cfe-dev <<a target="_blank" href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>> wrote:</p></div><blockquote style="border:none;border-left:solid #cccccc 1pt;padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-top:5pt;margin-right:0in;margin-bottom:5pt;"><p>> -----Original Message-----<br />> From: Dr D. Chisnall [mailto:<a target="_blank" href="mailto:dc552@hermes.cam.ac.uk">dc552@hermes.cam.ac.uk</a>] On Behalf Of David<br />> Chisnall<br />> Sent: Thursday, August 10, 2017 6:10 AM<br />> To: Marc-André Laperle <<a target="_blank" href="mailto:marc-andre.laperle@ericsson.com">marc-andre.laperle@ericsson.com</a>><br />> Cc: via cfe-dev <<a target="_blank" href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>>; <a target="_blank" href="mailto:zeratul976@hotmail.com">zeratul976@hotmail.com</a>; Doug<br />> Schaefer <<a target="_blank" href="mailto:dschaefer@blackberry.com">dschaefer@blackberry.com</a>><br />> Subject: Re: [cfe-dev] Adding indexing support to Clangd<br />><br />> On 8 Aug 2017, at 18:52, Marc-André Laperle via cfe-dev <cfe-<br />> <a target="_blank" href="mailto:dev@lists.llvm.org">dev@lists.llvm.org</a>> wrote:<br />> ><br />> > --ClangdIndexStorage--<br />> > malloc-like interface that allocates/frees data blocks of variable sizes on<br />> disk. The blocks can contain ints, shorts, strings, pointers (i.e. file offsets),<br />> etc. The data is cached in 4K pieces so that local and repeated accesses are all<br />> done quickly, in memory.<br />> > Clangd mallocs and writes its index model objects using this.<br />> ><br />> > --BTree--<br />> > A pretty classic BTree implementation. Used to speed up lookup (symbol<br />> names, file names). It allocates its nodes using ClangdIndexStorage therefore<br />> it is stored on disk. Keys are actually records in ClangdIndexStorage so you<br />> can really think of the BTree as a collection of sorted pointers (sorted<br />> according to a provided comparator).<br />><br />> This sounds very like bdb.  Is there a reason that we’re reimplementing a<br />> large chunk of bdb, rather than just using it (or using something like sqlite for<br />> the index storage)?<br /><br />It looks like Marc-Andre is following our work on the Eclipse CDT indexer. We found databases to be just too slow.</p></blockquote><div><p> </p></div><div><p>That is somewhat surprising. Which db's did you benchmark against?</p><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p></div><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p></div></div></div></div></div><div><div><div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4pt;"><div><div><p><span style="font-family:calibri,sans-serif;font-size:11pt;">This was many years ago and we were trying Apache Derby (since Eclipse is written in Java). And at the time the biggest issue was write performance totally destroying any gains we made with header caching. But that may have just been Derby.</span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><p><span style="font-family:calibri,sans-serif;font-size:11pt;">Though I think the bigger issue is that the language model is a graph which doesn’t fit naturally in tables. You’ll end up spending more time fighting that than building out your own data structures. But that’s just my experience.</span></p></div></div></div></div></div></blockquote><div><p> </p></div><div><p>Yea, the language model not fitting into tables well does match my intuition, but for simple queries, I'd have expected a db to be fast enough with room to spare. Would be curious about more details / numbers.</p></div><div><p> </p></div><div><p> </p></div><blockquote style="border:none;border-left:solid #cccccc 1pt;padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in;"><div><div><div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4pt;"><div><div><p><span style="font-family:calibri,sans-serif;font-size:11pt;"> </span></p><div><p> </p></div><blockquote style="border:none;border-left:solid #cccccc 1pt;padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-top:5pt;margin-right:0in;margin-bottom:5pt;"><p>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.<br /><br />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.<br /><br />Doug.<br />_______________________________________________<br />cfe-dev mailing list<br /><a target="_blank" href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br /><a target="_blank" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a></p></blockquote></div></div></div></div></div></blockquote></div></div></div></div></div></div></div><br />_______________________________________________<br />cfe-dev mailing list<br /><a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br /><a target="_blank" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><br /> </blockquote></div></div></div>,<p>_______________________________________________<br />cfe-dev mailing list<br /><a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br /><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a></p></blockquote>