dlaczego ogromna różnica czasu kompilacji między g ++ a clang ++?

Question

Natknąłem się na talk slide, a na stronie 12 znajduje się przykład ilustrujący trudność sprawdzania typu w obecności dziedziczenia.

struct a { 
    typedef int foo; 
}; 
struct a1 : a {}; 
struct a2 : a {}; 
#define X(b, a)    \ 
    struct a##1 : b##1, b##2 {}; \ 
    struct a##2 : b##1, b##2 {}; 
X(a, b) X(b, c) X(c, d) X(d, e) X(e, f) X(f, g) X(g, h) X(h, i) X(i, j) X(j, k) 
    X(k, l) X(l, m) X(m, n) n1::foo main() {} 

Po przerób to jest przekształcona na:

struct a { 
    typedef int foo; 
}; 
struct a1 : a {}; 
struct a2 : a {}; 

struct b1 : a1, a2 {}; 
struct b2 : a1, a2 {}; 
struct c1 : b1, b2 {}; 
struct c2 : b1, b2 {}; 
struct d1 : c1, c2 {}; 
struct d2 : c1, c2 {}; 
struct e1 : d1, d2 {}; 
struct e2 : d1, d2 {}; 
struct f1 : e1, e2 {}; 
struct f2 : e1, e2 {}; 
struct g1 : f1, f2 {}; 
struct g2 : f1, f2 {}; 
struct h1 : g1, g2 {}; 
struct h2 : g1, g2 {}; 
struct i1 : h1, h2 {}; 
struct i2 : h1, h2 {}; 
struct j1 : i1, i2 {}; 
struct j2 : i1, i2 {}; 
struct k1 : j1, j2 {}; 
struct k2 : j1, j2 {}; 
struct l1 : k1, k2 {}; 
struct l2 : k1, k2 {}; 
struct m1 : l1, l2 {}; 
struct m2 : l1, l2 {}; 
struct n1 : m1, m2 {}; 
struct n2 : m1, m2 {}; 
n1::foo main() {} 

kiedy przełożony zg ++ (Debian 4.9.1-16), to jednak pochłaniają dużo czasu:

$ time g++ type_check.cc 
real 29.35s 
user 29.34s 
sys  0.00s 

while clang ++ (clang version 3.4.2 (tags/RELEASE_34/dot2-final), x86_64-unknown-linux-gnu) robi to znacznie szybciej.

$ time clang++ type_check.cc 

real 0.06s 
user 0.04s 
sys  0.00s 

Dlaczego sprawdzić, czy rodzajów foo po obu stronach wielokrotnego dziedziczenia mecz koszt tyle czasu dla gcc/MTK, natomiast nie dla brzękiem?

Answer 1

Myślę, że to z powodu przedwczesnej optymalizacji, a więc błędu.

Myślę, że GCC śledzi dziedziczenie i podobnie jak Clang zapamiętuje klasy bazowe, aby natychmiast zauważyć niejednoznaczności podczas analizowania "następnej klasy bazowej", ale inaczej niż Clang GCC pomija tę fase, jeśli nie ma żadnych członków (należy jednak wziąć pod uwagę, że typedef ma być członkowie moim zdaniem)

dowód:

zmieniać struct

struct a { 
    int a; //add this 
    typedef int foo; 
}; 

i kod będzie kompilować jak najszybciej (tego samego rzędu wielkości co najmniej) dzyń.

Testowane na GCC 4.8.0/4.8.1/4.9.0

EDIT:

Od @HongxuChen poprosił więcej informacji mam edycję teraz: ci są względy osobiste wich nie mogą być poprawne, ale wydaje mi się rozsądne.

Nie dziwię się, że czasy kompilacji eksplodują z tak głębokim drzewem dziedziczenia bez memoizacji.

Zasadniczo masz wykładniczą złożoność, jeśli spróbujesz dodać

X(a, b) X(b, c) X(c, d) X(d, e) X(e, f) X(f, g) X(g, h) X(h, i) X(i, j) X(j, k) 
X(k, l) X(l, m) X(m, n) 
X(n, o)     //add this one 
o1::foo main() {} 

przekonasz czasie kompilacji jest teraz dwa razy.

Za każdym razem, gdy kompilator wykonuje podwójną liczbę sprawdzeń, nie jest zaskakujące, że rośnie tak szybko, szczególnie biorąc pod uwagę, że wewnętrznie kompilator wykonuje złożone operacje, które mogą wymagać tysięcy, jeśli nie więcej, instrukcji montażu i pomyłek w pamięci podręcznej.

Mamy 2^14 operacji w twoim przypadku (dwa razy 2^13). Przyjmując, że pojedynczy rdzeń 2Ghz oznacza 16,364 operacji przez 39 sekund, co oznacza 420 operacji na sekundę, a więc 4,7 milionów instrukcji/operacji.

Wygląda na to, że 4,7 miliona instrukcji/operacji to tak wiele, ale niekoniecznie. Zwiększenie czasu kompilacji o kilka sekund jest niezwykle łatwe ...

Interesujące byłoby wymuszenie scenariusza, w którym zarówno Clang, jak i GCC nie będą mogły korzystać z zapamiętywania i widzą, że jeden jest szybszy, ale nie mam pojęcia, jak to zrobić, a zresztą powinny one korzystać z zapamiętywania, aby zapisać większość pracy.

Uwaga: Wiem, że nie zbadałem bezpośrednio kodu GCC, który prawdopodobnie byłby ciężkim zadaniem również dla programistów GCC. Mam minimum doświadczyć pisania parserów i metakompilatorów, więc częściowo miałem do czynienia z najczęstszymi problemami, które mogą się pojawić podczas kompilacji (nie bezpośrednio GCC), inni użytkownicy są z pewnością bardziej wykwalifikowani ode mnie, aby odpowiedzieć na to pytanie.