Maximale Anzahl von Werten in Aufzählung Teil II

Erster Teil, Theoretisch  | Teil zwei, praktisch



Wir suchen weiterhin nach der maximal möglichen Anzahl von Werten in der Aufzählung.
Dieses Mal werden wir uns auf die praktische Seite des Problems konzentrieren und sehen, wie die IDE, der Compiler und die JVM auf unsere Erfolge reagieren werden.

Inhalt


  
  Javac Tools
  Extraktionsmethode
  Dynamische Klassendateikonstanten
    Plötzliche Schwierigkeiten
    Helle Zukunft
  Unsicherer
  Test
    Javac- und Switch- Leistung
  Schlussfolgerung
  Zusätzliche Ressourcen


Werkzeuge


Javac kümmert sich um uns: Es schneidet Zeichen, die es nicht mag, aus Bezeichnern aus und verbietet das Erben davon java.lang.Enum. Für Experimente benötigen wir daher andere Werkzeuge.

Wir werden Hypothesen mit asmtools , dem Assembler und Disassembler für die JVM, testen und mithilfe der ASM- Bibliothek Klassendateien im industriellen Maßstab generieren .

Zur Vereinfachung des Verständnisses wird die Essenz des Geschehens in einem Java-ähnlichen Pseudocode dupliziert.


Javac


Als Ausgangspunkt ist es logisch, mit nur einem das beste Ergebnis zu erzielen, das ohne Tricks erzielt werden kann javac. Hier ist alles einfach - wir erstellen die Quelldatei mit der Aufzählung und fügen ihr Elemente hinzu, bis javac sich weigert, sie mit dem Fluch „Code zu groß“ zu kompilieren .

Seit Java 1.7 wurde diese Zahl ziemlich lange auf dem Niveau von 2_746 Elementen gehalten. Aber irgendwo nach Java 11 gab es Änderungen im Algorithmus zum Speichern von Werten im konstanten Pool und die maximale Anzahl verringerte sich auf 2_743. Ja, ja, nur weil sich die Reihenfolge der Elemente im Konstantenpool geändert hat!

Wir werden uns auf die besten Werte konzentrieren.


Methode extrahieren


Da einer der einschränkenden Faktoren mit der Größe des Bytecodes im statischen Initialisierungsblock zusammenhängt, werden wir versuchen, letzteres so einfach wie möglich zu gestalten.

Erinnern Sie sich daran, wie es am Beispiel der Aufzählung FizzBuzzaus dem ersten Teil aussieht . Kommentare enthalten entsprechende Montageanleitungen.

statisch {}
static  {
    Fizz = new FizzBuzz("Fizz", 0);
    //  0: new           #2                  // class FizzBuzz
    //  3: dup
    //  4: ldc           #22                 // String Fizz
    //  6: iconst_0
    //  7: invokespecial #24                 // Method "<init>":(Ljava/lang/String;I)V
    // 10: putstatic     #25                 // Field Fizz:LFizzBuzz;
    Buzz = new FizzBuzz("Buzz", 1);
    // 13: new           #2                  // class FizzBuzz
    // 16: dup
    // 17: ldc           #28                 // String Buzz
    // 19: iconst_1
    // 20: invokespecial #24                 // Method "<init>":(Ljava/lang/String;I)V
    // 23: putstatic     #30                 // Field Buzz:LFizzBuzz;
    FizzBuzz = new FizzBuzz("FizzBuzz", 2);
    // 26: new           #2                  // class FizzBuzz
    // 29: dup
    // 30: ldc           #32                 // String FizzBuzz
    // 32: iconst_2
    // 33: invokespecial #24                 // Method "<init>":(Ljava/lang/String;I)V
    // 36: putstatic     #33                 // Field FizzBuzz:LFizzBuzz;

    $VALUES = new FizzBuzz[] {
    // 39: iconst_3
    // 40: anewarray     #2                  // class FizzBuzz
        Fizz, 
    // 43: dup
    // 44: iconst_0
    // 45: getstatic     #25                 // Field Fizz:LFizzBuzz;
    // 48: aastore
        Buzz, 
    // 49: dup
    // 50: iconst_1
    // 51: getstatic     #30                 // Field Buzz:LFizzBuzz;
    // 54: aastore
        FizzBuzz
    // 55: dup
    // 56: iconst_2
    // 57: getstatic     #33                 // Field FizzBuzz:LFizzBuzz;
    // 60: aastore
    };
    // 61: putstatic     #1                  // Field $VALUES:[LFizzBuzz;
    // 64: return
}


Das erste, was mir in den Sinn kommt, ist, die Erstellung und Füllung des Arrays $VALUESin eine separate Methode zu integrieren.

$VALUES = createValues();

Bei der Entwicklung dieser Idee kann die Erstellung von Instanzen von Aufzählungselementen auf dieselbe Methode übertragen werden:

static  {
    FizzBuzz[] localValues = createValues();

    int index = 0;
    Fizz = localValues[index++];
    Buzz = localValues[index++];
    FizzBuzz = localValues[index++];

    $VALUES = localValues;
}

private static FizzBuzz[] createValues() {
    return new FizzBuzz[] {
        new FizzBuzz("Fizz", 0), 
        new FizzBuzz("Buzz", 1), 
        new FizzBuzz("FizzBuzz", 2)
    };
}

Schon besser, aber jede Erfassung eines Array-Elements und das anschließende Indexinkrement kosten 6 Bytes, was für uns zu teuer ist. Setzen Sie sie in einer separaten Methode aus.


private static int valueIndex;

static  {
    $VALUES = createValues();

    valueIndex = 0;
    Fizz = nextValue();
    Buzz = nextValue();
    FizzBuzz = nextValue();
}

private static FizzBuzz nextValue() {
    return $VALUES[valueIndex++];
}

