Jakakolwiek optymalizacja dla dostępu swobodnego na bardzo dużej tablicy, gdy wartość w 95% przypadków wynosi 0 lub 1?


133

Czy jest możliwa optymalizacja dla dostępu losowego na bardzo dużej tablicy (obecnie używam uint8_ti pytam o to, co jest lepsze)

uint8_t MyArray[10000000];

gdy wartość w dowolnej pozycji w tablicy to

  • 0 lub 1 w 95% wszystkich przypadków,
  • 2 na 4% przypadków,
  • od 3 do 255 w pozostałych 1% przypadków?

Czy jest więc coś lepszego niż uint8_ttablica, której można użyć do tego? Powinno być tak szybkie, jak to możliwe, aby zapętlić całą tablicę w losowej kolejności, a to jest bardzo duże dla przepustowości pamięci RAM, więc gdy więcej niż kilka wątków robi to w tym samym czasie dla różnych macierzy, obecnie cała przepustowość pamięci RAM szybko się nasyca.

Pytam, ponieważ posiadanie tak dużej tablicy (10 MB) wydaje się bardzo nieefektywne, kiedy faktycznie wiadomo, że prawie wszystkie wartości, oprócz 5%, będą równe 0 lub 1. Więc kiedy 95% wszystkich wartości w tablicy w rzeczywistości wymagałby tylko 1 bitu zamiast 8 bitów, co zmniejszyłoby zużycie pamięci o prawie rząd wielkości. Wydaje się, że musi istnieć rozwiązanie bardziej wydajne pod względem pamięci, które znacznie zmniejszyłoby wymaganą do tego przepustowość pamięci RAM, aw rezultacie byłoby również znacznie szybsze w przypadku dostępu swobodnego.


36
Dwa bity (0/1 / patrz tablica haszy) i tablica haszy dla wartości większych niż 1?
user253751

6
@ user202729 Od czego to zależy? Myślę, że jest to interesujące pytanie dla każdego, kto musi zrobić coś podobnego jak ja, więc chciałbym zobaczyć bardziej uniwersalne rozwiązanie tego problemu, a nie odpowiedź, która jest bardzo specyficzna dla mojego kodu. Jeśli to od czegoś zależy, dobrze byłoby mieć odpowiedź wyjaśniającą, od czego to zależy, aby każdy, kto ją czyta, mógł zrozumieć, czy istnieje lepsze rozwiązanie dla jego własnego przypadku.
JohnAl

7
Zasadniczo to, o co pytasz, nazywa się rzadkością .
Mateen Ulhaq

5
Potrzebuje więcej informacji ... Dlaczego dostęp jest losowy i czy wartości niezerowe są zgodne ze wzorem?
Ext3h

4
@IwillnotexistIdonotexist Krok wstępnego obliczania byłby w porządku, ale tablica powinna być od czasu do czasu modyfikowana, więc krok wstępnego obliczenia nie powinien być zbyt kosztowny.
JohnAl

Odpowiedzi:


155

Prostą możliwością, która przychodzi na myśl, jest zachowanie skompresowanej tablicy 2 bitów na wartość dla typowych przypadków i oddzielnych 4 bajtów na wartość (24 bity dla indeksu elementu oryginalnego, 8 bitów dla rzeczywistej wartości, więc (idx << 8) | value)) posortowana tablica inni.

Kiedy szukasz wartości, najpierw przeszukujesz tablicę 2bpp (O (1)); jeśli znajdziesz 0, 1 lub 2, jest to wartość, której szukasz; jeśli znajdziesz 3, oznacza to, że musisz to sprawdzić w dodatkowej tablicy. Tutaj przeprowadzisz wyszukiwanie binarne, aby znaleźć indeks, który Cię interesuje, przesunięty w lewo o 8 (O (log (n) z małym n, ponieważ powinno to być 1%) i wyodrębnić wartość z 4- bajt rzecz.

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

Dla tablicy takiej jak ta, którą zaproponowałeś, powinno to zająć 10000000/4 = 2500000 bajtów dla pierwszej tablicy plus 10000000 * 1% * 4 B = 400000 bajtów dla drugiej tablicy; stąd 2900000 bajtów, czyli mniej niż jedna trzecia oryginalnej tablicy, a najczęściej używana część jest przechowywana razem w pamięci, co powinno być dobre do buforowania (może nawet pasować do L3).

Jeśli potrzebujesz więcej niż 24-bitowego adresowania, będziesz musiał dostosować „pamięć dodatkową”; trywialnym sposobem jego rozszerzenia jest posiadanie 256-elementowej tablicy wskaźników do przełączania 8 pierwszych bitów indeksu i przekazywania dalej do 24-bitowej posortowanej tablicy indeksowanej, jak powyżej.


Szybki test porównawczy

#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>

using namespace std::chrono;

/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
    /// This stuff allows to use this class wherever a library function
    /// requires a UniformRandomBitGenerator (e.g. std::shuffle)
    typedef uint32_t result_type;
    static uint32_t min() { return 1; }
    static uint32_t max() { return uint32_t(-1); }

    /// PRNG state
    uint32_t y;

    /// Initializes with seed
    XorShift32(uint32_t seed = 0) : y(seed) {
        if(y == 0) y = 2463534242UL;
    }

    /// Returns a value in the range [1, 1<<32)
    uint32_t operator()() {
        y ^= (y<<13);
        y ^= (y>>17);
        y ^= (y<<15);
        return y;
    }

    /// Returns a value in the range [0, limit); this conforms to the RandomFunc
    /// requirements for std::random_shuffle
    uint32_t operator()(uint32_t limit) {
        return (*this)()%limit;
    }
};

