Ist ArrayList.size () - Methode zwischengespeichert?

Frage ich mich, ist das size() Methode, die Sie aufrufen können auf eine bestehende ArrayList<T> zwischengespeichert?
Oder ist es besser in performance-kritischen code, dass ich einfach speichern size() in einem lokalen int?

Ich würde erwarten, dass es in der Tat zwischengespeichert, wenn Sie nicht das hinzufügen/entfernen von Elementen zwischen den anrufen zu size().

Habe ich Recht?

update

Ich spreche nicht von inlining oder solche Dinge. Ich will nur wissen ob die Methode size() selbst speichert den Wert intern, oder dass es dynamisch berechnet jedes mal, wenn Sie aufgerufen.

Es ist ein schnelles rufen Sie für ArrayList, aber speichern Sie das Ergebnis in die lokale variable, wenn Sie es verwenden, wie ein test der Bedingung in jeder loop-iteration.
können Sie bitte klären Sie die Frage. Es scheint, dass einige Leute interpretieren dies als "does size() führen Sie eine Berechnung oder ist es trivial return ein Feld" vs. "werden mehrere Aufrufe size() ersetzt werden, mit einem einzigen Aufruf von size() mit den nachfolgenden Anrufungen ersetzt durch eine lokale variable, in die das Vorherige Ergebnis wurde gespeichert". Ich habe interpretiert, als die letzteren, während andere interpretiert haben als die ersteren. Bitte stellen Sie das klar.
Vielen Dank für die Klarstellung.

InformationsquelleAutor Peterdk | 2010-05-18

13

Ich glaube nicht, ich würde sagen, es ist "im Cache" als solches - aber es ist einfach gespeichert in einem Feld, so ist es schnell genug, um anzurufen Häufig.

Sun JDK Implementierung von size() ist nur:
```
public int size() {
    return size;
}
```
- aber in performance-kritischen code, ist, dass zahlen eine Menge für Funktionsaufruf-overhead, wenn der Wert der gleiche sein wird.
- aber der JIT ist smart genug, um inline-Anrufe, so dass Sie dann nicht die Funktionsaufruf-overhead.
- Ich Schätze, dass es theoretisch möglich ist, inline-Aufruf, sondern die VM eigentlich tut?
- die Sun JVM macht das. Es ist raffinierter, als Sie denken.
- da die Sun JVM hast, dies seit Version 1.2 (d.h. seit 1998), ich denke, wir können davon ausgehen, dass alle von Ihnen tun, außer vielleicht embedded lieben. Verweis: java.sun.com/developer/onlineTraining/Programming/JDCBook/...
- danke für den link. Das klärt die Dinge.
- Ich denke, Sie gehen davon aus, dass der Anruf nicht kommen, der bereits in einer inline-Methode. Das ist wahrscheinlich wahr, aber es gibt Grenzen, die kann dazu führen, die JVM zu wählen, nicht zu inline eine anderweitig förderfähige Methode. Wenn Sie Leistungsprobleme haben, speichern den Wert in eine lokale variable, wenn Sie wissen, dass es nicht zu ändern wäre eine offensichtliche erste Schritt.
- haben Sie einen Blick auf pastebin.com/b6FJw7AX - auf meinem JVM, die (ähem) zwischengespeicherte version läuft in etwa 2/3 der Zeit mit Java HotSpot(TM) Client VM (build 1.5.0_22-147, mixed mode, sharing) und über 1/2 der Zeit mit Java HotSpot(TM) 64-Bit Server VM (build 14.3-b01-101, mixed mode). Gibt es etwas, was ich bin fehlt?
- meine Vermutung ist, dass auch bei inlining, ein Feld access beinhaltet eine memory-lookup, beim speichern in eine lokale variable explizit dazu, dass ein CPU-register verwendet werden.
- Großartig, das ist genau das, was ich wissen musste.
- Borgwardt die verlinkten Sonne Dokument Staaten, unter anderem "...die addCount Methode sieht nicht sehr attraktiv für die inline-Detektor in der VM, weil die addCount Methode gibt einen Wert zurück". Also nicht anwendbar auf die size() Methode.
InformationsquelleAutor Jon Skeet
5

Ja.

Einen kurzen Blick auf den Java-Quellcode würde dir die Antwort sagen.
- Sinn wies darauf hin, wo im code das ist?
- In der src.zip - Datei in Ihrem JDK-Installationsverzeichnis.
- Sorry! Ich habe Annahmen gemacht - ich halten in der Regel Zugang zu den JDK-Quellen von innerhalb meiner IDE. Danke für die hand, Jesper.
- wo ist es gespeichert wird in eine lokale variable?
- hast du dir den Quellcode java.util.ArrayList? Es gibt eine private int size; auf Linie 98 (in Sun JDK 1.6.0_20).
- wir interpretieren die Frage anders. Ich wurde gefragt, Woher kommt es, sicherzustellen, dass es wird gespeichert und wieder in eine lokale variable in der caller, nicht in der Funktion selbst. Auch, dass nicht eine lokale variable; das ist eine member-variable. Aber, nun gut, Michael hat sich geklärt, die Optimierung.
- href="http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/util/ArrayList.java#ArrayList.size%28%29" >grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/...
InformationsquelleAutor Timothy
2

