Computing map: valore di calcolo in anticipo

Question

Ho uno computing map (con soft values) che sto utilizzando per memorizzare i risultati di un calcolo costoso.

Ora ho una situazione in cui so che è probabile che una determinata chiave venga cercata nei prossimi secondi. Quella chiave è anche più costosa da calcolare rispetto alla maggior parte.

Vorrei calcolare preventivamente il valore, in un thread con priorità minima, in modo che quando il valore sia richiesto, esso verrà già memorizzato nella cache, migliorando il tempo di risposta.

cosa è un buon modo per fare questo in modo tale che:

1. ho controllo sopra il filo (in particolare la sua priorità) in cui viene eseguito il calcolo.
2. Il lavoro duplicato viene evitato, ovvero il calcolo viene eseguito una sola volta. Se l'attività di calcolo è già in esecuzione, il thread chiamante attende tale attività invece di calcolare nuovamente il valore (FutureTask implementa questa funzione. Con le mappe di calcolo di Guava ciò è vero se si chiama solo get ma non se lo si mescola con le chiamate a put.)
3. Il metodo "valore di calcolo in anticipo" è asincrono e idempotente. Se un calcolo è già in corso, dovrebbe tornare immediatamente senza attendere il termine del calcolo.
4. Evitare l'inversione di priorità, ad es. se un thread con priorità alta richiede il valore mentre un thread con priorità media sta facendo qualcosa di non correlato ma l'attività di calcolo è accodata su un thread con priorità bassa, il thread con priorità alta non deve essere affamato. Forse questo potrebbe essere ottenuto aumentando temporaneamente la priorità dei thread di calcolo e/o eseguendo il calcolo sul thread chiamante.

Come potrebbe essere coordinato tra tutti i thread coinvolti?

---

Ulteriori informazioni
I calcoli nella mia richiesta sono operazioni di filtraggio di immagini, il che significa che sono tutti CPU-bound. Queste operazioni includono trasformazioni affini (che vanno da 50μs a 1ms) e convoluzioni (fino a 10ms.) Naturalmente l'efficacia delle varie priorità del thread dipende dalla capacità del sistema operativo di anticipare i compiti più grandi.

Answer 1

È possibile disporre l'esecuzione "una sola volta" del calcolo dello sfondo utilizzando un futuro con ComputedMap. Il futuro rappresenta l'attività che calcola il valore. Il futuro viene creato da ComputedMap e, allo stesso tempo, passato a un ExecutorService per l'esecuzione in background. L'executor può essere configurato con la propria implementazione ThreadFactory che crea thread a bassa priorità, ad es.

class LowPriorityThreadFactory implements ThreadFactory 
{ 
    public Thread newThread(Runnable r) { 
    Tread t = new Thread(r); 
    t.setPriority(MIN_PRIORITY); 
    return t; 
    } 
} 

Quando è necessario il valore, il thread ad alta priorità poi recupera il futuro dalla mappa, e chiama il metodo get() per recuperare il risultato, in attesa che venga calcolato, se necessario. Per evitare priority inversion si aggiunge un po 'di codice aggiuntivo per il compito:

class HandlePriorityInversionTask extends FutureTask<ResultType> 
{ 
    Integer priority; // non null if set 
    Integer originalPriority; 
    Thread thread; 
    public ResultType get() { 
     if (!isDone()) 
     setPriority(Thread.currentThread().getPriority()); 
     return super.get(); 
    } 
    public void run() { 
     synchronized (this) { 
     thread = Thread.currentThread(); 
     originalPriority = thread.getPriority(); 
     if (priority!=null) setPriority(priority); 
     } 
     super.run(); 
    } 
    protected synchronized void done() { 
     if (originalPriority!=null) setPriority(originalPriority); 
     thread = null; 
    } 

    void synchronized setPriority(int priority) { 
     this.priority = Integer.valueOf(priority); 
     if (thread!=null) 
      thread.setPriority(priority); 
    } 
} 

Questo si prende cura di elevare la priorità del compito alla priorità del thread chiamante get() se l'attività non è stata completata, e restituisce la priorità al originale quando l'attività viene completata, normalmente o in altro modo. (Per essere breve, il codice non controlla se la priorità è effettivamente maggiore, ma è facile aggiungere.)