struct mean_variance {
    double rmean = 0.;
    double rvariance = 0.;
    int count = 0;

    void operator()(double x) {
        ++count;
        double ormean = rmean;
        rmean     += (x-rmean)/count;
        rvariance += (x-ormean)*(x-rmean);
    }

    double mean()     const { return rmean; }
    double variance() const { return rvariance/(count-1); }
    double stddev()   const { return std::sqrt(variance()); }
};

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

volatile unsigned out;

int main() {
    XorShift32 xs;
    std::vector<uint8_t> vec;
    int size = 10000000;
    for(int i = 0; i<size; ++i) {
        uint32_t v = xs();
        if(v < 1825361101)      v = 0; // 42.5%
        else if(v < 4080218931) v = 1; // 95.0%
        else if(v < 4252017623) v = 2; // 99.0%
        else {
            while((v & 0xff) < 3) v = xs();
        }
        vec.push_back(v);
    }
    populate(vec.data(), vec.size());
    mean_variance lk_t, arr_t;
    for(int i = 0; i<50; ++i) {
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += lookup(xs() % size);
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "lookup: %10d µs\n", dur);
            lk_t(dur);
        }
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += vec[xs() % size];
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "array:  %10d µs\n", dur);
            arr_t(dur);
        }
    }

    fprintf(stderr, " lookup |   ±  |  array  |   ±  | speedup\n");
    printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
            lk_t.mean(), lk_t.stddev(),
            arr_t.mean(), arr_t.stddev(),
            arr_t.mean()/lk_t.mean());
    return 0;
}

(kod i dane zawsze aktualizowane w moim Bitbuckecie)

Powyższy kod wypełnia tablicę elementów 10M losowymi danymi rozprowadzanymi jako OP określone w ich poście, inicjuje moją strukturę danych, a następnie:

  • wykonuje losowe wyszukiwanie 10M elementów z moją strukturą danych
  • robi to samo na oryginalnej tablicy.

(zauważ, że w przypadku wyszukiwania sekwencyjnego tablica zawsze wygrywa o ogromną miarę, ponieważ jest to najbardziej przyjazne dla pamięci podręcznej wyszukiwanie, jakie możesz zrobić)

Te dwa ostatnie bloki są powtarzane 50 razy i mierzone w czasie; na końcu obliczana i drukowana jest średnia i odchylenie standardowe dla każdego typu wyszukiwania, wraz z przyspieszeniem (średnia_szukania / średnia_tablicy).

Skompilowałem powyższy kod za pomocą g ++ 5.4.0 ( -O3 -staticplus kilka ostrzeżeń) na Ubuntu 16.04 i uruchomiłem go na niektórych maszynach; większość z nich pracuje pod systemem Ubuntu 16.04, niektóre starsze, niektóre nowsze. Nie sądzę, aby system operacyjny był w ogóle odpowiedni w tym przypadku.

            CPU           |  cache   |  lookup (µs)   |     array (µs)  | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB |  60011 ±  3667 |   29313 ±  2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB |  66571 ±  7477 |   33197 ±  3619 | 0.50
Celeron G1610T  @ 2.30GHz |  2048 KB | 172090 ±   629 |  162328 ±   326 | 0.94
Core i3-3220T   @ 2.80GHz |  3072 KB | 111025 ±  5507 |  114415 ±  2528 | 1.03
Core i5-7200U   @ 2.50GHz |  3072 KB |  92447 ±  1494 |   95249 ±  1134 | 1.03
Xeon X3430      @ 2.40GHz |  8192 KB | 111303 ±   936 |  127647 ±  1503 | 1.15
Core i7 920     @ 2.67GHz |  8192 KB | 123161 ± 35113 |  156068 ± 45355 | 1.27
Xeon X5650      @ 2.67GHz | 12288 KB | 106015 ±  5364 |  140335 ±  6739 | 1.32
Core i7 870     @ 2.93GHz |  8192 KB |  77986 ±   429 |  106040 ±  1043 | 1.36
Core i7-6700    @ 3.40GHz |  8192 KB |  47854 ±   573 |   66893 ±  1367 | 1.40
Core i3-4150    @ 3.50GHz |  3072 KB |  76162 ±   983 |  113265 ±   239 | 1.49
Xeon X5650      @ 2.67GHz | 12288 KB | 101384 ±   796 |  152720 ±  2440 | 1.51
Core i7-3770T   @ 2.50GHz |  8192 KB |  69551 ±  1961 |  128929 ±  2631 | 1.85

