SortAlgoBox - Scala, OpenCL i algorytmy sortujące

Zmęczony kopaniem się z C++ w moim poprzednim projekcie dotyczącym algorytmów sortujących ( https://github.com/tarsa/SortingAlgorithmsBenchmark ) postanowiłem zmienić strategię i przerzucić się na kombo Scala + OpenCL. Kod OpenCLowy na razie jest wbity na sztywno, ale w zamierzeniu mają być albo szablony, albo tłumaczenie AST na OpenCL. Zmiana podejścia ma umożliwić ucywilizowanie procesu rozwoju projektu, bo wcześniej zbyt dużo czasu poświęcałem na to, jak zrobić wydajne konstrukcje w C++, nie robiłem w ogóle testów jednostkowych, a sam refaktoring kodu w C++ to koszmar (moje subiektywne odczucie o którym nie mam zamiaru polemizować).

Projekt jest tutaj: https://github.com/tarsa/SortAlgoBox - jest w bardzo wczesnej fazie rozwoju, ale jest już kilka algorytmów sortujących wraz z jedną działającą implementacją w OpenCL

Jak ktoś ma ochotę to może konstruktywnie skrytykować :) albo nawet coś naklepać na ochotnika (np kolejny algorytm sortujący albo jakiś refaktor). Na start (tzn po ściągnięciu projektu na dysk) najtrudniejszą rzeczą do zrobienia jest zainstalowanie sterownika OpenCL i skonfigurowanie systemu/ projektu tak by połączenie Scala + OpenCL zadziałało. Mi działa tylko z linii komend, nie działa mi z poziomu IntelliJa (leci błąd, że JVM nie może znaleźć libOpenCL.so mimo że próbuję cudować z java.library.path).

Nie piszę w Scali, ale czemu SortAlgorithm jest klasą abstrakcyjną, a nie traitem? W Javie chyba dobrą praktyką jest unikanie klas abstrakcyjnych na rzecz interfejsów.

Kod gwałtownie ewoluuje :) więc klasy zmieniają się w traity i odwrotnie.

Podchodząc do pytania z innej strony - trait to z angielskiego cecha i to bardzo pasuje do zastosowania. Bycie algorytmem sortującym bardziej pasuje do klasy funkcjonalności, a nie do cechy czy zachowania.
Hierarchia się zresztą rozrasta - doszedł CpuSort do sortowania na CPU za pomocą OpenCL. Dojdzie jeszcze GpuSort i może rozbiję CpuSort np na CpuSeqSort i CpuParSort?

Poza tym, zamiana z abstract class na trait jest zwykle trywialna (w przeciwieństwie do zamiany w drugą stronę) i w moim przypadku taka zmiana jest kosmetyczna. No chyba, że jest jakiś konkretny, silny argument. Mam w zespole kolegę, który wszystko by robił za pomocą traitów i funkcyjnych konstrukcji, ale nie potrafi podać solidnej argumentacji. Mówi tylko, że chyba u samego Oderskiego wyczytał, że najlepiej używać (procentowo) jak najwięcej traitów i case class, ale nie mogę znaleźć artykułu o tym.

Wibowit napisał(a):

(...) refaktoring kodu w C++ to koszmar (moje subiektywne odczucie o którym nie mam zamiaru polemizować).

Niby napisałeś, że masz zamiaru polemizować ale obok czegoś takiego: https://github.com/tarsa/SortingAlgorithmsBenchmark/blob/master/sortalgo/sortheaphybrid.hpp ciężko przejść obojętnie. Nie wnikałem w sam algorytm ale ten kod to niezły WTF. W związku z tym nie dziwie się, że jego refaktoring to koszmar ; >

@Satirev:
Masz jakiś pomysł jak ulepszyć ten kod nie pogarszając wydajności? Zaletą C++ nad Javą czy Scalą jest właśnie ten trochę niższy stały współczynnik. Bezsensem byłoby pozbywanie się tej przewagi, skoro prawie we wszystkim innym C++ leży i kwiczy.

