xxx_xx_x

xxx_xx_x
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

xxx_xx_x

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

krwq

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