Rezultaty są ... mieszane!

  1. Ogólnie rzecz biorąc, na większości tych maszyn występuje pewne przyspieszenie, a przynajmniej są one na równi.
  2. Dwa przypadki, w których tablica naprawdę przewyższa wyszukiwanie "inteligentnej struktury", dotyczą maszyn z dużą ilością pamięci podręcznej i niezbyt obciążonych: Xeon E5-1650 powyżej (pamięć podręczna 15 MB) jest maszyną do nocnego budowania, w tej chwili całkiem bezczynną; Xeon E5-2697 (35 MB pamięci podręcznej) to maszyna do obliczeń o wysokiej wydajności, również w stanie bezczynności. To ma sens, oryginalna tablica mieści się całkowicie w ich ogromnej pamięci podręcznej, więc zwarta struktura danych tylko zwiększa złożoność.
  3. Po przeciwnej stronie „spektrum wydajności” - ale tam, gdzie macierz jest nieco szybsza, jest skromny Celeron, który zasila mój NAS; ma tak małą pamięć podręczną, że ani tablica, ani „inteligentna struktura” w ogóle się do niej nie mieszczą. Inne maszyny z wystarczająco małą pamięcią podręczną działają podobnie.
  4. Do Xeon X5650 należy podchodzić z pewną ostrożnością - są to maszyny wirtualne na dość obciążonym dwugniazdowym serwerze maszyny wirtualnej; może się zdarzyć, że chociaż nominalnie ma przyzwoitą ilość pamięci podręcznej, w czasie testu jest kilka razy wywłaszczany przez całkowicie niepowiązane maszyny wirtualne.

7
@JohnAl Nie potrzebujesz struktury. uint32_tBędzie dobrze. Usunięcie elementu z bufora pomocniczego oczywiście pozostawi go posortowanym. Wstawianie elementu można wykonać za pomocą, std::lower_bounda następnie insert(zamiast dołączać i ponownie sortować całość). Aktualizacje sprawiają, że pełnowymiarowa tablica dodatkowa jest znacznie bardziej atrakcyjna - na pewno od tego bym zaczął.
Martin Bonner wspiera Monikę

6
@JohnAl Ponieważ wartość jest taka (idx << 8) + val, nie musisz się martwić o część wartości - po prostu użyj prostego porównania. Zawsze będzie porównywać mniej niż ((idx+1) << 8) + vali mniej niż((idx-1) << 8) + val
Martin Bonner wspiera Monikę

3
@JohnAl: jeśli to może być przydatne, dodałem populatefunkcję, która powinna się zapełniać main_arri sec_arrzgodnie z oczekiwanym formatem lookup. Właściwie to nie próbowałem, więc nie oczekuj, że naprawdę działa poprawnie :-); w każdym razie powinno dać ci ogólny pomysł.
Matteo Italia

6
Daję +1 tylko do testów porównawczych. Miło widzieć pytanie dotyczące wydajności oraz wyników dla wielu typów procesorów! Ładny!
Jack Aidley

2
@JohnAI Powinieneś go sprofilować dla swojego rzeczywistego przypadku użycia i nic więcej. Prędkość w białym pokoju nie ma znaczenia.
Jack Aidley

33

Inną opcją może być

  • sprawdź, czy wynik to 0, 1 lub 2
  • jeśli nie, przeprowadź regularne wyszukiwanie

Innymi słowy coś takiego:

unsigned char lookup(int index) {
    int code = (bmap[index>>2]>>(2*(index&3)))&3;
    if (code != 3) return code;
    return full_array[index];
}

gdzie bmapwykorzystuje 2 bity na element, przy czym wartość 3 oznacza „inne”.

Ta struktura jest łatwa do zaktualizowania, zużywa 25% więcej pamięci, ale duża część jest przeszukiwana tylko w 5% przypadków. Oczywiście, jak zwykle, czy to dobry pomysł, czy nie, zależy od wielu innych warunków, więc jedyną odpowiedzią jest eksperymentowanie z rzeczywistym użyciem.


4
Powiedziałbym, że to dobry kompromis, aby uzyskać jak najwięcej trafień w pamięci podręcznej (ponieważ zmniejszona struktura może łatwiej zmieścić się w pamięci podręcznej), bez straty czasu na losowy dostęp.
meneldal

Myślę, że można to jeszcze poprawić. W przeszłości odniosłem sukces z podobnym, ale innym problemem, w którym wykorzystanie predykcji gałęzi bardzo pomogło. Może pomóc podzielenie się if(code != 3) return code;naif(code == 0) return 0; if(code==1) return 1; if(code == 2) return 2;
kutschkem

@kutschkem: w takim przypadku __builtin_expect& co lub PGO również mogą pomóc.
Matteo Italia

23

To bardziej „długi komentarz” niż konkretna odpowiedź

O ile twoje dane nie są czymś dobrze znanym, wątpię, aby ktokolwiek mógł BEZPOŚREDNIO odpowiedzieć na twoje pytanie (i nie znam niczego, co pasuje do twojego opisu, ale wtedy nie wiem WSZYSTKIEGO o wszelkiego rodzaju wzorcach danych dla wszystkich) rodzaje przypadków użycia). Rzadkie dane są częstym problemem w obliczeniach o wysokiej wydajności, ale zazwyczaj jest to „mamy bardzo dużą tablicę, ale tylko niektóre wartości są niezerowe”.

