Radzenie sobie z zaskakującym brakiem ParList w scala.collections.parallel

Question

Tak więc Scala 2.9 pojawiła się niedawno w testach Debiana, wprowadzając do niego nowoodkryte kolekcje równoległe.

Załóżmy, że mam kodu jakiś odpowiednik

def expensiveFunction(x:Int):Int = {...} 

    def process(s:List[Int]):List[Int} = s.map(expensiveFunction) 

teraz z malusieńki bit ja zgromadzonego o kolekcjach równoległych przed docs faktycznie pojawił się na moim komputerze, spodziewałem parallelize to właśnie przez przełączenie Lista do ParList ... ale ku mojemu zdziwieniu, nie ma jednego! (Tylko ParVector, ParMap, ParSet ...).

Jako workround ten (lub równoważny jednej linii) wydaje się działać na tyle dobrze:

def process(s:List[Int]):List[Int} = { 
    val ps=scala.collection.parallel.immutable.ParVector()++s 
    val pr=ps.map(expensiveFunction) 
    List()++pr 
    } 

uzyskując około x3 poprawę wydajności w kodzie testowym i osiągnięcie znacznie wyższe obciążenie procesora (rdzeń quad oraz Hyperthreading i7). Ale wydaje się trochę przyziemne.

Moje pytanie jest rodzajem zagregowanym:

• Dlaczego nie jest ParList?
• Biorąc pod uwagę, że nie ma ParList, czy istnieje lepszy wzór/idiom, który powinienem przyjąć, aby nie czułem, że ich brakuje?
• jestem po prostu „za czasów” Korzystanie wymienia LOT moich programów Scala (jak wszystkie książki Scala I odkupione w 2,7 dni nauczył mnie) i powinien być rzeczywiście szersze wykorzystanie Vectors? (Mam na myśli w C++ land Zasadniczo potrzebuję całkiem dobrego powodu, aby użyć std::list przez std::vector).

Answer 1

Po pierwsze, pozwól mi pokazać, jak zrobić równoległą wersję tego kodu:

def expensiveFunction(x:Int):Int = {...} 

def process(s:List[Int]):Seq[Int] = s.par.map(expensiveFunction).seq 

To będzie mieć rzeczy Scala dowiedzieć się, dla siebie - i, nawiasem mówiąc, to używa ParVector. Jeśli naprawdę chcesz List, zadzwoń pod numer .toList zamiast .seq.

Co do pytania:

• Nie ma ParList ponieważ List jest nierozerwalnie nierównoległe struktura danych, ponieważ każda operacja na nim wymaga przechodzenie.

• Powinieneś kodować do cech zamiast klas - Seq, ParSeq i GenSeq, na przykład. Nawet cechy wydajności List są gwarantowane przez LinearSeq.

• Wszystkie książki sprzed Scala 2.8 nie miały na myśli nowej biblioteki kolekcji. W szczególności kolekcje naprawdę nie miały spójnego i kompletnego API. Teraz to robią, a zyskasz dużo, wykorzystując to.

  Co więcej, nie było kolekcji takiej jak Vector w Scala 2.7 - niezmienna kolekcja z (prawie) stałym dostępem indeksowanym.

Answer 2

List s są świetne, jeśli chcesz dopasować do wzorca (np. case x :: xs) i dla sprawnego przedrostka/iteracji. Jednak nie są one zbyt dobre, gdy chcesz szybko uzyskać dostęp do indeksu lub podzielić na porcje lub dołączyć (tj. xs ::: ys).

Dlatego nie ma sensu (aby mieć równoległe List), kiedy myślisz, że tego typu rzeczy (dzielenie i łączenie) jest dokładnie co jest potrzebne do wydajnej równoległości. Zastosowanie:

xs.toIndexedSeq.par 

Answer 3

List nie można łatwo podzielić na różne podlist który sprawia, że ​​trudno parallelise. Po pierwsze ma dostęp O (n); również List nie może rozebrać ogona, więc trzeba podać parametr długości.

Domyślam się, że przyjęcie Vector będzie lepszym rozwiązaniem.

Należy zauważyć, że Scala jest Vector różni się od std::vector. Ta ostatnia jest zasadniczo opakowaniem wokół standardowej tablicy, ciągłym blokiem w pamięci, który musi być kopiowany co jakiś czas podczas dodawania lub usuwania danych. Scala's Vector jest wyspecjalizowaną strukturą danych, która pozwala na wydajne kopiowanie i dzielenie przy jednoczesnym zachowaniu samych danych niezmiennych.