Часть первая, теоретическая | Часть вторая, практическая
По мотивам твита от Evgeny Mandrikov aka godin:
В нём он задаётся вопросом, какое максимальное количество значений может быть определено в перечислении (enum) в Java. После ряда экспериментов и применения чёрной магии ConstantDynamic (JEP 309) автор вопроса приходит к числу 8191.
В серии из двух статей поищем теоретические пределы числа элементов в перечислении, попробуем к ним приблизиться на практике и попутно выясним, чем может помочь JEP 309.
Рекогносцировка
Обзорная глава, в которой мы впервые видим перечисление дизассемблированным.
Для начала посмотрим, во что транслируется следующее перечисление:
public enum FizzBuzz {
Fizz,
Buzz,
FizzBuzz;
}
После компиляции и дизассемблирования:
Classfile /dev/null/FizzBuzz.class
Last modified 32 дек. 2019 г.; size 903 bytes
MD5 checksum add0af79de3e9a70a7bbf7d57dd0cfe7
Compiled from "FizzBuzz.java"
public final class FizzBuzz extends java.lang.Enum<FizzBuzz>
minor version: 0
major version: 58
flags: (0x4031) ACC_PUBLIC, ACC_FINAL, ACC_SUPER, ACC_ENUM
this_class: #2 // FizzBuzz
super_class: #13 // java/lang/Enum
interfaces: 0, fields: 4, methods: 4, attributes: 2
Constant pool:
#1 = Fieldref #2.#3 // FizzBuzz.$VALUES:[LFizzBuzz;
#2 = Class #4 // FizzBuzz
#3 = NameAndType #5:#6 // $VALUES:[LFizzBuzz;
#4 = Utf8 FizzBuzz
#5 = Utf8 $VALUES
#6 = Utf8 [LFizzBuzz;
#7 = Methodref #8.#9 // "[LFizzBuzz;".clone:()Ljava/lang/Object;
#8 = Class #6 // "[LFizzBuzz;"
#9 = NameAndType #10:#11 // clone:()Ljava/lang/Object;
#10 = Utf8 clone
#11 = Utf8 ()Ljava/lang/Object;
#12 = Methodref #13.#14 // java/lang/Enum.valueOf:(Ljava/lang/Class;Ljava/lang/String;)Ljava/lang/Enum;
#13 = Class #15 // java/lang/Enum
#14 = NameAndType #16:#17 // valueOf:(Ljava/lang/Class;Ljava/lang/String;)Ljava/lang/Enum;
#15 = Utf8 java/lang/Enum
#16 = Utf8 valueOf
#17 = Utf8 (Ljava/lang/Class;Ljava/lang/String;)Ljava/lang/Enum;
#18 = Methodref #13.#19 // java/lang/Enum."<init>":(Ljava/lang/String;I)V
#19 = NameAndType #20:#21 // "<init>":(Ljava/lang/String;I)V
#20 = Utf8 <init>
#21 = Utf8 (Ljava/lang/String;I)V
#22 = String #23 // Fizz
#23 = Utf8 Fizz
#24 = Methodref #2.#19 // FizzBuzz."<init>":(Ljava/lang/String;I)V
#25 = Fieldref #2.#26 // FizzBuzz.Fizz:LFizzBuzz;
#26 = NameAndType #23:#27 // Fizz:LFizzBuzz;
#27 = Utf8 LFizzBuzz;
#28 = String #29 // Buzz
#29 = Utf8 Buzz
#30 = Fieldref #2.#31 // FizzBuzz.Buzz:LFizzBuzz;
#31 = NameAndType #29:#27 // Buzz:LFizzBuzz;
#32 = String #4 // FizzBuzz
#33 = Fieldref #2.#34 // FizzBuzz.FizzBuzz:LFizzBuzz;
#34 = NameAndType #4:#27 // FizzBuzz:LFizzBuzz;
#35 = Utf8 values
#36 = Utf8 ()[LFizzBuzz;
#37 = Utf8 Code
#38 = Utf8 LineNumberTable
#39 = Utf8 (Ljava/lang/String;)LFizzBuzz;
#40 = Utf8 LocalVariableTable
#41 = Utf8 name
#42 = Utf8 Ljava/lang/String;
#43 = Utf8 this
#44 = Utf8 Signature
#45 = Utf8 ()V
#46 = Utf8 <clinit>
#47 = Utf8 Ljava/lang/Enum<LFizzBuzz;>;
#48 = Utf8 SourceFile
#49 = Utf8 FizzBuzz.java
{
public static final FizzBuzz Fizz;
descriptor: LFizzBuzz;
flags: (0x4019) ACC_PUBLIC, ACC_STATIC, ACC_FINAL, ACC_ENUM
public static final FizzBuzz Buzz;
descriptor: LFizzBuzz;
flags: (0x4019) ACC_PUBLIC, ACC_STATIC, ACC_FINAL, ACC_ENUM
public static final FizzBuzz FizzBuzz;
descriptor: LFizzBuzz;
flags: (0x4019) ACC_PUBLIC, ACC_STATIC, ACC_FINAL, ACC_ENUM
private static final FizzBuzz[] $VALUES;
descriptor: [LFizzBuzz;
flags: (0x101a) ACC_PRIVATE, ACC_STATIC, ACC_FINAL, ACC_SYNTHETIC
public static FizzBuzz[] values();
descriptor: ()[LFizzBuzz;
flags: (0x0009) ACC_PUBLIC, ACC_STATIC
Code:
stack=1, locals=0, args_size=0
0: getstatic #1 // Field $VALUES:[LFizzBuzz;
3: invokevirtual #7 // Method "[LFizzBuzz;".clone:()Ljava/lang/Object;
6: checkcast #8 // class "[LFizzBuzz;"
9: areturn
LineNumberTable:
line 1: 0
public static FizzBuzz valueOf(java.lang.String);
descriptor: (Ljava/lang/String;)LFizzBuzz;
flags: (0x0009) ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=1, args_size=1
0: ldc #2 // class FizzBuzz
2: aload_0
3: invokestatic #12 // Method java/lang/Enum.valueOf:(Ljava/lang/Class;Ljava/lang/String;)Ljava/lang/Enum;
6: checkcast #2 // class FizzBuzz
9: areturn
LineNumberTable:
line 1: 0
LocalVariableTable:
Start Length Slot Name Signature
0 10 0 name Ljava/lang/String;
private FizzBuzz();
descriptor: (Ljava/lang/String;I)V
flags: (0x0002) ACC_PRIVATE
Code:
stack=3, locals=3, args_size=3
0: aload_0
1: aload_1
2: iload_2
3: invokespecial #18 // Method java/lang/Enum."<init>":(Ljava/lang/String;I)V
6: return
LineNumberTable:
line 1: 0
LocalVariableTable:
Start Length Slot Name Signature
0 7 0 this LFizzBuzz;
Signature: #45 // ()V
static {};
descriptor: ()V
flags: (0x0008) ACC_STATIC
Code:
stack=4, locals=0, args_size=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;
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;
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;
39: iconst_3
40: anewarray #2 // class FizzBuzz
43: dup
44: iconst_0
45: getstatic #25 // Field Fizz:LFizzBuzz;
48: aastore
49: dup
50: iconst_1
51: getstatic #30 // Field Buzz:LFizzBuzz;
54: aastore
55: dup
56: iconst_2
57: getstatic #33 // Field FizzBuzz:LFizzBuzz;
60: aastore
61: putstatic #1 // Field $VALUES:[LFizzBuzz;
64: return
LineNumberTable:
line 3: 0
line 5: 13
line 7: 26
line 1: 39
}
Signature: #47 // Ljava/lang/Enum<LFizzBuzz;>;
SourceFile: "FizzBuzz.java"
В листинге нас встречают
— По одному public static final полю для каждого значения, определённого в перечислении
— Приватное синтетическое поле $VALUES, деталь реализации метода values()
— Реализация методов values() и valueOf()
— Приватный конструктор
— Блок статической инициализации, где собственно и происходит всё самое интересное. Рассмотрим его подробнее.
В виде java-кода последний выглядит примерно так:
static {
Fizz = new FizzBuzz("Fizz", 0);
Buzz = new FizzBuzz("Buzz", 1);
FizzBuzz = new FizzBuzz("FizzBuzz", 2);
$VALUES = new FizzBuzz[] {
Fizz,
Buzz,
FizzBuzz
};
}
Вначале создаются экземпляры элементов перечисления. Созданные экземпляры немедленно записываются в соответствующие public static final поля.
Затем создаётся и заполняется массив со ссылками на экземпляры всех элементы перечисления. Ссылки достаются из полей класса, которые мы инициализировали абзацем выше. Заполненный массив сохраняется в private static final поле $VALUES.
После этого перечисление готово к работе.
Бутылочное горлышко
Скучная глава, в которой мы ищем ограничения на количество элементов перечисления.
Начать поиски можно с главы JLS §8.9.3 «Enum Members»:
The members of an enum type E are all of the following:
…
* For each enum constant c declared in the body of the declaration of E, E has
an implicitly declared public static final field of type E that has the same
name as c. The field has a variable initializer which instantiates E and passes any
arguments of c to the constructor chosen for E. The field has the same annotations
as c (if any).These fields are implicitly declared in the same order as the corresponding
enum constants, before any static fields explicitly declared in the body of the
declaration of E.
…
* The following implicitly declared methods:/** * Returns an array containing the constants of this enum * type, in the order they're declared. This method may be * used to iterate over the constants as follows: * * for(E c : E.values()) * System.out.println(c); * * @return an array containing the constants of this enum * type, in the order they're declared */ public static E[] values(); /** * Returns the enum constant of this type with the specified * name. * The string must match exactly an identifier used to declare * an enum constant in this type. (Extraneous whitespace * characters are not permitted.) * * @return the enum constant with the specified name * @throws IllegalArgumentException if this enum type has no * constant with the specified name */ public static E valueOf(String name);
Итак, у каждого класса-перечисления есть метод values(), который возвращает массив со всеми объявленными в данном перечислении элементами. Из этого следует, что сферическое перечисление в вакууме не может содержать более Integer.MAX_VALUE + 1 элементов.
Движемся дальше. Перечисления в Java представляются в виде наследников класса java.lang.Enum, а следовательно на них распространяются все ограничения, присущие классам в JVM.
Посмотрим на высокоуровневое описание структуры class-файла, приведённое в JVMS §4.1 «The ClassFile Structure»:
ClassFile {
u4 magic;
u2 minor_version;
u2 major_version;
u2 constant_pool_count;
cp_info constant_pool[constant_pool_count-1];
u2 access_flags;
u2 this_class;
u2 super_class;
u2 interfaces_count;
u2 interfaces[interfaces_count];
u2 fields_count;
field_info fields[fields_count];
u2 methods_count;
method_info methods[methods_count];
u2 attributes_count;
attribute_info attributes[attributes_count];
}
Как мы уже знаем из JLS §8.9.3, для каждого элемента перечисления в результирующем классе создаётся одноимённое поле. Число полей в классе задаёт 16-битное беззнаковое fields_count, что ограничивает нас 65_535 полями в одном class-файле или 65_534 элементами перечисления. Одно поле зарезервировано под массив $VALUES, клон которого возвращает метод values(). Это не прописано явно в спецификации, но вряд ли получится придумать более изящное решение.
Имена полей, методов, классов, константные значения и многое другое хранится в пуле констант.
Если вы совсем ничего не знаете про внутреннее устройство пула констант, рекомендую почитать древнюю статью от lany. Не смотря на то, что с момента её написания в пуле констант появилось много нового и интересного, основные принципы остаются неизменными.
Размер пула констант класса ограничен также числом в 65_535 элементов. Пул констант корректно сформированного класса никогда не бывает пуст. Как минимум, там будет имя этого класса.
К примеру, пул констант класса пустого перечисления, скомпилированный javac из OpenJDK 14-ea+29 без отладочной информации содержит 29 вхождений.
Из этого следует, что число в 65_534 элемента в одном перечислении также недостижимо. В лучшем случае можем рассчитывать на 65_505 или близкое к этому число.
Последний аккод в этом затянувшемся вступлении:
Записать значение в static final поле можно только в блоке статической инициализации, который на уровне class-файла представлен методом с именем <clinit>. Байткод любого метода при этом не может занимать более 65_535 байтов. Знакомое число, не правда ли?
Одна инструкция записи в статическое поле putstatic занимает 3 байта, что даёт нам грубую оценку в 65_535 / 3 = 21_845. На самом деле эта оценка завышена. Значение для записи в поле инструкция берёт с вершины стека, которое туда поместила одна из предыдущих инструкций. И эта инструкция тоже занимает драгоценные байты. Но даже если не принимать это во внимание, полученное число всё равно значительно меньше 65_505.
Резюмируя:
— Формат class-файла ограничивает максимальное число элементов перечисления примерно 65_505
— Механизм инициализации static final полей ограничивает нас ещё сильнее. Теоретически — до 21_845 элементов максимум, на практике это число ещё меньше
В заключительной статье цикла займёмся нездоровой оптимизацией и генерацией class-файлов.
Автор: Maccimo
