JEP draft: Classifier API to Map Finite Sets to Indexes

ЧЕРНОВОЙ ВАРИАНТ

Аннотация

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

Цели

• Ускорить многие задачи поиска, которые сейчас опираются на поиск по таблице, двоичный поиск, switch или деревья решений.

• Создать основу для постоянного повышения скорости выполнения операторов switch без перекомпиляции.

Мотивация

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

Это можно назвать задачей классификации, а конкретный алгоритм для конкретного множества альтернативных значений — классификатором.

С логической точки зрения получаемый индекс — целое число, хотя его можно «нарядить» в перечисление или другой токен. Для любого фиксированного множества альтернативных значений множество возможных индексов соответствует диапазону 0..N-1, где N — число альтернативных значений. Некоторое сигнальное значение, например -1 (или любое отрицательное число), зарезервировано, чтобы сообщать о значении (оговорённого типа T), которого нет в заданном множестве.

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

Но когда нужна скорость, линейного поиска недостаточно. Иногда подходит двоичный поиск, или какой-нибудь хитрый поиск по таблице на основе хешей или поразрядного разбиения, или может подойти оператор или выражение switch в Java. Выбор между этими вариантами (и не только!) зависит от особенностей T и от конкретных альтернативных значений, которые нужно различать.

В общем случае трудно понять, какую тактику выбрать, чтобы построить хороший классификатор для данной задачи классификации. Хуже того, лучшие тактики (например, идеальное хеширование) невозможно сопровождать. Если вы потратите час на поиск идеальной хеш-функции для какого-то конкретного входного множества, через год тому, кто сопровождает код, может понадобиться несколько дней, чтобы разобраться, что вы сделали. В результате вручную оптимизируют до максимальной скорости только код для самых требовательных применений, мирясь с более высокими затратами на сопровождение.

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

В Java среди списков можно разглядеть скрывающиеся простые объекты-классификаторы:

interface Classifier<T> { int indexOf(T value); }
Classifier<String> cfr1 = List.of("no", "yes")::indexOf;
System.out.println(cfr1.indexOf("yes"));   //=> 1
System.out.println(cfr1.indexOf("no"));    //=> 0
System.out.println(cfr1.indexOf("maybe")); //=> -1

Но так их используют редко, поскольку List::indexOf выполняет линейный поиск. Если линейный поиск — единственный вариант, нет никакой пользы в том, чтобы выделять специальный интерфейс Classifier.

Есть классификатор, скрытый и в API Enum, — специально для множества значений каждого перечисления:

enum Suit { CLUB, SPADE, HEART, DIAMOND }
Classifier<Suit> ecfr = Suit::ordinal;
System.out.println(ecfr.indexOf(Suit.HEART)); //=> 2

Этот классификатор очень быстрый, но работает, только если вам нужно всё перечисление, причём в заданном в нём порядке. Заметим, что это пример классификатора, который тотален на своём входном типе T.

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

Описание

Мы вводим интерфейс Classifier<T> и связанные с ним фабрики и bootstrap-методы. Согласно контракту интерфейса, экземпляры могут быть оптимизированы до производительности, которая, как правило, превосходит линейный поиск, не уступает большинству ручных приёмов, а часто и превосходит их.

С классификаторами из JDK программисты могут решать свои задачи классификации на полной скорости, не беспокоясь о том, чтобы выносить на поверхность сложные подробности оптимального алгоритма. JIT и JDK можно проектировать совместно, чтобы каждый классификатор использовал внутренний алгоритм, эффективный на той конкретной платформе, на которой работает JVM.

Приведённый выше классификатор «да/нет» можно запросить так:

var cfr2 = Classifier.of(String.class, List.of("no", "yes"));
System.out.println(cfr2.indexOf("yes")); => 1
System.out.println(cfr2.indexOf("no")); => 0
System.out.println(cfr2.indexOf("maybe")); => -1

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

var cfr3 = (Classifier<String>) s ->
  switch (s.length()) {
  case 2 -> (s.equals("no") ? 0 : -1);
  case 3 -> (s.equals("yes") ? 1 : -1);
  default -> -1;
  };

Явный switch по значению перечисления можно записать так:

private static final Classifier<Suit>
  ECLS = EnumClassifier.of(Suit.class, Suit.HEART, Suit.CLUB);
