Co sprawia, że ​​Scheming oparty na sterty jest wolniejszy niż schemat oparty na stosie?

Question

Pracuję nad kompilatorem dla języka podobnego do Schematu i czytam przez dysertację Dybviga. Mówi on, że osiągnął większą część swojego wzrostu wydajności przez przydzielanie ramek połączeń na stosie zamiast na stercie. Istnieje kilka sztuczek, które należy wykonać, aby faktycznie wykonać tę pracę w obecności zamknięć i kontynuacji.

Moje pytanie brzmi: skąd bierze się ten wzrost wydajności? Czy to tylko dlatego, że mniej obciążamy odśmiecarkę?

Innymi słowy: zakładając, że mamy nieskończoną ilość pamięci, czy przydzielone alokowane ramki połączeń będą nadal szybsze niż klatki alokowane dla sterty?

Answer 1

Myślę, że Eli odpowiedział na twoje pytanie, więc mam zamiar wkleić jego komentarz tutaj i dostać kredyt za to :).

Eli Barzilay pisze:

(a) do czynienia z sterty zajmuje więcej czasu, ponieważ wymaga skanując go (to nie jest liniowa jak stosie); (b) praktycznie wszystkie architektury procesorów kładą szczególny nacisk na jak najszybszy dostęp do stosu, a nie tak, jak w przypadku sterty.

Do tego dodałbym ogólne wskazówki dotyczące lokalizacji w pamięci podręcznej. Oznacza to, że stos zachowuje całą akcję w bardzo małej części pamięci, która prawie na pewno pozostanie w pamięci podręcznej.

Answer 2

Appel napisał paper twierdząc, że przydział sterty może być szybszy niż przydział sterty. Matematycznie ma rację, ale ignoruje to, w jaki sposób nowoczesne procesory są przystosowane do działania kodu, który używa stosu (miejsce w pamięci podręcznej, wydajne instrukcje dotyczące stosów itp.), A dostęp do sterty ma więcej pośredników (źle w nowoczesnych procesorach).