Ogłaszam, że projekt nadal żyje :]

Właśnie dodałem implementację sortowania bitonicznego dla dowolnych rozmiarów tablic. Są 3 wersje:

• czysta Scalowa,
• OpenCL dla CPU,
• OpenCL dla GPU

Enjoy!

https://github.com/tarsa/SortAlgoBox/blob/master/core/src/main/scala/pl/tarsa/sortalgobox/sorts/bubble/BubbleSort.scala#L30 <- może (array.size-1 to 1 by -1)? Mniej żonglowania, podobnie tutaj https://github.com/tarsa/SortAlgoBox/blob/master/core/src/main/scala/pl/tarsa/sortalgobox/sorts/selection/SelectionSort.scala#L30

Zrobione: https://github.com/tarsa/SortAlgoBox/commit/765538a4f43f3dcccc82c5bf80f5fd5aaf6c6519

< 20 min od zgłoszenia - ale ze mnie no-life :P

Dorobiłem GUI w JavieFX (a konkretniej to w ScaliFX). Pokazuje się bardzo podniecający widoczek przedstawiający wykres rozmiar vs czas dla różnych sortowań. Nagranie tutaj:
(BitonicSort to wersja w Scali, CpuBitonicSort to wersja w OpenCL dla CPU, GpuBitonicSort to wersja w OpenCL dla GPU)

Swoją drogą to animacje w tej JavieFX działają dość intrygująco (albo ja coś sknociłem) - kreski rosną do góry (bądź w dół), a potem uciekają w bok o_O

Dorzucę jeszcze jedną rzecz:

Wyniki po dodaniu standardowych sortów, czyli java.util.Arrays.sort (SequentialArraysSort) i java.util.Arrays.parallelSort (ParallelArraysSort).

Niby sortowanie bitoniczne ma złożoność O(n lg n lg n) ale w praktyce czas rośnie wolniej niż przy sortowaniu szybkim o złożoności O(n lg n) :P

PS:
Sortowanie w Scali jest oparte na komparatorach, implicit konwersjach, itd stąd jest wieeeele razy wolniejsze niż to OpenCLowe. Bez cudowania wydajność byłaby dużo bardziej zbliżona.

Kolejny etap za mną. Dodałem obsługę natywnych binarek kompilowanych z kodu C++. Zaimplementowałem jednakowy generator liczb pseudolosowych na każdej obsługiwanej platformie (JVM, OpenCL, native).

Objaśnienia do benchmarka:

• NativeStdSort - std::sort w C++
• BitonicSort - sortowanie bitoniczne w czystej Scali (z konwersjami implicit itd bajerami spowalniającymi)
• CpuBitonicSort - niezoptymalizowane sortowanie bitoniczne w OpenCL dla CPU
• GpuBitonicSort - niezoptymalizowane sortowanie bitoniczne w OpenCL dla GPU
• SequentialArraysSort - Arrays.sort w Javie
• ParallelArraySort - Arrays.parallelSort w Javie
• CpuQuickSort - sortowanie szybkie w OpenCLu dla CPU

Wyniki benchmarka (dla danego rozmiaru wygenerowane tablica wejściowa zawiera te same losowe wartości dla każdego typu testu):

