Napisałem kod Scali, aby wykonać elementową operację na kolekcji. Tutaj zdefiniowałem dwie metody, które wykonują to samo zadanie. Jedna metoda wykorzystuje, zip
a druga wykorzystuje zipped
.
def ES (arr :Array[Double], arr1 :Array[Double]) :Array[Double] = arr.zip(arr1).map(x => x._1 + x._2)
def ES1(arr :Array[Double], arr1 :Array[Double]) :Array[Double] = (arr,arr1).zipped.map((x,y) => x + y)
Aby porównać te dwie metody pod względem prędkości, napisałem następujący kod:
def fun (arr : Array[Double] , arr1 : Array[Double] , f :(Array[Double],Array[Double]) => Array[Double] , itr : Int) ={
val t0 = System.nanoTime()
for (i <- 1 to itr) {
f(arr,arr1)
}
val t1 = System.nanoTime()
println("Total Time Consumed:" + ((t1 - t0).toDouble / 1000000000).toDouble + "Seconds")
}
Wywołuję fun
metodę i przekazuję ES
i ES1
jak poniżej:
fun(Array.fill(10000)(math.random), Array.fill(10000)(math.random), ES , 100000)
fun(Array.fill(10000)(math.random), Array.fill(10000)(math.random), ES1, 100000)
Wyniki pokazują, że metoda, ES1
która używa, zipped
jest szybsza niż metoda, ES
która używa zip
. Na podstawie tych obserwacji mam dwa pytania.
Dlaczego jest zipped
szybszy niż zip
?
Czy istnieje jeszcze szybszy sposób wykonywania elementarnych operacji na kolekcji w Scali?
scala
performance
scala-collections
jmh
elementwise-operations
użytkownik12140540
źródło
źródło
Odpowiedzi:
Aby odpowiedzieć na drugie pytanie:
Smutna prawda jest taka, że pomimo zwięzłości, zwiększonej produktywności i odporności na błędy, języki funkcjonalne niekoniecznie są najbardziej wydajne - użycie funkcji wyższego rzędu do zdefiniowania projekcji, która ma być wykonana na kolekcjach, które nie są wolne, a twoja wąska pętla podkreśla to. Jak zauważyli inni, dodatkowy przydział pamięci dla wyników pośrednich i końcowych również będzie miał narzut.
Jeśli wydajność ma kluczowe znaczenie, choć nie jest uniwersalna, w takich przypadkach jak twoje możesz cofnąć operacje Scali z powrotem do bezwzględnych odpowiedników, aby odzyskać bardziej bezpośrednią kontrolę nad wykorzystaniem pamięci i wyeliminować wywołania funkcji.
W konkretnym przykładzie
zipped
sumy można wykonać imperatywnie, wstępnie przydzielając stałą, zmienną tablicę o prawidłowym rozmiarze (ponieważ zip zatrzymuje się, gdy w jednej z kolekcji zabraknie elementów), a następnie dodając elementy o odpowiednim indeksie razem (od momentu uzyskania dostępu elementy tablic według indeksu porządkowego to bardzo szybka operacja).Dodanie trzeciej funkcji
ES3
do zestawu testów:Na moim i7 otrzymuję następujące czasy odpowiedzi:
Jeszcze bardziej haniebne byłoby dokonanie bezpośredniej mutacji w miejscu krótszej z dwóch tablic, co oczywiście zniszczyłoby zawartość jednej z tablic, i byłoby to zrobione tylko wtedy, gdyby pierwotna tablica ponownie nie była potrzebna:
Ale oczywiście bezpośrednia mutacja elementów tablicy nie jest w duchu Scali.
źródło
Array.tabulate(minSize)(i => arr(i) + arr1(i))
Stworzenie tablicy będzie bardziej podobne doArray.tabulate
powinien być znacznie szybszy niż którykolwiekzip
lubzipped
tutaj (i jest w moich testach).for
jest przeznaczony do wywołania funkcji wyższego rzędu (foreach
). Sonda lambda zostanie utworzona tylko raz w obu przypadkach.Żadna z pozostałych odpowiedzi nie wspomina o głównej przyczynie różnicy prędkości, która polega na tym, że
zipped
wersja unika 10.000 alokacji krotek. Jak kilka innych odpowiedzi zrobić noty,zip
wersja obejmuje pośrednią tablicę, natomiastzipped
wersja nie robi, ale przydzielanie tablicę do 10000 elementów nie jest to, co sprawia, żezip
wersja o wiele gorsze jest to 10,000 krótkotrwałe krotki że są umieszczane w tej tablicy. Są one reprezentowane przez obiekty w JVM, więc wykonujesz kilka przydziałów obiektów dla rzeczy, które natychmiast zamierzasz wyrzucić.Reszta tej odpowiedzi zawiera tylko trochę więcej szczegółów na temat tego, jak możesz to potwierdzić.
Lepsze testy porównawcze
Naprawdę chcesz używać frameworku, takiego jak jmh, do odpowiedzialnego testowania wydajności w JVM, a nawet wtedy odpowiedzialna część jest trudna, chociaż samo skonfigurowanie jmh nie jest takie złe. Jeśli masz coś
project/plugins.sbt
takiego:I
build.sbt
podobne (używam 2.11.8, ponieważ wspominasz, że tego właśnie używasz):Następnie możesz napisać swój test porównawczy w następujący sposób:
I uruchom z
sbt "jmh:run -i 10 -wi 10 -f 2 -t 1 zipped_bench.ZippedBench"
:Co pokazuje, że
zipped
wersja uzyskuje około 80% większą przepustowość, co prawdopodobnie jest mniej więcej takie samo jak twoje pomiary.Pomiar przydziałów
Możesz także poprosić jmh o pomiar przydziałów za pomocą
-prof gc
:… Gdzie
gc.alloc.rate.norm
jest prawdopodobnie najciekawsza część, pokazująca, żezip
wersja przydziela ponad trzy razy więcejzipped
.Konieczne wdrożenia
Gdybym wiedział, że ta metoda będzie wywoływana w kontekstach bardzo wrażliwych na wydajność, prawdopodobnie zastosowałbym ją w następujący sposób:
Zauważ, że w przeciwieństwie do wersji zoptymalizowanej w jednej z pozostałych odpowiedzi, ta funkcja jest używana
while
zamiast,for
ponieważfor
nadal będzie się przełączać do operacji kolekcji Scala. Możemy porównać tę implementację (withWhile
), zoptymalizowaną (ale nie na miejscu) implementację drugiej odpowiedzi (withFor
) oraz dwie oryginalne implementacje:To naprawdę ogromna różnica między wersjami imperatywną i funkcjonalną, a wszystkie sygnatury metod są dokładnie identyczne, a implementacje mają tę samą semantykę. To nie jest tak, że implementacje imperatywne używają stanu globalnego itp. Chociaż wersje
zip
izipped
są bardziej czytelne, osobiście nie sądzę, by istniał sens, w którym wersje imperatywne są sprzeczne z „duchem Scali”, i nie zawahałbym się korzystać z nich osobiście.Z tabelą
Aktualizacja: Dodałem
tabulate
implementację do testu porównawczego na podstawie komentarza w innej odpowiedzi:Jest znacznie szybszy niż
zip
wersje, choć wciąż znacznie wolniejszy niż te niezbędne:Tego się spodziewałem, ponieważ wywoływanie funkcji nie jest z natury drogie, a dostęp do elementów tablicy za pomocą indeksu jest bardzo tani.
źródło
Rozważać
lazyZip
zamiast
zip
Scala 2.13 dodana
lazyZip
na korzyść.zipped
zipped
(i stądlazyZip
) jest szybszy niżzip
dlatego, że, jak wyjaśnili Tim i Mike Allen ,zip
następnamap
spowoduje dwie osobne transformacje ze względu na ścisłość, azipped
następniemap
spowoduje pojedynczą transformację wykonaną za jednym razem z powodu lenistwa.zipped
dajeTuple2Zipped
, i analizowanieTuple2Zipped.map
,widzimy dwie kolekcje
coll1
icoll2
są iterowane, a po każdej iteracjif
przekazywana funkcjamap
jest stosowana po drodzebez konieczności przydzielania i przekształcania struktur pośrednich.
Stosując metodę testu porównawczego Travisa, oto porównanie między nowym
lazyZip
a przestarzałymzipped
gdziedaje
lazyZip
wydaje się działać nieco lepiej niżzipped
naArraySeq
. Co ciekawe, zauważy znacznie pogorszeniu podczas używanialazyZip
naArray
.źródło
Zawsze powinieneś być ostrożny przy pomiarze wydajności ze względu na kompilację JIT, ale prawdopodobnie przyczyną jest
zipped
lenistwo iArray
wyciąganie elementów z oryginalnych vaules podczasmap
połączenia, podczas gdyzip
tworzy nowyArray
obiekt, a następnie wywołujemap
nowy obiekt.źródło