Come posso eliminare il controllo del limite di array su questa vettorizzazione del ciclo?

Question

Ho un'attività per dividere più esecuzioni di colonne varbinary (8000) da una tabella di database sul valore letterale binario 0x0. Tuttavia, questo potrebbe cambiare quindi vorrei così mantenere questa variabile. Mi piacerebbe usare SQLCLR per farlo rapidamente come una funzione di valore della tabella di streaming. So che le mie corde saranno sempre di almeno qualche migliaio di byte ciascuna.

Modifica: ho aggiornato il mio algoritmo. Per evitare la cattiveria dello srotolamento del circuito interno. Ma è estremamente difficile convincere il CLR a fare le scelte giuste sull'assegnazione dei registri. Sarebbe fantastico se ci fosse un modo semplice per convincere il CLR che io e io siamo VERAMENTE la stessa cosa. Ma invece fa davvero cose stupide. Sarebbe bello ottimizzare il primo anello del percorso. Ma non puoi usare un goto in un ciclo.

Ho deciso di adattare un'implementazione a 64 bit della funzione C memchr. Fondamentalmente, invece di scansionare un byte alla volta e confrontarlo, eseguo la scansione di 8 byte alla volta usando un po 'di twiddling. Per riferimento, Array.IndexOf<Byte> fa qualcosa di simile con una scansione a 4 byte per una risposta, voglio solo continuare a farlo. Ci sono un paio di cose da notare:

1. pressione memoria è un problema molto reale nelle funzioni SQLCLR. String.Split è fuori perché in primo piano alloca molta memoria che vorrei davvero evitare. Funziona anche con le stringhe UCS-2, che mi richiederebbero di convertire le mie stringhe ascii in stringhe unicode e quindi trattare i miei dati come un tipo di dati lob sul rendimento. (SqlChars/SqlString può restituire solo 4000 byte prima di essere trasformato in un tipo di pallonetto).

2. Mi piacerebbe streaming. Un altro motivo per evitare String.Split fa il suo lavoro tutto in una volta, creando molta pressione di memoria. Il codice con un sacco di metodi T-SQL purissimi delimitatori inizierà a batterlo.

3. Mi piacerebbe tenerlo "sicuro". Quindi tutto gestito. Sembra esserci una penalità molto grande in un controllo di sicurezza.

Buffer.BlockCopy è veramente veloce, e sembra essere meglio pagare quel costo in anticipo una volta che costantemente pagare il costo per BitConverter. Anche questo è ancora meno costoso, piuttosto che convertire il mio input in stringa e mantenere questo riferimento.

Il codice è abbastanza veloce, ma sembra che io stia pagando per un bel numero di controlli, nel ciclo iniziale e nella sezione critica quando trovo una corrispondenza. Di conseguenza, per il codice con molti delimitatori, tendo a perdere un enumeratore C# più semplice che fa solo un confronto tra byte.

Ecco il mio codice,

class SplitBytesEnumeratorA : IEnumerator 
{ 
    // Fields 
    private readonly byte[] _bytes; 
    private readonly ulong[] _longs; 
    private readonly ulong _comparer; 
    private readonly Record _record = new Record(); 
    private int _start; 
    private readonly int _length; 

    // Methods 
    internal SplitBytesEnumeratorA(byte[] bytes, byte delimiter) 
    { 
     this._bytes = bytes; 
     this._length = bytes.Length; 
     // we do this so that we can avoid a spillover scan near the end. 
     // in unsafe implementation this would be dangerous as we potentially 
     // will be reading more bytes than we should. 

     this._longs = new ulong[(_length + 7)/8]; 
     Buffer.BlockCopy(bytes, 0, _longs, 0, _length); 
     var c = (((ulong)delimiter << 8) + (ulong)delimiter); 
     c = (c << 16) + c; 
     // comparer is now 8 copies of the original delimiter. 
     c |= (c << 32); 
     this._comparer = c; 
    } 

    public bool MoveNext() 
    { 
     if (this._start >= this._length) return false; 
     int i = this._start; 
     var longs = this._longs; 
     var comparer = this._comparer; 
     var record = this._record; 
     record.id++; 
     // handle the case where start is not divisible by eight. 
     for (; (i & 7) != 0; i++) 
     { 
      if (i == _length || _bytes[i] == (comparer & 0xFF)) 
      { 
       record.item = new byte[(i - _start)]; 
       Buffer.BlockCopy(_bytes, _start, record.item, 0, i - _start); 
       _start = i + 1; 
       return true; 
      } 
     } 

     // main loop. We crawl the array 8 bytes at a time. 

     for (int j=i/8; j < longs.Length; j++) 
     { 
      ulong t1 = longs[j]; 
      unchecked 
      { 
       t1 ^= comparer; 
       ulong t2 = (t1 - 0x0101010101010101) & ~t1; 
       if ((t2 & 0x8080808080808080) != 0) 
       { 
        i =j*8; 
        // make every case 3 comparison instead of n. Potentially better. 
        // This is an unrolled binary search. 
        if ((t2 & 0x80808080) == 0) 
        { 
         i += 4; 
         t2 >>= 32; 
        } 

        if ((t2 & 0x8080) == 0) 
        { 
         i += 2; 
         t2 >>= 16; 
        } 

        if ((t2 & 0x80) == 0) 
       { 
       i++; 
       } 
       record.item = new byte[(i - _start)]; 
       // improve cache locality by not switching collections. 
       Buffer.BlockCopy(longs, _start, record.item, 0, i - _start);    _start = i + 1; 
       return true; 
      } 
     } 
     // no matches found increment by 8 
    } 
    // no matches left. Let's return the remaining buffer. 
    record.item = new byte[(_length - _start)]; 
    Buffer.BlockCopy(longs, _start, record.item, 0, (_length - _start)); 
    _start = _bytes.Length; 
    return true; 
    } 

    void IEnumerator.Reset() 
    { 
     throw new NotImplementedException(); 
    } 

    public object Current 
    { 
     get 
     { 
      return this._record; 
     } 
    } 
} 

// We use a class to avoid boxing . 
class Record 
{ 
    internal int id; 
    internal byte[] item; 
} 

Answer 1

Pensando fuori della scatola, avete considerato convertire le stringhe in XML e XQuery utilizzando per fare la scissione?

Ad esempio, è possibile passare il delimitatore e (codice d'aria):

DECLARE @xml as xml 
DECLARE @str as varchar(max) 
SET @str = (SELECT CAST(t.YourBinaryColumn AS varchar(max) FROM [tableName] t) 
SET @xml = cast(('<X>'+replace(@str,@delimiter,'</X><X>')+'</X>') as xml) 

Questo converte il binario in una stringa e sostituisce il delimitatore con tag XML. Quindi:

SELECT N.value('.', 'varchar(10)') as value FROM @xml.nodes('X') as T(N) 

otterrà i singoli "elementi", i dati tra ogni occorrenza del delimitatore.

Forse questa idea potrebbe essere utile come-è o come catalizzatore da cui è possibile costruire.