Wydajność si szarpa to tragedia, czy tylko ja nie umiem go efektywnie wykorzystać?

Wydajność si szarpa to tragedia, czy tylko ja nie umiem go efektywnie wykorzystać?

Zadanie: Wskazać w którym miejscu obrazka koncentracja szczegółów jest duża, a w którym mała.
Pomysł na rozwiązanie: Zrobić lekki blur obrazka, a potem policzyć różnicę między oryginałem a rozmytą kopią. Jeszcze wszystko było fajnie, wstępny test na Photoshopie pokazuje, że da się uzyskać całkiem niezłe efekty. Jednak moja implementacja tego w C# jest KOSZMARNIE wolna!

Nie wiem, czy ja robię błąd, czy to po prostu c# jest mało wydajny, ale coś jest nie tak. Skalowanie i pozbawianie koloru obrazka idzie całkiem szybko, natomiast liczenie rozmycia – okropnie wolno.

Zacząłem od wersji takiej, że każdy piksel obrazka jest wczytywany osobno. Było tragicznie. Przepisałem obrazek do tablicy bajtów i na niej liczę wg przekształcenia:

[1,2,1,
2,4,2,
1,2,1]/16

i znów okropnie wolno. Dla wersji z macierzą 5×5 jeszcze gorzej. Zdaję sobie sprawę, że dla marnego obrazka 100×100 to jest 2 600 000 mnożeń i dzieleń oraz trochę przepisywania, ale na Teutatesa! Stary Photoshop na kiepskim sprzęcie liczy rozmycie Gaussa nieporównywalnie szybciej!

Próbowałem wykorzystać do zadania bajerek o nazwie Parallel.For ale zrezygnowałem po oberwaniu wyjątkiem… Pozwoliłoby to policzyć wynik teoretycznie krócej, ale nie szybciej…

Czy rzeczywiście muszę robić hacki typu przemycanie bajtów w longach lub pisać samemu kod wykorzystujący SSE żeby to zrobić szybko? A może zamienić .net na mono i użyć ichniego wsparcia dla SSE? Ostatecznie mógłbym uzyć zewnętrznych bibliotek działających szybko i sprawnie, ale to jest niewskazane, bo chcę się czegoś nauczyć, a nie tylko osiągnąć efekt.
Jeśli trzeba, to z bólem serca porzucę ce kratkę na rzecz ce pe pe, ale bardzo, bardzo niechętnie…