Es dauert 11 Bytes, um zu initialisieren und vom statischen Initialisierungsblock zurückzukehren $VALUES, valueIndexund 65_524 weitere Bytes verbleiben, um die Felder zu initialisieren. Die Initialisierung jedes Feldes erfordert 6 Bytes, wodurch wir eine Aufzählung von 10_920 Elementen erstellen können.

Fast das Vierfache des Wachstums im Vergleich zu Javac muss definitiv durch Codegenerierung gefeiert werden!

Generator-Quellcode: ExtractMethodHugeEnumGenerator.java
Beispiel für eine generierte Klasse: ExtractMethodHugeEnum.class

Dynamische Klassendateikonstanten


Es ist Zeit, sich an JEP 309 und seine mysteriösen dynamischen Konstanten zu erinnern .

Das Wesentliche an Innovation auf den Punkt gebracht:

Zu bereits vorhandenen Typen, die von einem Konstantenpool unterstützt werden, wurde ein weiterer hinzugefügt CONSTANT_Dynamic. Beim Laden einer Klasse ist der Typ einer solchen Konstante bekannt, ihr Wert ist jedoch unbekannt. Das erste Laden einer Konstante führt zu einem Aufruf der in ihrer Deklaration angegebenen Bootstrap-Methode.

Das Ergebnis dieser Methode wird zu einem konstanten Wert. Es gibt keine Möglichkeit, den Wert zu ändern, der einer bereits initialisierten Konstante zugeordnet ist. Was für eine Konstante ziemlich logisch ist.

Wenn Sie auch an Singleton gedacht haben, vergessen Sie es sofort. In der Spezifikation wird separat hervorgehoben, dass in diesem Fall keine Garantie für die Thread-Sicherheit besteht und die Initialisierungsmethode in Multithread-Code mehrmals aufgerufen werden kann. Es ist nur garantiert, dass bei mehreren Aufrufen der Bootstrap-Methode für dieselbe Konstante die JVM eine Münze wirft und einen der berechneten Werte für die Rolle des konstanten Werts auswählt, während die anderen dem Garbage Collector geopfert werden.

Verhaltensmäßig wird eine CONSTANT_Dynamic-Konstante aufgelöst, indem ihre Bootstrap-Methode für die folgenden Parameter ausgeführt wird:

  1. ein lokales Suchobjekt,
  2. der String, der die Namenskomponente der Konstante darstellt,
  3. die Klasse, die den erwarteten Konstantentyp darstellt, und
  4. alle verbleibenden Bootstrap-Argumente.

As with invokedynamic, multiple threads can race to resolve, but a unique winner will be chosen and any other contending answers discarded.

Um Werte aus dem Pool der Konstanten in der Bytecode zu laden, Befehle werden zur Verfügung gestellt ldc, ldc_wund ldc2_w. Von Interesse für uns ist der erste von ihnen - ldc.

Im Gegensatz zu den anderen kann es nur Werte aus den ersten 255 Slots des konstanten Pools laden, benötigt jedoch 1 Byte weniger Bytecode. All dies gibt uns Einsparungen von bis zu 255 Bytes und ein 255 + ((65_524 - (255 * 5)) / 6) = 10_963Element in der Aufzählung. Dieses Mal ist das Wachstum nicht so beeindruckend, aber es ist immer noch da.

Mit diesem Wissen können wir loslegen.

Im statischen Initialisierungsblock nextValue()laden wir jetzt anstelle von Methodenaufrufen den Wert der dynamischen Konstante. Der Wert des ordinalOrdnungsindex des Aufzählungselements wird explizit übergeben, wodurch das Feld valueIndex, die Factory-Methode, entfernt wirdnextValue()und Zweifel an der Thread-Sicherheit unserer Implementierung.

Als Bootstrap-Methode verwenden wir einen speziellen Subtyp von MethodHandle , der das Verhalten eines Operators newin Java imitiert . Die Standardbibliothek bietet eine MethodHandles.Lookup :: findConstructor () -Methode zum Abrufen eines solchen Methodenhandles. In unserem Fall kümmert sich die JVM jedoch um die Erstellung des erforderlichen Methodenhandles.

Um den Konstruktor unserer Aufzählung als Bootstrap-Methode zu verwenden, muss er durch Ändern der Signatur geringfügig geändert werden. Die für die Bootstrap-Methode erforderlichen Parameter werden dem traditionellen Konstruktor des Namensaufzählungselements und der Seriennummer hinzugefügt:

private FizzBuzz(MethodHandles.Lookup lookup, String name, Class<?> enumClass, int ordinal) {
    super(name, ordinal);
}

In Form von Pseudocode sieht die Initialisierung folgendermaßen aus:

static  {
    Fizz = JVM_ldc(FizzBuzz::new, "Fizz", 0);
    Buzz = JVM_ldc(FizzBuzz::new, "Buzz", 1);
    FizzBuzz = JVM_ldc(FizzBuzz::new, "FizzBuzz", 2);

    $VALUES = createValues();
}

Im obigen Beispiel werden die Anweisungen ldcals Methodenaufrufe bezeichnet JVM_ldc(). Im Bytecode an ihrer Stelle befinden sich die entsprechenden JVM-Anweisungen.

Da wir jetzt für jedes Element der Aufzählung eine eigene Konstante haben, kann das Erstellen und Füllen des Arrays $VALUESauch über eine dynamische Konstante implementiert werden. Die Bootstrap-Methode ist sehr einfach:

private static FizzBuzz[] createValues(MethodHandles.Lookup lookup, String name, Class<?> clazz, FizzBuzz... elements) {
    return elements;
}

Alle Tricks in der Liste der statischen Parameter für diese dynamische Konstante, dort werden wir alle Elemente auflisten, die wir einfügen möchten $VALUES:

