On Fri, Oct 18, 2013 at 8:35 PM, Rafael Espíndola < [email protected]> wrote:
> > Currently decl chaining is O(n). We use a circular singly linked list > > that points to the previous element and has a bool to say if we are > > the first element (and actually point to the last). > > > > Adding a new decl is O(n) because we have to find the first element by > > walking the prev links. One way to make this O(1) that is sure to work > > is a doubly linked list, but that would be very wasteful in memory. > What about just storing both the first and the last and keeping the direction as it is now? > > > > What this patch does is reverse the list so that a decl points to the > > next decl (or to the first if it is the last). With this chaining > > becomes O(1). The flip side is that getPreviousDecl is now O(n). > > The patch still needs work, but I managed to convert all calls to > getPreviousDecl in the above testcase. In my machine the clang -cc1 > time on it goes from 4.819s to 0.865s now (5.57x faster). > > > Cheers, > Rafael > > _______________________________________________ > 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