W przypadku niezbyt znanych wzorców, takich jak myślę, że jest twój, nikt nie będzie wiedział bezpośrednio, co jest lepsze, a to zależy od szczegółów: jak losowy jest dostęp przypadkowy - czy system uzyskuje dostęp do klastrów danych, czy też jest całkowicie losowy, jak z jednolity generator liczb losowych. Czy dane w tabeli są całkowicie losowe, czy też istnieją sekwencje 0, a następnie sekwencje 1, z rozproszeniem innych wartości? Kodowanie długości serii działałoby dobrze, jeśli masz rozsądnie długie sekwencje 0 i 1, ale nie zadziała, jeśli masz „szachownicę 0/1”. Ponadto musisz mieć tabelę „punktów początkowych”, aby móc szybko dotrzeć do odpowiedniego miejsca.

Od dawna wiem, że niektóre duże bazy danych to po prostu duże tabele w pamięci RAM (w tym przykładzie dane abonenta centrali telefonicznej), a jednym z problemów jest to, że pamięci podręczne i optymalizacja tabeli stron w procesorze są dość bezużyteczne. Osoba dzwoniąca jest tak rzadko taka sama, jak osoba, która niedawno do kogoś dzwoniła, że ​​nie ma żadnych wstępnie załadowanych danych, jest to po prostu przypadkowe. Duże tabele stron to najlepsza optymalizacja dla tego typu dostępu.

W wielu przypadkach kompromis między „szybkością a małym rozmiarem” jest jedną z tych rzeczy, między którymi trzeba wybierać w inżynierii oprogramowania [w innych inżynierii niekoniecznie jest to taki kompromis]. Zatem „marnowanie pamięci na prostszy kod” jest często preferowanym wyborem. W tym sensie „proste” rozwiązanie jest prawdopodobnie lepsze pod względem szybkości, ale jeśli masz „lepsze” wykorzystanie pamięci RAM, optymalizacja pod kątem rozmiaru tabeli zapewni wystarczającą wydajność i znaczną poprawę rozmiaru. Można to osiągnąć na wiele różnych sposobów - jak zasugerowano w komentarzu, 2-bitowe pole, w którym przechowywane są dwie lub trzy najpopularniejsze wartości, a następnie alternatywny format danych dla innych wartości - moja tablica skrótów byłaby moim pierwsze podejście, ale lista lub drzewo binarne też może działać - znowu, zależy to od wzorców, gdzie twoje „nie 0, 1 lub 2” są. Znowu zależy to od tego, jak wartości są „rozproszone” w tabeli - czy są w klastrach, czy też są bardziej równomiernie rozłożone?

Problem polega jednak na tym, że nadal odczytujesz dane z pamięci RAM. Następnie wydajesz więcej kodu na przetwarzanie danych, w tym trochę kodu radzącego sobie z „to nie jest powszechna wartość”.

Problem z większością popularnych algorytmów kompresji polega na tym, że opierają się one na rozpakowywaniu sekwencji, więc nie można uzyskać do nich swobodnego dostępu. A obciążenie związane z dzieleniem dużych zbiorów danych na fragmenty, powiedzmy 256 wpisów naraz, i dekompresowaniem 256 do tablicy uint8_t, pobieraniem żądanych danych, a następnie wyrzucaniem nieskompresowanych danych, jest bardzo mało prawdopodobne, wydajność - oczywiście zakładając, że ma to pewne znaczenie.

W końcu prawdopodobnie będziesz musiał wdrożyć jeden lub kilka pomysłów w komentarzach / odpowiedziach, aby przetestować, sprawdzić, czy pomoże to rozwiązać twój problem, czy też magistrala pamięci jest nadal głównym czynnikiem ograniczającym.


Dzięki! W końcu interesuje mnie tylko to, co jest szybsze, gdy 100% procesora jest zajęty zapętlaniem się takich tablic (różne wątki w różnych tablicach). Obecnie w przypadku uint8_tmacierzy przepustowość pamięci RAM jest nasycana po tym, jak ~ 5 wątków pracuje nad nią w tym samym czasie (w systemie czterokanałowym), więc użycie więcej niż 5 wątków nie daje już żadnych korzyści. Chciałbym, aby używał> 10 wątków bez problemów z przepustowością pamięci RAM, ale jeśli strona procesora dostępu staje się tak wolna, że ​​10 wątków jest wykonywanych mniej niż 5 wątków wcześniej, to oczywiście nie byłby postęp.
JohnAl

@JohnAl Ile masz rdzeni? Jeśli jesteś związany z procesorem, nie ma sensu mieć więcej wątków niż rdzeni. A może czas przyjrzeć się programowaniu GPU?
Martin Bonner wspiera Monikę

@MartinBonner Mam obecnie 12 wątków. I zgadzam się, to prawdopodobnie działałoby bardzo dobrze na GPU.
JohnAl

2
@JohnAI: Jeśli po prostu uruchamiasz wiele wersji tego samego nieefektywnego procesu w wielu wątkach, zawsze zobaczysz ograniczony postęp. Zaprojektowanie algorytmu przetwarzania równoległego odniesie większe korzyści niż modyfikowanie struktury pamięci.
Jack Aidley

13

To, co zrobiłem w przeszłości, to użycie hashmap przed zestawem bitów.

Zmniejsza to o połowę przestrzeń w porównaniu z odpowiedzią Matteo, ale może być wolniejsze, jeśli wyszukiwania „wyjątków” są powolne (tj. Jest wiele wyjątków).

Często jednak „pamięć podręczna jest królem”.


