gribozavr added inline comments.
================
Comment at: clang/lib/AST/ASTContext.cpp:584
+ // terminating early.
+ for (auto CIt = RawComments.begin(); CIt != RawComments.end(); ++CIt) {
+ RawComment *C = *CIt;
----------------
jkorous wrote:
> gribozavr wrote:
> > Scanning all comments for every decl? Isn't that O(n^2)?
> >
> > Also logic duplication below. I was expecting a call to
> > `getRawCommentForDeclNoCache`, with an appropriate flag to disable loading
> > external comments (it is a low-level API, users generally don't call it).
> The important thing is that the expensive operation is source location
> decomposition. That's why I cache everything - `GetCachedCommentBegin` etc.
>
> So while you're right that iteration-wise it's O(iteration*c*d) it`s actually
> O(decompose*c + decompose*d) because of the caching. The current code (which
> is sorting all the comments) is at least O(decompose*c*ln(c)) once you have
> more comments than `sqrt(300)` (==`MagicCacheSize` in
> `SourceManager::getInBeforeInTUCache()`).
>
> That being said - you're right that just not-loading external comments in
> `getRawCommentForDeclNoCache` definitely has it's appeal. I'm running a test
> now get some idea about performance of both approaches.
>
> BTW in theory we could also do one of these:
> 1. Allow clients to transparently set `MagicCacheSize` in
> `SourceManager::getInBeforeInTUCache()` which is used for SourceLocation
> sorting (`BeforeThanCompare<RawComment>`) is currently hard-coded to 300
> while we are comparing ~100k x ~100k locations.
> 2. Change caching strategies in `SourceManager::getFileID` and
> `SourceManager::getLineNumber`.
> So while you're right that iteration-wise it's O(iteration*c*d) it`s actually
> O(decompose*c + decompose*d) because of the caching.
The cost of decomposing is non-trivial, but the cost of each iteration is still
at least a hash table lookup.
> That being said - you're right that just not-loading external comments in
> getRawCommentForDeclNoCache definitely has it's appeal. I'm running a test
> now get some idea about performance of both approaches.
Reopening, waiting for the results.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D61103/new/
https://reviews.llvm.org/D61103
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
