Dovrei usare il threading e la ricorsione insieme?

Question

Ho armeggiato con alberi BSP da un po 'di tempo e sto anche giocando con i thread. Quando si aggiunge un triangolo a un albero BSP, si presenta l'opportunità di creare un nuovo thread allo scopo di elaborare i dati in parallelo.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    insert(frontpiece, bspnode.front)
    insert(backpiece, bspnode.back)
  }
  ....
}

Le due operazioni di inserimento sopra potrebbero essere eseguite da due thread e poiché non modificano gli stessi dati, è possibile utilizzare una sincronizzazione economica.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    handle = beginthread(insert(backpiece, bspnode.front))
    insert(frontpiece, bspnode.back)
    if(handle)
    {
      waitforthread(handle)
    }
    else
    {
      insert(backpiece, bspnode.front)
    }
  }
  ....
}

Questo nuovo metodo tenta di creare un thread per completare l'operazione in parallelo, ma non dovrebbe fallire se non è possibile creare il thread (tornerà semplicemente all'algoritmo originale).

È una buona pratica di programmazione o sto usando i thread in modo errato? Non sono stato in grado di trovare alcuna letteratura su questa tecnica. Mi piace che tende a utilizzare la mia CPU al massimo (2 core) e teoricamente si ridimensionerebbe a qualsiasi numero di processori disponibili. Non mi piace che potrebbe essere orribilmente dispendioso per CPU e memoria.

Answer 1

I thread sono fantastici se una parte dell'elaborazione sta aspettando qualcosa di esterno (input dell'utente, I / O, qualche altra elaborazione) - il thread che sta aspettando può continuare ad aspettare, mentre un thread che non sta aspettando prosegue .

Tuttavia, per le attività ad alta intensità di elaborazione, più thread che processori creano effettivamente sovraccarico. Sembra che i tuoi thread stiano facendo tutto il "lavoro della CPU", quindi mi atterrei a un thread per core - test per trovare il numero ottimale, tuttavia.

Il sovraccarico maggiore creato deriva dal cambio di contesto (congelamento di un thread e caricamento del contesto di esecuzione di quello successivo), nonché da errori della cache quando i thread eseguono attività con memoria diversa (se il thread può utilizzare efficacemente la cache della CPU) .

Answer 2

la soluzione migliore sarebbe quella di creare un pool di thread, quindi utilizzarlo 'in modo trasparente' per aggiungere nodi.

ad esempio, crea 2 thread all'avvio del programma, invitali ad attendere un semaforo o un evento. Quando si hanno nodi da aggiungere, i dati vengono inseriti in una coda, quindi si attiva il semaforo. Questo riattiva uno dei thread che estrae i dati dalla coda ed esegue l'elaborazione. (assicurati che l'accesso alla coda sia sicuro per i thread - è meglio sincronizzare completamente con una sezione critica).

Le prestazioni complessive della tua app sono più lente poiché hai più sovraccarico, copiando i dati nella coda ed eseguendo i thread extra, ma se hai usato l'esecuzione su un singolo core ora funzionerai su 2. Funziona meglio se l'elaborazione con thread è costosa.

Answer 3

Certo, ad esempio, Quicksort può essere programmato in modalità multithread abbastanza facilmente e ottenere grandi guadagni in termini di prestazioni su sistemi multi-core e alcune piccole perdite in termini di prestazioni in non-multithread. Ricorda solo che stai aggiungendo due volte overhead: una volta per il salvataggio dello stack nella ricorsione e una volta nel thread, quindi se stai facendo un gran numero di ricorsioni, potrebbe sopraffare un sistema più velocemente di un approccio non multithread.