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


По мотивам твита от 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)


  1. blueboar2
    10.01.2020 07:13
    +1

    Я немного не понимаю, если «автор вопроса приходит к числу 8191», то почему у нас получилось ~20000? Кто-то не прав?


    1. gudvinr
      10.01.2020 08:37
      +2

      Теоретически — до 21_845 элементов максимум, на практике это число ещё меньше

      С чего вы взяли что около 20000? 8192 это все же до 21845, так что в принципе друг другу эти заключения не противоречат


      1. blueboar2
        10.01.2020 10:16

        Не противоречат. Просто человек вдался в такие подробности, и дошел до <21845, и остановился, но при этом он знает, что есть какие-то данные о более точном числе — 8191. Это странно как-то же. Надо было рассмотреть те аргументы, и уточнить еще больше, если это возможно.


    1. Maccimo Автор
      10.01.2020 08:52

      21_845 это оценка сверху при следующих допущениях:


      • Для полной инициализации одного элемента перечисления нужна только инструкции putstatic
      • Более выгодного по размеру кода способа инициализировать static final поле нет

      Первое утверждение неверно, как и указано в статье:


      На самом деле эта оценка завышена. Значение для записи в поле инструкция берёт с вершины стека, которое туда поместила одна из предыдущих инструкций. И эта инструкция тоже занимает драгоценные байты.

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


      Число 8_191 у автора твита получилось после дополнительных оптимизаций, которые не делает javac.


    1. gudvinr
      10.01.2020 08:39

      Теоретически — до 21_845 элементов максимум, на практике это число ещё меньше

      С чего вы взяли что около 20000? 8192 это все же до 21845, так что в принципе друг другу эти заключения не противоречат


    1. gudvinr
      10.01.2020 08:39

      Теоретически — до 21_845 элементов максимум, на практике это число ещё меньше

      С чего вы взяли что около 20000? 8192 это все же до 21845, так что в принципе друг другу эти заключения не противоречат


    1. osmanpasha
      10.01.2020 20:03

      Наверное, об этом будет часть 2


  1. Deosis
    10.01.2020 07:27

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


    1. Maccimo Автор
      10.01.2020 09:11

      Зависимость от количества элементов не совсем линейна, небольшой спойлер из второй части:


      javac из OpenJDK 14-ea+29 сдаётся намного раньше, на 2_746 элементах


  1. kursornn
    10.01.2020 12:08

    Интересное исследование =) Хотя кому на практике понадобится 20к значений в ENUM?


    1. Borz
      10.01.2020 14:19

      всяким кодогенераторам в каких-то уж очень вычурных реализациях?


    1. foal
      10.01.2020 14:40

      Мне однажды понадобилось. И да — кодегенератор (метаинформация по библиотеки иконек). В моём случае, количество констант оказалось ограниченно именно размером сгенерёного класса.


    1. vsergoog
      10.01.2020 15:14

      В сях, в различных драйверах и поболее встречалось.


  1. lany
    10.01.2020 15:48
    +1

    После установления точной границы интересное предложение исследования — сделать хотя бы один свитч по этому енаму. Хоть бы и пустой. Сработает? Или придётся лимит ещё снижать?


    1. lgorSL
      10.01.2020 23:18

      Для каждого свича делать свой анонимный класс)
      А вместо кода в ветках вызывать методы родительского класса — их вполне может быть 8к.


    1. 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.
      Интрига в том, сможем ли мы дойти до этого числа.


      1. lany
        11.01.2020 06:03

        Нет-нет, один пустой свитч :-) А чего ты гадаешь вообще? Кодогенератор тривиально написать и установить граница экспериментально.


        1. Maccimo Автор
          11.01.2020 08:18

          В уме посчитать обычно проще и быстрее, чем эмпирические опыты проводить.
          Проверка на работоспособность, безусловно, будет. Неработающий код нам не нужен.


  1. reforms
    11.01.2020 10:16

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

    столько
    2746


    1. Maccimo Автор
      13.01.2020 12:51

      На уровне javac со времён Java 7 в компиляции перечислений ничего не изменилось, javac из OpenJDK 14 по-прежнему поддерживает не больше
      2_746 элементов в перечислении.


      Тем интереснее искать теоретически достижимый максимум.