Rechenkarte: Rechenwert vor der Zeit

Question

Ich habe eine computing map (mit soft values), die ich verwende, um die Ergebnisse einer teuren Berechnung zwischenzuspeichern.

Jetzt habe ich eine Situation, in der ich weiß, dass ein bestimmter Schlüssel wahrscheinlich innerhalb der nächsten Sekunden nachgeschlagen wird. Dieser Schlüssel ist auch teurer zu berechnen als die meisten.

Ich möchte den Wert im Voraus in einem Thread mit minimaler Priorität berechnen, so dass der Wert, wenn er schließlich angefordert wird, bereits zwischengespeichert wird, wodurch die Antwortzeit verbessert wird.

Was für eine gute Möglichkeit ist, dies so zu tun:

1. Ich habe die Kontrolle über das Gewinde (insbesondere seine Priorität), in dem die Berechnung durchgeführt wird.
2. Doppelarbeit wird vermieden, d. H. Die Berechnung wird nur einmal durchgeführt. Wenn die Berechnungsaufgabe bereits ausgeführt wird, wartet der aufrufende Thread auf diese Aufgabe, anstatt den Wert erneut zu berechnen (FutureTask implementiert dies. Bei Guavas Computing Maps ist dies der Fall, wenn Sie nur get aufrufen, aber nicht, wenn Sie ihn mit Aufrufen von put mischen.)
3. Die Methode "Berechnungswert im Voraus" ist asynchron und idempotent. Wenn eine Berechnung bereits ausgeführt wird, sollte sie sofort zurückkehren, ohne darauf zu warten, dass diese Berechnung beendet wird.
4. Vermeiden Sie die Prioritätsinversion, z. Wenn ein Thread mit hoher Priorität den Wert anfordert, während ein Thread mit mittlerer Priorität einen nicht verwandten Vorgang ausführt, der Task für die Berechnung jedoch für einen Thread mit niedriger Priorität in die Warteschlange gestellt wird, darf der Thread mit hoher Priorität nicht ausgehungert werden. Vielleicht könnte dies erreicht werden, indem vorübergehend die Priorität der Computer-Threads erhöht wird und/oder die Berechnung auf dem aufrufenden Thread ausgeführt wird.

Wie könnte dies zwischen allen beteiligten Threads koordiniert werden?

---

Zusatzinfo
Die Berechnungen in meiner Anwendung sind Bildfiltervorgänge, das heißt, sie sind alle CPU-gebunden. Diese Operationen umfassen affine Transformationen (im Bereich von 50 μs bis 1 ms) und Faltungen (bis zu 10 ms). Natürlich hängt die Wirksamkeit unterschiedlicher Thread-Prioritäten von der Fähigkeit des OS ab, die größeren Aufgaben zu verhindern.

Answer 1

Sie können eine "einmalige" Ausführung der Hintergrundberechnung veranlassen, indem Sie ein Future mit der ComputedMap verwenden. Die Zukunft stellt die Aufgabe dar, die den Wert berechnet. Die Zukunft wird von der ComputedMap erstellt und gleichzeitig an eine ExecutorService zur Hintergrundausführung übergeben. Der Executor kann mit Ihrer eigenen ThreadFactory-Implementierung konfiguriert werden, die Threads mit niedriger Priorität erstellt, z.

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

Wenn der Wert benötigt wird, Ihr hoher Priorität Thread holt dann die Zukunft aus der Karte, und ruft die Methode get() das Ergebnis abzurufen, zu warten, ggf. berechnet werden. Um zu vermeiden, priority inversion Sie einige zusätzliche Code, um die Aufgabe hinzuzufügen:

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); 
    } 
} 

Diese kümmert sich um die Priorität der Aufgabe, die Priorität des Threads zu heben Aufruf get(), wenn die Aufgabe nicht abgeschlossen ist, und gibt die Priorität der Original, wenn die Aufgabe normal oder anderweitig abgeschlossen ist. (Um es kurz zu halten, überprüft der Code nicht, ob die Priorität tatsächlich größer ist, aber das ist einfach hinzuzufügen.)