BootstrapMethods:
  ...
  1: # 54 REF_invokeStatic FizzBuzz.createValues: (Ljava / lang / invoke / MethodHandles $ Lookup; Ljava / lang / String; Ljava / lang / Class; [LFizzBuzz;) [LFizzBuzz;
    Methodenargumente:
      # 1 # 0: Fizz: LFizzBuzz;
      # 2 # 0: Buzz: LFizzBuzz;
      # 3 # 0: FizzBuzz: LFizzBuzz;

Die JVM verwöhnt das Array mit diesen statischen Parametern und übergibt es als vararg-Parameter an unsere Bootstrap-Methode elements. Die maximale Anzahl statischer Parameter beträgt traditionell 65_535, sodass sie garantiert für alle Elemente der Aufzählung ausreichen, unabhängig davon, wie viele es gibt.

Bei Übertragungen mit einer großen Anzahl von Elementen wird durch diese Änderung die Größe der resultierenden Klassendatei verringert. Wenn die Methode aufgrund der großen Anzahl von Elementen createValues()in mehrere Teile aufgeteilt werden musste, werden auch Slots im konstanten Pool gespeichert .
Und am Ende ist es einfach wunderschön.


Plötzliche Schwierigkeiten


Was wir heldenhaft überwinden, indem wir Klassen manuell generieren.

Hochrangige Bibliotheken bieten eine bequeme Schnittstelle im Austausch für eine gewisse Einschränkung der Handlungsfreiheit. Die ASM-Bibliothek, mit der wir Klassendateien generieren, ist keine Ausnahme. Es bietet keine Mechanismen zur direkten Steuerung des Inhalts des Konstantenpools. Dies ist normalerweise nicht sehr wichtig, aber in unserem Fall nicht.

Wie Sie sich erinnern, benötigen wir die ersten 255 Elemente des konstanten Pools, um wertvolle Bytes im statischen Initialisierungsblock zu speichern. Wenn dynamische Konstanten auf standardmäßige Weise hinzugefügt werden, werden sie an zufälligen Indizes lokalisiert und mit anderen Elementen gemischt, die für uns nicht so kritisch sind. Dies verhindert, dass wir das Maximum erreichen.

Fragment eines auf traditionelle Weise gebildeten Konstantenpools
Konstanter Pool:
   # 1 = Utf8 FizzBuzz
   #2 = Class              #1             // FizzBuzz
   #3 = Utf8               java/lang/Enum
   #4 = Class              #3             // java/lang/Enum
   #5 = Utf8               $VALUES
   #6 = Utf8               [LFizzBuzz;
   #7 = Utf8               valueIndex
   #8 = Utf8               I
   #9 = Utf8               Fizz
  #10 = Utf8               LFizzBuzz;
  #11 = Utf8               Buzz
  #12 = Utf8               FizzBuzz
  #13 = Utf8               values
  #14 = Utf8               ()[LFizzBuzz;
  #15 = NameAndType        #5:#6          // $VALUES:[LFizzBuzz;
  #16 = Fieldref           #2.#15         // FizzBuzz.$VALUES:[LFizzBuzz;
  #17 = Class              #6             // "[LFizzBuzz;"
  #18 = Utf8               clone
  #19 = Utf8               ()Ljava/lang/Object;
  #20 = NameAndType        #18:#19        // clone:()Ljava/lang/Object;
  #21 = Methodref          #17.#20        // "[LFizzBuzz;".clone:()Ljava/lang/Object;
  ...
  #40 = NameAndType        #9:#10         // Fizz:LFizzBuzz;
  #41 = Dynamic            #0:#40         // #0:Fizz:LFizzBuzz;
  #42 = Fieldref           #2.#40         // FizzBuzz.Fizz:LFizzBuzz;
  #43 = NameAndType        #11:#10        // Buzz:LFizzBuzz;
  #44 = Dynamic            #0:#43         // #0:Buzz:LFizzBuzz;
  #45 = Fieldref           #2.#43         // FizzBuzz.Buzz:LFizzBuzz;
  #46 = NameAndType        #12:#10        // FizzBuzz:LFizzBuzz;
  #47 = Dynamic            #0:#46         // #0:FizzBuzz:LFizzBuzz;
  #48 = Fieldref           #2.#46         // FizzBuzz.FizzBuzz:LFizzBuzz;



Glücklicherweise gibt es eine Problemumgehung: Beim Erstellen einer Klasse können Sie eine Beispielklasse angeben, aus der ein Pool von Konstanten und ein Attribut mit einer Beschreibung der Bootstrap-Methoden kopiert werden. Erst jetzt müssen wir es manuell generieren.

In der Tat ist es nicht so schwierig, wie es auf den ersten Blick scheinen mag. Das Format der Klassendatei ist recht einfach und die manuelle Generierung ist ein etwas langwieriger Prozess, aber keineswegs kompliziert.

Das Wichtigste hier ist ein klarer Plan. Um aus den COUNTElementen aufzuzählen, die wir brauchen:

  • COUNTTypdatensätze CONSTANT_Dynamic- unsere dynamischen Konstanten
  • COUNTTypdatensätze CONSTANT_NameAndType- Verknüpfungspaare mit dem Namen des Aufzählungselements und seinem Typ. Der Typ ist für alle gleich, dies ist der Klassentyp unserer Aufzählung.
  • COUNTTypdatensätze CONSTANT_Utf8- direkt die Namen der Aufzählungselemente
  • COUNTDatensätze vom Typ CONSTANT_Integer- Seriennummern von Aufzählungselementen, die als Parameterwert an den Konstruktor übergeben wurdenordinal
  • Namen der aktuellen und Basisklassen, Attribute, Methodensignaturen und andere langweilige Implementierungsdetails. Interessenten können im Quellcode des Generators nachsehen.

