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

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.

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.

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.

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.

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”.

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.

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.

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ć.

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ść.

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ł.

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!

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.

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%.

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.