Wenn die Task mit hoher Priorität get() aufruft, kann die Zukunft noch nicht mit der Ausführung begonnen haben. Sie könnten versucht sein, dies zu vermeiden, indem Sie eine große Obergrenze für die Anzahl der vom Executor-Dienst verwendeten Threads festlegen, aber dies ist möglicherweise eine schlechte Idee, da jeder Thread mit hoher Priorität ausgeführt werden könnte und so viel CPU verbraucht wie zuvor Das Betriebssystem schaltet es aus. Der Pool sollte wahrscheinlich die gleiche Größe wie die Anzahl der Hardware-Threads haben, z. Größe der Pool zu Runtime.availableProcessors(). Wenn die Task nicht gestartet wurde, anstatt auf die Ausführung durch den Executor zu warten (was eine Form der Prioritätsumkehr ist, da Ihr Thread mit hoher Priorität darauf wartet, dass die Threads mit niedriger Priorität abgeschlossen werden), können Sie ihn abbrechen Der aktuelle Executor wird erneut an einen Executor übergeben, der nur Threads mit hoher Priorität ausführt.

Answer 2

Eine gängige Methode zur Koordinierung dieser Art von Situation ist eine Karte, deren Werte FutureTask-Objekte sind. Wenn ich also einen Code, den ich von einem meiner Webserver geschrieben habe, als Beispiel nehme, ist die wesentliche Idee, dass wir für einen gegebenen Parameter sehen, ob es bereits eine FutureTask gibt (was bedeutet, dass die Berechnung mit diesem Parameter bereits geplant wurde), und Wenn ja, warten wir darauf. In diesem Beispiel haben wir sonst den Nachschlag planen, aber das an anderer Stelle mit einem separaten Aufruf getan werden könnte, wenn dies erwünscht ist:

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 Bezug auf den Thread-Prioritäten: Ich frage mich, ob dies erreichen, was Sie denken, es wird? Ich verstehe nicht ganz, wie Sie die Priorität der Suche über den wartenden Thread hinaus erhöhen: Wenn der Thread wartet, dann wartet er, unabhängig von den relativen Prioritäten anderer Threads ... (Vielleicht möchten Sie sich einige ansehen Artikel, die ich auf thread priorities und thread scheduling geschrieben habe, aber um eine lange Geschichte kurz zu machen, bin ich mir nicht sicher, dass die Änderung der Priorität wird Sie unbedingt kaufen, was Sie erwarten.)

Answer 3

Ich vermute, dass Sie auf dem Weg nach unten sind falscher Pfad durch Fokussierung auf Thread-Prioritäten.Normalerweise sind die Daten, die ein Cache enthält, aufgrund von I/O-Daten (out-of-memory data) vs. CPU bound (logic computation) teuer zu berechnen. Wenn Sie die zukünftige Aktion eines Benutzers voraussagen, z. B. wenn Sie ungelesene E-Mails ansehen, weist dies darauf hin, dass Ihre Arbeit wahrscheinlich E/A-gebunden ist. Dies bedeutet, dass, solange kein Thread-Verhungern auftritt (was Scheduler verbieten), das Spielen von Spielen mit Thread-Priorität nicht viel von einer Leistungsverbesserung bieten wird.

Wenn die Kosten ein E/A-Anruf sind, dann wird der Hintergrundthread blockiert, der auf das Eintreffen der Daten wartet, und die Verarbeitung dieser Daten sollte ziemlich billig sein (z. B. Deserialisierung). Da die Änderung der Threadpriorität keine große Beschleunigung bedeutet, sollte die asynchrone Ausführung der Arbeit im Hintergrundthreadpool ausreichend sein. Wenn die Cache-Miss-Strafe zu hoch ist, hilft die Verwendung mehrerer Cache-Speicherschichten, die vom Benutzer wahrgenommene Latenz weiter zu verringern.

Answer 4

Als Alternative zu Thread-Prioritäten können Sie eine Task mit niedriger Priorität nur ausführen, wenn keine Tasks mit hoher Priorität ausgeführt werden. Hier ist eine einfache Art und Weise zu tun, dass:

AtomicInteger highPriorityCount = new AtomicInteger(); 

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

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

In Ihrem Anwendungsfall, sowohl Impl() Methoden erhalten würde() aufrufen, auf der Computerkarte, highPriorityImpl() im selben Thread und lowPriorityImpl() in einem anderen Thread .

Sie könnten eine komplexere Version schreiben, die Aufgaben mit niedriger Priorität auflöst, bis die Aufgaben mit hoher Priorität abgeschlossen sind und die Anzahl gleichzeitiger Aufgaben mit niedriger Priorität begrenzt.