Максимальное количество значений в enum Часть II

Часть первая, теоретическая | Часть вторая, практическая



Продолжаем поиск максимального возможного количества значений в перечислении.
На этот раз сосредоточимся на практической стороне вопроса и посмотрим, как на наши достижения будут реагировать IDE, компилятор и JVM.

Содержание


  Инструменты
  Javac
  Extract method
  Dynamic Class-File Constants
    Внезапные трудности
    Светлое будущее
  Unsafe
  Проверяем работоспособность
    Javac и switch
  Заключение
  Дополнительные материалы


Инструменты


Javac заботится о нас: вырезает из идентификаторов не понравившиеся ему символы и запрещает наследоваться от java.lang.Enum, поэтому для экспериментов нам потребуются другие инструменты.

Проверять гипотезы будем при помощи asmtools — ассемблера и дизассемблера для JVM, а генерировать class-файлы в промышленных масштабах — при помощи библиотеки ASM.

Для простоты понимания суть происходящего будет продублирована на java-подобном псевдокоде.


Javac


В качестве отправной точки логично взять лучший результат, достижимый без ухищрений, при помощи одного лишь javac. Здесь всё просто — создаём исходный файл с перечислением и добавляем в него элементы до тех пор, пока javac не откажется компилировать это с руганью «code too large».

Довольно долго, ещё со времён Java 1.7 это число держалось на уровне 2_746 элементов. Но где-то после Java 11 произошли изменения в алгоритме укладки значений в пул констант и максимальное число снизилось до 2_743. Да-да, просто из-за изменения порядка элементов в пуле констант!

Ориентироваться будем на лучшее из значений.


Extract method


Так как один из ограничивающих факторов связан с размером байткода в блоке статической инициализации, попробуем максимально облегчить последний.

Вспомним как он выглядит на примере перечисления FizzBuzz из первой части. Комментариями даны соответствующие ассемблерные инструкции.

static {}
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
}


Первое, что приходит на ум — вынести создание и заполнение массива $VALUES в отдельный метод.

$VALUES = createValues();

Развивая эту мысль, в тот же метод можно перенести и создание экземпляров элементов перечисления:

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

Уже лучше, но каждое взятие элемента массива и последующий инкремент индекса стоят по 6 байтов, что слишком дорого для нас. Вынесем их в отдельный метод.


private static int valueIndex;

static  {
    $VALUES = createValues();

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

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

На инициализацию $VALUES, valueIndex и возврат из блока статической инициализации уходит 11 байтов и остаётся ещё 65_524 байта на инициализацию полей. Инициализация каждого поля требует по 6 байтов, что даёт нам возможность создать перечисление из 10_920 элементов.

Почти четырёхкратный рост по сравнению с javac обязательно нужно отпраздновать кодогенерацией!

Исходный код генератора: ExtractMethodHugeEnumGenerator.java
Пример сгенерированного класса: ExtractMethodHugeEnum.class

Dynamic Class-File Constants


Самое время вспомнить про JEP 309 и его таинственные динамические константы.

Суть нововведения в двух словах:

К уже существующим типам поддерживаемым пулом констант добавлен ещё один, CONSTANT_Dynamic. При загрузке класса известен тип такой константы, но неизвестно её значение. Первая загрузка константы приводит к вызову bootstrap-метода, указанного в её декларации.

Результат выполнения этого метода становится значением константы. Способов изменить значение, связанное с уже проинициализированной константой не предусмотрено. Что для константы вполне логично.

Если вы тоже подумали про Singleton, то немедленно забудьте. В спецификации отдельно подчёркнуто, что гарантий потокобезопасности в этом случае нет и метод инициализации в многопоточном коде может быть вызван более одного раза. Гарантируется только, что в случае нескольких вызовов bootstrap-метода для одной и той же константы JVM подкинет монетку и выберет какое-то одно из вычисленных значений на роль значения константы, а прочие будут принесены в жертву сборщику мусора.

Behaviorally, a CONSTANT_Dynamic constant is resolved by executing its bootstrap method on the following parameters:

  1. a local Lookup object,
  2. the String representing the name component of the constant,
  3. the Class representing the expected constant type, and
  4. any remaining bootstrap arguments.

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

Для загрузки значений из пула констант в байткоде предусмотрены команды ldc, ldc_w и ldc2_w. Интерес для нас представляет первая из них — ldc.

Она, в отличии от прочих, способна загружать значения только из первых 255 слотов пула констант, но зато занимает в байткоде на 1 байт меньше. Всё это даёт нам экономию до 255 байтов и 255 + ((65_524 - (255 * 5)) / 6) = 10_963 элемента в перечислении. В этот раз прирост не такой впечатляющий, но он всё же есть.

Вооружившись этими знаниями, приступим.

В блоке статической инициализации вместо вызовов метода nextValue() теперь будем загружать значение динамической константы. Значение ordinal, порядкового индекса элемента перечисления, будем передавать явно, избавившись таким образом от поля valueIndex, фабричного метода nextValue() и сомнений по поводу потокобезопасности нашей реализации.

В качестве bootstrap-метода будем использовать специальный подвид MethodHandle, имитирующий поведение оператора new в Java. В стандартной библиотеке для получения такого method handle предусмотрен метод MethodHandles.Lookup::findConstructor(), но в нашем случае все заботы по конструированию нужного method handle возьмёт на себя JVM.

Для использования конструктора нашего перечисления в качестве bootstrap-метода его придётся слегка доработать, изменив сигнатуру. К традиционным для конструктора элемента перечисления имени и порядковому номеру добавятся параметры, обязательные для bootstrap-метода:

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

В виде псевдокода инициализация будет выглядеть так:

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

    $VALUES = createValues();
}