Es gibt viele konstituierende Elemente im Pool von Konstanten, die sich nach Index auf andere Elemente des Pools beziehen. Daher sollten alle Indizes, die wir im Voraus berechnen müssen, elementNameseine Liste der Namen der Elemente unserer Aufzählung enthalten:

int elementCount = elementNames.size();

int baseConDy = 1;
int baseNameAndType = baseConDy + elementCount;
int baseUtf8 = baseNameAndType + elementCount;
int baseInteger = baseUtf8 + elementCount;
int indexThisClass = baseInteger + elementCount;
int indexThisClassUtf8 = indexThisClass + 1;
int indexSuperClass = indexThisClassUtf8 + 1;
int indexSuperClassUtf8 = indexSuperClass + 1;
int indexBootstrapMethodsUtf8 = indexSuperClassUtf8 + 1;
int indexConDyDescriptorUtf8 = indexBootstrapMethodsUtf8 + 1;
int indexBootstrapMethodHandle = indexConDyDescriptorUtf8 + 1;
int indexBootstrapMethodRef = indexBootstrapMethodHandle + 1;
int indexBootstrapMethodNameAndType = indexBootstrapMethodRef + 1;
int indexBootstrapMethodName = indexBootstrapMethodNameAndType + 1;
int indexBootstrapMethodDescriptor = indexBootstrapMethodName + 1;

int constantPoolSize = indexBootstrapMethodDescriptor + 1;

Danach fangen wir an zu schreiben.

Zu Beginn - die Signatur der Klassendatei, die vier allen bekannten Bytes 0xCA 0xFE 0xBA 0xBEund die Dateiformatversion:

// Class file header
u4(CLASS_FILE_SIGNATURE);
u4(version);

Dann - ein Pool von Konstanten:

Pool von Konstanten
// Constant pool
u2(constantPoolSize);

// N * CONSTANT_Dynamic
for (int i = 0; i < elementCount; i++) {
    u1u2u2(CONSTANT_Dynamic, i, baseNameAndType + i);
}

// N * CONSTANT_NameAndType
for (int i = 0; i < elementCount; i++) {
    u1u2u2(CONSTANT_NameAndType, baseUtf8 + i, indexConDyDescriptorUtf8);
}

// N * CONSTANT_Utf8
//noinspection ForLoopReplaceableByForEach
for (int i = 0; i < elementCount; i++) {
    u1(CONSTANT_Utf8);
    utf8(elementNames.get(i));
}

// N * CONSTANT_Integer
for (int i = 0; i < elementCount; i++) {
    u1(CONSTANT_Integer);
    u4(i);
}

// ThisClass
u1(CONSTANT_Class);
u2(indexThisClassUtf8);

// ThisClassUtf8
u1(CONSTANT_Utf8);
utf8(enumClassName);

// SuperClass
u1(CONSTANT_Class);
u2(indexSuperClassUtf8);

// SuperClassUtf8
u1(CONSTANT_Utf8);
utf8(JAVA_LANG_ENUM);

// BootstrapMethodsUtf8
u1(CONSTANT_Utf8);
utf8(ATTRIBUTE_NAME_BOOTSTRAP_METHODS);

// ConDyDescriptorUtf8
u1(CONSTANT_Utf8);
utf8(binaryEnumClassName);

// BootstrapMethodHandle
u1(CONSTANT_MethodHandle);
u1(REF_newInvokeSpecial);
u2(indexBootstrapMethodRef);

// BootstrapMethodRef
u1u2u2(CONSTANT_Methodref, indexThisClass, indexBootstrapMethodNameAndType);

// BootstrapMethodNameAndType
u1u2u2(CONSTANT_NameAndType, indexBootstrapMethodName, indexBootstrapMethodDescriptor);

// BootstrapMethodName
u1(CONSTANT_Utf8);
utf8(BOOTSTRAP_METHOD_NAME);

// BootstrapMethodDescriptor
u1(CONSTANT_Utf8);
utf8(BOOTSTRAP_METHOD_DESCRIPTOR);


Nachdem der Pool konstant sprechen über Zugriffsmodifikatoren und Flaggen ( public, final, enun, usw.), der Klassenname und seine Vorfahren:

u2(access);
u2(indexThisClass);
u2(indexSuperClass);

Die von uns generierte Dummy-Klasse hat keine Schnittstellen, keine Felder, keine Methoden, aber es gibt ein Attribut mit einer Beschreibung der Bootstrap-Methoden:

// Interfaces count
u2(0);
// Fields count
u2(0);
// Methods count
u2(0);
// Attributes count
u2(1);

Und hier ist der Hauptteil des Attributs selbst:

// BootstrapMethods attribute
u2(indexBootstrapMethodsUtf8);
// BootstrapMethods attribute size
u4(2 /* num_bootstrap_methods */ + 6 * elementCount);
// Bootstrap method count
u2(elementCount);

for (int i = 0; i < elementCount; i++) {
    // bootstrap_method_ref
    u2(indexBootstrapMethodHandle);
    // num_bootstrap_arguments
    u2(1);
    // bootstrap_arguments[1]
    u2(baseInteger + i);
}

Das ist alles, die Klasse ist gebildet. Wir nehmen diese Bytes und erstellen daraus ClassReader:

private ClassReader getBootstrapClassReader(int version, int access, String enumClassName, List<String> elementNames) {
    byte[] bootstrapClassBytes = new ConDyBootstrapClassGenerator(
        version,
        access,
        enumClassName,
        elementNames
    )
    .generate();

    if (bootstrapClassBytes == null) {
        return null;
    } else {
        return new ClassReader(bootstrapClassBytes);
    }
}

Es war nicht so schwierig.

Generator-Quellcode: ConDyBootstrapClassGenerator.java

Strahlende Zukunft


Wir schweifen kurz von unseren Auflistungen ab:


public class DiscoverConstantValueAttribute {

    public static final String STRING = "Habrahabr, world!";