Da się to zrobić szybciej? JAK?

  • Szymon

    nie znam sie, tak mi tylko przyszło do głowy że niektóre programy mogą korzystać przy takich obliczeniach z karty graficznej…

  • AdamK

    Weź pod uwagę że PS jest najprawdopodobniej podoptymalizowany w asemblerze.

    No i jak byś opublikował kod to można by coś doradzić.

  • Krystian

    "moja implementacja tego w C# jest KOSZMARNIE wolna"

    Wolna… tzn? Przydałby się jakiś rząd wielkości. Poza tym jeśli się nie mylę to Paint.NET jest napisany w C# i tam są dostępne tego typu efekty, a program radzi sobie z nimi całkiem nieźle.

    Z drugiej strony ja bym nie wymyślał koła na nowo:P Jako miłośnik Pythona skorzystałbym z biblioteki PIL. Wiem, wiem… Python i wydajność… Ale PIL jest napisany w większości w C. Wraz z biblioteką NumPy jest częścią wchodzącą w skład Inkscape.

    Pierwszy lepszy przykład z google:

    http://archive.alwaysmovefast.com/basic-edge-detection-in-python.html

  • Jedziesz najpierw po wierszach licząc sobie maskę [1, 2, 1], a następnie jedziesz po kolumnach wyniku poprzedniej operacji licząc maskę [1, 2, 1]^T. Na koniec dzielisz wynik przez 16. Daje to 60k dodawań, 20k przesunięć w lewo o jeden i 10k przesunięć o cztery w prawo.

  • Metoda zaproponowana przez mina86 jest chyba najlepsza do tego przypadku. Ogólnie splot z maską jest bardzo wolny licząc go w pętlach, zwłaszcza jak maski są spore (w,h > 10). Dochodzi wtedy także problem wartości na brzegu, gdzie prawie połowa maski wychodzi poza obraz. Są lepsze metody, jak chociażby użycie FFT czy wspomniane rozbicie na wiersze i kolumny, które tutaj będzie najlepsze.

  • Co do samej metody, to faktycznie przejście na dziedzinę częstotliwości jest polecanym sposobem wykrywania "zmian". Można wtedy nałożyć ładne maski i wyciąć żądaną informację dość prosto.

  • Daniel

    Jeżeli robisz operacje na Bitmapie za pomocą kodu zarządzanego, to będzie to wolne. Musisz wykorzystać kod unsafe oraz LockBits na bitmapie i bezpośrednio operować.
    Różnica jest drastyczna.

  • @mina86:
    Spróbuję w weekend. Powinno to dać niezłego kopa wydajnościowego.
    Dla pewności: w [1,2,1]^T co oznacza^T ?
    I jak zastosować to dla 5×5? Wystarczy tylko zwiększyć wektor?

    @ratixu: FFT jest trochę zbyt mądre dla mnie 😉 jeśli się nie uda, to cóż, trzeba będzie się dokształcić. Mam jednak nadzieję, że obejdzie się bez tego.

    @Daniel: Trafna uwaga. Domyślałem się, że gdzieś tkwi haczyk, ale nie wiedziałem gdzie…

    @Szymon: moja karta graficzna tego nie obsłuży. Stary photoshop też raczej tego nie robił 😉 Poza tym karta graficzna dla zwykłego blura? Overkill!

    @Krystian: Dla obrazka wielkości tapety na pulpit zdążyłem zrobić kawę. Ten rząd wielkości 😉

    @AdamK: Opublikuję kod, jak całość będzie miała ręce i nogi, albo chociaż będzie jakiś etap zamknięty. A tak – możnaby się jedynie śmiać z nieczytelności mojego kodu. Na co mi to? 😉
    O optymalizacji w asm myślałem, ale to chyba też overkill… Poza tym za słaby jestem w te klocki.

    @Krystian: Brałem pod uwagę pythona, ale chyba wolę pozostac przy c# póki co. Lepiej je znam, visual studio jest wygodniejsze od vi. A przekształcenie jest takie, a nie inne bo skończona postać, bez żadnych kolejnych przekształceń jest dokładnie taka, jakiej potrzebuję do dalszego celu.

    Podsumowując – najpierw przejść do wersji z rozbitej na wiersze i kolumny, potem na kod niezarządzany, a jak to nic nie da, to mono i SIMD. Jak i to nic nie da, to FFT… Tyle zabawy, a to dopiero wstęp do właściwej funkcjonalności programu…

  • To co napisał Daniel plus pomyśl, czy nie dałoby się gdzieś zamienić dzielenia na mnożenie przez odwrotność (a/b=a*(1/b)), jak i policzyć pewne rzeczy poza pętlami i używać stałych (prekalkulacje). Pomyśl też, czy wszędzie potrzebujesz rachunku zmiennoprzecinkowego – mnożenie i dzielenie liczb rzeczywistych jest wolniejsze niż całkowitych. A najlepiej to pokaż kod.

  • mt3o, [1, 2, 1]^T to macierz obrócona do pionu. Z punktu widzenia pisanego kodu, czymś takim się przejmować nie będziesz. Chodzi o to, że maska którą podałeś to złożenie [1, 2, 1] * [1, 2, 1]^T i właśnie to pozwala na taką optymalizację jak opisałem.

    Branch Predictor, akurat ta maska, którą używa mt3o pozwala na zastosowanie przesunięć bitowych zamiast mnożenie i dzielenia, więc na dobrą sprawę nie ma się co zastanawiać jak dzielenie zastąpić mnożeniem.

  • Code or it didn’t happen! 😉
    Rozumiem, że pixelami można manipulować traktując ich wartości jako trójki liczb z zakresu 0-1, ale naturalnie faktycznie to są liczby naturalne 😉 Gdzieś musza zostać przekształcone do postaci całkowitej…

  • @mina86: racja, jakoś ominął mnie Twój komentarz, przepraszam.
    W ogóle, to odradzam stosowanie asma zanim wyczerpie się wszystkie inne możliwości. 😉

  • @mina86: Wektor transponowany, jasne. Rozumiem. Daszek ^ kojarzy mi się z xor ale to było zbyt dziwne 😉

    @Branch: Macierz do filtru wydzieliłem już jako osobną tablicę, piksele z obrazka wyrzuciłem do zewnętrznej tablicy. Obecnie przetwarzanie jest w podwójnej pętli, a sam filtr w kolejnej podwójnej pętli. Ubicie potokowości 😉 Wersję 3×3 rozpisywałem sam, ale dla 5×5 wygodniejsze były pętle.

    Tak prawdę mówiąc, czy w dzisiejszych procesorach wspierających cuda typu SSE które ponoć jest używane przez .net zastępowanie dzielenia i mnożenia prostszymi operacjami na sens? Wydaje mi się, że jmp jest większym wyzwaniem dla CPU niż dzielenie…

    @Caladan: Nie pokażę źródła bo się go wstydzę 😛 Jak coś zacznie działać i doprowadzę kod do kultury to wrzucę gdzieś źródła. Nie wcześniej.

  • Pytanie, czy SSE zadziała w tym momencie. Ale akurat fakt, można zoptymalizować kod po prostu unikając skoków i przewidywań. Nie wiem, czy .NET rozwija pętle i wektoryzuje działania, ale przecież takie mnożenie 3 współczynniki razy 3 pixele to można wykonać jedną instrukcją. Potem "pozioma suma" i już masz policzony jeden wiersz 🙂

  • @mt30: wrzucanie pikseli do osobnej tablicy samo w sobie zajmuje trochę czasu szczególnie, jeśli robisz to po pikselu, a już w ogóle makabra, jeśli rozbijasz każdy piksel na składowe i każdą składową (pierwotnie 8 bitów) wrzucasz do nowego, 32-bitowego elementu. Jeżeli używasz do tego GetPixel (czy jak to się nazywało), to pierwsze "wąskie gardło" gotowe.
    Obecność SSE w procesorze i .net’cie o niczym nie świadczy, bo są przypadki, gdy użycie SSE zadziała na niekorzyść (to jest narzędzie, a nie rozwiązanie) – co zresztą napisał Caladan.
    Rozbijanie operacji na prostsze przeważnie ma sens, szczególnie w środowiskach takich jak .net’owy CLR. Proste operacje łatwiej dalej optymalizować.

  • Talica jest typu byte[,] z wartościami w skali szarości. Wąskiego gardła jeszcze w tym miejscu nie ma (nie sprawdząłem dla obrazków większych niż rozmiar pulpitu na laptopie).
    Z ciekawości, jak inaczej, jeśli nie poprzez getPixel? Za pomocą kodu niezarządzanego i z rzutowaniem na long? 🙂 Przeszło mi to przez głowę, przyznaję.
    Zdaję sobie sprawę, że SSE nie jest cudownym lekiem, ale trochę by przyspieszył obliczenia. Nie chcę dyskutować o szczegółach, bo jeśli tylko się da – nie zamierzam tak tego pisać. Ani porywać się na optymalizację w asm…
    W weekend będę miał trochę czasu, zobaczymy co z tego wyjdzie.

  • A skąd masz te wartościi?
    A zamiast GetPixel, to tak jak napisał Daniel – LockBits i dalej sobie poszukaj na MSDNie.