On Tue, Jul 21, 2009 at 1:32 PM, Fariborz Jahanian<[email protected]> wrote: > On Jul 21, 2009, at 1:16 PM, Daniel Dunbar wrote: >> On Tue, Jul 21, 2009 at 10:08 AM, Douglas Gregor<[email protected]> wrote: >>> On Jul 9, 2009, at 1:00 PM, Fariborz Jahanian wrote: >>>> >>>> + int Last = AllBaseOrMembers.size(); >>>> + int curIndex = 0; >>>> + CXXBaseOrMemberInitializer *PrevMember = 0; >>>> + for (unsigned i = 0; i < NumMemInits; i++) { >>>> + CXXBaseOrMemberInitializer *Member = >>>> + static_cast<CXXBaseOrMemberInitializer*>(MemInits[i]); >>>> + void *MemberInCtorList; >>>> + if (Member->isBaseInitializer()) >>>> + MemberInCtorList = Member->getBaseClass(); >>>> + else >>>> + MemberInCtorList = Member->getMember(); >>>> + >>>> + int j; >>>> + for (j = curIndex; j < Last; j++) >>>> + if (MemberInCtorList == AllBaseOrMembers[j]) >>>> + break; >>> >>> It's too bad that this is O(N^2), but I can't think of a way to make >>> it faster without having the ability to sort the initializer list by >>> its initialization-position. Besides, the initializer list will >>> generally be short. >> >> Am I missing something, why not just create a DenseMap from >> AllBaseOrMembers[j] -> j? (Assuming the contents of that array are >> distinct). >> >> (A SmallDenseMap ideally, if we happened to have that ADT) > > I think Doug was making the point that a very small list of initializers may > not justify > changing the algorithm to make it faster. I don't think setting up a > DenseMap and populating it > justifies finding a uniqueness of 4 or 5 elements.
Well, I can't speak for what point Doug was making, but personally given a choice between fast and O(N^2) and slightly slower and O(N), I think the correct choice in a compiler is always the latter. In addition, all we need is a SmallDenseMap ADT and the latter should be categorically better than the former, and probably less code. - Daniel _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