Dies ist die Umsetzung in OpenJDK version:
```
/**
 * Returns the number of elements in this list.
 *
 * @return the number of elements in this list
 */
public int size() {
    return size;
}
```
So, es ist so gut wie ein Methodenaufruf zu erhalten. Es ist nicht sehr wahrscheinlich, dass die HotSpot-caches den Wert dieser Methode zurückgegeben wird, also, wenn Sie wirklich , DASS besorgt sind, können Sie cache-it-yourself. Es sei denn, Ihr profiling hat gezeigt, dass dies ein Flaschenhals, obwohl (nicht sehr wahrscheinlich), sollte man einfach beschäftigen Sie sich mit der Lesbarkeit eher, als ob ein einfacher Aufruf der Methode liefert den Wert eines Feldes zwischengespeichert wird oder nicht.

InformationsquelleAutor polygenelubricants
2

Weiß ich nicht sicher beantworten, aber meine Vermutung wäre: Nein. Es gibt keine Möglichkeit für einen Java-compiler, kurz von besonderen Gehäuse ArrayList, zu wissen, dass die Funktionen, die Sie aufrufen, werden nicht mutiert und dass, als Ergebnis, der Aufruf von size() sollte den gleichen Wert zurückgeben. Deshalb finde ich es sehr unwahrscheinlich, dass ein Java-compiler Faktor wiederholte Aufrufe size() und speichern Sie Sie in einem temporären Wert. Wenn Sie das Niveau der Optimierung, dann sollten Sie speichern den Wert in eine lokale variable selbst. Ansonsten, ja, Sie bezahlen für den Funktion-Aufruf-overhead im Zusammenhang mit dem Aufruf der size () - Methode. Beachten Sie jedoch, dass die size () - Methode ist O(1) für ArrayList (obwohl der Funktionsaufruf-overhead ziemlich heftige). Persönlich würde ich den Faktor, der aus einem Aufruf von size() aus Schleifen und manuell speichern Sie diese in einem lokalen (wo zutreffend).

Bearbeiten

Auch wenn so eine Optimierung nicht durchgeführt werden kann durch einen Java-compiler, es wurde treffend darauf hingewiesen, dass der JIT-können inline die Umsetzung der ArrayList.size (), so dass es nur Kosten das gleiche wie ein Feld zuzugreifen, ohne zusätzlichen Aufruf der Methode Aufwand, so dass im Effekt die Kosten sind vernachlässigbar, obwohl Sie vielleicht noch sparen leicht durch manuelles speichern in einer temporären (die möglicherweise beseitigen memory-lookup-stattdessen dienen die variable aus einem CPU-register).
- Vermutlich, weil deine Antwort ist sachlich falsch - size() hat in der Tat zurück, ohne durchführen von zusätzlichen Berechnungen verwenden, und den code nicht wissen, welche Methode Implementierungen anpassen von Größe und welche nicht. Ihre Diskussion von Compilern ist ein Roter Hering, umgesetzt wird dies auf Quellcode-Ebene und ist sehr einfach. Außerdem sagen Sie, dass Sie die Antwort nicht wissen, für sicher, dass (wenn es dauern würde, zwei Minuten zu überprüfen) und die Beantwortung ohnehin nicht sehr hilfreich.
- Ich gehe davon aus, dass es ist, weil alle anderen ist die Interpretation der Frage "ist der Wert, der intern gespeichert oder berechnet jedes mal," und Sie sind zu interpretieren als "wird Sie zum aufrufen der Methode jedes mal, oder ist der Wert, gespeichert in einem register nach dem ersten Anruf."
- Ich wollte nicht implizieren, dass size() ist ein zusätzlicher Berechnung. Ich sagte sogar, dass es O(1). Sie eindeutig nicht verstehen, die Frage, und diese müssten umgesetzt werden, indem der Java-compiler (von dem es mehrere Umsetzung, so dass es unmöglich eine einzige Antwort ohne suchen in allen Implementierungen).
- ja, denke ich so... kommen von einem C++ - hintergrund, wo "const" verwendet wird, speziell als ein Weg, um Hinweis an den compiler, dass es sicher ist zu elide-Funktion aufruft und einfach speichern das Ergebnis in einer lokalen variable, ich klar haben die unterschiedliche Interpretation der Frage als einige der anderen Leute.
- auch würde es dauern, einige nicht-triviale-Analyse für einen compiler, um festzustellen, dass es sicher war, zu umgehen, aber der Anruf. Und bedenkt, dass unterschiedliche Gläser verwendet werden können, die Umsetzung der gleichen Klasse, wäre es wirklich unmöglich für den compiler, um zu wissen, dass die JAR, die zur Laufzeit geladen werden, wird das gleiche Verhalten in Bezug auf, ob es mutiert das Ergebnis der Größe () - Aufruf.
- Funktionsaufruf-overhead ist in der Regel vernachlässigbar im Java-code, da der JIT-compiler kann einfach inline-triviale Funktionen wie diese. Sie nicht haben, um halten Sie den Wert getrennt, ist es lediglich ein, dass client-code Zugriff auf die zugrunde liegenden Feld direkt.
- Diese Art der Sache ist natürlich nicht von den java-compiler, sondern durch den JIT-compiler zur Laufzeit.
- Unsere alternative Lesarten der Frage, ich sehe, wo du herkommst. Sie unterhielten sich darüber, ob der Aufwand einer Methode dispatch vermieden werden könnten, während ich (und vermutlich die downvoter) dachte, dass Peterdk wurde gefragt, ob die Kosten der (intern) Iteration über alle Elemente zu zählen, die vermieden werden könnten. Also warum Compiler und inlining schien offtopic. Obwohl eigentlich die meisten die Optimierung der Zusammenstellung geschieht zur Laufzeit (Hotspot) so dynamischen Rekompilierung, um inline-Methoden (und wiederherstellen später, wenn eine neue Subklasse geladen wird) ist in der Tat möglich.
InformationsquelleAutor Michael Aaron Safyan
0

Die offensichtliche Umsetzung der ArrayList wäre zum speichern der Größe intern in einem Feld. Ich wäre sehr überrascht, wenn es jemals zu werden berechnet, auch nach der Größenänderung.

InformationsquelleAutor Marcelo Cantos
0

Warum würde es sein? ArrayList implementiert das List-interface, unterstützt durch ein array, nachdem alle.

Ich würde annehmen, dass es nur noch eine size Mitglied, dass ist erhöht, wenn Sie legen Sie Dinge, und verringert, wenn Sie zu entfernen, und dann ist es nur die Renditen, die.

Habe ich noch nicht angeschaut, mehr als die API-docs, jetzt, wenn.
- da Funktions-Aufruf-overhead ist nicht neglibible. Sie zahlen eine Menge, nur werden zurückgegeben, die den Wert eines Feldes. Wenn es aufgerufen wird, immer und immer wieder in einer Schleife, können Sie sich ein paar Einsparungen von eliding den Anruf.
- der JIT ist smart genug, um inline-solche einfachen Methoden, so dass Sie dann nicht die Funktionsaufruf-overhead.
- Sicher, aber das war es nicht, was die Frage war. Die Frage war, ob ArrayList caches die Größe, so dass size() kann nur wieder eine zwischengespeicherte Wert eher als "berechnen Sie". Meine Antwort versucht zu erklären, dass es sehr wahrscheinlich ist, nichts zu berechnen, und andere scheinen zu belegen, die nach Prüfung der Quelle. Das hat nichts zu tun mit der Methode call-overhead.
- eigentlich die Frage war nicht, ob ArrayList speichert die Größe, aber ob die Größe Cache, die implizieren verschiedene Orte, an denen es zwischengespeichert wurde. Es ist offensichtlich, dass eine array-Liste wird einfach die Größe des Arrays in O(1) Zeit, so dass ich es interpretieren wie die Frage, ob das Ergebnis des Aufrufs von size() zwischengespeichert wird in einer lokalen variable in der Funktion, dass Anrufe size(), ich denke das ist ein absolut korrekter (und in der Tat, mehr logische) interpretation der Frage.
- egal, der OP hat seine Frage geklärt.
InformationsquelleAutor unwind

Wenn das Zwischenspeichern das Ergebnis der size() Methode würde die Leistung spürbar verbessern (was es oft tut - ich regelmäßig zu sehen ArrayList.size() als top-kompilierten Methode in meinem -Xprof Ausgang), dann betrachten Umwandlung die ganze Liste in ein array für eine noch größere Beschleunigung.

Hier ist ein trick, der funktionieren kann, wenn Sie die Liste Durchlaufen, regelmäßig aber nur selten aktualisieren:

class FooProcessor {

    private Foo[] fooArray = null;
    private List<Foo> fooList = new ArrayList<Foo>();

    public void addFoo(Foo foo) {
       fooList.add(foo);
       fooArray = null;
    }

    public void processAllFoos() {
        Foo[] foos = getFooArray();
        for (int i = 0; i < foos.length; ++ i) {
            process(foos[i]);
        }
    }

    private void getFooArray() {
        if (fooArray == null) {
            Foo[] tmpArray = new Foo[fooList.size()];
            fooArray = fooList.toArray(tmpArray);
        }
        return fooArray;
    }

}

InformationsquelleAutor finnw

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.