По мотивам твита от Evgeny Mandrikov aka godin:
В нём он задаётся вопросом, какое максимальное количество значений может быть определено в перечислении (
enum) в Java. После ряда экспериментов и применения чёрной магии ConstantDynamic (JEP 309) автор вопроса приходит к числу 8191.В серии из двух статей поищем теоретические пределы числа элементов в перечислении, попробуем к ним приблизиться на практике и попутно выясним, чем может помочь JEP 309.
Рекогносцировка
Обзорная глава, в которой мы впервые видим перечисление дизассемблированным.
Для начала посмотрим, во что транслируется следующее перечисление:
public enum FizzBuzz {
Fizz,
Buzz,
FizzBuzz;
}
После компиляции и дизассемблирования:
javap -c -s -p -v FizzBuzz.class
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»:
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-файлов.
Комментарии (25)
Deosis
10.01.2020 07:27Судя по листингу, на инициализацию одного поля уходит 13 байт инструкций и ещё 6 байт на заполнение массива. Поэтому больше 3500 значений не должно быть, если только компилятор не генерирует другой код для больших перечислений.
Maccimo Автор
10.01.2020 09:11Зависимость от количества элементов не совсем линейна, небольшой спойлер из второй части:
javac из OpenJDK 14-ea+29 сдаётся намного раньше, на 2_746 элементах
kursornn
10.01.2020 12:08Интересное исследование =) Хотя кому на практике понадобится 20к значений в ENUM?
foal
10.01.2020 14:40Мне однажды понадобилось. И да — кодегенератор (метаинформация по библиотеки иконек). В моём случае, количество констант оказалось ограниченно именно размером сгенерёного класса.
lany
10.01.2020 15:48+1После установления точной границы интересное предложение исследования — сделать хотя бы один свитч по этому енаму. Хоть бы и пустой. Сработает? Или придётся лимит ещё снижать?
lgorSL
10.01.2020 23:18Для каждого свича делать свой анонимный класс)
А вместо кода в ветках вызывать методы родительского класса — их вполне может быть 8к.
Maccimo Автор
11.01.2020 04:00Один
switchсо всеми элементами?
Так-то можно обрабатывать фрагментами, помещая в веткуdefaultвызов метода с обработкой следующего фрагмента.
С ходу можно прикинуть:
Пропусков у
ordinal()нет, заголовок уtableswitchзанимает ~16 байтов, дальше — по 4 байта на каждый вариант. Плюс, как минимум,aload_<n>иinvokevirtual OurEnum::ordinal()в начале иreturnв конце.
(65_535 - 16 - 1 - 1 - 3) / 4 ~ 16_378элементов, дальше будетCode too large.
Интрига в том, сможем ли мы дойти до этого числа.lany
11.01.2020 06:03Нет-нет, один пустой свитч :-) А чего ты гадаешь вообще? Кодогенератор тривиально написать и установить граница экспериментально.
Maccimo Автор
11.01.2020 08:18В уме посчитать обычно проще и быстрее, чем эмпирические опыты проводить.
Проверка на работоспособность, безусловно, будет. Неработающий код нам не нужен.
reforms
11.01.2020 10:16В 2017 году мне тоже был интересен этот вопрос, тогда я решил задачу в лоб с помощью кодогенерации и проверил эмпирически для java7. Статья на хабре здесь — ответ в секции Эксперимент. У меня получилось
столько2746Maccimo Автор
13.01.2020 12:51На уровне javac со времён Java 7 в компиляции перечислений ничего не изменилось, javac из OpenJDK 14 по-прежнему поддерживает не больше
2_746 элементов в перечислении.
Тем интереснее искать теоретически достижимый максимум.
blueboar2
Я немного не понимаю, если «автор вопроса приходит к числу 8191», то почему у нас получилось ~20000? Кто-то не прав?
gudvinr
С чего вы взяли что около 20000? 8192 это все же до 21845, так что в принципе друг другу эти заключения не противоречат
blueboar2
Не противоречат. Просто человек вдался в такие подробности, и дошел до <21845, и остановился, но при этом он знает, что есть какие-то данные о более точном числе — 8191. Это странно как-то же. Надо было рассмотреть те аргументы, и уточнить еще больше, если это возможно.
Maccimo Автор
21_845 это оценка сверху при следующих допущениях:
putstaticstatic finalполе нетПервое утверждение неверно, как и указано в статье:
Как дело обстоит со вторым пунктом сейчас и в вероятном будущем — узнаете из заключительной статьи цикла.
Число 8_191 у автора твита получилось после дополнительных оптимизаций, которые не делает
javac.gudvinr
С чего вы взяли что около 20000? 8192 это все же до 21845, так что в принципе друг другу эти заключения не противоречат
gudvinr
С чего вы взяли что около 20000? 8192 это все же до 21845, так что в принципе друг другу эти заключения не противоречат
osmanpasha
Наверное, об этом будет часть 2