CountedCompleter Klasse

Definition

[Android.Runtime.Register("java/util/concurrent/CountedCompleter", ApiSince=24, DoNotGenerateAcw=true)]
[Java.Interop.JavaTypeParameters(new System.String[] { "T" })]
public abstract class CountedCompleter : Java.Util.Concurrent.ForkJoinTask

[<Android.Runtime.Register("java/util/concurrent/CountedCompleter", ApiSince=24, DoNotGenerateAcw=true)>]
[<Java.Interop.JavaTypeParameters(new System.String[] { "T" })>]
type CountedCompleter = class
    inherit ForkJoinTask

Vererbung

Object

Object

ForkJoinTask

CountedCompleter

Attribute

RegisterAttribute JavaTypeParametersAttribute

Hinweise

A ForkJoinTask with a completion action perform when triggered and there are no remaining pending actions. CountedCompleter sind in der Regel robuster in Anwesenheit von Teilvorgängen und Blockierungen als andere Formen von ForkJoinTasks, aber weniger intuitiv zu programmieren. Die Verwendung von CountedCompleter ähnelt denen anderer abgeschlossener Komponenten (zjava.nio.channels.CompletionHandler. B. ) mit der Ausnahme, dass mehrere <em-ausstehende></em-Fertigstellungen> erforderlich sein können, um die Abschlussaktion #onCompletion(CountedCompleter)auszulösen , nicht nur eine. Sofern nicht anders initialisiert, beginnt die #getPendingCount ausstehende Anzahl bei Null, kann jedoch (atomisch) mithilfe von Methoden #setPendingCount, #addToPendingCountund #compareAndSetPendingCount. Wenn die Anzahl der ausstehenden Aktionen nicht null ist, wird sie beim Aufruf von #tryComplete"Ausstehend" dekrementiert. Andernfalls wird die Abschlussaktion ausgeführt, und wenn dieser Abschluss selbst über einen vollständigen Wert verfügt, wird der Prozess mit dem Vollständigen fortgesetzt. Wie bei verwandten Synchronisierungskomponenten wie Phaser z. B. und Semaphore, wirken sich diese Methoden nur auf interne Zählungen aus. Sie richten keine weiteren internen Buchführungen ein. Insbesondere werden die Identitäten ausstehender Aufgaben nicht verwaltet. Wie unten dargestellt, können Sie Unterklassen erstellen, die einige oder alle ausstehenden Aufgaben oder deren Ergebnisse bei Bedarf aufzeichnen. Wie unten dargestellt, werden auch Hilfsmethoden bereitgestellt, die die Anpassung der Abschluss-Traversale unterstützen. Da CountedCompleters jedoch nur grundlegende Synchronisierungsmechanismen bereitstellt, kann es hilfreich sein, weitere abstrakte Unterklassen zu erstellen, die Verknüpfungen, Felder und zusätzliche Unterstützungsmethoden beibehalten, die für eine Reihe verwandter Verwendungen geeignet sind.

Eine konkrete CountedCompleter-Klasse muss die Methode #computedefinieren, die in den meisten Fällen (wie unten dargestellt) vor dem Zurückgeben einmal aufgerufen werden tryComplete() soll. Die Klasse kann optional auch die Methode #onCompletion(CountedCompleter) außer Kraft setzen, um eine Aktion nach normalem Abschluss auszuführen, und die Methode #onExceptionalCompletion(Throwable, CountedCompleter) , um eine Aktion für jede Ausnahme auszuführen.

CountedCompleters tragen meist keine Ergebnisse, in diesem Fall werden sie normalerweise als CountedCompleter<Void>" deklariert" deklariert und werden immer als Ergebniswert zurückgegeben null . In anderen Fällen sollten Sie die Methode #getRawResult außer Kraft setzen, um ein Ergebnis aus join(), invoke()und verwandte Methoden bereitzustellen. Im Allgemeinen sollte diese Methode den Wert eines Felds (oder einer Funktion eines oder mehrerer Felder) des CountedCompleter-Objekts zurückgeben, das das Ergebnis nach Abschluss enthält. Die Methode #setRawResult spielt standardmäßig keine Rolle in CountedCompleters. Es ist möglich, aber selten anwendbar, diese Methode außer Kraft zu setzen, um andere Objekte oder Felder beizubehalten, die Ergebnisdaten enthalten.

