On Wed, Mar 25, 2015 at 6:47 PM, Sean Silva <[email protected]> wrote:
> On Wed, Mar 25, 2015 at 6:10 PM, Richard Smith <[email protected]> > wrote: > >> On Wed, Mar 25, 2015 at 6:01 PM, Sean Silva <[email protected]> >> wrote: >> >>> On Wed, Mar 25, 2015 at 5:56 PM, Sean Silva <[email protected]> >>> wrote: >>> >>>> Awesome performance numbers! >>>> >>>> When we discussed this previously, one alternative (should we ever need >>>> it; not sure we do) if the memory overhead is excessive is to use a >>>> waymarking scheme to find the canonical decl in constant time (unlike Use >>>> http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm >>>> , we don't have random access, but we can instead take advantage of the >>>> stable address of the canonical decl and directly store bits of the stable >>>> address). >>>> >>> >>> D'oh, just saw the review thread and >>> https://llvm.org/bugs/show_bug.cgi?id=21264 where Richard suggests a >>> more elaborate (but not guaranteed constant time?) scheme. >>> >> >> It's guaranteed constant time to get the canonical decl (because every >> decl either is it or has a pointer to it) and to find the previous decl >> (although the constant on that is a bit higher if there are multiple >> redeclarations, as is the memory usage). >> > > Doesn't your suggested scheme require a hash table lookup for > getPreviousDecl? That isn't guaranteed constant time. > Well sure, but not in an interesting way; that is not the pathological case we're trying to avoid. I was thinking of something cruder like having the low two bits of the > pointers in the chain be {0,bit from address} or {1,bit from address}, with > {1,bit from address} meaning "if you have already collected 32/64 bits of > the address, go ahead and reinterpret them as a pointer to the canonical > decl". That has constant time finding of the canonical decl, constant time > previous decl, and doesn't require any auxiliary data structures on the > side. Although I'm not sure how practical of a "constant time" 10's of > linked-list follows are (and not to mention maintaining that structure, > which takes a similar "constant time"). > The expected common case is a short redeclaration chain; I would expect most of the gain for non-modules builds comes from reducing the cost from walking < 5 PreviousDecl links down to walking zero of them, and your proposed scheme doesn't help for that case. -- Sean Silva > > >> >> >>> -- Sean Silva >>> >>> >>>> >>>> -- Sean Silva >>>> >>>> On Wed, Mar 25, 2015 at 4:18 PM, Manuel Klimek <[email protected]> >>>> wrote: >>>> >>>>> Author: klimek >>>>> Date: Wed Mar 25 18:18:30 2015 >>>>> New Revision: 233228 >>>>> >>>>> URL: http://llvm.org/viewvc/llvm-project?rev=233228&view=rev >>>>> Log: >>>>> Keep track of canonical decls in Redeclarable. >>>>> >>>>> More than 2x speedup on modules builds with large redecl chains. >>>>> Roughly 15-20% speedup on non-modules builds for very large TUs. >>>>> Between 2-3% cost in memory on large TUs. >>>>> >>>>> Modified: >>>>> cfe/trunk/include/clang/AST/Decl.h >>>>> cfe/trunk/include/clang/AST/Redeclarable.h >>>>> cfe/trunk/lib/Serialization/ASTReaderDecl.cpp >>>>> >>>>> Modified: cfe/trunk/include/clang/AST/Decl.h >>>>> URL: >>>>> http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/Decl.h?rev=233228&r1=233227&r2=233228&view=diff >>>>> >>>>> ============================================================================== >>>>> --- cfe/trunk/include/clang/AST/Decl.h (original) >>>>> +++ cfe/trunk/include/clang/AST/Decl.h Wed Mar 25 18:18:30 2015 >>>>> @@ -3738,8 +3738,6 @@ void Redeclarable<decl_type>::setPreviou >>>>> assert(RedeclLink.NextIsLatest() && >>>>> "setPreviousDecl on a decl already in a redeclaration >>>>> chain"); >>>>> >>>>> - decl_type *First; >>>>> - >>>>> if (PrevDecl) { >>>>> // Point to previous. Make sure that this is actually the most >>>>> recent >>>>> // redeclaration, or we can build invalid chains. If the most >>>>> recent >>>>> >>>>> Modified: cfe/trunk/include/clang/AST/Redeclarable.h >>>>> URL: >>>>> http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/Redeclarable.h?rev=233228&r1=233227&r2=233228&view=diff >>>>> >>>>> ============================================================================== >>>>> --- cfe/trunk/include/clang/AST/Redeclarable.h (original) >>>>> +++ cfe/trunk/include/clang/AST/Redeclarable.h Wed Mar 25 18:18:30 2015 >>>>> @@ -121,14 +121,15 @@ protected: >>>>> /// >>>>> /// If there is only one declaration, it is <pointer to self, true> >>>>> DeclLink RedeclLink; >>>>> + decl_type *First; >>>>> >>>>> decl_type *getNextRedeclaration() const { >>>>> return RedeclLink.getNext(static_cast<const decl_type *>(this)); >>>>> } >>>>> >>>>> public: >>>>> - Redeclarable(const ASTContext &Ctx) >>>>> - : RedeclLink(LatestDeclLink(Ctx)) {} >>>>> + Redeclarable(const ASTContext &Ctx) >>>>> + : RedeclLink(LatestDeclLink(Ctx)), First(static_cast<decl_type >>>>> *>(this)) {} >>>>> >>>>> /// \brief Return the previous declaration of this declaration or >>>>> NULL if this >>>>> /// is the first declaration. >>>>> @@ -144,21 +145,11 @@ public: >>>>> >>>>> /// \brief Return the first declaration of this declaration or >>>>> itself if this >>>>> /// is the only declaration. >>>>> - decl_type *getFirstDecl() { >>>>> - decl_type *D = static_cast<decl_type*>(this); >>>>> - while (D->getPreviousDecl()) >>>>> - D = D->getPreviousDecl(); >>>>> - return D; >>>>> - } >>>>> + decl_type *getFirstDecl() { return First; } >>>>> >>>>> /// \brief Return the first declaration of this declaration or >>>>> itself if this >>>>> /// is the only declaration. >>>>> - const decl_type *getFirstDecl() const { >>>>> - const decl_type *D = static_cast<const decl_type*>(this); >>>>> - while (D->getPreviousDecl()) >>>>> - D = D->getPreviousDecl(); >>>>> - return D; >>>>> - } >>>>> + const decl_type *getFirstDecl() const { return First; } >>>>> >>>>> /// \brief True if this is the first declaration in its >>>>> redeclaration chain. >>>>> bool isFirstDecl() const { return RedeclLink.NextIsLatest(); } >>>>> >>>>> Modified: cfe/trunk/lib/Serialization/ASTReaderDecl.cpp >>>>> URL: >>>>> http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Serialization/ASTReaderDecl.cpp?rev=233228&r1=233227&r2=233228&view=diff >>>>> >>>>> ============================================================================== >>>>> --- cfe/trunk/lib/Serialization/ASTReaderDecl.cpp (original) >>>>> +++ cfe/trunk/lib/Serialization/ASTReaderDecl.cpp Wed Mar 25 18:18:30 >>>>> 2015 >>>>> @@ -2106,6 +2106,7 @@ ASTDeclReader::VisitRedeclarable(Redecla >>>>> // which is the one that matters and mark the real previous >>>>> DeclID to be >>>>> // loaded & attached later on. >>>>> D->RedeclLink = Redeclarable<T>::PreviousDeclLink(FirstDecl); >>>>> + D->First = FirstDecl->getCanonicalDecl(); >>>>> } >>>>> >>>>> // Note that this declaration has been deserialized. >>>>> @@ -2209,6 +2210,7 @@ void ASTDeclReader::mergeRedeclarable(Re >>>>> // of the existing declaration, so that this declaration has the >>>>> // appropriate canonical declaration. >>>>> D->RedeclLink = Redeclarable<T>::PreviousDeclLink(ExistingCanon); >>>>> + D->First = ExistingCanon; >>>>> >>>>> // When we merge a namespace, update its pointer to the first >>>>> namespace. >>>>> // We cannot have loaded any redeclarations of this declaration >>>>> yet, so >>>>> @@ -2828,6 +2830,7 @@ void ASTDeclReader::attachPreviousDeclIm >>>>> Redeclarable<DeclT> *D, >>>>> Decl *Previous, Decl >>>>> *Canon) { >>>>> D->RedeclLink.setPrevious(cast<DeclT>(Previous)); >>>>> + D->First = cast<DeclT>(Previous)->First; >>>>> } >>>>> namespace clang { >>>>> template<> >>>>> @@ -2838,6 +2841,7 @@ void ASTDeclReader::attachPreviousDeclIm >>>>> FunctionDecl *PrevFD = cast<FunctionDecl>(Previous); >>>>> >>>>> FD->RedeclLink.setPrevious(PrevFD); >>>>> + FD->First = PrevFD->First; >>>>> >>>>> // If the previous declaration is an inline function declaration, >>>>> then this >>>>> // declaration is too. >>>>> >>>>> >>>>> _______________________________________________ >>>>> cfe-commits mailing list >>>>> [email protected] >>>>> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits >>>>> >>>> >>>> >>> >>> _______________________________________________ >>> cfe-commits mailing list >>> [email protected] >>> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits >>> >>> >> >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
