Oggi ho letto il codice utilizzando una tabella di ricerca anziché if-else per il ritaglio di due valori uint8 sommati. La mappa è in i={0...255}
e 255 in i={256...511}
. Mi chiedevo quanto è grande il guadagno di questo potrebbe essere, e ho cercato di scoprirlo, con gprof,Lookup Table vs if-else
g++ -std=c++0x -pg perfLookup.cpp -O2 -o perfLookup && ./perfLookup && gprof perfLookup |less
con il codice allegato qui sotto. Ora senza il flag -O2 gprof dice che lookup() prende il 45% e ifelse() come il 48% del tempo di esecuzione. Con -O2 anche se è 56% per lookup() e 43% per ifelse(). Ma questo benchmark è veramente corretto? Forse un sacco di codice è ottimizzato perché il dst non viene mai letto?
#include <iostream>
#include <cstdint>
#include <vector>
void lookup(std::vector<uint8_t> src, int repeat) {
uint8_t lookup[511];
for (int i = 0; i < 256; i++) {
lookup[i] = i;
}
for (int i = 256; i < 512; i++) {
lookup[i] = 255;
}
std::vector<uint8_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
for (int i = 0; i < src.size(); i++) {
dst[i] = lookup[src[i]];
}
}
}
void ifelse(std::vector<uint8_t> src, int repeat) {
std::vector<uint8_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
for (int i = 0; i < src.size(); i++) {
dst[i] = (src[i] > 255) ? 255 : src[i];
}
}
}
int main()
{
int n = 10000;
std::vector<uint8_t> src(n);
for (int i = 0; i < src.size(); i++) {
src[i] = rand() % 510;
}
lookup(src, 10000);
ifelse(src, 10000);
}
codice aggiornato:
#include <iostream>
#include <cstdint>
#include <cstring>
#include <vector>
#include <algorithm>
// g++ -std=c++0x -pg perfLookup.cpp -O2 -o perfLookup && ./perfLookup && gprof perfLookup |less
std::vector<uint16_t> lookup(std::vector<uint16_t> src, int repeat) {
uint16_t lookup[511];
for (int i = 0; i < 256; i++) {
lookup[i] = i;
}
for (int i = 256; i < 511; i++) {
lookup[i] = 255;
}
std::vector<uint16_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
for (int k = 0; k < src.size(); k++) {
dst[k] = lookup[src[k]];
}
}
return dst;
}
std::vector<uint16_t> ifelse(std::vector<uint16_t> src, int repeat) {
std::vector<uint16_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
for (int k = 0; k < src.size(); k++) {
dst[k] = (src[k] > 255) ? 255 : src[k];
}
}
return dst;
}
std::vector<uint16_t> copyv(std::vector<uint16_t> src, int repeat) {
std::vector<uint16_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
dst = src;
for (int k = 0; k < src.size(); k++) {
if (dst[k] > 255) {
dst[k] = 255;
}
}
}
return dst;
}
std::vector<uint16_t> copyC(std::vector<uint16_t> src, int repeat)
{
uint16_t* dst = (uint16_t *) malloc(sizeof(uint16_t) * src.size()); // Alloc array for dst
for (int i = 0; i < repeat; i++) {
std::memcpy(dst, &src[0], sizeof(uint16_t) * src.size()); // copy src into array
for (int k = 0; k < src.size(); k++) {
if ((dst[k] & 0xFF00) != 0)
dst[k] = 0x00FF;
}
}
free(dst);
return std::vector<uint16_t>();
}
int main()
{
int n = 10000;
std::vector<uint16_t> src(n);
for (int i = 0; i < src.size(); i++) {
src[i] = rand() % 510;
}
std::vector<uint16_t> dst;
dst = lookup(src, 10000);
dst = ifelse(src, 10000);
dst = copyv(src, 10000);
}
nota che si sta misurando l'inizializzazione della tabella di ricerca come parte della vostra benchmarking. Normalmente si inizializza una tabella di ricerca separatamente e non la si include nel benchmarking. –
Non includerei l'inizializzazione della tabella di ricerca nella funzione mesured perché ciò può essere eseguito una sola volta durante l'esecuzione di un programma. –
Alcune modifiche apportate al codice: utilizzare l'argomento 'src' ed eseguire il clipping sul posto --note che questa è già una copia, non un riferimento all'originale. Restituisci quel vettore dalla funzione, altrimenti il compilatore potrebbe rimuovere tutto il codice dalle funzioni poiché la variabile locale non viene mai utilizzata. Crea e archivia la tabella di ricerca al di fuori del codice di test, senza aggiungere operazioni che non influiranno sul risultato. –