В примере выше инструкции ldc обозначены как вызовы метода JVM_ldc(), в байткоде на их месте будут соответствующие инструкции JVM.

Так как теперь у нас есть по отдельной константе на каждый элемент перечисления, создание и заполнение массива $VALUES можно реализовать также через динамическую константу. Bootstrap-метод получается очень простым:

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

Вся хитрость в списке статических параметров для этой динамической константы, там мы перечислим все элементы, которые хотим поместить в $VALUES:

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

JVM сфромирует из этих статических параметров массив и передаст его в наш bootstrap-метод в качестве vararg-параметра elements. Максимальное количество статических параметров — традиционные 65_535, так что его гарантированно хватит на все элементы перечисления, сколько бы их ни было.

Для перечислений с большим количеством элементов это изменение сократит размер результирующего class-файла, а в случае, когда из-за большого количества элементов метод createValues() приходилось разбивать на несколько частей ещё и сэкономит слоты в пуле констант.
И, в конце концов, это просто красиво.


Внезапные трудности


Которые мы героически преодолеваем, генерируя классы вручную.

Высокоуровневые библиотеки предоставляют удобный интерфейс в обмен на некоторое ограничение свободы действий. Используемая нами для генерации class-файлов библиотека ASM здесь не исключение. В ней не предусмотрено механизмов для непосредственного управления содержимым пула констант. Обычно это не очень важно, но не в нашем случае.

Как вы помните, первые 255 элементов пула констант нужны нам для экономии драгоценных байтов в блоке статической инициализации. При добавлении динамических констант стандартным способом, они будут расположены по случайным индексам и перемешаны с другими, не столь критичными для нас элементами. Это помешает нам достичь максимума.

Фрагмент пула констант, сформированного традиционным способом
Constant 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;



К счастью, есть обходной путь — при формировании класса можно указать класс-образец, из которого будут скопированы пул констант и аттрибут с описанием bootstrap-методов. Только вот сгенерировать его нам придётся вручную.

На самом деле это не так трудно, как может показаться на первый взгляд. Формат class-файла довольно прост и его ручная генерация — процесс несколько нудный, но совершенно не сложный.

Самое главное здесь — чёткий план. Для перечисления из COUNT элементов нам понадобятся:

  • COUNT записей типа CONSTANT_Dynamic — наши динамические константы
  • COUNT записей типа CONSTANT_NameAndType — пары ссылок на имя элемента перечисления и его тип. Тип будет одинаков для всех, это тип класса нашего перечисления.
  • COUNT записей типа CONSTANT_Utf8 — непосредственно сами имена элементов перечисления
  • COUNT записей типа CONSTANT_Integer — порядковые номера элементов перечисления, передаваемые в конструктор в качестве значения параметра ordinal
  • имена текущего и базового классов, аттрибутов, сигнатуры методов и прочие скучные детали реализации. Интересующиеся могут посмотреть в исходном коде генератора.

