Bitpacking – C / C++ – Fórum – Programujte.com

Našel jsem tento článek (program napsaný v C++)

 http://lemire.me/blog/archives/2012/03/06/how-fast-is-bit-packing/

Mám i7 podobně jako autor článku (nepíše jaký má CPU ale já mám 2.9Ghz), ale moje časy jsou asi 4x pomalejší než ty jeho. Poradíte jak nastavit options pro GCC (4.7.1)? Aby mi to jelo rychleji?

A taky bych potřeboval pomoc nebo poradit jak to přepsat do C, protože to chci použív v programu pro C ne C++. Jsou tam vektory a jiné vychytávky nevím co s tím. Nebo znáte jinou lepší knihovnu přímo pro C?

http://pastebin.com/ugGnk00p

#1 oxidián
Vektor je normální dynamicky alokované pole, takže si musíš udělat funkce, které ti budou alokace řešit.

Chápu to správně?

vector<uint32_t> generateArray(uint32_t N) {
        vector<uint32_t> ans(N);
        for(uint32_t k = 0; k<N;++k)
          ans[k] = rand();
        return ans;
}

ans je pole o počtu prvků N, jo?

A co s tou třídou?

class ZTimer
{
public:
    struct timeval t1, t2;
public:
    ZTimer() :  t1(), t2() { gettimeofday(&t1,0); t2 = t1; }
    void reset() {gettimeofday(&t1,0); t2 = t1;}
    int elapsed() { return ((t2.tv_sec - t1.tv_sec) * 1000) + ((t2.tv_usec - t1.
tv_usec) / 1000); }
    int split() { gettimeofday(&t2,0); return elapsed(); }
};

Co je to za typ struct timeval t1 co tam mám dát?

#3 oxidián
Ano, s tím vektorem to je přesně tak. Timeval struktura je definována v sys/time.h a je to speciální struktura na měření časových intervalů.

Dobře takže zkouším toto, ale je tam problém s pointery:

void timer_init(struct timeval * t1, struct timeval * t2){
    gettimeofday(&t1,0);
    t2 = t1;
}
void timer_reset(struct timeval * t1, struct timeval * t2) {
        gettimeofday(&t1,0);
        t2 = t1;
        }
int timer_elapsed(struct timeval * t1, struct timeval * t2) {
    return ((t2.tv_sec - t1.tv_sec) * 1000) + ((t2.tv_usec - t1. tv_usec) / 1000);
}
int timer_split(struct timeval * t1, struct timeval * t2) {
    gettimeofday(&t2,0);
    return elapsed();
}

timer_reset(&t1, &t2);

fastpack(data, compressed, bit);

packtime += timer_split(&t1,&t2);

Musím tám dávat ampersandy když chci aby se ty hodnoty updatovaly přece? A pak jak volám tu funkci na čas tak to chce jeden pointer ne dva pointer takže problém

#5 oxidián
Adresní operátor tam, předpokládám, je kvůli tomu, že je funkce tak nadefinovaná. Jsem jenom na mobilu, nicméně si myslím, že k tv_sec máš přistupovat přes "->", nikoliv přes ".".

Např. t2->tv_sec.

ono to hlavně hlásí chybu tady:

gettimeofday(&t1,0);

error: cannot convert 'timeval**' to 'timeval*' for argument '1' to 'int gettimeofday(timeval*, void*)'|

Mám to udělat takto?

gettimeofday(&(*t1),0);

#7 oxidián
Tak v tom případě tomu normálně předej ten pointer, namísto &t1 jenom t1. Když tomu předáváš &t1, tak vlastně předáváš adresu na ukazatel, což překladač interpretuje jako ukazatel na ukazatel.

Za modifikací přístupových operátorů k atributům daných struktur si stojím.

Ještě toto:

