Stai usando un browser non aggiornato. Potresti non visualizzare correttamente questo o altri siti web. Dovreste aggiornare o usare un browser alternativo.
Salve gente sto scrivendo un codice in c++ usando la libreria thread, sperando magari che diventasse più prestante.
Ma così non è stato (neanche usando un solo thread in più), pertanto mi chiedo che accortezze si prendono affinché sia effettivamente più veloce o cosa potrebbe rendere l'uso di un singolo thread (oltre quello del programma stesso) meno prestante del programma stesso senza l'uso della libreria thread.
Ad esempio, faccio solo un'ipotesi, ho notato che la funzione eseguita dei thread nel mio programma richiedere un indirizzo di memoria con malloc. Tuttavia non so se la libreria standard sia pronta per la visita di più thread contemporaneamente.
Voi solitamente che accortezze prendete?
Dovresti condividere il codice, senza non si può dire cosa va ottimizzato, magari è l'algoritmo stesso il problema. Non sappiamo nemmeno che algoritmo è, cosa fa quel codice. ?
Salve gente sto scrivendo un codice in c++ usando la libreria thread, sperando magari che diventasse più prestante.
Ma così non è stato (neanche usando un solo thread in più), pertanto mi chiedo che accortezze si prendono affinché sia effettivamente più veloce o cosa potrebbe rendere l'uso di un singolo thread (oltre quello del programma stesso) meno prestante del programma stesso senza l'uso della libreria thread.
Mi sa che non hai parallelizzato per bene l'algoritmo. Non è che usando thread multipli si ottengano magicamente risultati migliori. Se ogni thread dipende dal precedente, l'esecuzione diventa serializzata in ogni caso.
Ad esempio, faccio solo un'ipotesi, ho notato che la funzione eseguita dei thread nel mio programma richiedere un indirizzo di memoria con malloc. Tuttavia non so se la libreria standard sia pronta per la visita di più thread contemporaneamente.
Dovresti condividere il codice, senza non si può dire cosa va ottimizzato, magari è l'algoritmo stesso il problema. Non sappiamo nemmeno che algoritmo è, cosa fa quel codice. ?
Per capire il codice facilmente ritengo sia giusto dire prima cosa faccia.
Abbiamo 3 strutture dati che comunicano tra di loro:
è una lista doppiamente concatenata, ogni nodo ha una chiave che è un type_freq.
Le operazioni su di essa sono:
incremento (aumenta di uno la chiave nel nodo)
allocare ed inserire un nodo con chiave 1.
eliminare intera lista (solo al termine del programma)
è un albero binario, ogni nodo contiene solo gli indirizzi dei nodi figli nel tipo void*. La profondità massima è prestabilita e le foglie a tali prodondità sono dei simple_node (quindi con l'operatore di casting si accede facilmente a tali nodi)
Le operazioni su di esso sono:
costruire nuovi nodi
leggere i nodi presenti
eliminare intero albero (solo al termine del programma)
è una lista doppiamente concatenata, ogni nodo rappresenta quello che ho chiamato "nodo di controllo" quello che fa è muoversi nell'albero binario ed eventualmente costruire nuovi selection_node. I suoi campi più importanti sono location (il nodo corrente), deep (la profondità), rule (che operazione deve eseguire).
le operazioni su di essa sono:
costruire nuovi nodi
leggere le chiavi dei nodi e modificarle
eliminare i nodi.
rule può essere di 3 tipi: SEEKER, BUILDER, EXPRESS
Detto ciò vi scrivo cosa fa l'algoritmo:
Codice:
inizializzo la radice dell'albero binario
inizializzo ctrl_list con un singolo nodo con location la radice, deep = 0 e rule: BUILDER
do
{
type_path p = estrazione del valore da un file txt
ciclo sui nodi di ctrl_list
{
assegno p al campo path del nodo di controllo
eseguo la funzione jump
}
pulisco i nodi di controllo che hanno terminato, quindi li elimino dalla lista ed eseguo free
se serve genero un nuovo nodo di controllo
}while(controllo che ci siano altri valori type_path nel file txt)
Con il multithreading pensavo di far eseguire l'operazione di jump (in seguito mostrata in dettaglio) da dei thread con le seguenti modifiche
Codice:
inizializzo la radice dell'albero binario
inizializzo ctrl_list con un singolo nodo con location la radice, deep = 0 e rule: BUILDER
inizializzo un vettore di thread (la grandezza la imposto io con una macro) e un contatore = 0
do
{
type_path p = estrazione del valore da un file txt
ciclo sui nodi di ctrl_list
{
assegno p al campo path del nodo di controllo
///codice C++
se ( vec_thread[counter].joinable()) vec_thread[counter].join(); //attendo che il thread si renda disponibile
vec_thread[counter] = std::thread(jump, nodo di controllo->jump); //quindi eseguo il thread
counter++;
se (counter == NTHREAD) counter = 0;
///termine codice C++
}
attendo che tutti i thread abbiano finito (ciclo for su vec_thread)
pulisco i nodi di controllo che hanno terminato, quindi li elimino dalla lista ed eseguo free
se serve genero un nuovo nodo di controllo
}while(controllo che ci siano altri valori type_path nel file txt)
La funzione jump è la funzione più gettonata, il suo codice è di 100 righe circa e fa quanto segue:
legge il campo rule del nodo type_jumper capendo così cosa deve fare.
La premessa (forse scontata) è che path è un percorso nell'albero:
se ad esempio 011 è il campo path allora la funzione jump deve percorrere il percorso 1-1-0 ossia dal nodo corrente può andare al figlio destro, poi di nuovo al figlio destro e infine al figlio sinistro (1 è destra 0 è sinistra)
Quindi
Se il nodo ha regola SEEKER allora deve verificare semplicemente che il percorso path sia presente nell'albero, se non trova un figlio (lo capisce perché l'indirizzo del figlio è nullptr) allora diventa automaticamente BUILDER, inizializza i campi linker, deep_linker e direction utili per l'ultima fase (EXPRESS)
Se SEEKER giunge alla foglia allora incrementa il simple_node presente quindi termina la funzione
Se il nodo ha regola BUILDER allora deve costruire nuovi nodi dell'albero secondo le indicazioni del campo path
Se BUILDER giunge alla foglia allora alloca un simple_node (uso malloc) e diventa EXPRESS, termina la funzione
Se il nodo ha regola EXPRESS deve scendere l'albero secondo le indicazioni del campo direction (che gli dice tendenzialmente se stare a destra o a sinistra) compiendo LBITS salti (una macro che stabilisce quanti bit ha un type_path)
Dopo quindi aver fatto saltare (nome simpatico) i nodi di controllo sull'albero binario, procedo con la pulizia dei nodi di controllo di troppo.
I nodi di controllo che saranno SEEKER e giunti in foglia saranno normalmente espulsi dalla lista dei controlli
I nodi di controllo che saranno EXPRESS possono essere di 3 tipi:
1- è il primo nodo di controllo generato (nato come BUILDER poi divenuto EXPRESS) quindi viene rimosso prontamente il nodo prima che ricominci il ciclo do while
2- è un nodo EXPRESS con deep_linker non giunto ancora alla foglia
3- è un nodo EXPRESS con deep_linker giunto alla foglia, quindi lega i simple_node presenti in linker e in location, rimuove infine il nodo di controllo dalla lista dei controlli
Interazioni tra i thread
viene generato al più un nodo di controllo nuovo ad ogni ciclo (quello del do_while)
ogni type_path ha la medesima lunghezza quindi i nodi di controllo scendono l'albero a salti uguali
l'unica coincidenza c'è quando un builder diventa express e si attende che l'express giunga alla foglia, nel frattempo dei seeker possono passare per il simple_node nuovo generato. Essi si limiteranno però solo a incrementare la chiave.
Costi computazionali:
Non dovrebbe superare il costo temporale O(nlog(n)) con n il numero di foglie generate alla fine dei cicli così anche la memoria usata.
Il codice funziona perfettamente senza usare multithreading e anche abbastanza velocemente. La funzione jump, secondo la profilatura delle prestazioni, è quella che viene più chiamata (praticamente c'è solo lei che lavora...)
Questa è la descrizione generale, dove potrebbe essere il problema?
Non ho letto completamente (scusa, mi sono appena svegliato, non vivo in Italia) ma uno dei problemi che saltano subito alla vista è l’uso del Join, che rovina tutti i benefici dei working thread. Il Join andrebbe usato solo alla fine o quando si voglia cancellare l’operazione, un algoritmo che usi il Join per aspettare che un thread finisca non ottimizza nulla.
Ottimizzare un algoritmo non è cosa facile, e un working thread aiuta solo in certe circostanze. La prima cosa da fare è vedere DOVE il tempo viene passato principalmente, ossia è inutile ottimizzare funzioni che occupano solo una piccola percentuale del tempo di esecuzione. Poi occorre analizzare i punti “morti” passati per esempio ad aspettare che il SO risponda (tipico per esempio nelle operazioni di lettura/scrittura disco). Infine, se veramente i working thread possano essere una soluzione, è sfruttare i multipli core della cpu (se, grosso SE, i thread possano girare in parallelo)
Ma queste sono solo indicazioni di massima.
Non è proprio chiarissimo tutto l'andazzo, ma leggo una cosa molto brutta
Codice:
type_path p = estrazione del valore da un file txt
ciclo sui nodi di ctrl_list
{
assegno p al campo path del nodo di controllo
...
Mi pare di capire che ci sia un solo p per ogni ciclo. Cioè i nodi di controllo seguono tutti lo stesso path? Se è così, siamo di fronte ad un orribile caso scarsissima parallelizzabilità. Se è come penso, quei nodi di controllo si pestano i piedi a vicenda in continuazione, causando una marea di accessi alle medesime istanze delle varie strutture dati. Questi inevitabilmente vengono serializzati.
Non è proprio chiarissimo tutto l'andazzo, ma leggo una cosa molto brutta
Codice:
type_path p = estrazione del valore da un file txt
ciclo sui nodi di ctrl_list
{
assegno p al campo path del nodo di controllo
...
Mi pare di capire che ci sia un solo p per ogni ciclo. Cioè i nodi di controllo seguono tutti lo stesso path? Se è così, siamo di fronte ad un orribile caso scarsissima parallelizzabilità. Se è come penso, quei nodi di controllo si pestano i piedi a vicenda in continuazione, causando una marea di accessi alle medesime istanze delle varie strutture dati. Questi inevitabilmente vengono serializzati.
sì, eseguono lo stesso percorso nel medesimo ciclo, tuttavia, come scritto alla fine della spiegazione, vengono attivati a livelli diversi dell'albero binario
quindi faccio una simulazione così si comprende meglio:
attivo il primo nodo di controllo alla radice dell'albero binario (lo chiamo A)
sposto A (assegno il percorso ed eseguo jump)
il nodo di controllo va eliminato? risposta no (per esempio)
va generato un nuovo nodo di controllo? risposta sì (per esempio)
metto in coda alla lista dei nodi di controllo il nuovo nodo di controllo (lo chiamo B) che parte dalla radice dell'albero binario
ricomincio il ciclo, quindi sposto A e sposto B //idea: il loro movimento è indipendente, quindi può essere parallelizzato
l nodo di controllo A va eliminato? risposta no (per esempio) //idea: la fase di eliminazione è facilmente ottimizzabile
Procedo così generando sempre nuovi nodi di controllo che partono dalla radice e fanno salti di lunghezza uguale partendo da quello più in fondo, quindi non si incontreranno mai (visto che l'albero è un grafo aciclico con una sola fonte)
Con una lieve modifica del codice (fatta ieri), si può evitare qualsiasi altro incontro (prima era solo tra due nodi di controllo che si limitano a leggere i nodi dell'albero binario, ossia EXPRESS e SEEKER che si muovono insieme nel medesimo nodo o SEEKER che legge il nodo dove era in attesa BUILDER).
Mettiamo che A sia SEEKER (quindi verifica che il percorso sia esistente) e che diventi BUILDER poiché durante il suo jump non ha trovato il percorso già costruito. Diciamo che a un certo punto path gli diceva di andare a destra ma il nodo corrente (chiamiamolo N) non ha un figlio destro quindi lui costruisce il nodo destro e scende in quello come BUILDER e quindi costruirà piano piano il nuovo percorso.
Si genera il nodo di controllo EXPRESS riferito al figlio sinistro del nodo N, come unico compito ha quello di scendere gradualmente l'albero mantenendosi a destra ( nota: nella lista dei nodi di controllo questo è messo subito dopo A ).
Garanzie che non si generino eccezioni: il figlio sinistro esiste poiché N esiste e la sua esistenza garantisce che lì ci sia passato un BUILDER che dunque ha costruito almeno un nodo figlio, se il destro non c'è allora per forza c'è il sinistro. L'esistenza del sinistro garantisce che esista almeno un percorso che porta a una foglia (percorso generato dal suddetto BUILDER)
Quindi con tale modifica nemmeno in lettura vi è possibilità che i nodi controllo in movimento si scontrino.
Non ho letto completamente (scusa, mi sono appena svegliato, non vivo in Italia) ma uno dei problemi che saltano subito alla vista è l’uso del Join, che rovina tutti i benefici dei working thread. Il Join andrebbe usato solo alla fine o quando si voglia cancellare l’operazione, un algoritmo che usi il Join per aspettare che un thread finisca non ottimizza nulla.
Ottimizzare un algoritmo non è cosa facile, e un working thread aiuta solo in certe circostanze. La prima cosa da fare è vedere DOVE il tempo viene passato principalmente, ossia è inutile ottimizzare funzioni che occupano solo una piccola percentuale del tempo di esecuzione. Poi occorre analizzare i punti “morti” passati per esempio ad aspettare che il SO risponda (tipico per esempio nelle operazioni di lettura/scrittura disco). Infine, se veramente i working thread possano essere una soluzione, è sfruttare i multipli core della cpu (se, grosso SE, i thread possano girare in parallelo)
Ma queste sono solo indicazioni di massima.
Ho usato il profiler delle prestazioni di Visual Studio, questo mi dice che il numero di chiamate più alto lo ha la funzione jump (anche un milione di chiamate) con tempo esclusivo del 45% (tempo escludivo trascorso medio è 0,00 ms)
Non ho un profiler con il multithreading per il semplice fatto che va così lento che probabilmente impiegherà una mezzora buona.
La spiegazione, pensandoci adesso, potrebbe essere la seguente:
1) la funzione jump non pesa molto quindi in poco tempo un thread termina il suo compito
2) io uso pochi thread (non ho superato 7 thread)
3) il thread quindi esegue la funzione, termina quasi subito, viene disattivato con join, quindi poi riattivato con la nuova funzione, questo con una frequenza decisamente alta
ok, quindi mi sorge una domanda. Io ho usato join perché pensavo che era l'unico modo per evitare di incasinare i thread. mi spiego facendo un paragone.... lo usavo come se fosse un semaforo, visto che ho a disposizione N thread, se sono tutti occupati allora fermo il programma in attesa che se ne liberi uno.
Quindi, vediamo se sto deducendo bene, join non ha la stessa funzionalità, mi basterebbe quindi scrivere solo:
vec_thread[counter] = std::thread(jump, nodo di controllo->jump);
senza la condizione if di prima insomma.
E ciò creerebbe una sorta di coda di istruzioni inviate ai thread che ho stanziato nell'array.
Sto sparando, senza join non capisco come potrei fare.
La seconda ipotesi che mi viene in mente è usare detach, ma mi sembra rischioso perché da quello che ho capito dovrebbe tipo scollegare il thread dal programma principale che, deduco, ne perda le tracce (sa solo che sta lavorando ma non sa a che punto è con il lavoro)