2
Jak dokładnie haszmapa zmniejszyłaby o połowę przestrzeń w porównaniu z odpowiedzią Matteo ? Co powinno być w tej tablicy?
JohnAl

1
@JohnAl Używając 1-bitowego zestawu bitów = bitvec zamiast 2-bitowego bitvec.
o11c

2
@ o11c Nie jestem pewien, czy dobrze to rozumiem. Masz na myśli tablicę wartości 1-bitowych, gdzie 0oznacza spojrzenie namain_arr i 1oznacza spojrzenie nasec_arr (w przypadku kodu Matteos)? Wymagałoby to jednak ogólnie więcej miejsca niż odpowiada Matteos, ponieważ jest to jedna dodatkowa tablica. Nie do końca rozumiem, jak byś to zrobił, używając tylko połowy miejsca w porównaniu z odpowiedzią Matteosa.
JohnAl

1
Czy mógłbyś to wyjaśnić? Najpierw sprawdzasz przypadki oczekiwane , a potem przeglądasz mapę bitową? Jeśli tak, podejrzewam, że powolne wyszukiwanie w skrócie przytłoczy oszczędności wynikające ze zmniejszenia rozmiaru mapy bitowej.
Martin Bonner wspiera Monikę

Myślałem, że to się nazywa hashlinking - ale Google nie wyświetla żadnych trafień, więc to musi być coś innego. Sposób, w jaki zwykle działało, polegał na tym, że na przykład tablica bajtów zawierała wartości, z których zdecydowana większość mieściła się, powiedzmy, między 0..254. Wtedy użyjesz 255 jako flagi, a jeśli masz element 255, sprawdzisz prawdziwą wartość w powiązanej tabeli skrótów. Czy ktoś pamięta, jak to się nazywało? (Myślę, że czytałem o tym w starym IBM TR.) W każdym razie, możesz też ustawić to tak, jak sugeruje @ o11c - zawsze najpierw szukaj w hashu, jeśli go nie ma, zajrzyj do swojej tablicy bitów.
davidbak

11

O ile w danych nie ma wzorca, jest mało prawdopodobne, aby istniała jakakolwiek rozsądna optymalizacja szybkości lub rozmiaru, a także - zakładając, że celujesz w normalny komputer - 10 MB i tak nie jest takie duże.

W twoich pytaniach są dwa założenia:

  1. Dane są źle przechowywane, ponieważ nie używasz wszystkich bitów
  2. Lepsze przechowywanie przyspieszyłoby sprawę.

Myślę, że oba te założenia są fałszywe. W większości przypadków odpowiednim sposobem przechowywania danych jest przechowywanie najbardziej naturalnej reprezentacji. W twoim przypadku to jest ten, który wybrałeś: bajt dla liczby od 0 do 255. Każda inna reprezentacja będzie bardziej złożona i dlatego - wszystkie inne rzeczy są równe - wolniejsza i bardziej podatna na błędy. Aby odejść od tej ogólnej zasady, potrzebujesz mocniejszego powodu niż potencjalnie sześć „zmarnowanych” bitów na 95% danych.

Drugie założenie będzie prawdziwe wtedy i tylko wtedy, gdy zmiana rozmiaru tablicy spowoduje znacznie mniej braków w pamięci podręcznej. To, czy tak się stanie, można definitywnie określić tylko poprzez profilowanie działającego kodu, ale myślę, że jest mało prawdopodobne, aby spowodował znaczącą różnicę. Ponieważ w obu przypadkach będziesz mieć losowy dostęp do tablicy, procesor będzie miał trudności z ustaleniem, które bity danych mają być buforowane i zachowywane w obu przypadkach.


8

Jeśli dane i dostępy są równomiernie rozłożone losowo, wydajność prawdopodobnie będzie zależeć od tego, jaki ułamek dostępów pozwala uniknąć pominięcia pamięci podręcznej na poziomie zewnętrznym. Optymalizacja będzie wymagała znajomości rozmiaru tablicy, która może być niezawodnie umieszczona w pamięci podręcznej. Jeśli twoja pamięć podręczna jest wystarczająco duża, aby pomieścić jeden bajt na każde pięć komórek, najprostszym podejściem może być przechowywanie w jednym bajcie pięciu wartości zakodowanych w trzech zasadach z zakresu 0-2 (są 243 kombinacje 5 wartości, więc zmieścić w bajcie), wraz z tablicą 10 000 000 bajtów, która byłaby odpytywana za każdym razem, gdy wartość przy podstawie 3 wskazuje „2”.

Jeśli pamięć podręczna nie jest tak duża, ale mogłaby pomieścić jeden bajt na 8 komórek, nie byłoby możliwe użycie jednej wartości bajtowej do wybrania spośród wszystkich 6561 możliwych kombinacji ośmiu wartości o podstawie 3, ale ponieważ jedyny efekt zmiana 0 lub 1 na 2 spowodowałaby niepotrzebne w innym przypadku wyszukiwanie, poprawność nie wymagałaby obsługi wszystkich 6,561. Zamiast tego można skupić się na 256 najbardziej „użytecznych” wartościach.

