On Jul 24, 2009, at 4:34 PM, Daniel Dunbar wrote: > 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.
I was pretty unclear :( I, too, favor the O(N) solution even if it's slightly slower for small N. Otherwise, some idiot [*] is going to come up with a template metaprogram somewhere that exposes the O(N^2) behavior, and we'll get flogged for it. > In addition, all we need is a SmallDenseMap ADT and the latter should > be categorically better than the former, and probably less code. A SmallDenseMap ADT would be great. Even a SmallPtrMap to complement SmallPtrSet would be extremely useful. - Doug [*] Naturally, I have such a template metaprogram. My preferred implementation of C++0x's tuple has N direct base classes, where N is the length of the tuple. Since tuple is a common metaprogramming primitive, that N can get quite large. _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