Ein CountedCompleter, der nicht selbst über einen Vollständiger verfügt (d. h. eine, für die #getCompleter zurückgegeben nullwird) kann als reguläre ForkJoinTask mit dieser hinzugefügten Funktionalität verwendet werden. Jeder Completer, der wiederum über einen anderen Completer verfügt, dient jedoch nur als internes Hilfsprogramm für andere Berechnungen, sodass sein eigener Vorgangsstatus (wie in Methoden wie ) ForkJoinTask#isDonewillkürlich angegeben ist; dieser Status ändert sich nur bei expliziten Aufrufen von #complete, , ForkJoinTask#canceloder ForkJoinTask#completeExceptionally(Throwable) nach außergewöhnlichem Abschluss der Methode compute. Nach einem außergewöhnlichen Abschluss kann die Ausnahme an den Abschluss eines Vorgangs (und seinen Abschluss usw.) weitergeleitet werden, sofern vorhanden und nicht bereits abgeschlossen wurde. Ebenso hat das Abbrechen eines internen CountedCompleter nur lokale Auswirkungen auf diesen Completer, daher ist dies nicht häufig hilfreich.

<b>Beispielverwendungen.</b>

<b>Parallel rekursive Analyse.</b> CountedCompleter können in Bäumen angeordnet werden, die denen ähneln, die häufig mit RecursiveActions verwendet werden, obwohl die konstruktionen, die an der Einrichtung beteiligt sind, in der Regel variieren. Hier ist der Completer jeder Aufgabe das übergeordnete Element in der Berechnungsstruktur. Obwohl sie ein bisschen mehr Buchführung mit sich bringen, sind CountedCompleter möglicherweise bessere Auswahlmöglichkeiten bei der Anwendung eines möglicherweise zeitaufwendigen Vorgangs (der nicht weiter unterteilt werden kann) auf jedes Element eines Arrays oder einer Sammlung; insbesondere, wenn der Vorgang eine wesentlich andere Zeit benötigt, um einige Elemente abzuschließen, als bei anderen, entweder aufgrund der systeminternen Variation (z. B. E/A) oder hilfseffekten wie der Garbage Collection. Da CountedCompleters ihre eigenen Fortsetzungen bereitstellen, müssen andere Aufgaben nicht blockieren, bis sie ausgeführt werden.

Hier ist z. B. eine erste Version einer Hilfsmethode, die dividive rekursive Dekomposition verwendet, um Arbeit in einzelne Teile (Blattaufgaben) zu unterteilen. Selbst wenn die Arbeit in einzelne Aufrufe aufgeteilt wird, werden strukturbasierte Techniken in der Regel bevorzugt, um Blattaufgaben direkt zu verzweigen, da sie die Interthreadkommunikation reduzieren und den Lastenausgleich verbessern. Im rekursiven Fall löst das zweite Paar von Teilvorgängen, die den Abschluss des übergeordneten Elements beenden möchten , aus (da keine Ergebniskombination ausgeführt wird, wird die standardmäßige No-Op-Implementierung der Methode onCompletion nicht außer Kraft gesetzt). Die Hilfsmethode richtet die Stammaufgabe ein und ruft sie auf (hier, implizit unter Verwendung der ForkJoinPool#commonPool()). Es ist einfach und zuverlässig (aber nicht optimal), um die ausstehende Anzahl immer auf die Anzahl der untergeordneten Aufgaben festzulegen und unmittelbar vor der Rückgabe anzurufen tryComplete() .

{@code
            public static <E> void forEach(E[] array, Consumer<E> action) {
              class Task extends CountedCompleter<Void> {
                final int lo, hi;
                Task(Task parent, int lo, int hi) {
                  super(parent); this.lo = lo; this.hi = hi;
                }

                public void compute() {
                  if (hi - lo >= 2) {
                    int mid = (lo + hi) >>> 1;
                    // must set pending count before fork
                    setPendingCount(2);
                    new Task(this, mid, hi).fork(); // right child
                    new Task(this, lo, mid).fork(); // left child
                  }
                  else if (hi > lo)
                    action.accept(array[lo]);
                  tryComplete();
                }
              }
              new Task(null, 0, array.length).invoke();
            }}

Dieser Entwurf kann verbessert werden, indem festgestellt wird, dass der Vorgang im rekursiven Fall nichts zu tun hat, nachdem er seine rechte Aufgabe umgefließt hat, sodass die linke Aufgabe direkt aufgerufen werden kann, bevor sie zurückgegeben wird. (Dies ist eine Analogie zur Entfernung von Schwanz rekursion.) Wenn die letzte Aktion in einem Vorgang auch einen Teilvorgang (ein "Tail Call") abzweigen oder aufrufen soll, kann der Aufruf tryComplete() weg optimiert werden, um die ausstehende Anzahl "von einem" auszusehen.

{@code
                public void compute() {
                  if (hi - lo >= 2) {
                    int mid = (lo + hi) >>> 1;
                    setPendingCount(1); // looks off by one, but correct!
                    new Task(this, mid, hi).fork(); // right child
                    new Task(this, lo, mid).compute(); // direct invoke
                  } else {
                    if (hi > lo)
                      action.accept(array[lo]);
                    tryComplete();
                  }
                }}

Beachten Sie als weitere Optimierung, dass die linke Aufgabe nicht einmal vorhanden ist. Anstatt eine neue Aufgabe zu erstellen, können wir die ursprüngliche Aufgabe weiterhin verwenden und für jede Verzweigung eine ausstehende Anzahl hinzufügen. Da in dieser Struktur keine Aufgabe eine #onCompletion(CountedCompleter) Methode implementiert, tryComplete kann sie durch ersetzt #propagateCompletionwerden.

{@code
                public void compute() {
                  int n = hi - lo;
                  for (; n >= 2; n /= 2) {
                    addToPendingCount(1);
                    new Task(this, lo + n/2, lo + n).fork();
                  }
                  if (n > 0)
                    action.accept(array[lo]);
                  propagateCompletion();
                }}

Wenn ausstehende Zählungen vorkompiliert werden können, können sie im Konstruktor eingerichtet werden:

{@code
            public static <E> void forEach(E[] array, Consumer<E> action) {
              class Task extends CountedCompleter<Void> {
                final int lo, hi;
                Task(Task parent, int lo, int hi) {
                  super(parent, 31 - Integer.numberOfLeadingZeros(hi - lo));
                  this.lo = lo; this.hi = hi;
                }

                public void compute() {
                  for (int n = hi - lo; n >= 2; n /= 2)
                    new Task(this, lo + n/2, lo + n).fork();
                  action.accept(array[lo]);
                  propagateCompletion();
                }
              }
              if (array.length > 0)
                new Task(null, 0, array.length).invoke();
            }}

Zusätzliche Optimierungen solcher Klassen könnten dazu führen, dass Klassen für Blattschritte spezialisiert werden, indem man beispielsweise vier statt zwei pro Iteration unterteilt und einen adaptiven Schwellenwert verwendet, anstatt immer auf einzelne Elemente zu unterteilen.

<b>Suchen.</b> Eine Struktur von CountedCompleters kann in verschiedenen Teilen einer Datenstruktur nach einem Wert oder einer Eigenschaft suchen und ein Ergebnis melden, sobald eine java.util.concurrent.atomic.AtomicReference AtomicReference gefunden wird. Die anderen können das Ergebnis abfragen, um unnötige Arbeit zu vermeiden. (Sie könnten auch andere Vorgänge #cancel abbrechen, aber es ist in der Regel einfacher und effizienter, sie einfach zu bemerken, dass das Ergebnis festgelegt ist und wenn dies der Grund ist, die weitere Verarbeitung zu überspringen.) Das Wiedererfüllen mit einem Array mit vollständiger Partitionierung (in der Praxis werden Blattaufgaben fast immer mehr als ein Element verarbeiten):

{@code
            class Searcher<E> extends CountedCompleter<E> {
              final E[] array; final AtomicReference<E> result; final int lo, hi;
              Searcher(CountedCompleter<?> p, E[] array, AtomicReference<E> result, int lo, int hi) {
                super(p);
                this.array = array; this.result = result; this.lo = lo; this.hi = hi;
              }
              public E getRawResult() { return result.get(); }
              public void compute() { // similar to ForEach version 3
                int l = lo, h = hi;
                while (result.get() == null && h >= l) {
                  if (h - l >= 2) {
                    int mid = (l + h) >>> 1;
                    addToPendingCount(1);
                    new Searcher(this, array, result, mid, h).fork();
                    h = mid;
                  }
                  else {
                    E x = array[l];
                    if (matches(x) && result.compareAndSet(null, x))
                      quietlyCompleteRoot(); // root task is now joinable
                    break;
                  }
                }
                tryComplete(); // normally complete whether or not found
              }
              boolean matches(E e) { ... } // return true if found

              public static <E> E search(E[] array) {
                  return new Searcher<E>(null, array, new AtomicReference<E>(), 0, array.length).invoke();
              }
            }}

In diesem Beispiel und anderen, in denen Vorgänge keine anderen Auswirkungen haben, außer auf compareAndSet ein gemeinsames Ergebnis, kann der nachfolgende bedingungslose Aufruf tryComplete bedingt (if (result.get() == null) tryComplete();) werden, da keine weitere Buchführung erforderlich ist, um Fertigstellungen zu verwalten, sobald die Stammaufgabe abgeschlossen ist.

<b>Aufzeichnen von Teilvorgängen.</b> CountedCompleter-Vorgänge, die Ergebnisse mehrerer Teilvorgänge kombinieren, müssen in der Regel auf diese Ergebnisse in der Methode #onCompletion(CountedCompleter)zugreifen. Wie in der folgenden Klasse dargestellt (die eine vereinfachte Form der Zuordnung reduziert, bei der Zuordnungen und Reduzierungen alle arten Esind), ist eine Möglichkeit, dies bei der Aufteilung und Erzwingung von Designs zu tun, besteht darin, dass jeder Teilvorgang seine gleichgeordneten Datensätze aufzeichnen, sodass er in der Methode onCompletionaufgerufen werden kann. Diese Technik bezieht sich auf Verringerungen, bei denen die Reihenfolge der Kombination von links- und rechts-Ergebnissen keine Rolle spielt; geordnete Reduzierungen erfordern explizite Links-/Rechtsbezeichnungen. Varianten anderer Verschlankungen, die in den obigen Beispielen zu sehen sind, können ebenfalls angewendet werden.

{@code
            class MyMapper<E> { E apply(E v) {  ...  } }
            class MyReducer<E> { E apply(E x, E y) {  ...  } }
            class MapReducer<E> extends CountedCompleter<E> {
              final E[] array; final MyMapper<E> mapper;
              final MyReducer<E> reducer; final int lo, hi;
              MapReducer<E> sibling;
              E result;
              MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
                         MyReducer<E> reducer, int lo, int hi) {
                super(p);
                this.array = array; this.mapper = mapper;
                this.reducer = reducer; this.lo = lo; this.hi = hi;
              }
              public void compute() {
                if (hi - lo >= 2) {
                  int mid = (lo + hi) >>> 1;
                  MapReducer<E> left = new MapReducer(this, array, mapper, reducer, lo, mid);
                  MapReducer<E> right = new MapReducer(this, array, mapper, reducer, mid, hi);
                  left.sibling = right;
                  right.sibling = left;
                  setPendingCount(1); // only right is pending
                  right.fork();
                  left.compute();     // directly execute left
                }
                else {
                  if (hi > lo)
                      result = mapper.apply(array[lo]);
                  tryComplete();
                }
              }
              public void onCompletion(CountedCompleter<?> caller) {
                if (caller != this) {
                  MapReducer<E> child = (MapReducer<E>)caller;
                  MapReducer<E> sib = child.sibling;
                  if (sib == null || sib.result == null)
                    result = child.result;
                  else
                    result = reducer.apply(child.result, sib.result);
                }
              }
              public E getRawResult() { return result; }

              public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
                return new MapReducer<E>(null, array, mapper, reducer,
                                         0, array.length).invoke();
              }
            }}

Hier verwendet die Methode onCompletion eine Form, die vielen Vervollständigungsdesigns gemeinsam ist, die Ergebnisse kombinieren. Diese Rückrufmethode wird einmal pro Aufgabe ausgelöst, in einem der beiden unterschiedlichen Kontexte, in denen die ausstehende Anzahl abgeschlossen ist oder null wird: (1) durch einen Vorgang selbst, wenn die ausstehende Anzahl null ist, wenn die ausstehende Anzahl bei Aufruf von tryComplete, oder (2) durch einen der Teilvorgänge, wenn sie abgeschlossen sind, und die ausstehende Anzahl auf Null erhöht. Das caller Argument unterscheidet Fälle. Meistens ist, wenn der Aufrufer ist this, keine Aktion erforderlich. Andernfalls kann das Aufruferargument (in der Regel über eine Umwandlung) verwendet werden, um einen zu kombinierenden Wert (und/oder Verknüpfungen zu anderen Werten) zu liefern. Bei ordnungsgemäßer Verwendung ausstehender Zählungen treten die innerhalb befindlichen onCompletion Aktionen (einmal) nach Abschluss eines Vorgangs und der zugehörigen Teilvorgänge auf. Innerhalb dieser Methode ist keine zusätzliche Synchronisierung erforderlich, um die Threadsicherheit des Zugriffs auf Felder dieser Aufgabe oder anderer erledigter Aufgaben sicherzustellen.

<b>Abschlussquerungen.</b> Wenn die Verwendung onCompletion zum Verarbeiten von Vervollständigungen nicht angewendet oder unannelich ist, können Sie Methoden #firstComplete verwenden und #nextComplete benutzerdefinierte Traversale erstellen. Um beispielsweise einen MapReducer zu definieren, der nur rechtshändige Vorgänge in Form des dritten ForEach-Beispiels aufteilt, müssen die Vervollständigungen kooperativ entlang nicht abgelaufener Teilvorgangsverknüpfungen reduziert werden, was wie folgt erfolgen kann:

{@code
            class MapReducer<E> extends CountedCompleter<E> { // version 2
              final E[] array; final MyMapper<E> mapper;
              final MyReducer<E> reducer; final int lo, hi;
              MapReducer<E> forks, next; // record subtask forks in list
              E result;
              MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
                         MyReducer<E> reducer, int lo, int hi, MapReducer<E> next) {
                super(p);
                this.array = array; this.mapper = mapper;
                this.reducer = reducer; this.lo = lo; this.hi = hi;
                this.next = next;
              }
              public void compute() {
                int l = lo, h = hi;
                while (h - l >= 2) {
                  int mid = (l + h) >>> 1;
                  addToPendingCount(1);
                  (forks = new MapReducer(this, array, mapper, reducer, mid, h, forks)).fork();
                  h = mid;
                }
                if (h > l)
                  result = mapper.apply(array[l]);
                // process completions by reducing along and advancing subtask links
                for (CountedCompleter<?> c = firstComplete(); c != null; c = c.nextComplete()) {
                  for (MapReducer t = (MapReducer)c, s = t.forks; s != null; s = t.forks = s.next)
                    t.result = reducer.apply(t.result, s.result);
                }
              }
              public E getRawResult() { return result; }

              public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
                return new MapReducer<E>(null, array, mapper, reducer,
                                         0, array.length, null).invoke();
              }
            }}

