On Fri, Jan 16, 2015 at 11:56 AM, Nathan Sidwell <[email protected]> wrote: > On 01/14/15 23:16, Richard Smith wrote: >> >> On Wed, Dec 24, 2014 at 8:46 AM, Nathan Sidwell <[email protected]> wrote: >>> >>> [*] As an aside, I wonder if completing the std:set with the direct bases >>> and keeping it with the RecordDecl would speed up base conversion checks >>> -- >>> the base conversion machinery could use it for a quick 'is this even >>> worth >>> figuring out' check. >> >> >> It shouldn't be a std::set; node-based containers are particularly bad >> for malloc traffic. Also, for a deep hierarchy, we'd end up storing >> O(N^2) nodes, which seems unfortunate (we already get that as a time >> cost with this patch; it'd be nice to avoid that too). > > I'm not sure what your N is here. For a hierarchy I'd expect O(N^M) size, > where N is the mean number of direct bases and M is the mean depth. Anyway, > it'd be a time-space tradeoff -- we're already doing an O(whatever) walk on > every class-related overload argument check. I just don't know how much > that costs in performance.
N here is the number of classes. As a worst case, imagine a long inheritance chain; class I would store a set of I-1 elements and we store N^2 set elements overall. As you say, the typical case should be significantly better. >> I wonder if >> there's some relatively compact way of representing this information >> that supports fast query and fast updates... > > A pointer hash table would suffice, I'd've thought. We don't care about > ordering, just uniqueness. That'd have O(1) lookup and insertion costs. That's still a quadratic storage overhead. So anyway... the problem of finding inaccessible base classes is equivalent to that of computing the transitive reduction of the inheritance graph, which takes O(CD) time where C is the number of classes and D is the number of base class specifiers; we're within a logarithmic factor of that (and in practice the number of base specifiers we need to explore will be small), so I think this is algorithmically fine. _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
