Schwierige Optimierung

camper

Sunday schrieb:

- niemals variablen in einer inneren schleife deklarieren

macht keinen unterschied für builtins oder PODs.

- direkt mit zeigern arbeiten und nicht über die array-indizierung gehen

komisch dass genau das gegenteil in diversen optimierungsmanualen vorgeschlagen wird (alias-problem)

Sunday

wo wird das vorgeschlagen? bei mir laufen zeiger schneller. vlei liegts auch an meinem compiler, dass er das nicht gebacken bekommt.

camper

Sunday schrieb:

wo wird das vorgeschlagen? bei mir laufen zeiger schneller. vlei liegts auch an meinem compiler, dass er das nicht gebacken bekommt.

z.b. hier:
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF Abschnitt 2.2

die wahrheit dürfte wohl leider sein, dass die beste variante vom compiler und evtl. auch vom kontext abhängt.

Danke für eure Antworten,

- kennst du nicht die länge von codes, weil du diese immer neu abfragst?
- dito mit size()

Nein, die Längen der Codes variieren bei jedem Array-Element
Die Buffergröße ist ebenfalls nicht anders herauszukriegen, da sich der Buffer alle 8 Bits um 1 neues Char-Element vegrößert.

- addbit inlinen

Ich glaube, die Funktion ist schon zu groß dafür, oder unterstützt noch jemand den Inline-Vorschlag?

@camper:
codes ist ein normales String Array, in dem jedes (Pseudo) Bit ein ganzes Byte verbraucht. Dahingegen speichert bitlist jeweils 8 Bit Gruppen zu einem Byte zusammen, was viel speicherschonender ist. Ich poste mal etwas mehr Code, hoffentlich hilft dir das weiter:

// bitlist.h
class bitlist {

private:
    std::vector<unsigned char>  buf;
    char                        nextbit;

public:
                    bitlist     ();
                    ~bitlist    () { buf.clear(); }
    void            addbit      (const unsigned char &b);
    std::string     getbits     ();
    long            complete    ();
    long            size        () { return (buf.size()-1); }
};

Ich glaube eine gute Verbesserung wäre es, wie angesprochen, eine Funktion zu schreiben, der man den gesamten Code-String übergeben kann und die dann die einzelnen 0en und 1en selbst in den Buffer tut, anstatt das Zeichen für Zeichen in einer Schleife zu tun.

camper

du könntest auch einen vector<bool> einsetzen, dass ist möglicherweise sogar effizienter. bleibt noch die frage, wie portabel das ganze sein muss wegen byteorder und int grösse.

übrigens hat dein addbit einen bug - was passiert wenn die finale streamlänge mal nicht durch 8 teilbar ist? oder ist das das, was complete() macht?

könnte man so heilen (ist evtl. auch effizienter):

void bitlist::addbit(const unsigned char &b) {
    if ( b ) buf[buf.size()-1] |= 1 << bitleft;
    if ( !bitleft-- ) {
        bitleft = 7;
        buf.push_back(0);
    }
}

also nextbit durch bitleft ersetzen und von 7 herunterzählen, statt umgekehrt. ausserdem finden höchtens halbsoviele zugriffe auf den vector statt.

oder ist das das, was complete() macht?

Exakt.

Inwiefern halbieren sich die Zugriffe?
Ich werde den Code mal testen.

camper

NeoInferno schrieb:

oder ist das das, was complete() macht?

Exakt.

Inwiefern halbieren sich die Zugriffe?
Ich werde den Code mal testen.

hatte nicht genau hingesehen: wenn der compiler was taugt dann nicht - sonst verursachen <<= und + jeweils eine read-modify-write operation auf speicheroperanden, was nicht optimal wäre.

camper

hier mal ein entwurf für blockweises arbeiten ohne stringfunktionen, die huffmann codes müssen zuerst in der encoded klasse gespeichert werden - dabei nutze ich aus, dass bei einem alphabet von 256 zeichen, der längste huffmann code höchtens 255 bit lang ist, man kann das ganze also bequem in 8 integern (32bit) speichern:

typedef unsigned u32;

class encoded
{
public:
    encoded() : pos_() { std::fill_n( code_, 8, 0 ); }
    void clear() { std::fill_n( code_, 8, 0 ); pos_ = 0; }
    void push_back(bool set)
    {
        code_[ pos_ / 32 ] |= u32( set ) << 31 - pos_ % 32;
        ++pos_;
    }
    unsigned char length() const { return pos_; }
    u32& operator[](std::size_t i) { return code_[ i ]; }
    const u32& operator[](std::size_t i) const { return code_[ i ]; }
private:
    u32 code_[ 8 ];
    unsigned char pos_;
};

class huff_stream
{
public:
    huff_stream() : buf_(), last_word_(), current_bit_( 32 ) { }