<b>Trigger.</b> Einige CountedCompleter werden selbst nie verzweigt, sondern dienen stattdessen als Klempner in anderen Designs, einschließlich derjenigen, in denen der Abschluss einer oder mehrerer asynchroner Aufgaben eine andere asynchrone Aufgabe auslöst. Zum Beispiel:

{@code
            class HeaderBuilder extends CountedCompleter<...> { ... }
            class BodyBuilder extends CountedCompleter<...> { ... }
            class PacketSender extends CountedCompleter<...> {
              PacketSender(...) { super(null, 1); ... } // trigger on second completion
              public void compute() { } // never called
              public void onCompletion(CountedCompleter<?> caller) { sendPacket(); }
            }
            // sample use:
            PacketSender p = new PacketSender();
            new HeaderBuilder(p, ...).fork();
            new BodyBuilder(p, ...).fork();}

Hinzugefügt in 1.8.

Java-Dokumentation für java.util.concurrent.CountedCompleter.

Teile dieser Seite sind Änderungen auf der Grundlage von Arbeiten, die vom Android Open Source-Projekt erstellt und freigegeben werden und gemäß den in der Creative Commons 2.5 Attribution License beschriebenen Begriffen verwendet werden.

Konstruktoren

Eigenschaften

Methoden

Explizite Schnittstellenimplementierungen

Erweiterungsmethoden

Gilt für: