Newsgroup: it.comp.lang.c
Titolo: confronto buffer efficiente

Ciao a tutti
Da qualche giorno sto facendo un pò di prove con gli algoritmi di 
compressione loseless come scusa per imparare a programmare CUDA (farei 
meglio a fare altro per la mia ricerca di lavoro ma tant'è... a volte mi 
fisso)
Ora capita che ho bisogno di ordinare dei buffer (sostanzialmente un 
ordinamento di stringhe). Visto che i buffer in questione sono molto 
grandi, mi preme avere un confronto molto efficiente.
Nella versione attuale effettuo i confronti con memcmp che è un buon 
ordine di grandezza più veloce del confronto naive che avevo 
implementato inizialmente.
Avete consigli su come aumentare ancora l'efficienza?
Grazie
Giuseppe


se la mole di dati e' grande non ti conviene inserirli direttamente in
una struttura ordinata (come un btree)?
perdi in performance all'inserimento e alla cancellazione, ma la
ricerca e' molto veloce.
che algoritmo di ricerca usi adesso?
Ciao Jack

 wrote:

C'è solo un modo per confrontare due stringe alfabeticamente, ed il
fatto che siano molto lunghe non conta almeno che non siano molto
simili.
Se ne devi ordinare molte non ti serve un algoritmo di confronto, ma
un'algoritmo di ordinamento, la cui efficienza dipende dal contesto...
un quicksort?

 che algoritmo di ricerca usi adesso?
ovviamente volevo dire di ordinamento...
Ciao Jack

 
mergesort
non ho bisogno di fare ricerche ho semplicemente una serie di buffer da 
ordinare.
Siccome sono rotazioni dello stesso buffer iniziale non credo mi 
convenga utilizzare altre strutture dati.

 un quicksort?
al momento sto usando mergesort che dovrebbe fare un minor numero di 
confronti rispetto al quick.
Purtroppo il confronto è un passo che pesa molto visto che si tratta di 
stringhe dell'ordine delle centinaia di migliaia di caratteri.
Proverò anche con quicksort comunque grazie.


e sono *così* simili da dover fare centinaia di migliaia di confronti
tra char? Se sì, non puoi sapere *quanto* sono uguali (anche
euristicamente) in maniera da ridurre il campo di confronto?

fma...@gmail.com
 ha scritto:

Non posso fare ipotesi sui dati, sono semplicemente buffer. Però l'idea 
di valutare approssimativamente quanto sono uguali non mi sembra male.
Sinceramente avevo pensato ad un hash per evitarmi almeno di verificare 
l'uguaglianza ma credo di aver toppato malamente... ci possono essere 
collisioni!
Ci penso un pò su...
Comunque quando ho scritto il post originale pensavo più a questioni 
tecnologiche tipo utilizzare più efficacemente cache pipeline e roba 
simile, visto che usare memcmp piuttosto che fare il confronto byte per 
byte mi porta già da 4 min abbondanti a 10s nell'ordinamento di 7 
blocchi di 1.000.000 di elementi.

 blocchi di 1.000.000 di elementi.
Mi sembra troppa la differenza.. Comunque, meglio così!
Potresti provare semplicemente a scalare l'ordinamento su più thread
(uno per ogni core che hai a disposizione): il confronto tra due
stringhe non è scalabile, ma niente ti vieta di mettere più confronti
in parallelo ;)

fma...@gmail.com
 ha scritto:

