Come posso interrogare, incrementare e decrementare interi di lunghezza arbitraria codificati in un array di bit?

Ecco l'inizio di una soluzione pseudocodice per W = 4.

// beware: untested code ahead

uint64[] array;

int read(int i)
{
  uint64 loaded = array[i / 16];
  return (loaded >> ((i % 16) * 4)) & 0xF;
}

i / 16 perché ci sono 16 inti a 4 bit per uint64 (è 64 / W).

0xF è la maschera di bit (è 2 ** W - 1).

l'incremento potrebbe essere simile, costruito sopra quello:

1. leggi
2. incrementa il numero intero risultante
3. scrittura

La scrittura è simile alla lettura (si supponga che il nuovo valore incrementato di n sia piccolo e non necessiti di masking / truncating):

void write(i, n)
{
  uint64 loaded = array[i / 16];
  shift = ((i % 16) * 4);
  // zero (mask-out) some bits to make a hole into which to OR the new value
  loaded = loaded & ~(0xF << shifted);
  // or-in the new value, suitably shifted
  loaded = loaded | (n << shifted);
  // write the result back into the buffer
  array[i / 16] = loaded;
}

Sono disponibili micro-ottimizzazioni combinando queste operazioni (lettura e scrittura) in un'unica funzione (ad esempio, carico e spostamento devono essere calcolati una sola volta).

Suppongo che l'implementazione più veloce utilizzi un'implementazione separata / dedicata / codificata per ogni valore di W.

I valori di W di 3, 5, 6 e 7 introducono complicazioni che non voglio risolvere, cioè "un esercizio per il lettore". : - (

L'implementazione più veloce potrebbe essere l'uso di tabelle di ricerca anziché di bit-twiddling; per esempio, considera questa soluzione per W è 4:

uint8[] array; // not uint64
uint8[256][2] lookup; // precalculated lookup table

increment(i)
{
    uint8 loaded = array[i/2];
    // lookup the incremented value
    // choose the right lookup table to increment either the 1st or 2nd nibble
    loaded = lookup[loaded][i % 2];
    // write the result back
    array[i/2] = loaded;
}

Per W è 2 avresti bisogno di una tabella di ricerca come

uint8[256][4] lookup;

Precalcolare il contenuto della tabella di ricerca è un esercizio per il lettore (puoi farlo per macchina, usando un'implementazione più lenta) ... e così stai cercando di implementare quei valori di W meno convenienti (3, 5, 6 e 7).

Forse dovresti, però, a meno che tu non stia facendo questo per divertimento o per i compiti, prendi i consigli di qualcuno e cerca qualche implementazione esistente (perché invece di "reinventare la ruota", in genere prova ad usare un professionista pre-creato, ottimizzato, soluzione testata, sottoposta a peer-review, supportata).

Se stai cercando l'implementazione più rapida (non la più piccola), IMO potresti prendere in considerazione l'implementazione di W = 3 e simili sprecando spazio nel buffer (es. implementare W = 3 usando lo stesso codice e il layout dei dati di W = 4 ).

Se stai usando una tabella di ricerca, è meglio allineare un limite di byte (in modo da trasformare interi byte, che richiedono solo 256 elementi nella tabella di ricerca).

Se stai girando un po 'basta allinearsi su un limite a 64-bit, e puoi sprecare meno spazio (es. quando W = 6, invece di adattare ogni uint6 a un uint8, adattare 10 uint6 a un uint64, sprecare solo 4 bit per uint64).

L'approccio più rapido per accedere a numeri interi racchiusi in campi con meno di un singolo byte, almeno su un processore famiglia x86, è probabile che implichi l'utilizzo di PDEP e PEXP istruzioni di manipolazione dei bit . Non ho controllato quanto siano validi i compilatori correnti nel generare queste istruzioni, anche se un breve google suggerisce che almeno fino allo scorso anno LLVM non ha avuto alcun supporto diretto , sebbene possa essere supportato tramite intrinseche - il che significa che è improbabile che Go la utilizzi a meno che non ci sia un ottimizzazione o un'interfaccia esplicita nel compilatore progettato per abilitarli. LLVM in generale è abbastanza vicino a essere il miglior ottimizzatore disponibile per le macchine x86, quindi se LLVM non genera queste istruzioni è una buona scommessa che nessuno degli altri grandi compilatori faccia. Questo suggerisce che per una prestazione ottimale qui, il linguaggio assembly è probabilmente la scelta migliore.

A meno che non si abbia davvero bisogno dei risparmi di spazio prodotti utilizzando questo formato compatto, tuttavia, potrebbe essere meglio sprecare un po 'di spazio in modo da poter utilizzare le istruzioni SSE * più comunemente supportate (e più veloci) per eseguire le operazioni. La maggior parte dei compilatori moderni può generarli in molte circostanze e sono probabilmente il modo più rapido per eseguire operazioni su molti dati, ma richiedono che i valori vengano compressi in campi di almeno 1 byte per valore.

Puoi farlo con un po 'di matematica e un uso intelligente delle operazioni bit a bit come e ( & ) o ( | ), e shift ( >> ). Lascerò l'implementazione effettiva al lettore.