В пуле констант немало составных элементов, которые ссылаются на другие элементы пула по индексу, так что все нужные нам индексы стоит рассчитать заранее, elementNames — список имён элементов нашего перечисления:

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;

После этого начинаем писать.

Вначале — сигнатуру class-файла, всем известные четыре байта 0xCA 0xFE 0xBA 0xBE и версию формата файла:

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

Затем — пул констант:

Пул констант
// 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);


После пула констант идёт информация о модификаторах доступа и флагах (public, final, enun и так далее), именах класса и его предка:

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

Ни интерфейсов, ни полей, ни методов у сгенерированного нами класса-пустышки не будет, но будет один аттрибут с описанием bootstrap-методов:

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

А вот и тело самого атрибута:

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

На этом всё, класс сформирован. Берём эти байтики и создаём из них 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);
    }
}

Это было не так уж и сложно.

Исходный код генератора: ConDyBootstrapClassGenerator.java

Светлое будущее


Ненадолго отвлечёмся от наших перечислений:


public class DiscoverConstantValueAttribute {

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

    public static final Object OBJECT = new Object();

}


В блоке статической инициализации этого класса внезапно будет только одна операция записи, в поле 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
}


А как же STRING?
Пролить свет на эту загадку поможет команда javap -c -s -p -v DiscoverConstantValueAttribute.class, вот интересующий нас фрагмент:


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


Значение статического финального поля переехало из блока инициализации в отдельный аттрибут ConstantValue. Вот что пишут про этот аттрибут в JVMS11 §4.7.2:

A ConstantValue attribute represents the value of a constant expression (JLS §15.28), and is used as follows:
  • If the ACC_STATIC flag in the access_flags item of the field_info structure is set, then the field represented by the field_info structure is assigned the value represented by its ConstantValue attribute as part of the initialization of the class or interface declaring the field (§5.5). This occurs prior to the invocation of the class or interface initialization method of that class or interface (§2.9.2).
  • Otherwise, the Java Virtual Machine must silently ignore the attribute.


Если такой аттрибут встречается у одновременно static и final (хоть последнее здесь явно и не прописано) поля, то такое поле инициализируется значением из этого аттрибута. Причём происходит это ещё до вызова метода статической инициализации.

Было бы заманчиво использовать этот аттрибут для инициализации элементов перечисления, у нас в позапрошлой главе как раз были константы, пусть и динамические.

И мы не первые, кто задумался в этом направлении, в JEP 309 есть упоминание ConstantValue. К сожалению, это упоминание находится в главе «Future work»:

Future work

Possible future extensions include:


  • Attaching dynamic constants to the ConstantValue attribute of static fields


Пока же мы можем лишь мечтать о временах, когда эта фича перейдёт из состояния «хорошо бы сделать» в «готово». Тогда ограничения на размер кода в блоке инициализации утратят своё влияние и максимальное количество элементов в перечислении будут определять ограничения пула констант.

По грубым прикидкам в этом случае можно надеяться на 65 489 / 4 = 16_372 элемента. Здесь 65_489 — количество незанятых слотов пула констант, 46 из теоретически возможных 65_535 ушли на накладные расходы. 4 — количество слотов, необходимых для декларации одного поля и соответствующей ему динамической константы.

Точное число, конечно же, можно будет узнать только после выхода версии JDK с поддержкой этой возможности.


Unsafe


Наш враг — линейный рост блока инициализации при росте количества элементов перечисления. Найди мы способ свернуть инициализацию в цикл, тем самым убрав зависимость между количеством элементов в перечислении и размером блока инициализации, то совершили бы очередной прорыв.

К сожалению, ни один из стандартных публичных API не позволяет производить запись в static final поля даже внутри блока статической инициализации. Здесь не помогут ни Reflection, ни VarHandles. Наша единственная надежда — великий и ужасный sun.misc.Unsafe.

FizzBuzz в небезопасном исполнении мог бы выглядеть примерно так:

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

}


Такой подход позволяет нам создать перечисление с примерно 21 тысячей элементов, на большее не хватает ёмкости пула констант.