    public static final Object OBJECT = new Object();

}


Im statischen Initialisierungsblock dieser Klasse gibt es plötzlich nur noch eine Schreiboperation im Feld OBJECT:


static {
    OBJECT = new Object();
    //  0: new           #2                  // class java/lang/Object
    //  3: dup
    //  4: invokespecial #1                  // Method java/lang/Object."<init>":()V
    //  7: putstatic     #7                  // Field OBJECT:Ljava/lang/Object;
    // 10: return
}


Aber was ist mit STRING?
Das Team wird helfen, Licht in dieses Rätsel zu bringen javap -c -s -p -v DiscoverConstantValueAttribute.class. Hier ist das Fragment, das uns interessiert:


public static final java.lang.String STRING;
  descriptor: Ljava/lang/String;
  flags: (0x0019) ACC_PUBLIC, ACC_STATIC, ACC_FINAL
  ConstantValue: String Habrahabr, world!


Der Wert des statischen Endfelds wurde vom Initialisierungsblock in ein separates Attribut verschoben ConstantValue. Folgendes schreiben sie über dieses Attribut in JVMS11 §4.7.2 :

Ein ConstantValue-Attribut stellt den Wert eines konstanten Ausdrucks dar (JLS §15.28) und wird wie folgt verwendet:
  • Wenn das ACC_STATIC-Flag im Element access_flags der Struktur field_info gesetzt ist, wird dem durch die Struktur field_info dargestellten Feld der Wert zugewiesen, der durch das Attribut ConstantValue im Rahmen der Initialisierung der Klasse oder Schnittstelle dargestellt wird, die das Feld deklariert (§5.5). Dies erfolgt vor dem Aufruf der Klassen- oder Schnittstelleninitialisierungsmethode dieser Klasse oder Schnittstelle (§2.9.2).
  • Andernfalls muss die Java Virtual Machine das Attribut stillschweigend ignorieren.


Wenn ein solches Attribut gleichzeitig staticund final(obwohl letzteres hier nicht explizit angegeben ist) in einem Feld auftritt , wird ein solches Feld mit dem Wert aus diesem Attribut initialisiert. Dies geschieht bereits vor dem Aufruf der statischen Initialisierungsmethode.

Es wäre verlockend, dieses Attribut zu verwenden, um die Elemente der Aufzählung zu initialisieren. In unserem vorletzten Kapitel gab es nur Konstanten, wenn auch dynamische.

Und wir sind nicht die ersten, die in diese Richtung denken, es gibt eine Erwähnung in JEP 309 ConstantValue. Leider ist diese Erwähnung im zukünftigen Arbeitskapitel enthalten:

Zukünftige Arbeiten

Mögliche zukünftige Erweiterungen umfassen:

...
  • Anhängen dynamischer Konstanten an das ConstantValue-Attribut statischer Felder


In der Zwischenzeit können wir nur von den Zeiten träumen, in denen diese Funktion vom Status „Gut zu tun“ zu „Bereit“ wechselt. Dann verlieren die Einschränkungen für die Größe des Codes im Initialisierungsblock ihren Einfluss und die maximale Anzahl von Elementen in der Aufzählung bestimmt die Einschränkungen des konstanten Pools.

Nach groben Schätzungen können wir in diesem Fall auf ein 65 489 / 4 = 16_372Element hoffen . Hier 65_489ist die Anzahl der nicht besetzten Slots des konstanten Pools, 46 der theoretisch möglichen 65_535 gingen an den Overhead. 4- die Anzahl der für die Deklaration eines Feldes erforderlichen Slots und die entsprechende dynamische Konstante.

Die genaue Anzahl kann natürlich erst nach der Veröffentlichung der JDK-Version mit Unterstützung für diese Funktion ermittelt werden.


Unsicher


Unser Feind ist das lineare Wachstum des Initialisierungsblocks mit einer Zunahme der Anzahl von Aufzählungselementen. Wenn wir einen Weg gefunden hätten, die Initialisierung in einer Schleife einzuschränken und dadurch die Beziehung zwischen der Anzahl der Elemente in der Aufzählung und der Größe des Initialisierungsblocks zu entfernen, würden wir einen weiteren Durchbruch erzielen.

Leider erlaubt keine der öffentlichen Standard-APIs das Schreiben in static finalFelder, selbst innerhalb eines statischen Initialisierungsblocks. Weder Reflection noch VarHandles helfen hier. Unsere einzige Hoffnung ist groß und schrecklich sun.misc.Unsafe.

Eine unsichere Ausführung von FizzBuzz könnte ungefähr so ​​aussehen:

Unsicheres FizzBuzz
import java.lang.reflect.Field;
import sun.misc.Unsafe;

public enum FizzBuzz {

    private static final FizzBuzz[] $VALUES;

    public static final FizzBuzz Fizz;
    public static final FizzBuzz Buzz;
    public static final FizzBuzz FizzBuzz;

    public static FizzBuzz[] values() {
        return (FizzBuzz[]) $VALUES.clone();
    }

    public static FizzBuzz valueOf(String name) {
        return (FizzBuzz) Enum.valueOf(FizzBuzz.class, name);
    }

    private FizzBuzz(String name, int ordinal) {
        super(name, ordinal);
    }

    private static FizzBuzz[] createValues() {
        return new FizzBuzz[] {
            Fizz,
            Buzz,
            FizzBuzz
        }
    }

    static  {
        Field unsafeField = Unsafe.class.getDeclaredField("theUnsafe");
        unsafeField.setAccessible(true);
        Unsafe unsafe = (Unsafe) unsafeField.get(null);

        String[] fieldNames = "Fizz,Buzz,FizzBuzz".split(",");
        for(int i = 0; i < fieldNames.length; i++) {
            String fieldName = fieldNames[i];
            Field field = FizzBuzz.class.getDeclaredField(fieldName);
            long fieldOffset = unsafe.staticFieldOffset(field);
            unsafe.putObject(FizzBuzz.class, fieldOffset, new FizzBuzz(fieldName, i));
        }

        $VALUES = createValues();
    }

}