Zwłaszcza jeśli 0 występuje częściej niż 1 lub odwrotnie, dobrym podejściem może być użycie 217 wartości do zakodowania kombinacji 0 i 1 zawierających 5 lub mniej jedynek, 16 wartości do zakodowania od xxxx0000 do xxxx1111, 16 do zakodowania od 0000xxxx do 1111xxxx i jeden dla xxxxxxxx. Cztery wartości pozostałyby do jakiegokolwiek innego zastosowania. Jeśli dane są rozmieszczane losowo zgodnie z opisem, niewielka większość wszystkich zapytań trafiłaby w bajty zawierające tylko zera i jedynki (w około 2/3 wszystkich grup ośmiu wszystkie bity byłyby zerami i jedynkami, a około 7/8 miałyby sześć lub mniej 1 bitów); zdecydowana większość tych, które nie wylądowały w bajcie zawierającym cztery znaki x, i miałaby 50% szans na wylądowanie na zero lub jedynce. Dlatego tylko około jedno na cztery zapytania wymagałoby przeszukiwania dużej tablicy.

Jeśli dane są dystrybuowane losowo, ale pamięć podręczna nie jest wystarczająco duża, aby obsłużyć jeden bajt na osiem elementów, można spróbować zastosować to podejście z każdym bajtem obsługującym więcej niż osiem elementów, ale chyba że istnieje silne odchylenie w kierunku 0 lub w kierunku 1 , ułamek wartości, które można obsłużyć bez konieczności wyszukiwania w dużej tablicy, zmniejszy się wraz ze wzrostem liczby obsługiwanej przez każdy bajt.


7

Dodam do odpowiedzi @ o11c , ponieważ jego sformułowanie może być nieco zagmatwane. Gdybym musiał wycisnąć ostatni bit i cykl procesora, zrobiłbym co następuje.

Zaczniemy od skonstruowania zbalansowanego drzewa wyszukiwania binarnego, które zawiera 5% przypadków „czegoś innego”. Przy każdym wyszukiwaniu szybko poruszasz się po drzewie: masz 10000000 elementów, z czego 5% znajduje się w drzewie: stąd struktura danych drzewa zawiera 500000 elementów. Przechodzenie tego w czasie O (log (n)) daje 19 iteracji. Nie jestem w tym ekspertem, ale wydaje mi się, że istnieje kilka implementacji wydajnych pod względem pamięci. Zgadnijmy:

  • Drzewo jest zbalansowane, więc można obliczyć pozycję poddrzewa (indeksy nie muszą być przechowywane w węzłach drzewa). W ten sam sposób sterta (struktura danych) jest przechowywana w pamięci liniowej.
  • Wartość 1-bajtowa (od 2 do 255)
  • 3 bajty na indeks (10000000 zajmuje 23 bity, co odpowiada 3 bajtom)

W sumie 4 bajty: 500000 * 4 = 1953 kB. Pasuje do pamięci podręcznej!

We wszystkich innych przypadkach (0 lub 1) możesz użyć bitvectora. Pamiętaj, że nie możesz pominąć 5% innych przypadków dostępu losowego: 1,19 MB.

Połączenie tych dwóch zajmuje około 3099 MB. Korzystając z tej techniki, zaoszczędzisz współczynnik 3,08 pamięci.

Jednak to nie przebija odpowiedzi @Matteo Italia (który wykorzystuje 2,76 MB), szkoda. Czy jest coś, co możemy zrobić dodatkowo? Najbardziej zajmującą pamięć częścią są 3 bajty indeksu w drzewie. Jeśli uda nam się to zmniejszyć do 2, zaoszczędzilibyśmy 488 kB, a całkowite użycie pamięci wyniosłoby: 2,622 MB, czyli mniej!

Jak to robimy? Musimy zmniejszyć indeksowanie do 2 bajtów. Ponownie 10000000 zajmuje 23 bity. Musimy być w stanie upuścić 7 bitów. Możemy to po prostu zrobić, dzieląc zakres 10000000 elementów na 2 ^ 7 (= 128) regiony 78125 elementów. Teraz możemy zbudować zrównoważone drzewo dla każdego z tych regionów, zawierające średnio 3906 elementów. Wybranie odpowiedniego drzewa odbywa się poprzez proste podzielenie indeksu docelowego przez 2 ^ 7 (lub przesunięcie bitowe >> 7). Teraz wymagany indeks do przechowywania może być reprezentowany przez pozostałe 16 bitów. Zwróć uwagę, że długość drzewa, które musi być przechowywane, wiąże się z pewnym obciążeniem, ale jest to pomijalne. Należy również zauważyć, że ten mechanizm dzielenia zmniejsza wymaganą liczbę iteracji do przejścia po drzewie, co teraz zmniejsza się do 7 iteracji mniej, ponieważ porzuciliśmy 7 bitów: pozostało tylko 12 iteracji.

Zauważ, że teoretycznie możesz powtórzyć proces, aby odciąć kolejne 8 bitów, ale wymagałoby to stworzenia 2 ^ 15 zrównoważonych drzew, ze średnio ~ 305 elementami. Dałoby to 2,143 MB, z zaledwie 4 iteracjami na spacer po drzewie, co jest znacznym przyspieszeniem w porównaniu z 19 iteracjami, od których zaczynaliśmy.

Podsumowując: pokonuje to strategię 2-bitowych wektorów niewielkim zużyciem pamięci, ale jest to cała trudność do wdrożenia. Ale jeśli może to zadecydować o dopasowaniu pamięci podręcznej lub nie, warto spróbować.


