grski

i to jest mirko o jakie nic nie robiłem
quality content!

Hispano-Suiza

Szanuję! Gdyby tylko nie ten Mac Pro :-)

Visual Code

Właśnie czytając tamten wpis zastanawiałem się, czy można zamienić operacje pixelwise na coś szybszego.

xxx_xx_x

@Hispano-Suiza: Sam nie kupiłem, służbowy ;p

xxx_xx_x

@Visual Code: Optymalizacja cache to ciekawy temat i ma zwykle ogromny wpływ na przetwarzanie dużej ilości danych. NA potrzeby cache powstają osobne algorytmy np cache-blocking do mnożenia macierzy.

superdurszlak

Problem wynika raczej ze zwiększonej liczby dostępów do cache w ogóle, niż większej liczby chybień w cache - pod warunkiem, że obraz jest przechowywany w ciągłym obszarze, bez tych nieszczęsnych dopełnień. Ale bitmapa jako char* nie będzie mieć tego problemu.

Swoją drogą, próbowałeś sprawdzić, czy i jaką korzyść przyniesie zastąpienie uint32 przez uint64 i/lub włączenie SSE?

vpiotr

Można jeszcze użyć ułożenia RGBN gdzie 4-ty bajt jest nie używany na docelowym obrazku. Zysk jest taki że można robić operacje specyficzne dla danego koloru no i każda linia (a nie tylko co któraś) jest wyrównana do 4 bajtów.

xxx_xx_x

@superdurszlak: co do cache miss, to problem głównie obsługi kilku tablic (tablica obrazu i tablica palety), które współdzielą cache więc wzajemnie się wywłaszczają.
uint64 na pewno poprawiło by wydajność dla procesorów 64 bitowych, które radzą sobie z takimi operacjami za pomocą jednej instrukcji w innym przypadku emulowało by to dostęp 2 razy po 32 bity o ile wiem. Co do SSE, to prawdopodobnie kompilator sam je stosuje przy optymalizacji O2 i O3, zawsze można skompilować kod do postaci asm i sprawdzić.

xxx_xx_x

@vpiotr tak jest to rozwiązanie, ale dość kosztowne pamięciowo i moze sie okazać strzałem w stopę. Obraz 1920x1080 w 24 bpp ma 6mb, natomiast w 32 ma aż 8mb, więc te dwa dodatkowe 2mb trzeba przepchać przez magistralę.
Co do przetwarzania bitmap 24bpp można posłużyć się trikiem z rozwijaniem pętli, odczytujemy 12 bajtów(3 raz po 4) i z nich sami wypakowujemy 4 kolory.

superdurszlak

zdążyłem sprawdzić w Compiler Explorer pisząc mój poprzedni komentarz, użycie SSE przez kompilator trzeba wymusić flagami, przynajmniej w GCC i Clang, nie jestem pewien jak z ICC

superdurszlak

Btw. co do wywłaszczania z cache - problem będzie tylko w wariancie z paletą a i to zakładając, że faktycznie dojdzie do wywłaszczeń. Podejrzewam, że nie, bo odwołania do palety powinny mieć przyzwoitą lokalność czasową i potencjalnie również przestrzenną (paleta będzie siedzieć w 4 liniach cache po 64B każda, więc prawdopodobieństwo odwołania do danej linii będzie raczej spore, w dodatku jest pewnie jakaś korelacja między sąsiednimi kolorami na obrazie), poza tym cache miss bedą głównie wprzypadku tablicy image, do której odwołania są liniowe, każdy bajt czytany i zapisywany jest raz więc siłą rzeczy będziesz miał compulsory cache miss. Paleta jest czytana często więc ryzyko wypadnięcia z L1 cache będzie raczej niskie, a z L2 czy L3 to już w ogóle ;)

xxx_xx_x

@superdurszlak: Nie do końca, linie są oceniane w całości czyli 16 wartości palety mieści się w jednej linii cache. Odwołania do palety są na tyle losowe że nie podbijają żywotności takiego bloku zbyt dobrze. W praktyce zbyt ciężko jednoznacznie stwierdzić co robi CPU, można się kierować tylko ogólnymi założeniami, które i tak znowu zależą od architektury:)

superdurszlak

zawsze moglibyśmy dać sobie spokój z jałową dyskusją i odpalić cachegrinda... ale takie dywagacje są ciekawsze :D

xxx_xx_x

Nie znałem tego, ciekawe na ile ta symulacja jest wiarygodna i dla jakich procesorów?

superdurszlak

Wątpię by była w 100% precyzyjna, tym bardziej że symuluje tylko L1 i LL cache (pomijając L2 jeśli masz 3-poziomowy - uzasadnienie jest takie że podobno ma niewielkie znaczenie), ale jak robiliśmy w tym semestrze na HPC analizy teoretyczne, to cachegrind dawał liczby dostępów zgodne z przewidywanymi i w miarę sensowne liczby chybień (choć ciężko to oszacować analizując algorytm) - natomiast taki perf stat rzucał czasami tak absurdalnymi liczbami, że w ogóle nie traktowaliśmy go poważnie.Zresztą perf analizuje całość wykonania, więc chcąc przeanalizować konkretny fragment trzeba kombinować z wykonaniem z i bez fragmentu - kolejna okazja do błędów pomiarowych.

jarekr000000

Ładny post. Jakkolwiek, jak widzę takie coś pal[i] = (unsigned char)(i >> 1); to zawsze się zastanawiam: W 2019 naprawdę nadal nie masz zaufania do swojego kompilatora i on i/2 nie ogarnie? Może czas kompilator zmienić? Do tego to jest w prekalkulacji - zerowy wpływ na działanie systemu. Do tego.. własnie ze względu na cache na nowych prockach pewnie i tak nie ma znaczenia. Btw. możesz zmierzyć, jestem ciekaw czy się nie mylę.... (tylko proszę o nie robienie dowcipów z wyłączaniem optymalizacji).