Dieser Ansatz ermöglicht es uns, eine Aufzählung mit ungefähr 21.000 Elementen zu erstellen, für mehr reicht die Kapazität des Konstantenpools nicht aus.

Die Dokumentation zu Enum :: ordinal () erfordert, dass sein Wert mit der Sequenznummer des entsprechenden Elements in der Aufzählungsdeklaration übereinstimmt. Daher müssen Sie die Liste der Feldnamen explizit in der richtigen Reihenfolge speichern, wodurch sich die Größe der Klassendatei fast verdoppelt.

public final int ordinal ()

Gibt die Ordnungszahl dieser Aufzählungskonstante zurück (ihre Position in ihrer Aufzählungsdeklaration, wobei der Anfangskonstante eine Ordnungszahl von Null zugewiesen wird).

Hier könnte die öffentliche API zum Inhalt des Konstantenpools helfen. Wir wissen bereits, wie man sie in der von uns benötigten Reihenfolge ausfüllt, aber es gibt keine solche API und es ist unwahrscheinlich, dass dies jemals der Fall sein wird. Die in OpenJDK verfügbare Class :: getConstantPool () -Methode wird als paketprivat deklariert, und es wäre unüberlegt, sich im Benutzercode darauf zu verlassen.

Der Initialisierungsblock ist jetzt ziemlich kompakt und nahezu unabhängig von der Anzahl der Elemente in der Aufzählung. Sie createValues()können ihn also ablehnen, indem Sie seinen Körper in die Schleife einbetten:

static  {
    Field unsafeField = Unsafe.class.getDeclaredField("theUnsafe");
    unsafeField.setAccessible(true);
    Unsafe unsafe = (Unsafe) unsafeField.get(null);

    String[] fieldNames = "Fizz,Buzz,FizzBuzz".split(",");
    FizzBuzz[] localValues = new FizzBuzz[fieldNames.length];
    for(int i = 0; i < fieldNames.length; i++) {
        String fieldName = fieldNames[i];
        Field field = FizzBuzz.class.getDeclaredField(fieldName);
        long fieldOffset = unsafe.staticFieldOffset(field);
        unsafe.putObject(
            FizzBuzz.class,
            fieldOffset,
            (localValues[i] = new FizzBuzz(fieldName, i))
        );
    }

    $VALUES = localValues;
}

Hier geschieht ein Lawinen-ähnlicher Prozess: Zusammen mit der Methode createValues()verschwinden Anweisungen zum Lesen von Feldern von Aufzählungselementen, Typdatensätze Fieldreffür diese Felder werden unnötig und NameAndTypeTypdatensätze für Typdatensätze Fieldref. Im konstanten Pool werden 2 * < >Slots freigegeben , mit denen zusätzliche Aufzählungselemente deklariert werden können.

Aber nicht alles ist so rosig, Tests zeigen einen signifikanten Leistungsabfall: Das Initialisieren einer Aufzählungsklasse mit 65.000 Elementen dauert eineinhalb Minuten undenkbar. Wie sich ziemlich schnell herausstellte, "verlangsamt sich der Reflex".

Die Implementierung von Class :: getDeclaredField () in OpenJDK hat ein lineares asymptotisches Verhalten der Anzahl der Felder in der Klasse, und unser Initialisierungsblock ist aus diesem Grund quadratisch.

Das Hinzufügen von Caching verbessert die Situation etwas, löst es jedoch nicht vollständig:

static  {
    Field unsafeField = Unsafe.class.getDeclaredField("theUnsafe");
    unsafeField.setAccessible(true);
    Unsafe unsafe = (Unsafe) unsafeField.get(null);

    String[] fieldNames = "Fizz,Buzz,FizzBuzz".split(",");
    Field[] fields = FizzBuzz.class.getDeclaredFields();
    HashMap<String, Field> cache = new HashMap<>(fields.length);

    for(Field field : fields) {
        cache.put(field.getName(), field);
    }

    for (int i = 0; i < fieldNames.length; i++) {
        String fieldName = fieldNames[i];
        Field field = cache.get(fieldName);
        long fieldOffset = unsafe.staticFieldOffset(field);
        unsafe.putObject(
            FizzBuzz.class,
            fieldOffset,
            (localValues[i] = new FizzBuzz(fieldName, i))
        );
    }    

    $VALUES = localValues;
}

Mit dem in diesem Kapitel beschriebenen unsicheren Ansatz können Sie Übertragungen mit einer Anzahl von Elementen bis zu 65_410 erstellen. Dies ist fast das 24-fache des mit javac erzielbaren Ergebnisses und liegt ziemlich nahe an der theoretischen Grenze von 65_505 Elementen, die wir in der vorherigen Veröffentlichung des Zyklus berechnet haben.


Überprüfen Sie die Leistung


Für Tests nehmen wir die größte Aufzählung und generieren sie mit dem Befehl java -jar HugeEnumGen.jar -a Unsafe UnsafeHugeEnum. Als Ergebnis erhalten wir eine Klassendatei mit einer Größe von 2 Megabyte und 65_410 Elementen.

Erstellen Sie ein neues Java-Projekt in IDEA und fügen Sie die generierte Klasse als externe Bibliothek hinzu.

Fast sofort fällt auf, dass IDEA für einen solchen Stresstest nicht bereit ist: Die



