This project contains a large, real-world class hierarchy benchmark with 15246 classes and 63963 different derivation paths. The benchmark was previously used in the literature to study efficiency of type inclusion testing and dispatching techniques [1,2,3,4] and was maintained by Karel Driesen (see his original readme).

While working on Mach7 [5,6] we've tried to find this benchmark for our own experiments, but the original links were broken. Eventually we could dig up a version of it from archive.org, We revive it here for researchers to use, along with the translator to C++, we wrote for our own experiments.

While all the hierarchies were man-made, not all class hierarchies originated from C++, and sometimes used certain kinds of inheritance, not allowed in C++. This is why during conversion to C++, COU parser prunes inaccessible base classes (direct base class that is already an indirect base class) when used with repeated inheritance in order to satisfy semantic requirements of C++. It maintains the same number of virtual functions present in each class as well as the number of data members; the benchmarks, however, did not preserve the exact types of those.

The following table shows various parameters of the class hierarchies in each benchmark, after their adoption to C++:

The number of paths represents the number of distinct inheritance paths from the classes in the hierarchy to the roots of the hierarchy. This number reflects the number of possible subobjects in the hierarchy. The roots listed in the table are classes with no base classes. We will subsequently use the term "non-leaf" to refer to the possible root of a subhierarchy. Leafs are classes with no children, while "both" refers to utility classes that are both roots and leafs and thus neither have base nor derived classes. The average for the number of parents and the number of children were computed only among the classes having at least one parent or at least one child correspondingly.

71% of the classes in the entire benchmarks suite were leaf classes. Out of the 4369 non-leaf classes, 36% were spawning a subhierarchy of only 2 classes (including the root), 15% -- a subhierarchy of 3 classes, 10% of 4, 7% of 5 and so forth. Turning this into a cumulative distribution, M of subhierarchies had more than N classes in them:

Which means 1% of subhierarchies had more than 700 classes in them, 3% of subhierarchies had more than 110 classes, 5% of subhierarchies had more than 50 classes, 10% of subhierarchies had more than 20 classes, 20% of subhierarchies had more than 10 classes, 25% of hierarchies had more than 7 classes, only 50% of hierarchies had more than 3 classes and 64% -- more than 2.

1. J. Vitek, R. N. Horspool, and A. Krall. Efficient type inclusion tests. In Proc. of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, OOPSLA '97, pages 142-157, New York, NY, USA, 1997. ACM.
2. A. Krall, J. Vitek, and R. N. Horspool. Near optimal hierarchical encoding of types. In In Proc. European Conference on Object-Oriented Programming, ECOOP'97, Lecture Notes in Computer Science, pages 128-145. Springer-Verlag, 1997.
3. Y. Zibin and J. Y. Gil. Efficient subtyping tests with PQencoding. In Proc. of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, OOPSLA '01, pages 96-107, New York, NY, USA, 2001. ACM.
4. R. Ducournau. Perfect hashing as an almost perfect subtype test. ACM Trans. Program. Lang. Syst., 30(6):33:1-33:56, Oct. 2008. ISSN 0164-0925.
5. Y. Solodkyy, G. Dos Reis, and B. Stroustrup. Open and efficient type switch for C++. In Proc. OOPSLA'12, pp 963-982. ACM.
6. Y. Solodkyy, G. Dos Reis, and B. Stroustrup. Open pattern matching for C++. In Proc. GPCE'13. ACM, October 2013.