Документация на Enum::ordinal() требует, чтобы его значение соответствовало порядковому номеру соответствующего элемента в декларации перечисления, поэтому приходится явно хранить список имён полей в правильном порядке, тем самым почти удваивая размер class-файла.

public final int ordinal()

Returns the ordinal of this enumeration constant (its position in its enum declaration, where the initial constant is assigned an ordinal of zero).

Тут мог бы помочь публичный API к содержимому пула констант, заполнять его в нужном нам порядке мы уже умеем, но такого API нет и вряд ли когда-либо будет. Имеющийся в OpenJDK метод Class::getConstantPool() объявлен как package-private и рассчитывать на него в пользовательском коде было бы опрометчиво.

Блок инициализации теперь довольно компактен и почти не зависит от количества элементов в перечислении, так что от createValues() можно отказаться, встроив его тело в цикл:

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

Здесь случается лавинообразный процесс: вместе с методом createValues() исчезают инструкции чтения полей элементов перечисления, становятся ненужными записи типа Fieldref для этих полей, а значит и записи типа NameAndType для записей типа Fieldref. В пуле констант высвобождается 2 * <Количество элементов в перечислении> слотов, которые можно использовать для декларации дополнительных элементов перечисления.

Но не всё так радужно, тесты показывают значительную просадку производительности: инициализация класса перечисления с 65 тысячами элементов занимает немыслимые полторы минуты. Как довольно быстро выяснилось, «рефлекшн тормозит».

Реализация Class::getDeclaredField() в OpenJDK имеет линейную асимптотику от числа полей в классе, а наш блок инициализации из-за этого — квадратичную.

Добавление кеширования несколько улучшает ситуацию, хоть и не решает её полностью:

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

Описанный в данной главе небезопасный подход позволяет создавать перечисления с количеством элементов до 65_410, что почти в 24 раза больше результата, достижимого при помощи javac и довольно близко к теоретическому пределу в 65_505 элементов, вычисленному нами в предыдущей публикации цикла.


Проверяем работоспособность


Для тестов возьмём самое большое перечисление, сгенерировав его при помощи команды java -jar HugeEnumGen.jar -a Unsafe UnsafeHugeEnum. В результате получим class-файл размером в 2 мегабайта и 65_410 элементов.

Создадим новый Java-проект в IDEA и добавим сгенерированный класс в качестве внешней библиотеки.

Практически сразу становится заметно, что IDEA не готова к подобному стресс-тесту:



Автодополнение элемента перечисления занимает десятки секунд как на древнем мобильном i5, так и на более современном i7 8700K. А если попробовать при помощи quick fix добавить в switch недостающие элементы, то IDEA перестаёт даже перерисовывать окна. Подозреваю, что временно, но дождаться завершения не удалось. Отзывчивость во время отладки также оставляет желать лучшего.

Начнём с небольшого количества элементов в 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;
        }
    }

}

Здесь никаких сюрпризов, компиляция и запуск проходят штатно:

$ 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

Что насчёт большего количества элементов в switch? Можем мы, к примеру, обработать в одном switch сразу все наши 65 тысяч элементов?

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

Увы, но нет. При попытке компиляции мы получим целую пачку сообщений об ошибках:

$ 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 и switch


Для понимания происходящего нам предстоит разобраться в том, как происходит трансляция switch по элементам перечисления.

В спецификации JVM есть отдельная глава JVMS11 §3.10 Compiling Switches, рекомендации которой сводятся к тому, что для компиляции оператора switch следует использовать одну из двух инструкций байткода, — tableswitch или lookupswitch. Никаких упоминаний switch по строкам или элементам перечисления мы в этой главе не найдём.

Лучшая документация — это код, так что самое время погрузиться в исходники javac.

Выбор между tableswitch и lookupswitch происходит в Gen::visitSwitch() и зависит от числа вариантов в switch. В большинстве случаев выигрывает 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;

Заголовок tableswitch занимает примерно 16 байтов плюс по 4 байта на каждое значение. Таким образом, в одном switch ни при каких условиях не может быть больше ( 65_535 - 16 ) / 4 = 16_379 элементов.

И действительно, после снижения количества веток case в теле switch до 16 тысяч остаётся только одна ошибка компиляции, самая загадочная:

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

В поисках источника ошибки вернёмся чуть раньше, на стадию избавления от синтаксического сахара. За трансляцию switch отвечают методы visitEnumSwitch(), mapForEnum() и класс EnumMapping в Lower.java.