1
Dzielny wysiłek!
davidbak

1
Spróbuj tego: ponieważ 4% przypadków ma wartość 2 ... stwórz zbiór wyjątkowych przypadków (> 1). Utwórz drzewo w sposób opisany dla naprawdę wyjątkowych przypadków (> 2). Jeśli występuje w zestawie i drzewie, użyj wartości w drzewie; jeśli jest obecny w zestawie, a nie w drzewie, użyj wartości 2, w przeciwnym razie (nieobecny w zestawie) przeszukaj w swoim bitvector. Drzewo będzie zawierało tylko 100000 elementów (bajtów). Zestaw zawiera 500000 elementów (ale żadnych wartości). Czy to zmniejsza rozmiar, uzasadniając jednocześnie zwiększony koszt? (100% wyszukiwań wygląda w zestawie; 5% wyszukiwań musi również szukać w drzewie.)
davidbak

Zawsze chcesz używać tablicy posortowanej według CFBS, gdy masz niezmienne drzewo, więc nie ma alokacji dla węzłów, tylko dane.
o11c

5

Jeśli wykonujesz tylko operacje odczytu, lepiej byłoby nie przypisywać wartości do pojedynczego indeksu, ale do przedziału indeksów.

Na przykład:

[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...

Można to zrobić za pomocą struktury. Możesz również chcieć zdefiniować klasę podobną do tej, jeśli lubisz podejście OO.

class Interval{
  private:
    uint32_t start; // First element of interval
    uint32_t end; // Last element of interval
    uint8_t value; // Assigned value

  public:
    Interval(uint32_t start, uint32_t end, uint8_t value);
    bool isInInterval(uint32_t item); // Checks if item lies within interval
    uint8_t getValue(); // Returns the assigned value
}

Teraz wystarczy powtórzyć listę interwałów i sprawdzić, czy indeks znajduje się w jednym z nich, co może średnio zużywać znacznie mniej pamięci, ale kosztuje więcej zasobów procesora.

Interval intervals[INTERVAL_COUNT];
intervals[0] = Interval(0, 15000, 0);
intervals[1] = Interval(15001, 15002, 153);
intervals[2] = Interval(15003, 26876, 2);
intervals[3] = Interval(25677, 31578, 0);
...

uint8_t checkIntervals(uint32_t item)

    for(int i=0; i<INTERVAL_COUNT-1; i++)
    {
        if(intervals[i].isInInterval(item) == true)
        {
            return intervals[i].getValue();
        }
    }
    return DEFAULT_VALUE;
}

Jeśli uporządkujesz interwały malejąco, zwiększysz prawdopodobieństwo, że poszukiwany element zostanie wcześnie znaleziony, co dodatkowo zmniejszy średnie zużycie pamięci i zasobów procesora.

Możesz także usunąć wszystkie przedziały o rozmiarze 1. Umieść odpowiednie wartości na mapie i sprawdź je tylko wtedy, gdy szukany element nie został znaleziony w przedziałach. Powinno to również nieco podnieść średnią wydajność.


4
Ciekawy pomysł (+1), ale jestem nieco sceptyczny, że uzasadniłoby to narzut, chyba że jest dużo długich przebiegów zer i / lub długich przebiegów jedynek. W efekcie sugerujesz użycie kodowania danych na długość serii. Może to być dobre w niektórych sytuacjach, ale prawdopodobnie nie jest dobrym ogólnym podejściem do tego problemu.
John Coleman

Dobrze. W szczególności w przypadku dostępu swobodnego jest to prawie na pewno wolniejsze niż prosta tablica lub unt8_tnawet jeśli zajmuje znacznie mniej pamięci.
lewej około

4

Dawno, dawno temu, po prostu pamiętam ...

Na uniwersytecie otrzymaliśmy zadanie przyspieszenia programu ray tracera, który musi w kółko czytać przez algorytm z tablic buforowych. Znajomy powiedział mi, żebym zawsze używał odczytów RAM, które są wielokrotnościami 4 bajtów. Więc zmieniłem tablicę z wzoru [x1, y1, z1, x2, y2, z2, ..., xn, yn, zn] na wzorzec [x1, y1, z1,0, x2, y2, z2 , 0, ..., xn, yn, zn, 0]. Oznacza, że ​​po każdej współrzędnej 3D dodaję puste pole. Po kilku testach wydajności: było szybciej. Krótko mówiąc: przeczytaj wielokrotność 4 bajtów z twojej tablicy z pamięci RAM, a może także z właściwej pozycji początkowej, więc czytasz mały klaster, w którym znajduje się szukany indeks, i czytasz przeszukiwany indeks z tego małego klastra w procesorze. (W twoim przypadku nie będziesz musiał wstawiać pól wypełniających, ale koncepcja powinna być jasna)

Może także inne wielokrotności mogą być kluczem w nowszych systemach.

Nie wiem, czy to zadziała w Twoim przypadku, więc jeśli to nie zadziała: Przepraszamy. Jeśli to zadziała, z przyjemnością usłyszę o niektórych wynikach testu.

PS: Aha i jeśli istnieje jakiś wzorzec dostępu lub pobliskie indeksy, do których uzyskano dostęp, możesz ponownie użyć buforowanego klastra.

