xxx_xx_x

https://4programmers.net/Profile/52045
2019-02-09 22:18

Mój pierwszy post na mikro będzie dotyczyć dyskusji z wątku @furious programming odnośnie optymalizacji kodu do przyciemniania / rozjaśniania.

Moja propozycja ulepszenia kodu :
można napisać to znacznie lepiej, zamiast posuwać się pixel po pixelu zrobić cast tablicy na uint32, czytać po 4 bajty na raz, na każdym wykonujesz tą samą operacje, zamiast 3x (kanał >> 1) można wykonać po prostu (( (int32) >> 1) & 0x7f7f7f7f) w ten sposób masz 1 odczyt i 1 zapis oraz tylko 2 operacje logiczne. Dodatkowo ponieważ odczytujesz po 4 bajty na raz to masz dane zawsze wyrównane do 4 co znacznie przyśpiesza dostęp do nich.

Spotkała się z krytyką:

  1. Ze względu na brak podzielności bitmapy przez 4 i tym samym brak możliwości użycia kodu w sposób uniwersalny dla każdej bitmapy
  2. Rozwiązanie z paletą jest szybsze.

Po kolei udowodnię błąd tych twierdzeń;)

Założenie jest takie:

  • bitmapa o wymiarach x na y w 24 bitach czyli 3 bajty na kolor,
  • przyciemnianie poprzez shift bitów o jedną pozycję w prawo czyli po prostu dzielenie przez 2^1

Ad 1.
Oryginalny algorytm:

  • pobierz trzy bajty (R, G, B)
  • podziel każdy przez 2
  • zapisz
  • powiel dla każdego pixela obrazu

pierwszy problem to: komputer nie potrafi pobierać i zapisywać po trzy bajty więc kompilator o ile wspiera taką mechanikę musi ten problem obchodzić, czyli technicznie wykonywane muszą zostać dodatkowe operacje.
Drugi problem, odczyt bajtów "niewyrównanych" do rozmiaru słowa maszynowego jest znacznie wolniejszy.
Trzeci problem trzeba rozbić te trzy bajty na "trzy zmienne"
Czwarty problem każdy pixel wymaga 3 operacji logicznych

Moja propozycja :

  • pobierz 4 bajty jako jeden int - pierwszy i drugi problem zostaje wyeliminowany
  • nie rozbijamy pixeli na składowe, nawet ich nie rozróżniamy - problem trzeci nie istnieje
  • wykonaj jedno przesunięcie i jedna operację logiczną co daje 2 operacje logiczne na 4 bajty, czyli 4 pixele to 6 operacji logicznych czyli 1.5 operacji logicznej na pixel - dwa razy mniej operacji logicznych.

Dlaczego algorytm działa? Przykładowo mając 4 pixele mamy :
R0 G0 B0 R1 G1 B1 R2 G2 B2 R3 G3 B3

Odczytując je po 4 bajty odczytamy :
(R0 G0 B0 R1), (G1 B1 R2, G2), (B2, R3, G3 B3)

przesunięcie bitowe o jeden bit w prawo spowoduje że każdy bit0 wpadnie na pozycję bit7 sąsiedniego bajtu, musimy jedynie wygasić ten bit dla każdej składowej czyli operacja logiczna "and 0x7F" dla każdego oktetu to daje "and 0x7F7F7F7F".

Problem stanowi podzielność przez 4, jeżeli (total_bytes mod 4) daje wynik inny niż zero to znaczy że kilka ostatnich bajtów nie zostanie poddanych tej procedurze, w tej sytuacji możemy:
a) alokować kilka bajtów więcej tak aby total_bytes mod 4 było równe 0, czyli max 3 dodatkowe bajty
b) ostatnie max 3 bajty traktować starym algorytmem

Ad 2.
"Rozwiązanie z przeliczona paletą jest szybsze/podobne" to błędne stwierdzenie.
Rozwiązanie w optymistycznych warunkach będzie podobne w pesymistycznych będzie wolniejsze nawet od algorytmu podstawowego. Jest to typowy algorytm "memory bound"
Związane jest to ściśle z rozmiarami cache procesora (L1 L2 L3), oraz sposobem dostępu do danych, jeżeli dane odczytywane są liniowo wtedy komputer może nadążyć z ich odczytem, gorzej w sytuacji gdy dostęp jest losowy oraz gdy posługujemy się dużymi tablicami i cache są często utylizowane, powodując częsty cache miss:

Paleta ma 256 bajtów wystarczająco żeby zmieścić się w L1, niestety w przypadku edytowania obrazka(dużej bitmapy) również ona będzie umieszczana w tym cache, co spowoduje wywłaszczanie palety z cache i przenoszenie jej do L2, L3 oraz ram.
Dostępy pomiędzy warstwami cache różnią się znacząco :

https://stackoverflow.com/que[...]arious-caches-and-main-memory
Core i7 Xeon 5500 Series Data Source Latency (approximate)
local L1 CACHE hit, ~4 cycles ( 2.1 - 1.2 ns )
local L2 CACHE hit, ~10 cycles ( 5.3 - 3.0 ns )
local L3 CACHE hit, line unshared ~40 cycles ( 21.4 - 12.0 ns )
local L3 CACHE hit, shared line in another core ~65 cycles ( 34.8 - 19.5 ns )
local L3 CACHE hit, modified in another core ~75 cycles ( 40.2 - 22.5 ns )
remote L3 CACHE (Ref: Fig.1 [Pg. 5]) ~100-300 cycles ( 160.7 - 30.0 ns )
local DRAM ~60 ns
remote DRAM ~100 ns

Paleta jest niekorzystna w tym przypadku ponieważ zużywa memory bus, a procesor się po prostu... nudzi