Там же обнаруживаем и небольшой документирующий комментарий:

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.
 */


Таинственный try оказывается частью автоматически сгенерированного вспомогательного класса TestAll$0. Внутри — декларация статического массива и код для его инициализации.

Массив фиксирует соответствие между именами элементов перечисления и назаченными им при компиляции switch числовыми значениями, тем самым защищая скомпилированный код от пагубного влияния рефакторинга.

При переупорядочивании, добавлении новых или удалении уже существующих элементов перечисления у части из них может измениться значение ordinal() и именно от этого защищает дополнительный уровень косвенности.

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

Код инициализации бесхитростен и расходует от 15 до 17 байтов на каждый элемент. В результате блок статической инициализации вмещает инициализацию не более чем 3_862 элементов. Это число и оказывается максимальным количеством элементов перечисления, которые мы можем использовать в одном switch при текущей реализации javac.


Заключение


Мы увидели, что применение даже такого простейшего приёма, как выделение создания элементов перечисления и инициализации массива $VALUES в отдельный метод позволяет увеличить максимальное количество элементов в перечислении с 2_746 до 10_920.

Результаты constant dynamic на фоне предыдущих достижений выглядят не особо впечатляюще и позволяют получить всего лишь на 43 элемента больше, зато при таком подходе гораздо изящнее получается добавить новые свойства в перечисление — достаточно модифицировать конструктор и передать ему нужные значения через статические параметры динамической константы.

Если когда-нибудь в будущем аттрибут ConstantValue научат понимать динамические константы, то это число может возрасти с 10 тысяч до 16.

Использование sun.misc.Unsafe позволяет сделать гигантский скачок и увеличить максимальное количество элементов до 65_410. Но не стоит забывать про то, что Unsafe это проприетарное API, которое со временем может исчезнуть и его использование — немалый риск, о чём прямо предупреждает javac:

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

Но, как оказалось, недостаточно сгенерировать гигантское перечисление, нужно ещё и суметь им воспользоваться.

На сегодняшний момент есть проблемы с поддержкой таких перечислений как со стороны IDE, так и на уровне компилятора Java.

Большое количество полей в классе может ухудшать отзывчивость IDE как во время редактирования, так и во время отладки. Иногда вплоть до полного зависания.

Ограничения, налагаемые форматом class-файлов и детали реализации javac приводят к невозможности использования в коде switch более 3_862 элементов одновременно. Из положительных моментов стоит упомянуть, что это могут быть произвольные 3_862 элемента.

Дальнейшее улучшение результатов возможно только через доработку компилятора Java, но это уже совершенно другая история.


Дополнительные материалы


Исходный код на GitHub: https://github.com/Maccimo/HugeEnumGeneratorArticle

Собранный JAR-файл: https://github.com/Maccimo/HugeEnumGeneratorArticle/releases/tag/v1.0

Справка по поддерживаемым параметрам запуска

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


Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 7

    0
    Можно построить валидный enum из 21200 констант, причём средствами чистой Java 5, безо всяких Unsafe и ConstantDynamic. Пруф.

    Довольно интересная задача. Когда вы в прошлой части упомянули теоретический максимум в ~21K элементов, я ожидал в этой части увидеть, как вы его будете достигать ¯\_(ツ)_/¯
      0

      Трюк с инициализацией через конечный автомат — красиво, снимаю шляпу!
      Слегка доработав можно даже не автогенерированные "C" + index, а произвольные имена элементам перечисления дать, по аналогии с Unsafe вариантом.

        0
        Ещё пара трюков, и вот уже 21391 константа: LargeEnum.class. Можно ли больше?
          0
          21455 получил. Пожалуй, на этом пора остановиться.
    0
    Обработку следующих 60 000 значений можно вынести в следующий метод?
      +1

      Перечисление с более, чем примерно 65 000 элементов создать не получится, подробнее про это было в первой части.


      Разбить один switch () на несколько в разных методах и обрабатывать отдельные поддиапазоны значений можно, но тут понадобится доработка компилятора. Сейчас инициализация вспомогательного массива для switch сделана не самым оптимальным образом, см. главу «Javac и switch».

    Only users with full accounts can post comments. Log in, please.