void simplebenchmark() {
        uint32_t N = 1U<<26;
        uint32_t * data, *compressed, *recovered;
        data = malloc(N * sizeof(uint32_t));
        compressed = malloc(N * sizeof(uint32_t));
        recovered = malloc(N * sizeof(uint32_t));
        uint32_t k;
        for(k = 0; k<N;++k)
          data[k] = rand();

        vector<uint32_t> compressed(N, 0);
        vector<uint32_t> recovered(N, 0);

co je (N, 0) na konci? N je počet, ale 0 je co? Že by kam (Nth element ) má ukazovat iterator?

data = malloc( ...  error: invalid conversion from 'void*' to 'uint32_t* {aka unsigned int*}' [-fpermissive]

#9 oxidián
Tady se můžeš podívat, co jednotlivé parametry v konstruktoru vectoru znamenají.

co znamená data == recovered ? vektor == vektor ?

V c++ musis pointery pretypovavat, je tam striktnejsi hlidani typu.

Pak moc nechapu, proc tam delas pole uintu, kdyz pak jeste pod tim samym nazvem nahodis vectory (ktery cirou nahodou umi alokaci mista obstarat interne)

Co s tímto?

if(data[k] % (1U<<bit) != recovered[k]%(1U<<bit)) {

array data, array recovered

error: invalid operands of types 'uint32_t* {aka unsigned int*}' and 'unsigned int' to binary 'operator%'|

KIIV:

Je vidět že nesleduješ co dělám. Přepisuju z C++ do C. Takže odstraňuju vektory. Já vektory nepoužívám!

Kdo by se s tim celym cetl..

Udelej pole a vynuluj ho... cele kouzlo s tema vektorama...

a pokud jeste nevis, co jsou data/converted/recovered, tak je to presne co to znamena.. vstupni data, prevedena data, prevedena data zase prevedena zpet (aby se dalo zkontrolovat, jestli je pred a po to same)

A k tem 4x lepsim casum: zkusil si zapnout optimalizaci? Defaultne gcc moc neoptimalizuje

Ještě jednou. Ptal jsem se co znamená:

data == recovered 

vector data, vector recovered

Na to jsem se taky ptal, jak zapnout optimalizace u gcc

#13 je vyřešeno

Tady je současný kód:

http://pastebin.com/chBRN4RG

řádek 6142

6142|error: invalid conversion from 'uint32_t {aka unsigned int}' to 'const uint32_t* {aka const unsigned int*}' [-fpermissive]

6030|error:   initializing argument 1 of 'void fastpack(const uint32_t*, uint32_t*, uint32_t)' [-fpermissive]

#16 oxidián
data a recovered jsou prostě dva vektory obsahující informace, vektor má přetížený == operátor, pomocí něhož můžeš zjistit, zda se dva vektory rovnají, obsahují to stejné.

Takže to spustí funkci na porovnání jednotlivých elementů, tak?

No ale nedává to moc smysl:

bool equalOnFirstBits(uint32_t ** data, uint32_t ** recovered, uint32_t bit, uint32_t data_count) {
        if(bit == 32)
                return data == recovered;

        for(uint32_t k = 0; k<data_count; ++k) {
                if((*data)[k] % (1U<<bit) != (*recovered)[k]%(1U<<bit)) {
                        printf(" They differ at k = %d , data[k]= %d , recovered[k] = %d\n",k,data[k],recovered[k]);
                        return false;
                }
        }
        return true;
}

Proč by pak souštěl tu porovnávající smyčku?

Potřebuju nutně vysvětlit toto:

__attribute__ ((noinline))
void fastpack(const uint32_t *  __restrict__ in,
                        uint32_t *  __restrict__  out,
                        const uint32_t bit) {

co je to __restrict__ ?

Co je to __attribute__ ((noinline))

A proč tam je v argumentech pointer?

Ta funkce se totiž volá takto:

fastpack((*data)[0]+32*k,
                    (*out)[0]+(32 * bit)  * k / 32,
                    bit
                    );

Originál:

__attribute__ ((noinline))
void fastpack(const vector<uint> & data, vector<uint> & out, const uint bit) {
                const uint N = data.size();
                for(uint k = 0; k<N/32;++k) {
                                fastpack(& data[0]+32*k,&out[0]+(32 * bit)  * k / 32,bit);
                }
}

tak jsem myslel že fastpack arg1 a arg2 mahá být uint32_t
 

#20 oxidián
Ach jo, chlape, s tebou je to fakt těžký.   Kdybys 95% toho, na co se tady ptáš, prostě zadal do googlu, odpověď bez problému najdeš. Nauč se trošku hledat.

Jinak pokud nevíš, proč je v argumentech pointer, tak se podívej, jak v C předávat funkcím pole.

__attribute__ ((noinline)) se používá, aby funkce nikdy nebyla inlinovaná. Více o __restrict__ zde na wikipedii.

 

#21 ondrej39
Jaké pole?

Chceš mi říct, že tohle je pole?

& data[0]+32*k

článek o restrict na wikipedii jsem našel ale nečetl protože jsem hledal __restrict__ a z toho mi google nenašel nic
 

#22 oxidián
Ano, přesně to chci říct.   

Proč se používá restrict je vysvětleno v této části: It says that for the lifetime of the pointer, only it or a value directly derived from it (such as pointer + 1) will be used to access the object to which it points. This limits the effects of pointer aliasing, aiding optimizations.

Prostě nechceš, aby se uvnitř funkce vytvořil další pointer, který by mohl odkazovat na data uvnitř struktury (i pole je svým způsobem struktura), která je pod pointerem v parametru předávaná.

#23 ondrej39
Tak si to rozeberem ještě jednou

var = & data[0]+32*k;

Co je výsledkem var? Snad uint32_t, ne? Nikde jsem si nevšiml, že by data[0] obsahovalo pole. To by data muselo být výcerozměrné pole nebo vícerozměrný vekror (vektor uvnitř vektoru). A pokud je tam opravdu pole, tak co teda dělá to + a pro násobení *
 

Tvoje teorie že je tam pole by se dala příjmout pouze za předpokladu, že se to bere jako

data[0]+=32*k;

var = & data[0];

#24 oxidián
Ovšem, že data neobsahuje pole. data je pole obsahující unsigned integery. Normálně, pokud bys chtěl funkci předat uint32_t pole[], mohl bys do parametru napsat pole (překladač si z toho vytáhne, že mu dáváš adresu pole).

V tvém příkladě ale funkci předávají data[0], což je jeho první prvek ale už to není adresa, nýbrž konkrétní prvek pole, v tomto případě uint32_t, ale protože funkci v parametru očekává ukazatel, je potřeba předat funkci adresu tohoto prvku použitím adresního operátoru "&".

Proč k tomu ještě přičítají +32*k ti neřeknu, nevím, co ta funkce dělám, nezkoumal jsem to, ani to zkoumat nechci, nicméně předpokládám, že to je stále jen pointerová aritmetika, prostě se k adrese nultého prvku (data[0]) přičte +32*k, takže podle toho, kolik k bude, se dostaneš na určitou adresní pozici v paměti.

Takže myslíš že by to mělo vypadat takto?

void fastpack_main(uint32_t ** data, uint32_t **out, const uint32_t bit, uint32_t data_count) {
uint32_t count = data_count/32;

for(uint32_t k = 0; k<count ;++k) {
  /* fastpack((*data)[0]+32*k,
  (*out)[0]+(32 * bit)  * k / 32,
  */
  *data += 32*k;
  *out += (32 * bit)  * k / 32;
  fastpack( *data, *out, bit );
}
}

#26 oxidián
Jaký smysl má podle tebe v tebou psaném kódu pointer na pointer v parametru funkce? Proč ses ho rozhodl použít?

Původně jsem předpokládál že ty funkce mají ty pole měnit. Teď když jsem to porovnal a nemá tam pointer tak jsem to odstranil.

Z nějakého důvodu mi to tady krachuje:

void __fastpack1(const uint32_t *  __restrict__ in, uint32_t *  __restrict__  out) {
    *out |= (*in)   & 1 ;

na druhém řádku.

Ale dneska to už neřeším. Mám dost. Dík za pomoc

#28 oxidián
Měnit nemá, od toho je tam const. A kdyby funkce měla měnit obsah pole (tzn. třeba funkce 4. element v poli změní z 5 na 26 a chceš, aby se změna projevila i v původním poli, které funkci předáváš), jednoduchý pointer na první element pole ti bohatě stačí.

#29 ondrej39
nekdy pouziva i posouvani pointeru tak, aby se posunul i venku.. na to uz musi mit i pointer na ten pointer :)

#30 KIIV
Někdy, ne v tomto případě, V originále se funkci jako parametry kromě jednoho unsigned integeru předávají dvě konstantní reference na vektory. Prostě v C dva úplně obyčejné konstantní pointery na pole.

Co má znamenat tento zápis?

*out |= (*in)   & 1 ;

*out = *out | (*in) & 1

př. *out == 0 , *in == 41 => *out =1;

#32 oxidián
Pokud máš *out == 0 a *in == 41, pak jejich binární vyjádření je:

*out = 00000000;
*in  = 00101001;

Máš tam dva bitové operátory, |= je OR asignment operátor, & je AND. Příkazy se provádí zprava doprava, nejdřív se pomocí masky 1 a & namaskuje hodnota v *in, to znamená, že z ní vždycky uděláš jedničku, pomocí OR asignment operátoru potom tu jedničku buď přičteš k hodnotě v *out (pokud hodnota bude sudá a na první pozici zprava nebude nic mít), nebo s číslem neudělá nic, pokud číslo bude liché.

/* Sudá hodnota *out */
*out = 1010 (10);
*in  = 0111 (7);

/* Namaskování čísla v *in */
*in & 1 == 0111 & 0001 => 0001 (1)

/* Přiřazení do *out pomocí OR */
*out |= *in == *out = *out | *in == 1010 | 0001 => 1011 (11)

/* ---------------------------------------------------
 * Lichá hodnota *out */
*out = 1001 (9);
*in  = 1000 (8);

/* Namaskování čísla v *in */
*in & 1 == 1000 & 0001 => 0001 (1)

/* Přiřazení do *out pomocí OR */
*out |= *in == *out = *out | *in == 1001 | 1001 => 0001 (9)

Co znamená tato řádka?

compressed.resize(N*bit/32, 0);

myslel jsem že se tím změní velikost vektoru tedy pole, takže jsem reallockoval paměť ...A ejhle pamě't mu nestačí takže to krachuje

#33 ondrej39
dík za vysvětlení

#34 oxidián
Jo, chlape, sorry. To maskování mám blbě. Pokud budeš mít sudý *in, na první pozici zprava budeš mít 0, tak se namaskováním přes 1 z toho sudého čísla v *in stane 0, nikoliv jednička. Takže výstupy pak budou tyto:

• *out je sudé číslo, *in je sudé číslo, namaskování *in přes 1 ti vznikne 0, *out a 0 sloučíš dohromady pomocí |= a vznikne ti původní sudé číslo
• *out je sudé číslo, *in je liché číslo, namaskování *in přes 1 ti vznikne 1, *out a 1 sloučíš dohromady pomocí |= a vznikne ti liché číslo
• *out je liché číslo, *in je sudé číslo, namaskování *in přes 1 ti vznikne 0, *out a 0 sloučíš dohromady pomocí |= a vznikne ti původní liché číslo
• *out je liché číslo, *in je liché číslo, namaskování *in přes 1 ti vznikne 1, *out a 1 sloučíš dohromady pomocí |= a vznikne ti původní liché číslo

#33 ondrej39
Ať už to znamená cokoliv, nemohu pochopit proč je v originálním kódu vector.resize... Pravědpodobně proto mi tzo krachuje, protože jsem dal menší počet elementů než N do výstupního pole. N je původní počet elementů v poli s původními vstupními daty.

A ještě jedna věc, když se podíváš na ty jeho metody

__fastpackN (místo N si dosaď N<1] tak on všude používá modulo, a to i v __fastunpackN

jenže modulo je děsně pomalé jak dobře známo nešlo by to teda udělat jinak ty jeho výpočty? Lépe tak, aby to nepoužívalo modulo.

Mohl by mi někdo odpovědět na otázky níže?

• Co ty funkce vlastně maj dělat (__pack... __unpack... ) ?
• Co je to bitpacking, co se od toho očekává a jak to funguje?
• Jaké předpoklady musí být splněny, aby mělo smysl bitpacking použít?
• Co má být na vstupu a co na výstupu? Nějaký jednoduchý kód na ukázku jak funguje bitpacking?

Myslel jsem že ten kód prostě přepíšu to C a použiju, ale vlastně ani nechápu jak to funguje a k čemu by se to dalo použít (a protože to krachuje a nevím jak to má fungovat, kašlu na ten kód, ale chci pochopit co dělaj ty funkce). Hledal jsem původně knihovnu která zvládne rozbalit kod zabalený metodou bitpack.

No kdyz mas treba 16b barvy, tak mas 3 barvy zabaleny na 2 bajty.. muze to byt treba  5:6:5 bitu na jednotlive barvy a bylo by velice neefektivni to ukladat ve stylu 5bitu z 8 pro R, 6bitu z 8 pro G,...

A opak toho je zase ten unpack.

No ale autor toho kódu nepoužívá barvy, ale pouze čísla...

a) data == recovered - to je normalni porovnani, jako vraci to true nebo false
if (data == recovered) {...} else {...}

b) google a restrict, tam musis zadat uvozovky
https://www.google.cz/search?…
ale myslim, ze bohate staci, kdyz tam zadas c++ a restrict bez podtrzitek

KIIV - to vysvetleni nechapu :)
http://stackoverflow.com/…king-in-java
Jestli to spravne chapu, tak sada cisel, co jde do te funkce je treba 0-16, 0-255, 0-16, 0-255 (4 byty). Vsechny jsou typu byte. Vystupem je pole bitu. xxxx yyyyyyyy zzzz aaaaaaaa (16 bitu, cili 2 byty).
Neni mi jasne, cim takovy vstup ziska, ale asi je to vedlejsi. to asi vi tazatel.

Resp, oprava, on ma 0-16 celou radu a spojuje to do po dvou do jednoho byte.

V tom pripade by ale bylo rychlejsi pridat na konec toho pole 0 a spojovat to po dvou bez tech pomalych if. na konci by jen pridal byte, ktery rekne, jestli je na konci nula navic nebo ne. Cili, kdyz vemu ten kod z javy, tak nejak takto teoreticky
 

void compress(byte[] pic, byte[] picCompressed) {
    boolean odd = false;
    int pos = 0;
p[konec+1] = 0
li = floor(delka (pole p)/2)
for (i=0;i<li;)//    for (byte p : pic)
    {
            picCompressed[pos++] |= (byte)(quantize(p[i]) << 4);
++i;
            picCompressed[pos] = quantize(p[i]);             
++i;
//        byte b = quantize(p);
//        if (odd) {
//            picCompressed[pos++] |= (byte)(b << 4);
//        } else {
//            picCompressed[pos] = b;             
        }

//        odd = !odd;
    }       
}