Size: 1234
Sort name: NativeStdSort, time: 0.0 ms
Sort name: BitonicSort, time: 1.1 ms
Sort name: CpuBitonicSort, time: 0.85 ms
Sort name: GpuBitonicSort, time: 4.15 ms
Sort name: SequentialArraysSort, time: 0.05 ms
Sort name: ParallelArraySort, time: 0.05 ms
Sort name: CpuQuickSort, time: 0.7 ms
Size: 1609
Sort name: NativeStdSort, time: 0.0 ms
Sort name: BitonicSort, time: 1.05 ms
Sort name: CpuBitonicSort, time: 0.75 ms
Sort name: GpuBitonicSort, time: 3.6 ms
Sort name: SequentialArraysSort, time: 0.1 ms
Sort name: ParallelArraySort, time: 0.1 ms
Sort name: CpuQuickSort, time: 0.75 ms
Size: 2096
Sort name: NativeStdSort, time: 0.0 ms
Sort name: BitonicSort, time: 2.4 ms
Sort name: CpuBitonicSort, time: 0.55 ms
Sort name: GpuBitonicSort, time: 3.4 ms
Sort name: SequentialArraysSort, time: 0.15 ms
Sort name: ParallelArraySort, time: 0.1 ms
Sort name: CpuQuickSort, time: 0.8 ms
Size: 2729
Sort name: NativeStdSort, time: 0.0 ms
Sort name: BitonicSort, time: 2.3 ms
Sort name: CpuBitonicSort, time: 0.55 ms
Sort name: GpuBitonicSort, time: 3.5 ms
Sort name: SequentialArraysSort, time: 0.1 ms
Sort name: ParallelArraySort, time: 0.15 ms
Sort name: CpuQuickSort, time: 0.65 ms
Size: 3552
Sort name: NativeStdSort, time: 0.0 ms
Sort name: BitonicSort, time: 3.2 ms
Sort name: CpuBitonicSort, time: 0.9 ms
Sort name: GpuBitonicSort, time: 3.8 ms
Sort name: SequentialArraysSort, time: 0.25 ms
Sort name: ParallelArraySort, time: 0.25 ms
Sort name: CpuQuickSort, time: 0.75 ms
Size: 4622
Sort name: NativeStdSort, time: 0.0 ms
Sort name: BitonicSort, time: 4.4 ms
Sort name: CpuBitonicSort, time: 1.0 ms
Sort name: GpuBitonicSort, time: 3.65 ms
Sort name: SequentialArraysSort, time: 0.25 ms
Sort name: ParallelArraySort, time: 0.25 ms
Sort name: CpuQuickSort, time: 0.65 ms
Size: 6013
Sort name: NativeStdSort, time: 0.0 ms
Sort name: BitonicSort, time: 5.8 ms
Sort name: CpuBitonicSort, time: 1.2 ms
Sort name: GpuBitonicSort, time: 4.35 ms
Sort name: SequentialArraysSort, time: 0.3 ms
Sort name: ParallelArraySort, time: 0.3 ms
Sort name: CpuQuickSort, time: 0.8 ms
Size: 7821
Sort name: NativeStdSort, time: 0.05 ms
Sort name: BitonicSort, time: 7.05 ms
Sort name: CpuBitonicSort, time: 1.3 ms
Sort name: GpuBitonicSort, time: 4.0 ms
Sort name: SequentialArraysSort, time: 0.5 ms
Sort name: ParallelArraySort, time: 0.4 ms
Sort name: CpuQuickSort, time: 0.95 ms
Size: 10172
Sort name: NativeStdSort, time: 0.0 ms
Sort name: BitonicSort, time: 10.6 ms
Sort name: CpuBitonicSort, time: 1.9 ms
Sort name: GpuBitonicSort, time: 3.8 ms
Sort name: SequentialArraysSort, time: 0.7 ms
Sort name: ParallelArraySort, time: 0.45 ms
Sort name: CpuQuickSort, time: 1.15 ms
Size: 13228
Sort name: NativeStdSort, time: 0.0 ms
Sort name: BitonicSort, time: 14.05 ms
Sort name: CpuBitonicSort, time: 2.3 ms
Sort name: GpuBitonicSort, time: 4.15 ms
Sort name: SequentialArraysSort, time: 0.65 ms
Sort name: ParallelArraySort, time: 0.65 ms
Sort name: CpuQuickSort, time: 1.15 ms
Size: 17201
Sort name: NativeStdSort, time: 0.6 ms
Sort name: BitonicSort, time: 20.05 ms
Sort name: CpuBitonicSort, time: 2.95 ms
Sort name: GpuBitonicSort, time: 4.3 ms
Sort name: SequentialArraysSort, time: 1.0 ms
Sort name: ParallelArraySort, time: 0.7 ms
Sort name: CpuQuickSort, time: 1.3 ms
Size: 22366
Sort name: NativeStdSort, time: 1.0 ms
Sort name: BitonicSort, time: 26.0 ms
Sort name: CpuBitonicSort, time: 3.1 ms
Sort name: GpuBitonicSort, time: 4.0 ms
Sort name: SequentialArraysSort, time: 1.15 ms
Sort name: ParallelArraySort, time: 0.55 ms
Sort name: CpuQuickSort, time: 1.35 ms
Size: 29080
Sort name: NativeStdSort, time: 1.3 ms
Sort name: BitonicSort, time: 34.2 ms
Sort name: CpuBitonicSort, time: 4.55 ms
Sort name: GpuBitonicSort, time: 3.9 ms
Sort name: SequentialArraysSort, time: 1.6 ms
Sort name: ParallelArraySort, time: 0.8 ms
Sort name: CpuQuickSort, time: 1.9 ms
Size: 37809
Sort name: NativeStdSort, time: 1.65 ms
Sort name: BitonicSort, time: 49.25 ms
Sort name: CpuBitonicSort, time: 6.05 ms
Sort name: GpuBitonicSort, time: 4.7 ms
Sort name: SequentialArraysSort, time: 2.0 ms
Sort name: ParallelArraySort, time: 1.15 ms
Sort name: CpuQuickSort, time: 2.2 ms
Size: 49156
Sort name: NativeStdSort, time: 2.4 ms
Sort name: BitonicSort, time: 64.25 ms
Sort name: CpuBitonicSort, time: 8.1 ms
Sort name: GpuBitonicSort, time: 4.25 ms
Sort name: SequentialArraysSort, time: 2.7 ms
Sort name: ParallelArraySort, time: 1.65 ms
Sort name: CpuQuickSort, time: 2.5 ms
Size: 63907
Sort name: NativeStdSort, time: 3.0 ms
Sort name: BitonicSort, time: 84.58333333333333 ms
Sort name: CpuBitonicSort, time: 9.7 ms
Sort name: GpuBitonicSort, time: 5.2 ms
Sort name: SequentialArraysSort, time: 3.55 ms
Sort name: ParallelArraySort, time: 1.95 ms
Sort name: CpuQuickSort, time: 3.25 ms
Size: 83084
Sort name: NativeStdSort, time: 5.0 ms
Sort name: BitonicSort, time: 121.66666666666667 ms
Sort name: CpuBitonicSort, time: 13.55 ms
Sort name: GpuBitonicSort, time: 5.1 ms
Sort name: SequentialArraysSort, time: 4.55 ms
Sort name: ParallelArraySort, time: 2.45 ms
Sort name: CpuQuickSort, time: 4.15 ms
Size: 108014
Sort name: NativeStdSort, time: 6.15 ms
Sort name: BitonicSort, time: 159.71428571428572 ms
Sort name: CpuBitonicSort, time: 17.5 ms
Sort name: GpuBitonicSort, time: 8.0 ms
Sort name: SequentialArraysSort, time: 5.95 ms
Sort name: ParallelArraySort, time: 3.65 ms
Sort name: CpuQuickSort, time: 5.15 ms
Size: 140423
Sort name: NativeStdSort, time: 7.8 ms
Sort name: BitonicSort, time: 229.0 ms
Sort name: CpuBitonicSort, time: 24.45 ms
Sort name: GpuBitonicSort, time: 6.55 ms
Sort name: SequentialArraysSort, time: 7.85 ms
Sort name: ParallelArraySort, time: 4.4 ms
Sort name: CpuQuickSort, time: 6.65 ms
Size: 182554
Sort name: NativeStdSort, time: 9.35 ms
Sort name: BitonicSort, time: 300.75 ms
Sort name: CpuBitonicSort, time: 32.2 ms
Sort name: GpuBitonicSort, time: 7.25 ms
Sort name: SequentialArraysSort, time: 10.3 ms
Sort name: ParallelArraySort, time: 5.95 ms
Sort name: CpuQuickSort, time: 8.35 ms
Size: 237325
Sort name: NativeStdSort, time: 12.55 ms
Sort name: BitonicSort, time: 387.3333333333333 ms
Sort name: CpuBitonicSort, time: 41.9 ms
Sort name: GpuBitonicSort, time: 9.25 ms
Sort name: SequentialArraysSort, time: 13.55 ms
Sort name: ParallelArraySort, time: 7.1 ms
Sort name: CpuQuickSort, time: 10.1 ms
Size: 308527
Sort name: NativeStdSort, time: 17.0 ms
Sort name: BitonicSort, time: 555.0 ms
Sort name: CpuBitonicSort, time: 58.27777777777778 ms
Sort name: GpuBitonicSort, time: 9.5 ms
Sort name: SequentialArraysSort, time: 17.9 ms
Sort name: ParallelArraySort, time: 8.55 ms
Sort name: CpuQuickSort, time: 14.5 ms
Size: 401090
Sort name: NativeStdSort, time: 21.55 ms
Sort name: BitonicSort, time: 737.5 ms
Sort name: CpuBitonicSort, time: 76.14285714285714 ms
Sort name: GpuBitonicSort, time: 12.0 ms
Sort name: SequentialArraysSort, time: 23.95 ms
Sort name: ParallelArraySort, time: 11.8 ms
Sort name: CpuQuickSort, time: 18.15 ms
Size: 521422
Sort name: NativeStdSort, time: 28.6 ms
Sort name: BitonicSort, time: 958.0 ms
Sort name: CpuBitonicSort, time: 99.45454545454545 ms
Sort name: GpuBitonicSort, time: 11.5 ms
Sort name: SequentialArraysSort, time: 31.6 ms
Sort name: ParallelArraySort, time: 14.8 ms
Sort name: CpuQuickSort, time: 24.35 ms
Size: 677853
Sort name: NativeStdSort, time: 38.8 ms
Sort name: BitonicSort, time: 1371.0 ms
Sort name: CpuBitonicSort, time: 137.875 ms
Sort name: GpuBitonicSort, time: 16.2 ms
Sort name: SequentialArraysSort, time: 41.75 ms
Sort name: ParallelArraySort, time: 18.4 ms
Sort name: CpuQuickSort, time: 31.2 ms
Size: 881213
Sort name: NativeStdSort, time: 50.25 ms
Sort name: CpuBitonicSort, time: 180.66666666666666 ms
Sort name: GpuBitonicSort, time: 17.8 ms
Sort name: SequentialArraysSort, time: 55.10526315789474 ms
Sort name: ParallelArraySort, time: 23.75 ms
Sort name: CpuQuickSort, time: 40.95 ms
Size: 1145581
Sort name: NativeStdSort, time: 67.0 ms
Sort name: CpuBitonicSort, time: 248.4 ms
Sort name: GpuBitonicSort, time: 24.35 ms
Sort name: SequentialArraysSort, time: 73.57142857142857 ms
Sort name: ParallelArraySort, time: 28.8 ms
Sort name: CpuQuickSort, time: 54.31578947368421 ms
Size: 1489260
Sort name: NativeStdSort, time: 89.25 ms
Sort name: CpuBitonicSort, time: 330.0 ms
Sort name: GpuBitonicSort, time: 30.35 ms
Sort name: SequentialArraysSort, time: 96.0909090909091 ms
Sort name: ParallelArraySort, time: 36.6 ms
Sort name: CpuQuickSort, time: 71.78571428571429 ms
Size: 1936043
Sort name: NativeStdSort, time: 117.11111111111111 ms
Sort name: CpuBitonicSort, time: 437.6666666666667 ms
Sort name: GpuBitonicSort, time: 39.35 ms
Sort name: SequentialArraysSort, time: 125.75 ms
Sort name: ParallelArraySort, time: 47.05 ms
Sort name: CpuQuickSort, time: 94.72727272727273 ms
Size: 2516860
Sort name: NativeStdSort, time: 155.71428571428572 ms
Sort name: CpuBitonicSort, time: 608.5 ms
Sort name: GpuBitonicSort, time: 51.0 ms
Sort name: SequentialArraysSort, time: 182.66666666666666 ms
Sort name: ParallelArraySort, time: 63.6875 ms
Sort name: CpuQuickSort, time: 122.0 ms
Size: 3271923
Sort name: NativeStdSort, time: 207.4 ms
Sort name: CpuBitonicSort, time: 795.0 ms
Sort name: GpuBitonicSort, time: 65.0 ms
Sort name: SequentialArraysSort, time: 227.6 ms
Sort name: ParallelArraySort, time: 85.5 ms
Sort name: CpuQuickSort, time: 160.85714285714286 ms
Size: 4253504
Sort name: NativeStdSort, time: 270.0 ms
Sort name: CpuBitonicSort, time: 1095.0 ms
Sort name: GpuBitonicSort, time: 86.83333333333333 ms
Sort name: SequentialArraysSort, time: 295.75 ms
Sort name: ParallelArraySort, time: 112.11111111111111 ms
Sort name: CpuQuickSort, time: 209.6 ms
Size: 5529560
Sort name: NativeStdSort, time: 355.3333333333333 ms
Sort name: GpuBitonicSort, time: 110.7 ms
Sort name: SequentialArraysSort, time: 394.0 ms
Sort name: ParallelArraySort, time: 147.14285714285714 ms
Sort name: CpuQuickSort, time: 277.0 ms
Size: 7188433
Sort name: NativeStdSort, time: 470.6666666666667 ms
Sort name: GpuBitonicSort, time: 139.5 ms
Sort name: SequentialArraysSort, time: 525.5 ms
Sort name: ParallelArraySort, time: 193.83333333333334 ms
Sort name: CpuQuickSort, time: 363.3333333333333 ms
Size: 9344967
Sort name: NativeStdSort, time: 616.5 ms
Sort name: GpuBitonicSort, time: 191.16666666666666 ms
Sort name: SequentialArraysSort, time: 695.5 ms
Sort name: ParallelArraySort, time: 250.25 ms
Sort name: CpuQuickSort, time: 474.3333333333333 ms
Size: 12148462
Sort name: NativeStdSort, time: 821.5 ms
Sort name: GpuBitonicSort, time: 246.2 ms
Sort name: SequentialArraysSort, time: 921.5 ms
Sort name: ParallelArraySort, time: 335.6666666666667 ms
Sort name: CpuQuickSort, time: 628.5 ms
Size: 15793005
Sort name: NativeStdSort, time: 1082.0 ms
Sort name: GpuBitonicSort, time: 322.25 ms
Sort name: SequentialArraysSort, time: 1223.0 ms
Sort name: ParallelArraySort, time: 446.3333333333333 ms
Sort name: CpuQuickSort, time: 832.0 ms
Size: 20530911
Sort name: GpuBitonicSort, time: 435.0 ms
Sort name: ParallelArraySort, time: 593.0 ms
Sort name: CpuQuickSort, time: 1091.0 ms
Size: 26690189
Sort name: GpuBitonicSort, time: 558.5 ms
Sort name: ParallelArraySort, time: 761.0 ms
Size: 34697250
Sort name: GpuBitonicSort, time: 769.0 ms
Sort name: ParallelArraySort, time: 1061.0 ms
Size: 45106430
Sort name: GpuBitonicSort, time: 991.0 ms
Size: 58638364
Sort name: GpuBitonicSort, time: 1296.0 ms