automatische Vervollständigung eines Aufzählungselements dauert sowohl auf dem alten mobilen i5 als auch auf dem moderneren i7 8700K mehrere zehn Sekunden. Wenn Sie versuchen, die fehlenden Elemente mithilfe der Schnellkorrektur zum Switch hinzuzufügen, hört IDEA sogar auf, die Fenster neu zu zeichnen. Ich vermute das vorübergehend, konnte aber nicht auf die Fertigstellung warten. Die Reaktionsfähigkeit beim Debuggen lässt ebenfalls zu wünschen übrig.

Beginnen wir mit einer kleinen Anzahl von Elementen in switch:

public class TestFew {

    public static void main(String... args) {
        for(String arg : args) {
            System.out.print(arg + " : ");

            try {
                UnsafeHugeEnum value = UnsafeHugeEnum.valueOf(arg);

                doSwitch(value);
            } catch(Throwable e) {
                e.printStackTrace(System.out);
            }
        }
    }

    private static void doSwitch(UnsafeHugeEnum value) {
        switch(value) {
            case VALUE_00001:
                System.out.println("First");
                break;
            case VALUE_31415:
                System.out.println("(int) (10_000 * Math.PI)");
                break;
            case VALUE_65410:
                System.out.println("Last");
                break;
            default:
                System.out.println("Unexpected value: " + value);
                break;
        }
    }

}

Hier gibt es keine Überraschungen, Zusammenstellung und Start sind regelmäßig:

$ java TestFew VALUE_00001 VALUE_00400 VALUE_31415 VALUE_65410
VALUE_00001 : First
VALUE_00400 : Unexpected value: VALUE_00400
VALUE_31415 : (int) (10_000 * Math.PI)
VALUE_65410 : Last

Was ist mit mehr Artikeln in switch? Können wir zum Beispiel switchalle unsere 65.000 Elemente gleichzeitig verarbeiten?

switch(value) {
    case VALUE_00001:
    case VALUE_00002:
        ...
    case VALUE_65410:
        System.out.println("One of known values: " + value);
        break;
    default:
        System.out.println("Unexpected value: " + value);
        break;
}

Ach nein. Wenn wir versuchen zu kompilieren, erhalten wir eine ganze Reihe von Fehlermeldungen:

$ javac -fullversion
javac full version "14.0.1+7"