PPS: Możliwe, że wieloczynnik był bardziej podobny do 16 bajtów, czy coś w tym stylu, to było zbyt dawno, żebym dokładnie pamiętał.


Prawdopodobnie myślisz o cachelines, które zwykle mają 32 lub 64 bajty, ale to nie pomoże tutaj, ponieważ dostęp jest losowy.
Surt

3

Patrząc na to, możesz podzielić swoje dane, na przykład:

  • zestaw bitów, który jest indeksowany i reprezentuje wartość 0 (przydałby się tutaj std :: vector)
  • zestaw bitów, który jest indeksowany i reprezentuje wartość 1
  • std :: vector dla wartości 2, zawierający indeksy odnoszące się do tej wartości
  • mapa dla innych wartości (lub std :: vector>)

W tym przypadku wszystkie wartości pojawiają się do danego indeksu, więc możesz nawet usunąć jeden z zestawów bitów i reprezentować wartość, której brakuje w pozostałych.

Pozwoli to zaoszczędzić trochę pamięci na ten przypadek, chociaż pogorszyłoby to najgorszy. Będziesz także potrzebować większej mocy procesora do wyszukiwania.

Upewnij się, że mierzysz!


1
Zestaw bitów dla jedynek / zer. Zestaw wskaźników dla par. I rzadka tablica asocjacyjna dla reszty.
Red.Wave

Oto krótkie podsumowanie
JVApen

Poinformuj OP o terminach, aby mógł wyszukać alternatywne implementacje każdego z nich.
Red.Wave

2

Jak wspomina Mats w swoim komentarzu-odpowiedzi, trudno jest powiedzieć, jakie jest właściwie najlepsze rozwiązanie, nie wiedząc dokładnie, jakie masz dane (np. Czy są długie ciągi zer itd.) I jak wygląda twój wzorzec dostępu na przykład (czy „losowy” oznacza „w każdym miejscu”, czy po prostu „nie w całkowicie liniowy sposób” lub „każda wartość dokładnie raz, tylko losowo” lub…).

To powiedziawszy, przychodzą na myśl dwa mechanizmy:

  • Tablice bitowe; tj. gdybyś miał tylko dwie wartości, mógłbyś w trywialny sposób skompresować swoją tablicę o współczynnik 8; jeśli masz 4 wartości (lub „3 wartości + wszystko inne”), możesz skompresować dwukrotnie. Co może po prostu nie być warte zachodu i wymagałoby testów porównawczych, zwłaszcza jeśli masz naprawdę losowe wzorce dostępu, które wymykają się z twoich pamięci podręcznych, a zatem w ogóle nie zmieniają czasu dostępu.
  • (index,value)lub (value,index)stoły. To znaczy, mam jedną bardzo małą tabelę dla przypadku 1%, może jedną tabelę dla przypadku 5% (która musi tylko przechowywać indeksy, ponieważ wszystkie mają tę samą wartość) i dużą skompresowaną tablicę bitową dla dwóch ostatnich przypadków. A przez „tabelę” mam na myśli coś, co pozwala na stosunkowo szybkie wyszukiwanie; tj. może hash, drzewo binarne i tak dalej, w zależności od tego, co masz do dyspozycji i twoich rzeczywistych potrzeb. Jeśli te podtabele pasują do twoich skrzynek 1/2 poziomu, możesz mieć szczęście.

1

Nie jestem zbyt zaznajomiony z C, ale w C ++ możesz użyć znaku bez znaku do reprezentowania liczby całkowitej z zakresu 0 - 255.

W porównaniu do normalnego int (znowu pochodzę ze świata Java i C ++ ), w którym wymagane są 4 bajty (32 bity), bez znaku char wymaga 1 bajtu (8 bitów). więc może zmniejszyć całkowity rozmiar tablicy o 75%.


Prawdopodobnie tak jest już w przypadku użycia uint8_t - 8 oznacza 8 bitów.
Peter Mortensen

-4

Zwięźle opisałeś wszystkie cechy dystrybucji swojej tablicy; podrzucić tablicę .

Tablicę można łatwo zastąpić metodą losową, która generuje takie same probabilistyczne dane wyjściowe, jak tablica.

Jeśli liczy się spójność (generowanie tej samej wartości dla tego samego losowego indeksu), rozważ użycie filtra bloom i / lub mapy hash do śledzenia powtarzających się trafień. Jeśli jednak dostęp do tablicy naprawdę jest przypadkowy, jest to całkowicie niepotrzebne.


18
Podejrzewam, że użyto tutaj terminu „dostęp losowy”, aby wskazać, że dostęp jest nieprzewidywalny, a nie że w rzeczywistości jest przypadkowy. (tj. jest to zamierzone w znaczeniu „plików o swobodnym dostępie”)
Michael Kay

Tak, to jest prawdopodobne. OP nie jest jednak jasne. Jeśli dostępy OP nie są w jakikolwiek sposób przypadkowe, to wskazana jest jakaś forma rzadkiej tablicy, tak jak w innych odpowiedziach.
Dúthomhas

1
Myślę, że masz rację, ponieważ OP wskazał, że zapętli całą tablicę w losowej kolejności. W przypadku, gdy trzeba obserwować tylko rozkłady, jest to dobra odpowiedź.
Ingo Schalk-Schupp
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.