Wdrażałem algorytm w Swift Beta i zauważyłem, że wydajność była bardzo słaba. Po głębszym kopaniu zdałem sobie sprawę, że jednym z wąskich gardeł było coś tak prostego, jak sortowanie tablic. Odpowiednia część znajduje się tutaj:
let n = 1000000
var x = [Int](repeating: 0, count: n)
for i in 0..<n {
x[i] = random()
}
// start clock here
let y = sort(x)
// stop clock here
W C ++ podobna operacja zajmuje 0,06 s na moim komputerze.
W Pythonie zajmuje 0,6 s (bez lew, tylko y = sorted (x) dla listy liczb całkowitych).
W Swift zajmuje 6s, jeśli skompiluję go za pomocą następującego polecenia:
xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`
A kompilacja za pomocą następującego polecenia zajmuje aż 88 sekund :
xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`
Czasy w Xcode z kompilacjami „Release” vs. „Debug” są podobne.
Co tu jest nie tak? Mogłem zrozumieć pewną utratę wydajności w porównaniu z C ++, ale nie 10-krotne spowolnienie w porównaniu z czystym Pythonem.
Edycja: pogoda zauważyła, że zmiana -O3
na -Ofast
ten powoduje, że ten kod działa prawie tak szybko, jak wersja C ++! Jednak bardzo -Ofast
zmienia semantykę języka - w moich testach wyłączyłem sprawdzanie przepełnień liczb całkowitych i przepełnienia indeksowania tablic . Na przykład -Ofast
następujący kod Swift działa w trybie cichym bez awarii (i drukuje śmieci):
let n = 10000000
print(n*n*n*n*n)
let x = [Int](repeating: 10, count: n)
print(x[n])
Więc -Ofast
nie tego chcemy; chodzi o to, że mamy siatki bezpieczeństwa. Oczywiście siatki bezpieczeństwa mają pewien wpływ na wydajność, ale nie powinny powodować, że programy będą 100 razy wolniejsze. Pamiętaj, że Java już sprawdza granice tablic, a w typowych przypadkach spowolnienie jest znacznie mniejsze niż 2. A w Clang i GCC mamy -ftrapv
do sprawdzania (podpisanych) przepełnień liczb całkowitych, i to nie jest tak powolne.
Stąd pytanie: w jaki sposób możemy uzyskać rozsądną wydajność w Swift bez utraty sieci bezpieczeństwa?
Edycja 2: Zrobiłem trochę więcej testów porównawczych, z bardzo prostymi pętlami wzdłuż linii
for i in 0..<n {
x[i] = x[i] ^ 12345678
}
(Tutaj jest operacja xor, aby łatwiej znaleźć odpowiednią pętlę w kodzie asemblera. Próbowałem wybrać operację, która jest łatwa do wykrycia, ale także „nieszkodliwa” w tym sensie, że nie powinna wymagać żadnych kontroli związanych z do przelewów liczb całkowitych).
Ponownie, była ogromna różnica w wydajności pomiędzy -O3
i -Ofast
. Spojrzałem więc na kod asemblera:
Z
-Ofast
tym dostaję prawie to, czego bym się spodziewał. Odpowiednia część to pętla z 5 instrukcjami języka maszynowego.Z
-O3
I dostać coś, co było poza moim najdzikszych fantazji. Pętla wewnętrzna obejmuje 88 linii kodu asemblera. Nie próbowałem tego wszystkiego zrozumieć, ale najbardziej podejrzane są 13 wywołań „callq _swift_retain” i kolejne 13 wywołań „callq _swift_release”. To znaczy, 26 wywołań podprogramów w wewnętrznej pętli !
Edycja 3: W komentarzach Ferruccio poprosił o testy porównawcze, które są uczciwe w tym sensie, że nie polegają na wbudowanych funkcjach (np. Sortowanie). Myślę, że następujący program jest dość dobrym przykładem:
let n = 10000
var x = [Int](repeating: 1, count: n)
for i in 0..<n {
for j in 0..<n {
x[i] = x[j]
}
}
Nie ma arytmetyki, więc nie musimy się martwić o przepełnienie liczb całkowitych. Jedyne, co robimy, to po prostu wiele odniesień do tablicy. A wyniki są tutaj - Swift -O3 traci prawie 500 razy w porównaniu z opcją -Ofast:
- C ++ -O3: 0,05 s
- C ++ -O0: 0,4 s
- Java: 0,2 s
- Python z PyPy: 0,5 s
- Python: 12 s
- Szybki - szybki: 0,05 s
- Swift -O3: 23 s
- Swift -O0: 443 s
(Jeśli obawiasz się, że kompilator może całkowicie zoptymalizować niepotrzebne pętle, możesz go zmienić na np. x[i] ^= x[j]
I dodać instrukcję print, która wypisuje wynik x[0]
. To niczego nie zmienia; czasy będą bardzo podobne.)
I tak, tutaj implementacja Pythona była głupią czystą implementacją Pythona z listą liczb int i zagnieżdżoną dla pętli. Powinien być znacznie wolniejszy niż niezoptymalizowany Swift. Wydaje się, że coś jest poważnie zepsute w Swift i indeksowaniu tablic.
Edycja 4: Te problemy (podobnie jak niektóre inne problemy z wydajnością) zostały prawdopodobnie rozwiązane w Xcode 6 beta 5.
Do sortowania mam teraz następujące czasy:
- klang ++ -O3: 0,06 s
- swiftc -Ofast: 0,1 s
- swiftc -O: 0,1 s
- swiftc: 4 s
W przypadku zagnieżdżonych pętli:
- klang ++ -O3: 0,06 s
- swiftc -Ofast: 0,3 s
- swiftc -O: 0,4 s
- swiftc: 540 s
Wydaje się, że nie ma już powodu, aby używać tego niebezpiecznego -Ofast
(aka -Ounchecked
); zwykły -O
tworzy równie dobry kod.
źródło
xcrun --sdk macosx swift -O3
. Jest krótszyOdpowiedzi:
tl; dr Swift 1.0 jest teraz tak szybki jak C według tego testu porównawczego przy użyciu domyślnego poziomu optymalizacji wersji [-O].
Oto szybki Quick -ort w Swift Beta:
I to samo w C:
Oba działają:
Oba są wywoływane w tym samym programie, co napisane.
Konwertuje to czasy bezwzględne na sekundy:
Oto podsumowanie poziomów optymalizacji kompilatora:
Czas w sekundach z [-Onone] dla n = 10_000 :
Oto wbudowane sortowanie Swift () dla n = 10_000 :
Oto [-O] dla n = 10_000 :
Jak widać, wydajność Swift poprawiła się 20-krotnie.
Zgodnie z odpowiedzią mweathers , ustawienie [-Ofast] robi prawdziwą różnicę, czego rezultatem są czasy dla n = 10_000 :
A dla n = 1_000_000 :
Dla porównania jest to z [-Onone] dla n = 1_000_000 :
Zatem Swift bez optymalizacji był prawie 1000 razy wolniejszy niż C w tym teście, na tym etapie jego rozwoju. Z drugiej strony przy obu kompilatorach ustawionych na [-Ofast] Swift faktycznie działał co najmniej równie dobrze, jeśli nie nieco lepiej niż C.
Zwrócono uwagę, że [-Ofast] zmienia semantykę języka, czyniąc go potencjalnie niebezpiecznym. Tak stwierdza Apple w uwagach do wydania Xcode 5.0:
Wszyscy raczej to popierają. Bez względu na to, czy jest to mądre, czy nie, nie mogę powiedzieć, ale z tego, co mogę powiedzieć, wydaje się rozsądne użycie [-Ofast] w wydaniu, jeśli nie wykonujesz precyzyjnej arytmetyki zmiennoprzecinkowej i nie masz pewności, że liczba całkowita lub przepełnienia tablicy są możliwe w twoim programie. Jeśli potrzebujesz wysokiej wydajności i kontroli przepełnienia / precyzyjnej arytmetyki, wybierz na razie inny język.
AKTUALIZACJA BETA 3:
n = 10_000 przy [-O] :
Ogólnie rzecz biorąc, Swift jest nieco szybszy i wygląda na to, że wbudowane sortowanie Swift zmieniło się dość znacząco.
AKTUALIZACJA KOŃCOWA:
[-Onone] :
[-O] :
[-Oznaczone] :
źródło
TL; DR : Tak, jedyne wdrożenie języka Swift jest teraz powolne . Jeśli potrzebujesz szybkiego, numerycznego (i prawdopodobnie innego rodzaju kodu), po prostu wybierz inny. W przyszłości powinieneś ponownie ocenić swój wybór. Jednak może być wystarczający dla większości kodu aplikacji napisanego na wyższym poziomie.
Z tego, co widzę w SIL i LLVM IR, wygląda na to, że potrzebują szeregu optymalizacji do usuwania zachowań i wydań, które mogą być zaimplementowane w Clang (dla Objective-C), ale jeszcze ich nie przeniesiono. Z tą teorią popieram (na razie… muszę jeszcze potwierdzić, że Clang coś z tym robi), ponieważ profiler uruchomiony na ostatnim przypadku testowym tego pytania daje ten „ładny” wynik:
Jak zostało powiedziane przez wielu innych,
-Ofast
jest całkowicie niebezpieczny i zmienia semantykę języka. Dla mnie jest to etap „Jeśli zamierzasz tego użyć, po prostu użyj innego języka”. Ponownie ocenię ten wybór, jeśli się zmieni.-O3
daje nam garśćswift_retain
iswift_release
nazywa to, szczerze mówiąc, nie wygląda na to, że powinni być przy tym przykładzie. Optymalizator powinien unikać (większość) AFAICT, ponieważ zna większość informacji o tablicy i wie, że ma (przynajmniej) silne odniesienie do niej.Nie powinien emitować więcej zachowań, nawet jeśli nie wywołuje funkcji, które mogłyby zwolnić obiekty. Nie sądzę, aby konstruktor tablic mógł zwrócić tablicę, która jest mniejsza niż ta, o którą prosiliśmy, co oznacza, że wiele wysłanych kontroli jest bezużytecznych. Wie również, że liczba całkowita nigdy nie będzie większa niż 10k, więc kontrole przepełnienia można zoptymalizować (nie z powodu
-Ofast
dziwności, ale z powodu semantyki języka (nic innego się nie zmienia, ani nie można uzyskać do niej dostępu, i sumowanie do 10k jest bezpieczny dla tego typuInt
).Kompilator może jednak nie być w stanie rozpakować tablicy lub elementów tablicy, ponieważ są one przekazywane do
sort()
, która jest funkcją zewnętrzną i musi uzyskać oczekiwane argumenty. Spowoduje to, że będziemy musieli korzystać zInt
wartości pośrednio, co sprawi, że będzie trochę wolniej. Mogłoby to ulec zmianie, gdybysort()
funkcja ogólna (nie w trybie wielu metod) była dostępna dla kompilatora i została wstawiona.To jest bardzo nowy (publicznie) język i przechodzi przez to, co, jak zakładam, wiele zmian, ponieważ ludzie (mocno) zaangażowani w język Swift proszą o opinie i wszyscy mówią, że język nie jest ukończony i będzie zmiana.
Zastosowany kod:
PS: Nie jestem ekspertem od Objective-C, ani wszystkich udogodnień z Cocoa , Objective-C, ani Swift. Mogę również zakładać pewne rzeczy, których nie napisałem.
źródło
-Ofast
„całkowicie niebezpiecznym”? Zakładając, że wiesz, jak przetestować kod i wykluczyć przepełnienia.-Ofast
zmienia również semantykę języka, ale nie mogę za to sfinansować żadnych dokumentów. Jak możesz być pewien, że wiesz, co robi?Int[]
”, ponieważ zależy to od poziomu, w jakim kompilator może wbudować i powinien być w stanie wstawiać wąskie pętle z / po pewnych wskazówkach.Postanowiłem przyjrzeć się temu dla zabawy, a oto czasy, które otrzymuję:
Szybki
Wyniki:
Swift 1.1
Swift 1.2
Swift 2.0
Wydaje mi się, że jest to ta sama wydajność, jeśli się kompiluję
-Ounchecked
.Swift 3.0
Wydaje się, że nastąpiła regresja wydajności od Swift 2.0 do Swift 3.0, a także widzę różnicę między
-O
i-Ounchecked
po raz pierwszy.Swift 4.0
Swift 4 ponownie poprawia wydajność, zachowując lukę między
-O
i-Ounchecked
.-O -whole-module-optimization
nie wydaje się mieć znaczenia.C ++
Wyniki:
Apple Clang 6.0
Apple Clang 6.1.0
Apple Clang 7.0.0
Apple Clang 8.0.0
Apple Clang 9.0.0
Werdykt
W chwili pisania tego tekstu sortowanie Swift jest szybkie, ale jeszcze nie tak szybkie jak sortowanie w C ++ po kompilacji z
-O
powyższymi kompilatorami i bibliotekami. Dzięki-Ounchecked
wydaje się być tak szybki jak C ++ w Swift 4.0.2 i Apple LLVM 9.0.0.źródło
Od
The Swift Programming Language
:sort
Funkcja ma dwa oświadczenia.Domyślna deklaracja, która pozwala określić zamknięcie porównania:
I druga deklaracja, która bierze tylko jeden parametr (tablicę) i jest „zakodowana na stałe, aby użyć komparatora mniejszego niż”.
Przetestowałem zmodyfikowaną wersję twojego kodu na placu zabaw z dodanym zamknięciem, dzięki czemu mogłem nieco dokładniej monitorować tę funkcję, i odkryłem, że przy n ustawionym na 1000 zamknięcie było wywoływane około 11 000 razy.
To nie jest wydajna funkcja, polecam użycie lepszej implementacji funkcji sortowania.
EDYTOWAĆ:
Przejrzałem stronę wikipedii Quicksort i napisałem dla niej implementację Swift. Oto pełny program, z którego korzystałem (na placu zabaw)
Używając tego przy n = 1000, znalazłem to
Wygląda na to, że wbudowana metoda sortowania jest (lub jest bliska) szybkim sortowaniem i jest naprawdę powolna ...
źródło
2*n*log(n)
. To jest 13815 porównań do sortowania n = 1000 elementów, więc jeśli funkcja porównania jest wywoływana około 11000 razy, nie wydaje się to takie złe.log(n)
dla złożoności algorytmicznej konwencjonalnie odnosi się do log-base-2. Powodem, dla którego nie podano podstawy, jest to, że prawo zmiany podstawy dla logarytmów wprowadza jedynie stały mnożnik, który jest odrzucany do celów notacji O.C(n) = 2n ln n ≈ 1.39n log₂ n
. Dla n = 1000, co daje -C (Mn) = 13815, a to nie jest "zapis dużym o".Od Xcode 7 możesz włączyć
Fast, Whole Module Optimization
. Powinno to natychmiast zwiększyć wydajność.źródło
Ponownie sprawdzono wydajność funkcji Swift Array:
Napisałem własny test porównawczy Swift z C / Objective-C. Mój test porównawczy oblicza liczby pierwsze. Wykorzystuje tablicę poprzednich liczb pierwszych do wyszukiwania czynników pierwszych u każdego nowego kandydata, więc jest dość szybki. Jednak robi TONY odczytu tablicy i mniej zapisu do tablic.
Pierwotnie zrobiłem ten test porównawczy przeciwko Swift 1.2. Postanowiłem zaktualizować projekt i uruchomić go przeciwko Swift 2.0.
Projekt pozwala wybierać między użyciem zwykłych szybkich tablic a użyciem szybkich niebezpiecznych buforów pamięci przy użyciu semantyki macierzy.
W przypadku C / Objective-C możesz wybrać użycie NSArrays lub C malloc'ed.
Wyniki testu wydają się dość podobne z najszybszą, najmniejszą optymalizacją kodu ([-0s]) lub najszybszą, agresywną ([-0fast]) optymalizacją.
Wydajność Swift 2.0 jest nadal okropna przy wyłączonej optymalizacji kodu, podczas gdy wydajność C / Objective-C jest tylko umiarkowanie wolniejsza.
Najważniejsze jest to, że obliczenia oparte na tablicy C malloc'd są najszybsze, ze skromnym marginesem
Swift z niebezpiecznymi buforami zajmuje około 1,19X - 1,20X dłużej niż tablice C malloc'd przy użyciu najszybszej, najmniejszej optymalizacji kodu. różnica wydaje się nieco mniejsza w przypadku szybkiej, agresywnej optymalizacji (Swift zajmuje o 1,18x do 1,16x więcej niż C.
Jeśli używasz zwykłych tablic Swift, różnica z C jest nieco większa. (Swift zajmuje ~ 1,22 do 1,23 dłużej.)
Zwykłe tablice Swift są
DRAMATICALLY
szybsze niż w Swift 1.2 / Xcode 6. Ich wydajność jest tak bliska, jak w przypadku tablic Swift opartych na buforach niebezpiecznych, że używanie niebezpiecznych buforów pamięci nie wydaje się już warte większych kłopotów, co jest duże.BTW, wydajność NSArray Objective-C śmierdzi. Jeśli zamierzasz używać natywnych obiektów kontenerowych w obu językach, Swift jest DRAMATYCZNIE szybszy.
Możesz sprawdzić mój projekt na github na SwiftPerformanceBenchmark
Ma prosty interfejs użytkownika, który sprawia, że zbieranie statystyk jest bardzo łatwe.
Interesujące jest to, że sortowanie w Swift wydaje się nieco szybsze niż w C, ale ten algorytm liczb pierwszych jest jeszcze szybszy w Swift.
źródło
Głównym problemem, o którym wspominają inni, ale nie są wystarczająco wzywani, jest to, że
-O3
w Swift nic nie robi (i nigdy nie ma), więc po skompilowaniu jest efektywnie niezoptymalizowany (-Onone
).Nazwy opcji zmieniają się z czasem, więc niektóre inne odpowiedzi mają przestarzałe flagi dla opcji kompilacji. Prawidłowe bieżące opcje (Swift 2.2) to:
Optymalizacja całego modułu ma wolniejszą kompilację, ale może optymalizować pliki w module, tj. W ramach każdej struktury i w obrębie rzeczywistego kodu aplikacji, ale nie między nimi. Powinieneś używać tego do wszystkiego, co ma kluczowe znaczenie dla wydajności)
Możesz także wyłączyć kontrole bezpieczeństwa, aby uzyskać jeszcze większą prędkość, ale wszystkie twierdzenia i warunki wstępne są nie tylko wyłączone, ale zoptymalizowane na podstawie ich poprawności. Jeśli kiedykolwiek trafisz na stwierdzenie, oznacza to, że jesteś w nieokreślonym zachowaniu. Używaj z dużą ostrożnością i tylko wtedy, gdy stwierdzisz, że przyspieszenie jest dla Ciebie opłacalne (przez testowanie). Jeśli uznasz, że jest on cenny dla jakiegoś kodu, zalecam rozdzielenie tego kodu na osobną strukturę i wyłączenie kontroli bezpieczeństwa tylko dla tego modułu.
źródło
To jest mój blog o szybkim sortowaniu - przykładowy szybki sort Githuba
Możesz przyjrzeć się algorytmowi partycjonowania Lomuto w Partycjonowaniu listy. Napisane w Swift.
źródło
Swift 4.1 wprowadza nowy
-Osize
tryb optymalizacji.Dalsza lektura: https://swift.org/blog/osize/
źródło