Teaser
Witajcie!
Po dłuższej przerwie wróciłem do mojego projektu optymalizacji enigmy. Widzę, że w międzyczasie sesef wydał swoją wersję, na szczęście moja jest szybsza (przynajmniej u mnie).
Trochę historii
W styczniu 2014 miałem wersję która działała zdecydowanie szybciej niż jakakolwiek kompilacja oryginalnego kodu 0.76.2. Poza tym, że mała część zadań zwracała błędy. Do tego na nieszczęście dostałem nową pracę i skończył mi się wolny czas %)
Projekt cały czas czekał na swoją kolej i w tym roku postanowiłem wygospodarować trochę "zasobów" na enigmę. Po czysto technicznych zmianach, jak migracja z Mercuriala (IMO przegrał wojnę z gitem) i przeniesienie z Bitbucket na Github mogłem zacząć odświeżać sobie znajomość kodu :attack:
Aktualny stan
Dość szybko znalazłem błąd, który prawdopodobnie był odpowiedzialny za niepoprawne wyniki sprzed dwóch lat. Wygląda na to, że to był naprawdę prosty błąd. Najwięcej czasu zajęła mi nauka google test (który jest bardzo prosty w użyciu, przynajmniej na tym poziomie, który jest wystarczający).
Szczegóły
Ta optymalizacja ma zaimplementowane 4 ścieżki (wersje):
Program wykrywa automatycznie dostępny zestaw instrukcji (CPUID) i wybiera najnowszy.
x86 < SSSE3 < AVX < AVX2
Zoptymalizowana wersja standardowa
Wymagany jest dowolny procesor. Kod został zmodyfikowany m.in. tak, aby symulować w GCC najważniejszą optymalizację, jaką robił kompilator Intela. Dzięki temu szybkość była porównywalna.
Wersja SSSE3
Najlepiej przetestowana. Mam dwa komputery, oba z procesorami Intel i5/i7 (pierwszej generacji). Działa szybko dzięki SIMD w szczególności operacji PSHUFB.
Wersja AVX
Kod źródłowy praktycznie nie różni się od wersji SSSE3, jednak może używać VEX. Nie spodziewam się dużej różnicy, szczególnie, że z VEXem wiąże się kilka pułapek wydajnościowych.1
Ogólnie sprawdzone działanie w SDE
Szybkość nieznana.
Wersja AVX2
Kod praktycznie nie przetestowany. Z tego co przeczytałem przetwarzanie rozszerzone na 256 bitów, ale pamiętam, że nie wiąże się to z dwukrotnym przyspieszeniem dekodowania.
Bardzo szybkie porównanie szybkości
Test jest bardzo prosty, użyłem My old Windows benchmark
Wyniki z Intel i5-M580 (SSSE3).
Jak widać przy systemie obciążonym w 100% innymi programami jest tylko 15% przyspieszenia w porównaniu do standardowej kompilacji (prawdopodobnie Hyper Threading, enigma używa też relatywnie dużo pamięci cache). Wersja sesefa daje około 30% przyspieszenia.
Odwrotnie wygląda sytuacja przy nieobciążonym systemie: odcinamy 45% czasu działania w porównaniu do 33% u sesefa.
Co dalej?
Nie wiem, czy sesef opublikował kod źródłowy swojej wersji. Powinien, bo enigma jest licencjonowana GNU GPLv2 i wymaga publikacji kodu źródłowego. Jestem ciekawy jakie zmiany wprowadził, z tego co widziałem w zdekompilowanym kodzie musiał znaleźć inne podejście. Właściwie tylko szybko rzuciłem okiem na ten plik i wolałbym nie tracić czasu na reverse engineering. Wydaje mi się, że sesef "żyje" na BOINC Polish National Team. Jeżeli ktoś z Was mógłby go tam zagadnąć, będę wdzięczny.
Skompilowany plik udostępnię, gdy przejdzie mi dostatecznie dużo zadań na E@H. Powinno wystarczyć koło 100, nie chciałbym publikować wersji, która niepotrzebnie będzie zaśmiecać serwer. Co prawda TJM pisał mi kiedyś, że serwer da sobie z tym radę, ale po co go męczyć (już i tak error rate jest 5.6%...)
Pierwszą wersję chciałbym opublikować wewnętrznie dla naszej drużyny, żeby mieć w miarę kontrolowany zbiór użytkowników. Trzeba sprawdzić, jak aplikacja liczy w rzeczywistych warunkach, nie tylko na moich komputerach ;)
Wydaje mi się, że da się ten program przyspieszyć jeszcze o jakieś 10% (w porównaniu do moich aktualnych wyników) więc w sumie działałaby 2 razy szybciej niż standardowa. A jeszcze po dodaniu voodoo od sesefa, kto wie? Może zwracać wynik jeszcze przed rozpoczęciem obliczeń :fright:
Co o tym myślicie? Kto by się zgłosił do przetestowania?
Witajcie!
Po dłuższej przerwie wróciłem do mojego projektu optymalizacji enigmy. Widzę, że w międzyczasie sesef wydał swoją wersję, na szczęście moja jest szybsza (przynajmniej u mnie).
Trochę historii
W styczniu 2014 miałem wersję która działała zdecydowanie szybciej niż jakakolwiek kompilacja oryginalnego kodu 0.76.2. Poza tym, że mała część zadań zwracała błędy. Do tego na nieszczęście dostałem nową pracę i skończył mi się wolny czas %)
Projekt cały czas czekał na swoją kolej i w tym roku postanowiłem wygospodarować trochę "zasobów" na enigmę. Po czysto technicznych zmianach, jak migracja z Mercuriala (IMO przegrał wojnę z gitem) i przeniesienie z Bitbucket na Github mogłem zacząć odświeżać sobie znajomość kodu :attack:
Aktualny stan
Dość szybko znalazłem błąd, który prawdopodobnie był odpowiedzialny za niepoprawne wyniki sprzed dwóch lat. Wygląda na to, że to był naprawdę prosty błąd. Najwięcej czasu zajęła mi nauka google test (który jest bardzo prosty w użyciu, przynajmniej na tym poziomie, który jest wystarczający).
Szczegóły
Ta optymalizacja ma zaimplementowane 4 ścieżki (wersje):
- Zoptymalizowaną wersję standardową.
- Wersję SSSE3 (Intel Core 2+/Merom)
- Wersję AVX (Sandy Bridge+)
- Wersję AVX2 (Haswell)
Program wykrywa automatycznie dostępny zestaw instrukcji (CPUID) i wybiera najnowszy.
x86 < SSSE3 < AVX < AVX2
Zoptymalizowana wersja standardowa
Wymagany jest dowolny procesor. Kod został zmodyfikowany m.in. tak, aby symulować w GCC najważniejszą optymalizację, jaką robił kompilator Intela. Dzięki temu szybkość była porównywalna.
Wersja SSSE3
Najlepiej przetestowana. Mam dwa komputery, oba z procesorami Intel i5/i7 (pierwszej generacji). Działa szybko dzięki SIMD w szczególności operacji PSHUFB.
Wersja AVX
Kod źródłowy praktycznie nie różni się od wersji SSSE3, jednak może używać VEX. Nie spodziewam się dużej różnicy, szczególnie, że z VEXem wiąże się kilka pułapek wydajnościowych.1
Ogólnie sprawdzone działanie w SDE
Szybkość nieznana.
Wersja AVX2
Kod praktycznie nie przetestowany. Z tego co przeczytałem przetwarzanie rozszerzone na 256 bitów, ale pamiętam, że nie wiąże się to z dwukrotnym przyspieszeniem dekodowania.
Bardzo szybkie porównanie szybkości
Test jest bardzo prosty, użyłem My old Windows benchmark
Wyniki z Intel i5-M580 (SSSE3).
vanilla | sesef | Agbar | |
obciążony | 43.9 | 30.7 | 37.4 |
nieobciążony | 20.3 | 13.7 | 11.2 |
Jak widać przy systemie obciążonym w 100% innymi programami jest tylko 15% przyspieszenia w porównaniu do standardowej kompilacji (prawdopodobnie Hyper Threading, enigma używa też relatywnie dużo pamięci cache). Wersja sesefa daje około 30% przyspieszenia.
Odwrotnie wygląda sytuacja przy nieobciążonym systemie: odcinamy 45% czasu działania w porównaniu do 33% u sesefa.
Co dalej?
Nie wiem, czy sesef opublikował kod źródłowy swojej wersji. Powinien, bo enigma jest licencjonowana GNU GPLv2 i wymaga publikacji kodu źródłowego. Jestem ciekawy jakie zmiany wprowadził, z tego co widziałem w zdekompilowanym kodzie musiał znaleźć inne podejście. Właściwie tylko szybko rzuciłem okiem na ten plik i wolałbym nie tracić czasu na reverse engineering. Wydaje mi się, że sesef "żyje" na BOINC Polish National Team. Jeżeli ktoś z Was mógłby go tam zagadnąć, będę wdzięczny.
Skompilowany plik udostępnię, gdy przejdzie mi dostatecznie dużo zadań na E@H. Powinno wystarczyć koło 100, nie chciałbym publikować wersji, która niepotrzebnie będzie zaśmiecać serwer. Co prawda TJM pisał mi kiedyś, że serwer da sobie z tym radę, ale po co go męczyć (już i tak error rate jest 5.6%...)
Pierwszą wersję chciałbym opublikować wewnętrznie dla naszej drużyny, żeby mieć w miarę kontrolowany zbiór użytkowników. Trzeba sprawdzić, jak aplikacja liczy w rzeczywistych warunkach, nie tylko na moich komputerach ;)
Wydaje mi się, że da się ten program przyspieszyć jeszcze o jakieś 10% (w porównaniu do moich aktualnych wyników) więc w sumie działałaby 2 razy szybciej niż standardowa. A jeszcze po dodaniu voodoo od sesefa, kto wie? Może zwracać wynik jeszcze przed rozpoczęciem obliczeń :fright:
Co o tym myślicie? Kto by się zgłosił do przetestowania?
- Przejście ze zwykłego/starego kodowania instrukcji na kodowanie VEX wiąże się z dość długą karą w cyklach. Problem do rozwiązania, ale możliwe, że skończymy z dwoma plikami: SSSE3 i AVX+