Problem jest jeszcze większy w przypadku mocno zróżnicowanych danych wejściowych bitmapy, spowoduje to dużo losowych dostępów do palety, przez co cpu nie może przewidywać dostępu do danych (prefetch) co powoduje dodatkowe cache miss.

Algorytmy przetwarzania obrazów / macierzy bardzo często ograniczone są dostępem pamięci nie pracą cpu!
Lepiej dać więcej pracy CPU i ograniczyć dostęp do pamięci, a odczyty / zapisy ułożyć w sposób liniowy, dzięki czemu praca cache jest idealna, a procesor nie musi czekać na dane.

Ostatecznie kod dla bitmapy 1981 x 1280 w 24 bitach i dla 111 klatek :

#include <iostream>
#include <ctime>

using namespace std;

int main(int argc, char *argv[]) {
    int width = 1981;
    int height = 1281;
    int bpp = 3 * 111;  // 111 to ilość klatek, nie chciałem tworzyć w ramach testu dodatkowej zmiennej, kod najpierw powstał dla jednej klatki 

// trzy identyczne bitmapy
    unsigned char* image1 = new unsigned char [bpp * width * height];
    unsigned char* image2 = new unsigned char [bpp * width * height];
    unsigned char *image3 = new unsigned char [bpp * width * height];

// przygotowanie danych w taki sposób żeby dostęp do palety był mocno losowy
    for(int i=0; i<bpp * width * height; i++) {
    unsigned char val = (i * i * 5 + i * 4 + 2)  & 0xff;
    image1[i] = val;
    image2[i] = val;
        image3[i] = val;
    }

// przygotowanie palety
    unsigned char pal[256];
    for(int i=0; i<256; i++) {
        pal[i] = (unsigned char)(i >> 1);
    }

// oryginalny algorytm 
    clock_t t0 = clock();
    for(int i=0; i<bpp * width * height; i+=3) {
    image1[i + 0] = image1[i + 0] >> 1; 
    image1[i + 1] = image1[i + 1] >> 1; 
    image1[i + 2] = image1[i + 2] >> 1; 
    }
    clock_t t1 = clock();

// algorytm po 4 bajty 
    int* ptr = (int*)image2;
    int total = bpp * width * height;    
    for(int i=0; i<total / 4; i++) {
    ptr[i] = (ptr[i] >> 1) & 0x7f7f7f7f;
    }
// niepodzielna część danych 
    if ((total & 3) != 0) {
        for(int i=0; i<(total & 3); i++) {
            image2[total - (total & 3) + i] = image2[total - (total & 3) + i] >> 1; 
        }
    }
    clock_t t2 = clock();

// algorytm z paletą 
    for(int i=0; i<bpp * width * height; i+=3) {
    image3[i + 0] = pal[image3[i + 0]]; 
    image3[i + 1] = pal[image3[i + 1]]; 
    image3[i + 2] = pal[image3[i + 2]]; 
    }
    clock_t t3 = clock();

    cout<<"TIME 1: "<<((float)(t1 - t0)/CLOCKS_PER_SEC)<<endl;
    cout<<"TIME 2: "<<((float)(t2 - t1)/CLOCKS_PER_SEC)<<endl;
    cout<<"TIME 3: "<<((float)(t3 - t2)/CLOCKS_PER_SEC)<<endl;

// walidacja danych, sprawdzamy zgodność wyników 
    for(int i=0; i<bpp * width * height; i++) {
    if (image1[i] != image2[i] || image1[i] != image3[i]) {
        cout<<"INVALID DATA : " << i << endl;
        }
    }

    delete[] image3;
    delete[] image1;
    delete[] image2;
    return 0;
}

Wynik na moim komputerze (mac pro):
TIME 1: 0.32208
TIME 2: 0.092952
TIME 3: 0.437729

TIME 1 - oryginalny algorytm
TIME 2 - zaproponowany przeze mnie
TIME 3 - wariant z paletą

Jak widać test pokrywa się z opisem, algorytm oryginalny jest szybszy od tego z paletą ze względu na cache miss, natomiast mój algorytm z uwzględnieniem rozmiaru słowa jest ponad 3 razy szybszy od algorytmu oryginalnego.

Można również przetestować np tutaj :
https://www.onlinegdb.com/online_c++_compiler

Czasy jakie uzyskałem to :
TIME 1: 3.4489
TIME 2: 1.33976
TIME 3: 3.58184

Podobnie jak na moim komputerze, ale wyniki między test1 i test2 różnią się nieznacznie

https://4programmers.net/Profile/71375

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

https://4programmers.net/Profile/78956

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

https://4programmers.net/Profile/86261

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

https://4programmers.net/Profile/52045

@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.

https://4programmers.net/Profile/92941

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?

https://4programmers.net/Profile/48869

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.

https://4programmers.net/Profile/52045

@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ć.

https://4programmers.net/Profile/52045

@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.

https://4programmers.net/Profile/92941

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

https://4programmers.net/Profile/92941

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 ;)

https://4programmers.net/Profile/52045

@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:)

https://4programmers.net/Profile/92941

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

https://4programmers.net/Profile/52045

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

https://4programmers.net/Profile/92941

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.

https://4programmers.net/Profile/78878

Ł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).

https://4programmers.net/Profile/52045

@jarekr000000: dla mnie ma to taka sama czytelność, a plus jest taki że w debug jednak działa to szybciej dla niektórych algorytmów. Po prostu nie widzę różnicy w tych zapisach i preferuje ten.

https://4programmers.net/Profile/37933

czemu po prostu na CPU nie policzycie? zwykły shader by załatwił sprawe