Per la verità pensavo di parallelizzare a livello dell'algoritmo di 
ordinamento o di scrivere proprio un bitoncsort; ma questo in un 
sencondo momento. Ho bisogno innanzitutto di prestazioni sulle 
operazioni di base.
Anche a me è sembrato tantissimo. Per la verità prima avevo provato ad 
allineare a 32bit cioè trattavo il buffer come un buffer di interi in 
modo da confrontare quattro byte per volta (l'incremento di velocità 
intorno a 4x c'era effettivamente) però... x86 è little endian!
credo che memcmp faccia ottimizzazioni simili anche se non ho un'idea 
precisa di quali.

 precisa di quali.
Le due implementazioni che ho a disposizione dicono:
1- il kernel linux la definisce come:
static inline int memcmp(const void *s1, const void *s2, size_t len)
{
    u8 diff;
    asm("repe; cmpsb; setnz %0"
        : "=qm" (diff), "+D" (s1), "+S" (s2), "+c" (len));
    return diff;
}
2- mentre la libc (ho sottomano la newlib, adesso)
unsigned char *s1 = (unsigned char *) m1;
  unsigned char *s2 = (unsigned char *) m2;
  unsigned long *a1;
  unsigned long *a2;
  /* If the size is too small, or either pointer is unaligned,
     then we punt to the byte compare loop.  Hopefully this will
     not turn up in inner loops.  */
  if (!TOO_SMALL(n) && !UNALIGNED(s1,s2))
    {
      /* Otherwise, load and compare the blocks of memory one
         word at a time.  */
      a1 = (unsigned long*) s1;
      a2 = (unsigned long*) s2;
      while (n >= LBLOCKSIZE)
        {
          if (*a1 != *a2)
        break;
          a1++;
          a2++;
          n -= LBLOCKSIZE;
        }
      /* check m mod LBLOCKSIZE remaining characters */
      s1 = (unsigned char*)a1;
      s2 = (unsigned char*)a2;
    }
  while (n--)
    {
      if (*s1 != *s2)
    return *s1 - *s2;
      s1++;
      s2++;
    }
  return 0;

 in parallelo ;)
Mi sento in vena di sparare cagate quindi le condivido con tutti
voi :)
Davvero il confronto tra due stringhe non e' parallelizzabile? Ad
esempio:
- prendi la stringa da L caratteri, dividila in N chunk da L/N
caratteri l'uno
- fork N thread: ognuno calcola il confronto del suo chunk
- join N thread: adesso il master thread si trova in mano N valori (ad
es 1,0,-1) e gli basta controllare quelli, dal "piu' significativo" al
"meno significativo"
Pleg


Rispetto al parallelizzare i confronti, col tuo metodo hai un caso
ottimo uguale e pessimo veramente *pessimo* :D

 ottimo uguale e pessimo veramente *pessimo* :D
Ho assunto che non dovesse fare molti confronti, altrimenti li avrebbe gia' 
parallelizzati. Ho inteso la domanda come "velocizzare il singolo 
confronto".
Pleg 

 Davvero il confronto tra due stringhe non e' parallelizzabile? 
Io penso che non lo sia. Nel confronto tra stringhe molto lunghe il 
collo di bottiglia č l'accesso alla memoria, non l'utilizzo di CPU. 
Dunque piů parallelizzi e piů vai ad intasare il bus.
E.

 parallelizzi e piů vai ad intasare il bus.
Gia'... pero' la scheda grafica ha 100+ GB/s di banda, quindi forse 
l'intasamento e' ancora lontano.
Pleg 

 l'intasamento e' ancora lontano.
Boh... non capisco cosa c'entra la scheda grafica...
E.

 C'è solo un modo per confrontare due stringe alfabeticamente
Da un punto di vista logico si. Da un punto di vista implementativo,
dipende. 
In particolare io prenderei in considerazione (a meno che non lo faccia
gia' la memcmp/bcmp, cosa che ritengo probabile su un'implementazine
ragionevole) di fare i confronti parola a parola, gestendo "ad hoc" i
vari ed eventuali problemi di allineamento (questa nel caso generale
potrebbe non essere completamente banale).
Un'altra cosa da valutare potrebbe essere a seconda di come sono fatte
le stringhe di non fare i confronti in ordine crescente di byte ma di
usare una qualche mappa per valutare gli indici in altro ordine (a
seconda del tipo specifico di stringhe che si confrontano questo
potrebbe avere un caso medio minore).
-- 
-riko