Quando il task ad alta priorità chiama get(), il futuro potrebbe non aver ancora iniziato l'esecuzione. Potresti essere tentato di evitarlo impostando un limite superiore elevato sul numero di thread utilizzati dal servizio executor, ma questa potrebbe essere una cattiva idea, dal momento che ogni thread potrebbe essere eseguito ad alta priorità, consumando più CPU possibile prima il sistema operativo lo spegne. Il pool dovrebbe probabilmente avere le stesse dimensioni del numero di thread hardware, ad es. ridimensiona la piscina a Runtime.availableProcessors(). Se l'attività non ha avviato l'esecuzione, piuttosto che attendere che l'executor lo pianifichi (che è una forma di inversione di priorità, poiché il thread ad alta priorità attende i thread a bassa priorità da completare), è possibile scegliere di annullarlo l'attuale esecutore e re-invio su un esecutore che esegue solo thread ad alta priorità.

Answer 2

Un modo comune per coordinare questo tipo di situazione è disporre di una mappa i cui valori sono oggetti FutureTask. Quindi, rubando come esempio un codice che ho scritto da un mio server web, l'idea essenziale è che per un dato parametro, vediamo se c'è già un FutureTask (nel senso che il calcolo con quel parametro è già stato programmato), e se così lo aspettiamo. In questo esempio, altrimenti programmare la ricerca, ma che potrebbe essere fatto altrove con una chiamata separata se era auspicabile:

private final ConcurrentMap<WordLookupJob, Future<CharSequence>> cache = ... 

    private Future<CharSequence> getOrScheduleLookup(final WordLookupJob word) { 
    Future<CharSequence> f = cache.get(word); 
    if (f == null) { 
     Callable<CharSequence> ex = new Callable<CharSequence>() { 
     public CharSequence call() throws Exception { 
      return doCalculation(word); 
     } 
     }; 
     Future<CharSequence> ft = executor.submit(ex); 
     f = cache.putIfAbsent(word, ft); 
     if (f != null) { 
     // somebody slipped in with the same word -- cancel the 
     // lookup we've just started and return the previous one 
     ft.cancel(true); 
     } else { 
     f = ft; 
     } 
    } 
    return f; 
    } 

In termini di priorità di thread: Mi chiedo se questo sarà realizzare ciò che si pensa che sarà? Non capisco perfettamente il tuo punto di vista sulla priorità della ricerca al di sopra del thread in attesa: se il thread è in attesa, allora è in attesa, a prescindere dalle priorità relative degli altri thread ... (potresti dare un'occhiata ad alcuni articoli che ho scritto su thread priorities e thread scheduling, ma per farla breve, non sono sicuro che la modifica della priorità ti compri necessariamente ciò che ti aspetti.)

Answer 3

Sospetto che tu stia andando verso il basso percorso sbagliato concentrandosi sulle priorità del thread.Di solito i dati contenuti in una cache sono costosi da calcolare a causa di I/O (dati esauriti della memoria) rispetto alla CPU (calcolo logico). Se stai cercando di indovinare l'azione futura di un utente, come guardare le e-mail non lette, allora mi indica che il tuo lavoro è probabilmente legato all'I/O. Ciò significa che finché non si verifica l'esaurimento del thread (quali programmatori non sono consentiti), la riproduzione di giochi con priorità thread non offrirà gran parte del miglioramento delle prestazioni.

Se il costo è una chiamata I/O, il thread in background viene bloccato in attesa dell'arrivo dei dati e l'elaborazione di tali dati deve essere abbastanza economica (ad esempio deserializzazione). Poiché la modifica della priorità del thread non offrirà molta accelerazione, l'esecuzione del lavoro in modo asincrono sul threadpool in background dovrebbe essere sufficiente. Se la penalità di mancanza della cache è troppo alta, l'uso di più livelli di memorizzazione nella cache tende a ridurre ulteriormente la latenza percepita dall'utente.

Answer 4

In alternativa alle priorità del thread, è possibile eseguire un'attività a bassa priorità solo se non sono in corso attività ad alta priorità. Ecco un modo semplice per farlo:

AtomicInteger highPriorityCount = new AtomicInteger(); 

void highPriorityTask() { 
    highPriorityCount.incrementAndGet(); 
    try { 
    highPriorityImpl(); 
    } finally { 
    highPriorityCount.decrementAndGet(); 
    } 
} 

void lowPriorityTask() { 
    if (highPriorityCount.get() == 0) { 
    lowPriorityImpl(); 
    } 
} 

Nel vostro caso d'uso, sia Impl() metodi sarebbe chiamare get() sulla mappa computing, highPriorityImpl() nello stesso thread e lowPriorityImpl() in un thread diverso .

È possibile scrivere una versione più sofisticata che rimuova le attività a bassa priorità fino al completamento delle attività ad alta priorità e limita il numero di attività simultanee a bassa priorità.