SSE Optimierung fuer RLE (aehnlich)

[quote="knivil"]
for(unsigned int i=0; i<num; ++i) v[i] = i%256;
[/cpp]
bei sowas optimiert man fuer die daten, nicht den code, da waere wenigstens ein echtes testset wichtig.

Die Version von SSE sei erstmal unerheblich. Kann auch MMX sein.

welche cpu genau? wieviel threads?

hustbaer

kellerassel schrieb:

prefetch wurde sicher schon vorgeschlagen, oder

erkläre doch mal ein wenig was du in diesem zusammenhang mit "prefetch" meinst.

prefetchen tut die CPU schliesslich selbst.
CPUs sind da recht schlau.
die checken sogar mehrere streams auf unterschiedlichen pages, auch gerne rückwärts oder mit grösserer schrittweite.

und einfach so ein wort hinwerfen und so tun als ob es schlau wäre kann schliesslich jeder.

mit prefetch meinte ich, sich frauen 'aufzureißen', ehe mit der freundin schluss ist. sonst muss man im schlimmsten fall seine wäsche selber waschen

camper

Die Transformation des Signals in eines, das nur 0,1 enthält, ist relativ einfach.
Einfach PCMPGTB zwichen dem Signal und t anwenden (ggf. vorher noch 128 von jedem Byte abziehen, weil PCMPGTB vorzeichenbehaftetet Werte verwendet).
Ergebnis um ein Byte verschieben und XOR-Verknüpfen.
Schwieriger ist die RL-Codierung. Man könnte z.B. das obige Ergebnis in den Speicher schreiben und ein optimiertes strlen darüber laufen lassen. Oder z.B. PMOVMSKB mit bitscan verbinden. Eine effiziente Lösung mit SSE alleine fällt mir nicht ein.

knivil

const __m128i th = _mm_set1_epi8(t);
__m128i* p_in = (__m128i *)src;

for(int i=0; i<size; i+=16)
{
    v = _mm_load_si128((__m128i*)(&src[i]));
    __m128i tmp1v = _mm_min_epu8(v, th);
    __m128i tmp2v = _mm_cmpeq_epi8(tmp1v, th);

    uint16_t bits = _mm_movemask_epi8(v);

    // pos[...] = lut[bits] ...
}

Das ist mein bisheriger Ansatz. Danach kann uint16_t bits in 2 Bytes zerlegt werden und die Positionen aus einer Lookup-Tabelle herausgelesen warden. Auf diese Positionen wird der Offset i addiert und ins Positionsarray geschrieben. Ich knobel gerade noch am Aufbau der Lookup-Tabelle, so dass ich ebenfalls SSE benutzen kann. Wechsle ich von long auf short fuer Positionen, kann ich das Signal nur Segmentweise betrachten aber 8 shorts passen halt auch in ein XMM-Register.

Vielleicht kann ich auch noch was mit Ueberlaufarithmetik basteln und spare eine Instruktion. Mal schauen ob es was bringt:

const __m128i th = _mm_set1_epi8(255-t);
__m128i* p_in = (__m128i *)src;

for(unsigned int i=0; i<size/16; ++i)
{
    v = _mm_load_si128(&p_in[i]);
    v = _mm_add_epi8(v, th);

[quote="knivil"]

std::vector<unsigned char> v(num);
    for(unsigned int i=0; i<num; ++i) v[i] = i%256;
}

Wird V modifiziert? Falls ja, wie oft?

knivil

V wird nicht waehrend der "Punktextraktion" modifiziert und ist konstant. Waehrend der Suche nach einem geeigneten Schwellwert ist v ebenfalls konstant.

camper

knivil schrieb:

Vielleicht kann ich auch noch was mit Ueberlaufarithmetik basteln und spare eine Instruktion. Mal schauen ob es was bringt

Dann weißt du nicht mehr, welcher Wert der größere war, bei der Addition oder Subtraktion könnte ja ein Überlauf auftreten.

knivil schrieb:

V wird nicht waehrend der "Punktextraktion" modifiziert und ist konstant. Waehrend der Suche nach einem geeigneten Schwellwert ist v ebenfalls konstant.

Wieso berechnest du dir dann nicht die 256 Resultate vor? Sollte danach doch sehr viel effizienter sein das nur zu kopieren oder referenzieren. Notfalls ein Cache, ob ein Wert schon abgefragt wurde.