$ javac TestAll.java
TestAll.java:18: error: code too large for try statement
        switch(value) {
        ^
TestAll.java:65433: error: too many constants
                break;
                ^
TestAll.java:17: error: code too large
    private static void doSwitch(UnsafeHugeEnum value) {
                        ^
TestAll.java:1: error: too many constants
public class TestAll {
       ^
4 errors



Javac und wechseln


Um zu verstehen, was passiert, müssen wir herausfinden, wie die Übersetzung switchder Elemente der Aufzählung erfolgt .

Die JVM-Spezifikation enthält ein separates Kapitel in JVMS11 §3.10 Kompilieren von Switches , dessen Empfehlungen sich auf die switchVerwendung einer der beiden Bytecode-Anweisungen beschränken, tableswitchoder lookupswitch. switchIn diesem Kapitel finden wir keine Verweise auf Zeichenfolgen oder Aufzählungselemente.

Die beste Dokumentation ist Code, also ist es Zeit, in die Quelle einzutauchen javac.

Die Wahl zwischen tableswitchund lookupswitcherfolgt in Gen :: visitSwitch () und hängt von der Anzahl der Optionen in ab switch. In den meisten Fällen gewinnt tableswitch:

// Determine whether to issue a tableswitch or a lookupswitch
// instruction.
long table_space_cost = 4 + ((long) hi - lo + 1); // words
long table_time_cost = 3; // comparisons
long lookup_space_cost = 3 + 2 * (long) nlabels;
long lookup_time_cost = nlabels;
int opcode =
    nlabels > 0 &&
    table_space_cost + 3 * table_time_cost <=
    lookup_space_cost + 3 * lookup_time_cost
    ?
    tableswitch : lookupswitch;

Der Header tableswitchbesteht aus ungefähr 16 Bytes plus 4 Bytes pro Wert. Somit switchkann es unter keinen Umständen mehr ( 65_535 - 16 ) / 4 = 16_379Elemente geben.

In der Tat bleibt nach der Reduzierung der Anzahl der Zweige caseim Körper switchauf 16.000 nur ein Kompilierungsfehler übrig, der mysteriöseste:

TestAll.java:18: error: code too large for try statement
        switch(value) {
        ^

Auf der Suche nach der Fehlerquelle werden wir etwas früher zum Stadium der Beseitigung des syntaktischen Zuckers zurückkehren. Die switchMethoden sind für die Übersetzung visitEnumSwitch(), mapForEnum()und die Klasse EnumMappingin Lower.java .

Dort finden wir auch einen kleinen dokumentarischen Kommentar:

EnumMapping JavaDoc
/** This map gives a translation table to be used for enum
 *  switches.
 *
 *  <p>For each enum that appears as the type of a switch
 *  expression, we maintain an EnumMapping to assist in the
 *  translation, as exemplified by the following example:
 *
 *  <p>we translate
 *  <pre>
 *          switch(colorExpression) {
 *          case red: stmt1;
 *          case green: stmt2;
 *          }
 *  </pre>
 *  into
 *  <pre>
 *          switch(Outer$0.$EnumMap$Color[colorExpression.ordinal()]) {
 *          case 1: stmt1;
 *          case 2: stmt2
 *          }
 *  </pre>
 *  with the auxiliary table initialized as follows:
 *  <pre>
 *          class Outer$0 {
 *              synthetic final int[] $EnumMap$Color = new int[Color.values().length];
 *              static {
 *                  try { $EnumMap$Color[red.ordinal()] = 1; } catch (NoSuchFieldError ex) {}
 *                  try { $EnumMap$Color[green.ordinal()] = 2; } catch (NoSuchFieldError ex) {}
 *              }
 *          }
 *  </pre>
 *  class EnumMapping provides mapping data and support methods for this translation.
 */


Das Geheimnisvolle tryentpuppt sich als Teil einer automatisch generierten Helferklasse TestAll$0. Inside - eine Deklaration eines statischen Arrays und Codes zum Initialisieren.

Das Array korrigiert die Entsprechung zwischen den Namen der Aufzählungselemente und den ihnen beim Kompilieren zugewiesenen switchnumerischen Werten und schützt so den kompilierten Code vor den schädlichen Auswirkungen des Refactorings.

Beim Neuanordnen, Hinzufügen neuer oder Löschen vorhandener Aufzählungselemente können einige von ihnen den Wert ändern, ordinal()und dies ist es, wovor eine zusätzliche Indirektionsebene schützt.

try {
    $SwitchMap$UnsafeHugeEnum[UnsafeHugeEnum.VALUE_00001.ordinal()] = 1;
    //  9: getstatic     #2                  // Field $SwitchMap$UnsafeHugeEnum:[I
    // 12: getstatic     #3                  // Field UnsafeHugeEnum.VALUE_00001:LUnsafeHugeEnum;
    // 15: invokevirtual #4                  // Method UnsafeHugeEnum.ordinal:()I
    // 18: iconst_1
    // 19: iastore
}
// 20: goto          24
catch(NoSuchFieldError e) { }
// 23: astore_0

Der Initialisierungscode ist einfach und verbraucht 15 bis 17 Bytes pro Element. Infolgedessen nimmt der statische Initialisierungsblock die Initialisierung von nicht mehr als 3_862 Elementen auf. Diese Anzahl stellt sich als die maximale Anzahl von Aufzählungselementen heraus, die wir switchmit der aktuellen Implementierung in einem verwenden können javac.


Fazit


Wir haben gesehen, dass Sie mit einer so einfachen Technik wie dem Zuweisen der Erstellung von Aufzählungselementen und dem Initialisieren eines Arrays $VALUESin einer separaten Methode die maximale Anzahl von Elementen in einer Aufzählung von 2_746 auf 10_920 erhöhen können.

Die konstanten dynamischen Ergebnisse vor dem Hintergrund früherer Erfolge sehen nicht sehr beeindruckend aus und ermöglichen es Ihnen, nur 43 Elemente mehr zu erhalten. Bei diesem Ansatz ist es jedoch viel eleganter, der Aufzählung neue Eigenschaften hinzuzufügen. Ändern Sie einfach den Konstruktor und übergeben Sie die erforderlichen Werte an die statischen Parameter der dynamischen Konstante.

Wenn irgendwann in der Zukunft das Attribut ConstantValuegelehrt wird, die dynamischen Konstanten zu verstehen, könnte diese Zahl auf 10 Tausend bis 16 ansteigen.

Verwendungsun.misc.Unsafeermöglicht es Ihnen, einen riesigen Sprung zu machen und die maximale Anzahl von Elementen auf 65_410 zu erhöhen. Vergessen Sie jedoch nicht, dass Unsafedies eine proprietäre API ist, die im Laufe der Zeit verschwinden kann und deren Verwendung ein erhebliches Risiko darstellt, da javac direkt warnt:

Test.java:3: warning: Unsafe is internal proprietary API and may be removed in a future release
import sun.misc.Unsafe;
               ^

Wie sich herausstellte, reicht es jedoch nicht aus, eine riesige Aufzählung zu generieren, sondern Sie müssen sie auch verwenden können.

Derzeit gibt es Probleme mit der Unterstützung solcher Aufzählungen sowohl von der IDE als auch auf der Java-Compilerebene.

Eine große Anzahl von Feldern in der Klasse kann die Reaktionsfähigkeit der IDE sowohl während der Bearbeitung als auch während des Debuggens beeinträchtigen. Manchmal bis zu einem kompletten Hang.

Die durch das Klassendateiformat und die Implementierungsdetails von javac auferlegten Einschränkungen machen es unmöglich, switchmehr als 3_862 Elemente gleichzeitig im Code zu verwenden. Von den positiven Aspekten ist zu erwähnen, dass dies beliebige 3_862 Elemente sein können.

Eine weitere Verbesserung der Ergebnisse ist nur durch die Verfeinerung des Java-Compilers möglich, aber das ist eine ganz andere Geschichte.


Zusätzliche Materialien


GitHub-Quellcode: https://github.com/Maccimo/HugeEnumGeneratorArticle

Gesammelte JAR-Datei: https://github.com/Maccimo/HugeEnumGeneratorArticle/releases/tag/v1.0

Unterstützte Starthilfe

Huge enumeration generator

    https://github.com/Maccimo/HugeEnumGeneratorArticle

Additional information (in Russian):

    https://habr.com/ru/post/483392/
    https://habr.com/ru/post/501870/

Usage:
    java -jar HugeEnumGen.jar [ <options> ] <enum name>

    <enum name>
        An enumeration class name.
        Should be a valid Java identifier. May contain package name.

Options:

    -d <directory>
        Output directory path.
        Current working directory by default.

    -e <item list file>
        Path to UTF8-encoded text file with list of enumeration item names.
        Item names will be autogenerated if absent.
        Mutually exclusive with the -c option.

    -c <count>
        Count of autogenerated enumeration item names.
        Mutually exclusive with the -e option.
        Default value: Algorithm-depended

    -a <algorithm>
        Enumeration generation algorithm.
        Supported algorithms:
          ConDy          - Employ Constant Dynamic (JEP 309) for enum elements initialization
          ExtractMethod  - Extract enum elements initialization code to separate method
          Unsafe         - Employ sun.misc.Unsafe for enum elements initialization

        Default algorithm: ExtractMethod

    -h / -?
        Show this help page.

Example:

    java -jar HugeEnumGen.jar -d ./bin -c 2020 com.habr.maccimo.HugeEnum2020



All Articles