W jaki sposób wydana wersja Roslyn wprowadza niezmienne drzewa?

Question

Rozumiem, że wcześniejsza wersja Roslyn zaimplementowała niezmienne drzewa, jak opisano w this excellent blog post przez Eric Lippert. Jednak ten wpis kończy się na:

"Koszt jest taki, że ten system jest złożony i może pochłaniać dużo pamięci, jeśli" czerwona "fasada staje się duża. Obecnie przeprowadzamy eksperymenty, aby sprawdzić, czy możemy zmniejszyć niektóre z nich. koszty bez utraty korzyści. "

Chciałbym zapytać, jaki był wynik wersji Release. Zacząłem badać Roslyn sources, ale kod jest dość skomplikowany do naśladowania.

Interesują mnie niskie wyniki projektowe dotyczące wyżej wymienionych kosztów.

1. Jaki jest koszt pojedynczej edycji pod względem czerwonych/zielonych węzłów?
2. Jakie optymalizacje zostały wykonane dla innych operacji (np. Usuwanie, cofanie)?

Answer 1

Jest to fantastyczne spojrzenie na wykonanie i wdrożenie niezmiennych drzew Roslyn poprzez VSadov na forach dyskusyjnych tutaj: https://roslyn.codeplex.com/discussions/541953

na wysokim poziomie, omawia współbieżność, de-duplikacji zielonych węzłów, de-duplikacji terminali i dublowanie ciągów w tych drzewach.

Mówi także o lenistwie czerwonych drzew. Zamiast obliczać czerwone drzewo po każdej zmianie tekstu, czerwone drzewo jest obliczane tylko wtedy, gdy ktoś o to poprosi.

W końcu omawia czerwone drzewo i fakt, że jest słaby. Nigdy nie używałem ani nie widziałem klasy WeakReference, a VSadov zapewnia dobry przegląd tego, jak jest ona używana w czerwonym drzewie. Zasadniczo śmieciarz może oczyścić fragmenty czerwonego drzewa i można je później odtworzyć w razie potrzeby. Nie jestem zaznajomiony z implementacją, ale Eric Lippert zauważa, że ​​czerwona elewacja drzewa może powodować duży ślad pamięci. Wyobrażam sobie, że te WeakReferences pomóc złagodzić ten problem w pewnym stopniu.

Answer 2

Obecnie nadal robimy to samo, co Eric opisał. Próbowaliśmy niektórych eksperymentów, ale okazało się, że koszt przejrzystości interfejsu API jest zbyt wysoki, by zapłacić. Zamiast tego, główną zmianą, którą wprowadziliśmy, było zmniejszenie alokacji sterty i kosztów GC, poprzez wprowadzenie SyntaxToken do struktury w czerwonym modelu. Jest to znacząca oszczędność, ponieważ w przypadku plików źródłowych średnio połowa węzłów w drzewie składni to terminale (SyntaxToken s). Zielone węzły nie są strukturami, ale z drugiej strony, ponieważ nie zawierają wskaźników macierzystych ani pozycji, są internowane - dzielimy to samo wystąpienie zielonego węzła dla wszystkich identycznych węzłów (te same ciekawostki i tekst).

Nie jestem pewien, co masz na myśli przez "koszt" edycji. Czas/przestrzeń/złożoność/itd. Generalnie mamy przyrostowy lexer, który odświeża obszar, na który ma wpływ edycja. Następnie mamy inkrementalny analizator składni, który w najlepszym przypadku odradza stwierdzenie, które krzyżuje się z nowymi leksykalnymi żetonami, a następnie odtwarza "kręgosłup" zielonego drzewa z powrotem do korzenia, ponownie wykorzystując resztę zieleni węzły w drzewie. Żaden z czerwonych węzłów nie może być ponownie użyty z definicji. Istnieje nowy węzeł główny dla nowego drzewa i można go uzyskać z dowolnego innego węzła.

W kompilatorze nie wykonano żadnych innych optymalizacji. Ponownie używamy drzewa w pamięci podręcznej w IDE po cofnięciu, ale nie jestem pewien.