#39 oxidián
Pokud se nemýlím, uU těch čísel je to víceméně podobné, jako napsal KIIV. Víš, že máš různé druhy integerů, 8bit, 16bit, 32bit (standardní), 64bit. A nyní si vem, že budeš chtít ukládat čísla třeba v rozmezí 12 000 - 250 000. Na zpracování hodnoty 250 000 by ti stačilo 18 bitů, ale ejhle, 18bitový integer dostupný nemáš. Ale ty prostě potřebuješ 250 000 někam uložit, takže bys teoreticky mohl sáhnout po 32bitovém integeru, do něhož se ti hodnota 250 000 vleze, ale zároveň budeš mít 14 bitů zcela nevyužitých.

Pomocí bitového packingu se můžeš tomu plýtvání místem vyhnout.

já vůbec nevím co s těma funkcema dělá, vím jen to, že vstupem je náhodně vygenerované číslo integer.

kdyby tam posílal třeba čísla v nějakém rozsahu jak píšeš tak by to dávalo smysl. Třeba 0-15, 0-8, 0-1 ...

protože stejně to tu nikdo nechápe, nemá to smysl to řešit ale rád bych tu viděl nějakou funkci na které bych mohl pochopit jak udělat ten bitpacking například pro masky. Hodilo by se mi to pro můj grafický program, který bude pracovat s maskami. Ale abych ty černé (0) /bílé (255)  barvy nemusel ukládat jako integer, tak bych to chtěl převést do toho zabaleného formátu. Co mi není jasné, jestli se pod bitpakingem myslí to, že každý bit má představovat jednu barvu (0 černá, 1 bílá), nebo se to bere tak, že do jednoho bytu se vleze 128 bílých barev a 128 černých barev (tedy vzájemnou kombinací těch 8 bitů máme využito všech 256ti kombinací).