…
switch (ECLS.indexOf(e)) {
case 0 -> foo();  //case HEART
case 1 -> bar();  //case CLUB
}

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

(Ещё несколько примеров есть в этом файле с демонстрационным кодом.)

Такие перестройки больше не придётся делать вручную, в формах, которые может быть трудно сопровождать. С Classifier API эти подробности прозрачно берут на себя JDK (и JIT во взаимодействии с JDK).

Зоопарк классификаторов

Помимо типов T (и I, который равен int), в API классификаторов есть ещё несколько интересных степеней свободы. Во-первых, если пользователь требует определённой нумерации вариантов, альтернативные значения должны быть представлены в виде списка. Это полезно, когда номер соответствует какому-либо внешнему API или жёстко закодированному оператору switch.

Но если у пользователя нет твёрдого мнения о том, каким значениям какие индексы соответствуют, значения представляются в виде множества, которое по своей природе неупорядочено. Результат получается похожим на идеальную хеш-таблицу: каждое значение получает индекс, но какое значение попадёт в первую ячейку таблицы и т. д., решает внутренний алгоритм. При необходимости это будет выражено точкой API вида Classifier::ofSet. Это эквивалентно построению идеальной хеш-таблицы, и здесь может пригодиться дополнительный параметр, допускающий пропуски в множестве индексов (полуидеальные хеши, которые проще вывести).

Иногда также имеет смысл использовать ключи отображения как источник альтернативных значений — в тех особых случаях, когда пользователь хочет, чтобы два значения отображались в один индекс. Если два ключа отображаются в одно и то же значение хеш-таблицы, классификатор на основе отображения позаботится о том, чтобы присвоить обоим ключам один и тот же индекс. Такой классификатор на основе отображения можно сразу использовать для создания константного отображения, производительность и расход памяти которого могут превзойти обычное отображение. Получаемые индексы задавались бы значениями (а не ключами) таблицы — в виде списка или множества. При необходимости это будет выражено точкой API вида Classifier::ofMap с необязательными параметрами, управляющими тем, как индексируются значения отображения.

Ещё одна степень свободы — объём усилий, затрачиваемых на поиск эффективной внутренней организации логики классификации. Использовать ли хеш-коды, и даже идеальное хеширование? Есть ли у типа значения (T) какой-то компонент, который оказывается различным у всех альтернатив, чтобы можно было выполнить switch по нему? Генерировать ли статические таблицы? Нужно ли дерево решений логарифмической глубины?

Ответ зависит от того, какое множество альтернативных значений классифицируется (и от типа T), а также от того, сколько усилий пользователь готов потратить на поиск хорошего алгоритма. При выполнении оператора switch из исходного кода на Java небольшая задержка (во время связывания), скорее всего, — полезное вложение в будущую производительность. Но если множество значений недолговечно и в будущем к нему будет лишь несколько запросов, дополнительное время на оптимизацию не принесёт пользы. У некоторых продвинутых алгоритмов классификации (например, тех, которым заведомо требуется идеальное хеширование) может быть необязательный параметр «усилие», передающий пожелания пользователя.

Могут существовать специализированные фабрики классификаторов, рассчитанные на использование определённых техник. Однако для большинства применений предпочтительна обобщённая точка API Classifier::of, как показано выше, поскольку она вольна использовать любую внутреннюю технику, которая кажется лучшей для конкретного множества значений и аппаратной платформы.

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

Некоторым классификаторам могут быть приданы счётчики вызовов или статистика возвращаемых значений, чтобы после сбора статистики они могли прозрачно переоптимизировать себя. Switch, построенные на таких классификаторах, во многих случаях превосходили бы по производительности нынешние.

Чтобы классификаторы было проще комбинировать или чтобы повысить их прозрачность для других целей, возможно, будет определён более информативный подынтерфейс:

interface Classifier<T> { int indexOf(T value); }
interface ClassifierInfo<T> { Class<T> valueClass(); List<T> values(); }
interface InformativeClassifier<T> extends Classifier<T> {
  ClassifierInfo<T> classifierInfo();
}

(Из-за связи с bootstrap-методами этот JEP изначально размещён в java.lang.invoke. Как структура данных, родственная списку, он целиком или частично может относиться к java.util.)