Trochę to zajęło, ale Rustowa wersja kodu generującego położenia galaktyk w końcu osiągnęła poziom funkcjonalności wersji w C. Przy okazji zebrałem sporo ciekawych doświadczeń, którymi się teraz podzielę.
Rust vs inne języki
Programowanie w Ruście zupełnie nie przypomina programowania w innych językach, z którymi do tej pory miałem styczność (czyli zasadniczo rodzina C i Python). Jedyne, co trochę je przypominało, to eksperymentowanie z Haskellem, ale to głównie pod względem kompletnego niedopasowania mojej intuicji do języka (choć Rust ma sporo elementów funkcyjnych, ale jak będzie wspomniane później, nie należy z nimi przesadzać...).
Cechą, która wyróżnia Rusta spośród innych języków w ogóle jest pojęcie własności (ang. ownership). Każda wartość ma dowiązanie, które jest jej właścicielem. Gdy właściciel wychodzi z zasięgu, jego pamięć zostaje automatycznie zwolniona. Ponieważ każda wartość może mieć tylko jednego właściciela i wszystko prędzej czy później przestaje być widoczne, problemy typu wycieki pamięci czy podwójna dealokacja znikają.
Aby można było odwołać się do wartości z więcej niż jednego miejsca, można ją "pożyczyć" (ang. borrow). Wartości mogą być pożyczane wielokrotnie w sposób, który uniemożliwia ich modyfikację lub raz z możliwością ich modyfikowania. Celem tych zasad jest uniemożliwienie programom wielowątkowym jednoczesnej modyfikacji tych samych danych (a nawet czytania danych, które inny wątek modyfikuje).
Zasady te są proste, ale okazuje się, że wiele struktur znanych z innych języków staje się trudnych lub wręcz niemożliwych do zaprogramowania.
Cykliczne struktury danych w Ruście
W tzw. "bezpiecznym" Ruście (czyli przestrzegającym zasad opisanych wyżej - istnieje możliwość wyłączania ich we fragmentach kodu) cykliczne struktury danych zasadniczo nie istnieją. Można to zobaczyć na prostym przykładzie:
Niech A odwołuje się do B. Chcemy w B zapisać odwołanie do A (bo, np., kodujemy listę dwukierunkową albo drzewo, po którym chcemy móc się poruszać zarówno w górę, jak i w dół). Ponieważ A już zawiera odwołanie do B, nie jesteśmy w stanie "pożyczyć" B do modyfikacji - stoi to w sprzeczności z zasadami "pożyczania". Jedynym sposobem byłoby w zasadzie utworzenie obu obiektów naraz, ale takiej możliwości w Ruście nie ma.
Ściśle rzecz biorąc, sprawa nie jest do końca beznadziejna. Istnieją struktury danych, które pozwalają na dynamiczne sprawdzanie reguł pożyczania. Dzięki nim można tymczasowo uzyskać modyfikowalne odniesienie do obiektu, który jest już pożyczony w inny sposób. Tego jeszcze nie opanowałem, więc szerzej się nie rozpiszę.
Drzewa ósemkowe
Jedną ze struktur danych, które wykorzystuję w projekcie Universe, są drzewa ósemkowe. Używam ich do dzielenia przestrzeni i decydowania, w którym jej fragmencie mają znaleźć się generowane obiekty. Chciałem więc zakodować je w Ruście.
Na samym początku natknąłem się na problem opisany wyżej - nie byłem w stanie w węzłach potomnych zachować odniesienia do rodziców. Z pozoru więc na dzień dobry straciłem możliwość powracania do rodziców, a więc ponownego przeglądania większych obszarów przestrzeni po skupieniu się na mniejszych. Na szczęście po jakimś czasie przypomniałem sobie o jednym zagadnieniu.
Eksperymentując swego czasu z Haskellem, czytałem o kodowaniu drzew w tym języku. W artykule była również opisana struktura danych, pozwalająca na poruszanie się po drzewie - ang. zipper. Zipper składa się z dwóch głównych elementów - węzła, który aktualnie jest w centrum uwagi i listy węzłów nadrzędnych razem z gałęziami, przez które nie podróżowaliśmy. Podróżowanie w dół drzewa polega na wydzieleniu węzła potomnego i zapisaniu rodzica do listy węzłów nadrzędnych, a odwrotna operacja pozwala na podróżowanie w górę.
Postanowiłem zatem zakodować w Ruście zipper i w ten sposób umożliwić sobie poruszanie się po drzewie ósemkowym. Znów okazało się, że moja intuicja jest nieprzydatna i musiałem wielokrotnie zmieniać podejście do zagadnienia. W końcu stanęło na czymś, co najbardziej przypominało styl funkcyjny - operacje na drzewie i zipperach tworzyły zmodyfikowane kopie tych struktur i je zwracały. Dzięki temu oryginały mogły pozostać nie ruszone, a ja nie musiałem martwić się o naruszanie reguł pożyczania (pożyczać niezmienniczo można bez ograniczeń).
Gdy drzewo ósemkowe było gotowe, reszta stała się dużo prostsza. Po krótkim czasie mogłem przystąpić do testów i porównania wyników z C.
Wydajność stylu funkcyjnego
Napisałem krótki testowy program - zdefiniowanie ziarna wszechświata i jego rozmiaru, wygenerowanie nadrzędnego węzła (który zawiera liczbę wszystkich galaktyk), po czym odpytanie drzewa o galaktyki w pewnym niewielkim obszarze.
Pierwsze uruchomienie... wynik po kilkunastu sekundach. Niedobrze. Wersja w C robiła to samo w mgnieniu oka. Nieco zdołowany, że długi wysiłek poszedł na marne, przystąpiłem do szukania przyczyny.
W ruch poszedł valgrind - narzędzie profilujące. Miałem pewne podejrzenia, które okazały się słuszne - skutkiem ubocznym stylu funkcyjnego były miliony, jeśli nie miliardy, alokacji i dealokacji. Każda operacja na drzewie wiązała się z kopiowaniem wszystkich węzłów, które zawierały różne dodatkowe dane. Wszystko zebrane do kupy trwało długo.
Pewien znajomy potwierdził moje przypuszczenia, toteż przystąpiłem do modyfikowania kodu tak, aby struktury były modyfikowane w miejscu, zamiast kopiowane. Po intensywnej walce z kompilatorem, wciąż narzekającym że pożyczam wartości, których pożyczać nie mogę, udało mi się tego dokonać. Chwila prawdy - uruchomienie... 0,5 sekundy.
Dużo lepiej, jednak wciąż daleko w tyle za C, które z tym zadaniem radziło sobie w 0,1 sekundy. Coś wciąż było nie tak. Wtedy przyszło olśnienie.
W programie do reprezentacji współrzędnych korzystam z liczb wielokrotnej precyzji z biblioteki GMP. Aby używać jej z poziomu Rusta, korzystam z wrappera: rust-gmp. W tymże wrapperze są między innymi zdefiniowane działania matematyczne, tak abym w programie mógł pisać "c = a + b" zamiast "__gmpz_add(c, a, b)". Otóż te działania matematyczne za każdym razem tworzyły nowy obiekt liczby, który zwracały jako wynik. Jest to uzasadnione w przypadku, gdy potrzebuję zachować argumenty i tylko je pożyczam do wykonania operacji, jednak czasem argumenty są jedynie wynikami pośrednimi i mogę je spokojnie "skonsumować". Wówczas zamiast rezerwować nową pamięć, mogę wykorzystać tę zajmowaną przez jeden z argumentów.
Po wprowadzeniu tej modyfikacji i przepisaniu działań w bibliotece tak, żeby w możliwie wielu miejscach nie tworzyły nowych obiektów, uruchomiłem test. 0,25 sekundy. Bliżej.
Znów skorzystałem z valgrinda. Okazało się, że bardzo dużo czasu mój program spędza w funkcji przybliżającej całkę gęstości obiektów. Przyjrzenie się problemowi bliżej wykazało, że każde wywołanie tej funkcji tworzyło 8 nowych obiektów punktów w przestrzeni, z których każdy zawierał 3 liczby z biblioteki GMP. To wiązało się z 24 utworzeniami i usunięciami obiektów. Co więcej, funkcja ta była wywoływana przy dzieleniu bloków dla każdego bloku potomnego, czyli 8 razy... A bloki były dzielone wielokrotnie... Liczba operacji w pamięci rosła w rezultacie do niebotycznych wartości.
Rozwiązanie okazało się proste. Zmiana definicji funkcji gęstości tak, żebym mógł przekazać jej odniesienia do istniejących punktów, zamiast tworzyć kopie, i... 0,13 sekundy. Jesteśmy już prawie na poziomie C :)
Co dalej?
To jest moment, na którym się zatrzymałem. Miejsce na łatwą optymalizację się skończyło, ale i tak jest nieźle. Co nastraja optymistycznie, to że Rust teoretycznie czyni łatwym przetwarzanie wielowątkowe, więc przy odrobinie szczęścia będę jeszcze w stanie przyspieszyć kod przez jego zrównoleglenie. W swoim komputerze mam 8 procesorów, czyli czas wykonania może spaść nawet poniżej 0,02 sekundy. Przegonienie C jest realne ;)
A z innych rzeczy, został dalszy rozwój projektu. Kod generujący galaktyki w zadanym obszarze jest gotowy, teraz te galaktyki trzeba będzie podzielić na mniejsze elementy i wygenerować w nich gwiazdy. Wtedy nadejdzie też czas na jakąś prostą wizualizację, aby można było wreszcie zobaczyć rezultaty.
Testowa aplikacja
Poniżej znajduje się link do testowej aplikacji. Pozwala ona na wpisanie ziarna dla generatora wszechświata (które determinuje wszystkie jego własności) oraz współrzędnych dwóch narożników obszaru. Program następnie wylicza współrzędne galaktyk znajdujących się w tym obszarze i je wypisuje.
Uwaga: Wersja na Linuxa wymaga, aby w systemie zainstalowane były biblioteki GMP i MPFR.
Pobierz “Test Universe (Win32)” test-universe.zip – Pobrano 983 razy – 1,28 MB
Pobierz “Test Universe (Linux amd64)” test_universe-linux.tar.gz – Pobrano 901 razy – 275,83 KB