<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Manuel Klimek [mailto:klimek@google.com]
<br>
<b>Sent:</b> Friday, August 11, 2017 4:54 AM<br>
<b>To:</b> Doug Schaefer <dschaefer@blackberry.com>; David Chisnall <David.Chisnall@cl.cam.ac.uk>; Marc-André Laperle <marc-andre.laperle@ericsson.com><br>
<b>Cc:</b> via cfe-dev <cfe-dev@lists.llvm.org><br>
<b>Subject:</b> Re: [cfe-dev] Adding indexing support to Clangd<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<p class="MsoNormal">On Thu, Aug 10, 2017 at 5:57 PM Doug Schaefer via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">> -----Original Message-----<br>
> From: Dr D. Chisnall [mailto:<a href="mailto:dc552@hermes.cam.ac.uk" target="_blank">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 href="mailto:marc-andre.laperle@ericsson.com" target="_blank">marc-andre.laperle@ericsson.com</a>><br>
> Cc: via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>>;
<a href="mailto:zeratul976@hotmail.com" target="_blank">zeratul976@hotmail.com</a>; Doug<br>
> Schaefer <<a href="mailto:dschaefer@blackberry.com" target="_blank">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 href="mailto:dev@lists.llvm.org" target="_blank">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.<o:p></o:p></p>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">That is somewhat surprising. Which db's did you benchmark against?<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">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 href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><o:p></o:p></p>
</blockquote>
</div>
</div>
</div>
</div>
</body>
</html>