Infatti anche conoscere il contesto delle stringhe potrebbe aiutare,
saltando nel confronto intere parti. Mi viene in mente il caso dei
confronti tra due sequenze di dna, dove non è necessario analizzare
tutti i "caratteri" (e certamente questo è un tipo di applicazione
dove gli algoritmi di confronto e ricerca sulle stringhe sono più
evoluti ed ottimizzati).

 potrebbe avere un caso medio minore).
Non posso fare ipotesi sulle stringhe a limite forse fare un confronto 
random? Magari utilizzare una mappa casuale?
Perdonate la mia ignoranza di algoritmi randomizzati... questo dovrebbe 
riportare caso peggiore e migliore al caso medio? cioè stringa di 
lunghezza N, N/2 confronti?

 little endian non si può (almeno credo).
Come no, confronti 32bit alla volta fino a che sono diversi, punto in
cui vedi la differenza sui quei quattro byte. no?


Parlava di CUDA, pensavo volesse implementare l'algoritmo su una
scheda grafica. Per questo stavo pensando a qualcosa di massicciamente
parallelo.
Pleg

 cui vedi la differenza sui quei quattro byte. no?
cavolo hai ragione... non avevo pensato al secondo passo!
Solo che memcmp continua ad essere piů efficiente

 Pleg
Perň pensavo di parallelizzare a livello dell'algoritmo di ordinamento.

 potrebbe avere un caso medio minore).
No, questo non lo capisco. Avresti ragione se l'unica informazione che 
vogliamo avere è se sono uguali o diverse. Ma per ordinarle, è 
necessario confrontare tutti i bytes fino al primo che differisce.
E.

 E.
Provo a rispondere o cosě vediamo anche se ho capito bene quello che 
diceva Enrico Franchi.
Supponi di dare i primi k confronti 4byte alla volta. Il k-esimo č 
quello che ti torna diverso allora le due stringhe non sono uguali.
A questo punto rimane da stabilire quale sia la minore.
Poichč sai che i primi 4*(k-1)byte sono uguali, ti basta riprendere il 
confronto da questo punto per stabilire quale sia la minore.
Proprio una bella furbata!


Non è detto che l'"ordinamento" che ci interessa di due buffer sia
quello "alfabetico" in senso stretto.

 evoluti ed ottimizzati).
Esatto. 
-- 
-riko

 Solo che memcmp continua ad essere più efficiente
Non mi stupisce. Dopotutto suppongo che la versione che trovi oggi nelle
libc sia scritta cosi' dopo ottimizzazioni progressive e continue.
O hai informazioni semantiche aggiuntive che ti permettono di sveltire
il confronto (le stringhe se differiscono differiscono da meta' stringa
in poi) oppure te la chiappi cosi'.
-- 
-riko

 necessario confrontare tutti i bytes fino al primo che differisce.
Infatti confesso che in qualche momento del discorso mi sono convinto
che volesse confrontarle per uguaglianza, non ordinarle. :P
-- 
-riko

 lunghezza N, N/2 confronti?
-- 
-riko

 lunghezza N, N/2 confronti?
Uhm, aspetta. Per randomizzarti tutti gli indici IMHO spendi troppo
tempo. Oltretutto io pensavo al confronto booleano, non al caso medio.
Pensavo a qualche singolo salto a qualche indice che se ritorna falso
sai che e' falso, altrimenti parti con l'algoritmo standard.
Sostanzialmente a te da fastidio quando un confronto "fallisce tardi",
tutto qui.
Ma non e' che le cose dette cosi' siano sempre una buona idea. Prima di
azzardare un algoritmo randomizzato, e' bene farci sopra un poco di
studio per capire se veramente abbassi il caso medio. 
-- 
-riko

 quello "alfabetico" in senso stretto.
Sě, ok, in tal caso potrebbe essere utile quello che dice Enrico. Ma 
forse allora memorizzare una hash del buffer sarebbe ancora meglio... ma 
difficile fare ragionamenti del genere senza sapere esattamente il 
contesto del problema.
E.