    void insert_code(const encoded& what)
    {
        int left = what.length();
        std::size_t code_pos = 0;
        while ( left >= current_bit_ )
        {
            buf_.push_back( last_word_ | what[ code_pos ] >> 32 - current_bit_ );
            last_word_ = what[ code_pos ] << current_bit_;
            ++code_pos;
            left -= 32;
            if ( left <= 0 )
            {
                current_bit_ -= left;
                return;
            }
        };
        last_word_ |= what[ code_pos ] >> 32 - current_bit_;
    }
    void complete()
    {
        if ( current_bit_ != 32 )
        {
            buf_.push_back( last_word_ );
            current_bit_ = 32;
        }
    }

private:
    std::vector<unsigned> buf_;
    unsigned last_word_;
    int current_bit_;
};

Hui, ein sehr kryptisch anmutender, kommentarloser Code. Werd mich mal durchkämpfen und ihn übernehmen, wenn ich ihn verstehe. Bin kein Fan von sinnlosem Copy & Paste

Danke,
Neo

camper

ja, die kommentare kommen immer erst später, wenn überhaupt...
ich lass den code mal so wie er ist, schreib es einfach extra:

zunächst mal verwende ich gleich 32bit worte statt 8bit chars, da der prozessor damit ohne weiteres genauso schnell rechnen kann, ausserdem dürften die meisten codes kürzer sein. encoded enthält also den code im array, wobei wir beim füllen mit dem höchstwertigen bit des ersten wortes anfangen - das bedeutet allerdings, dass ein cast auf char* auf little endian maschinen (z.b.x86) nicht das gewünschte ergebnis liefern wird. pos gibt den index (als bitposition) des nächsten bits an, wenn noch bits an den code anzufügen sind. es ist also gleichzeitig die länge des codes. die idee ist, einfachen den string zu nehmen, wie du ihn sowieso schon hast, und dann einfach push_back für jedes zeichen durchführen:

encoded encoded_codes[256];
for ( int i = 0; i < 256; ++i)
{
    for ( int j = 0; j < codes[ i ].length(); ++j ) encoded_codes.push_back( codes[ index ][ j ] );
}

der ganze spass kostet dann 36*256 bytes also etwas 8KB.

der interessante teil ist in insert_code: das aktuelle wort wird erst dann in den vektor geschrieben, wenn es voll ist, am anfang ist der vektor also tatsächlich auch leer. current_bit gibt an, wieviele bits im wort noch zu füllen sind. left gibt an, wieviele bits, der aktuelle code noch hat. wenn der aktuelle code also mehr bits übrig hat, als noch frei sind, wird das last_word_ noch fertig gefüllt und in den vektor geschrieben, und der rest des worts des codes überschreibt dann, entsprechend verschoben, last_word_ für die nächste runde (im falle von left==current_bit_ bedeutet das, dass last_word_ im anschluss 0 ist, wie gewünscht). dann ziehen wir 32 von left ab, weil ja ein ganzes wort des inputs verarbeitet wurde. falls dieses allerdings kürzer war, müssen wir noch current_bit korrigieren und dann beenden. so, und dass ist der grund, warum ich keine kommentare schreibe - die würde ich nähmlich nicht verstehen :p
falls der ausgabestream little endian order haben soll (um ihn als char* stream auf little endian maschine zu verwenden) sollte bei jedem push_back in huff_stream noch eine byteswap eingefügt werden.

Windows verwenden die little endian Order, oder?
Btw: Heißt das, ich muss bei einem plattformunabhängigen App das direkt Bits bearbeitet immer *beide* Versionen parat haben? Oder zumindest eine Funktion haben muss, die die Bytes mal so, mal so aufbaut?

Oki, werd mir das ganze nochmal ansehen und mir meine Gedanken darüber machen.
Grundsätzlich tendiere ich aus vorhandenen Implementationen zu Lernzwecken immer *eigene* Varianten abzuleiten, das dürfte bei deinem Code (der für mich als Anfänger wie gesagt leicht schwierig zu lesen ist) auch notwendig sein.

Danke für deine Mühe.

camper

NeoInferno schrieb:

Windows verwenden die little endian Order, oder?

ja

Btw: Heißt das, ich muss bei einem plattformunabhängigen App das direkt Bits bearbeitet immer *beide* Versionen parat haben? Oder zumindest eine Funktion haben muss, die die Bytes mal so, mal so aufbaut?

im grunde ja (oder man schreibt die applikation so, dass sie nie darauf bezug nehmen muss - das wäre hier z.b. dann der fall, wenn nur mit chars und eben nicht mit ints gearbeitet würde). man kann das allerdings ganz gut in generische funktionen packen, so dass der code gleich bleibt.

Grundsätzlich tendiere ich aus vorhandenen Implementationen zu Lernzwecken immer *eigene* Varianten abzuleiten, das dürfte bei deinem Code (der für mich als Anfänger wie gesagt leicht schwierig zu lesen ist) auch notwendig sein.

das ist auf jeden fall das beste. es ist, wie gesagt, nur ein minimaler entwurf - viele dinge fehlen und bessere namen würden definitiv nicht schaden.

Danke für deine Mühe.

yw