knivil

at hand schrieb:

Wieso berechnest du dir dann nicht die 256 Resultate vor?

self quote for the win:

... in 2 Bytes zerlegt werden und die Positionen aus einer Lookup-Tabelle

knivil

Nun, meine Ergebnisse moechte ich euch nicht vorenthalten. Als Vergleich dient die einfachste Implementierung, die ich mir vorstellen kann. Es ist daher nicht ganz fair. Es wird fuer Tests immer angenommen, dass das Positionsarray immer genug Platz bietet.

long line_thresh(unsigned char* line, unsigned long width, unsigned char th, unsigned short* pos, unsigned long size)
{
    bool above = true;
    unsigned long count = 0;
    for(unsigned long i=0; i<width; ++i)
    { 
        bool tmp = line[i]>=th; 

        if (above != tmp) 
        { 
            if (count<size) pos[count] = i; 
            above = tmp; 
            ++count; 
        } 
    }
    return count; 
}

Fuer SSE bedarf es einiger Vorbereitung, wie das Initialisieren einer Lookup-Tabelle:

__m128i above_lut[256];
unsigned char above_count[256];

unsigned int calc_entry(uint8_t b, bool above, unsigned short pos[8], bool* ab)
{
    std::bitset <8> bs(b);
    unsigned int count = 0;

    for(unsigned int i=0; i<8; ++i)
    {
        bool tmp = bs.test(i);
        if (above != tmp)
        {
            pos[count] = i;
            ++count;
            above = tmp;
        }
    }
    *ab = above;
    return count;
}

void init_above(__m128i above_lut[256], unsigned char above_count[256])
{
    bool dummy;
    for(unsigned int i=0; i<256; ++i)
    {
        above_count[i] = calc_entry(i, true, (unsigned short*)&above_lut[i], &dummy);
    }
}

Und schliesslich mittels SSE:

long line_thresh_sse(unsigned char* pbytes, unsigned int length, unsigned char th, unsigned short* pos, unsigned int size)
{
    // check alignment
    unsigned int a = 16-((unsigned int)pbytes)%16;
    bool above = true;
    unsigned int count = 0;
    unsigned short num = 0;

    while((((unsigned int)pbytes)%16) && num<length)
    { 
        bool tmp = (*pbytes)>=th;

        if (above != tmp) 
        { 
            if (count<size) pos[count] = num; 
            above = tmp; 
            ++count;
        }
        ++pbytes;
        ++num;
    }
    length -= num;

    __m128i idx = _mm_set1_epi16(num);
    __m128i t = _mm_set1_epi8(th);
    __m128i eight = _mm_set1_epi16(8);
    __m128i p;

    for(unsigned int i=0; i<length-16; i+=16)
    {
        __m128i v = _mm_load_si128((__m128i*)(pbytes));
        v = _mm_min_epu8(v, t); 
        v = _mm_cmpeq_epi8(v, t);
        uint16_t res = _mm_movemask_epi8(v);

        unsigned int lut_idx = (above) ? (res&0x00FF) : (res&0x00FF)^0xFF; // symmetry of lookup table
        if (lut_idx != 255) // same as above_count[lut_idx] != 0
        {
            p = _mm_load_si128(&above_lut[lut_idx]);
            p = _mm_add_epi16(p, idx);
            _mm_storeu_si128((__m128i*)(pos+count), p);
            count += above_count[lut_idx];
        }

        above = (res&0x0080);
        idx = _mm_add_epi16(idx, eight);

        lut_idx = (above) ? (res>>8) : (res>>8)^0xFF;
        if (lut_idx != 255)
        {
            p = _mm_load_si128(&above_lut[lut_idx]);
            p = _mm_add_epi16(p, idx);
            _mm_storeu_si128((__m128i*)(pos+count), p);
            count += above_count[lut_idx];
        }

        above = (res&0x8000);
        idx = _mm_add_epi16(idx, eight);
        pbytes += 16;
    }

    // do something for trailing bytes

    return count;
}

Zeitmessungen ergeben, dass die simple Implementierung etwa 3 bis 5 mal mehr Zeit benoetigt. Nicht gerade der Brueller. Leider ist SSE recht unflexibel beispielsweise bei Shifts zu benutzen, so dass ein SSE-Register schlecht als Positionsakkumulator dienen kann.