<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Apr 9, 2015 at 1:15 PM, Richard <span dir="ltr"><<a href="mailto:legalize@xmission.com" target="_blank" class="cremed">legalize@xmission.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
In article <CAOsfVvmev4Y7Q=Wr=<a href="mailto:8RJQFs49S94J0OE97-iJyaWRZVvCD60Jg@mail.gmail.com" class="cremed">8RJQFs49S94J0OE97-iJyaWRZVvCD60Jg@mail.gmail.com</a>>,<br>
<span class=""> Manuel Klimek <<a href="mailto:klimek@google.com" class="cremed">klimek@google.com</a>> writes:<br>
<br>
> We actually went from a more expression templatey to a less expression<br>
> templatey design.<br>
<br>
</span>Interesting! So far, I feel like what I've been trying to match is<br>
completely expressable at compile-time and deferring things to runtime<br>
is making things slow.</blockquote><div><br></div><div>What I found is that using type erasure actually sped up clang-tidy considerably.</div><div>The template approach we used at the beginning was causing a huge amount of code to be generated. More code == slower code.</div><div>Type erasure allowed to collapse common things into a single implementation.</div><div>In any case, most of the matching happens dynamically anyway because the type of the children of nodes is not statically known. They are Expr or Decl and we have to dyn_cast<> them anyway.</div><div><br></div><div>I optimized the runtime cost of the matchers until they stopped being the bottle neck.</div><div>Right now, most of the runtime comes from the parsing phase, memory allocation due to caching and hits found in uninteresting code.</div><div>It doesn't seem that running the matchers themselves is the slow section anymore.</div><div>For most compilation units, parsing is still more than half the walltime.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> This seems to be consistent with the findings<br>
of the imlpementors of OCLint and why they make the statement I quoted<br>
earlier.<br>
<span class=""><br>
> On Tue, Apr 7, 2015, 3:31 PM Sean Silva <<a href="mailto:chisophugis@gmail.com" class="cremed">chisophugis@gmail.com</a>> wrote:<br>
><br>
> > Although I'm mostly an armchair spectator right now w.r.t. clang tooling<br>
> > stuff, I think that use cases like clang-query and in general the dynamic<br>
> > AST matchers suggests that expression templates aren't a very good solution<br>
> > because they will require reimplementing things from scratch for the<br>
> > "dynamic" case.<br>
<br>
</span>When I look at a library like Boost.Spirit that heavily uses<br>
expression templates I don't see how I'm losing the dynamic case at<br>
all. Maybe I'm misunderstanding what you're saying.<br>
<span class=""><br>
> Sam has worked on making clang tidy use cases faster. I<br>
> expect in the end the right thing is to do less duplicate work which I<br>
> think we will be able to do with modules.<br></span></blockquote><div><br></div><div>I have done work on many fronts, like:</div><div> - Skip redundant work. Eg: filter the matchers by type and run only the ones that are compatible.</div><div> - Reduce overhead of the system. Eg: collapse virtual functions to avoid multiple consecutive vtable jumps.</div><div> - Extract common ops: Eg: move the type checking outside of the virtual dispatch.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
<br>
</span>While modules are nice, I don't think it's reasonable to expect that<br>
modules will be deployed over a significant chunk of the world's C++<br>
code anytime soon. So it doesn't seem practical to say "modules will<br>
fix this".<br>
<span class=""><br>
> > Regardless, I don't think that the primary bottleneck is not doing enough<br>
> > at compile time (of the matchers). Rather we aren't effectively indexing<br>
> > the underlying data set we are trying to query (right now, we're more like<br>
</span>> > grep and less like google).</blockquote><div><br></div><div>Right now we do a single pass on the AST to run all checks.</div><div>Adding an indexing step would not help much, unless we can do it directly in the parsing.</div><div>Maybe with modules we could add an index into the module and avoid the full AST traversal.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> [...] (a<br>
<span class="">> > good example is using a trigram index to prune the search space for regexp<br>
> > matching <a href="http://swtch.com/~rsc/regexp/regexp4.html" target="_blank" class="cremed">http://swtch.com/~rsc/regexp/regexp4.html</a>).<br>
> ><br>
> > * "multiple" here also scales numerically with the number of TU's. An<br>
> > index can avoid visiting certain TU's at all in many cases.<br>
<br>
</span>Thanks for that link Sean, that was an interesting read. I couldn't<br>
find it "live" on the web, but was able to get it via the wayback<br>
machine on <a href="http://archive.org" target="_blank" class="cremed">archive.org</a>.<br>
<div class="HOEnZb"><div class="h5">--<br>
"The Direct3D Graphics Pipeline" free book <<a href="http://tinyurl.com/d3d-pipeline" target="_blank" class="cremed">http://tinyurl.com/d3d-pipeline</a>><br>
The Computer Graphics Museum <<a href="http://ComputerGraphicsMuseum.org" target="_blank" class="cremed">http://ComputerGraphicsMuseum.org</a>><br>
The Terminals Wiki <<a href="http://terminals.classiccmp.org" target="_blank" class="cremed">http://terminals.classiccmp.org</a>><br>
Legalize Adulthood! (my blog) <<a href="http://LegalizeAdulthood.wordpress.com" target="_blank" class="cremed">http://LegalizeAdulthood.wordpress.com</a>><br>
_______________________________________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@cs.uiuc.edu" class="cremed">cfe-dev@cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev" target="_blank" class="cremed">http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</a><br>
</div></div></blockquote></div><br></div></div>