Argomenti Variadic associati: Bitmask vs Array

0

Introduzione

Quanto segue assume C # come lingua di riferimento, o qualsiasi altra lingua tipizzata in modo statico. Questa non è una domanda specifica per l'API di Unity, ma viene utilizzata come esempio.

Nell'API di Unity, la maggior parte delle persone si imbatte in la funzione Raycast . Questo ha un argomento, di tipo int chiamato layerMask . Questo è un numero intero, che funziona come una maschera bit per bit (se c'è 1 al posto n-esimo, il posto n-esimo è incluso nel calcolo).

Ho sempre pensato che questa fosse una scelta di design molto strana per le loro API.

Prima di tutto, dovrei chiarire che non ci possono essere solo 32 livelli in Unity, quindi, questi livelli sono finiti, ma puoi avere un numero qualsiasi di livelli (sotto i 32).

Personalmente, vorrei chiedere come argomento, una matrice di numeri interi, i cui elementi sarebbero i livelli con i quali si desidera eseguire il raycast (identici all'implementazione effettiva, senza che sia bit a bit). Un altro modo, sarebbe di avere argomenti variardici, se la lingua lo supporta. (questi punti si applicano anche alle lingue digitate dinamicamente). (Ho letto alcuni argomenti contro l'uso di argomenti variardici, quindi non sceglierei questo)

La domanda effettiva

Why would one choose a bitwise mask as a representation of a selection of a (finite/bound) amount of items, instead of an array of the selected items?

Dato che stai sacrificando l'usabilità e la leggibilità *, quali sono i vantaggi?

Ipotesi

Poiché Raycast è una funzione molto utile e ampiamente utilizzata, suppongo che abbiano scelto questo per motivi di prestazioni (le operazioni bit a bit possono essere molto più veloci rispetto all'iterazione su un array). In questo caso particolare, dato che la lunghezza massima dell'array sarebbe 32, dubito che la differenza sarebbe enorme, ma suppongo che in questo caso ogni prestazione sia importante.

L'altro vantaggio è sicuramente l'impronta della memoria (un numero intero rispetto a un'intera serie di essi), ma dubito che questo sia generalmente importante (in questo e in altri casi).

Noterò anche che sia gli array che i numeri interi non impongono il limite delle dimensioni degli elementi. L'array, può essere grande quanto vuoi, e il numero intero ha una certa dimensione di implementazione / macchina specifica, quindi se si desidera attivare 17 elementi, nessuna dimensione di intero importerà che non ci sia elemento 18.

* Esempio: per indicare il terzo e il quarto elemento, invece dell'argomento 12 (1100 in binario), potresti avere [3,4]

    
posta K. Gkinis 29.03.2016 - 15:08
fonte

1 risposta

2

Le maschere di bit sono certamente un C-ismo a cui ci vuole un po 'per abituarsi. Tuttavia, le operazioni a livello di bit possono essere eseguite con poche istruzioni di codice macchina senza alcuna indiretta di puntamento o diramazione, diversamente dalle operazioni che coinvolgono le raccolte. Nel codice sensibile alle prestazioni come i motori grafici, questo può fare una grande differenza.

Evitare la ramificazione è una buona cosa perché le moderne CPU usano lunghe pipeline per la decodifica delle istruzioni, e quindi cercano di indovinare quale percorso attraverso il tuo codice sarà preso. Se la CPU sbaglia, la pipeline viene svuotata e devi attendere un paio di istruzioni prima che la CPU raggiunga la velocità massima.

Se avessimo a che fare con un array, controllare se quell'array contiene un layer specifico è costoso in termini di branching. Come pseudocodice:

func contains(Array xs, uint x) -> bool {
  for (Index i = 0; i < xs.length; ++i) {
    if (xs[i] == x) return true;
  }
  return false;
}

Un'invocazione contains([4, 3], 5) verificherebbe la dimensione dell'array, il primo elemento, la dimensione dell'array, il secondo elemento, la dimensione dell'array, quindi tornerà definitivamente in negativo.

Per essere onesti, questo ciclo può essere srotolato considerando la dimensione superiore fissa:

func contains(Array xs, uint x) -> bool {
  switch (xs.length) {
  case 32: if (xs[31] == x) return true;
  ...
  case  2: if (xs[ 1] == x) return true;
  case  1: if (xs[ 0] == x) return true;
  default: return false;
}

Ma avrai ancora bisogno di un ramo per ogni elemento. Con una maschera bit, contains(mask, x) può essere implementata senza rami come (mask & (1 << x)) != 0 . Se il tuo x è noto, questo può essere piegato in modo costante in modo che il test possa essere eseguito in una o due istruzioni di codice macchina. Non c'è niente di meglio.

L'altra parte per le considerazioni sull'efficienza sono gli accessi alla memoria. Un numero intero si inserisce in un registro. Un array no. A meno che i contenuti dell'array non siano nella cache (e anche in quel caso), gli accessi alla memoria sono più lenti di quanto non facciano le istruzioni della CPU. Un singolo accesso alla memoria è sufficiente per leggere l'intera maschera di bit; con gli array avremmo solo un puntatore ai contenuti ora. A seconda di quanto intelligente possa essere fatto, avremmo bisogno di uno o più accessi per ottenere effettivamente i contenuti.

Non solo l'uso delle maschere di bit è più efficiente, ma può anche essere visto come una progettazione di API migliore . In particolare, l'utilizzo degli array presenta i seguenti problemi:

  • un elemento può verificarsi più di una volta (non abbiamo a che fare con un set).
  • gli elementi non sono ordinati, il che rende più costoso testare l'appartenenza in quanto dobbiamo controllare tutti gli elementi.
  • la creazione e l'inizializzazione degli array utilizza una sintassi ingombrante in molte lingue
  • la convalida dell'input è più costosa. Prendi in considerazione tutti i limiti che controllano per ogni argomento.

L'usabilità delle maschere di bit non è terribile. Se conosci un livello solo per indice, puoi facilmente creare il modello di bit con uno spostamento a sinistra. Il livello n utilizza il modello di bit 1 << n . Potresti anche nominare i livelli nel tuo codice. Una maschera può quindi essere facilmente costruita come mask = PLAYER_LAYER | WATER_LAYER | (1 << 12) . Questo può essere sostanzialmente più leggibile rispetto a molte opzioni booleane ( layer8: true, waterLayer: true, layer12: true ), può essere facilmente memorizzato in una variabile e adattato ( defaultMask | additionalLayer , defaultMask & ~excludedLayer ), e l'ordine delle maschere e la duplicazione delle maschere non ha importanza. L'unico problema delle maschere di bit è che sono limitati al numero di bit nel tipo di intero di backup.

    
risposta data 29.03.2016 - 15:53
fonte

Leggi altre domande sui tag