20 августа 2018 г.

Оценки квантилей распределений потока данных


Последнюю неделю копаю алгоритмы оценок для квантилей выборок. Началось все с префетчинга: есть хранилище данных на диске, часть из них кэшируется в памяти, и надо бы успевать кэшировать предварительно с такой скоростью, чтобы клиентам не приходилось ожидать ввода-вывода. Доступ последовательный, так что все сводится к вопросу "сколько страниц загрузить в текущем раунде упреждающего чтения". И обычно в таких случаях я вижу что-то вроде
int estimatePagesToPrefetch(...){
   return 4;//carefully chosen
}
Иногда (реже) что-то вроде
int estimatePagesToPrefetch(int pagesReadSinceLastPrefetch){
   return ema( pagesReadSinceLastPrefetch ) * 3/2; //150% is enough for everyone
}
И я сам так пишу, но в этот раз душа физика-теоретика захотела бОльшего: можно ли обойтись без с потолка взятых констант? Проблема с константами не только в том, что они непонятно откуда взялись (хотя многие да). Еще одна проблема, что непонятно даже, из каких соображений они взялись. Вот эти 4 страницы, или 150% от средней скорости использования — какого внешнего результата автор от них ожидал? По какому критерию он их выбрал (если вообще выбирал)?

Ну и я спросил себя: а по какому критерию я бы выбирал параметры префетчинга? Мне кажется, префетчинг должен с заданной вероятностью (90%, 95%, 99%...) опережать использование. Это критерий, понятный человеку, он легко пересчитывается в другие latency-oriented критерии. И чтобы его реализовать, нужно оценить соответствующий квантиль распределения величин pagesReadSinceLastPrefetch.

И я начал искать какой-нибудь простой и быстрый способ оценить n-ый квантиль распределения по потоку сэмплов из него. BigData сейчас в моде, так что статей обнаружилось много, но алгоритмы меня не порадовали:
  1. Cложные — не напишешь за 5 минут, если тебе вдруг понадобилось оценить 0.95-й квантиль.
  2. Cами по себе не приспосабливаются к нестационарному распределению: если распределение данных меняется со временем (а в реальных сценариях это почти всегда так), то приходится делать дополнительные усложнения
Но потом я наткнулся статью Frugal Streaming for Estimating Quantiles. И в ней излагаются два совершенно замечательных, очень экономных стохастических алгоритма оценки квантилей потока данных.

Замечательные они вот почему:
  1. Очень бережливо (frugal) относятся к памяти. Frugal1U использует для хранения состояния одну-единственную ячейку памяти (!), Frugal2U использует 2 ячейки + 1 бит. Строго говоря есть еще один конфигурационный параметр, да нужен генератор случайных чисел, у которого есть состояние, и неочевидно, считать ли это все "состоянием алгоритма", или относить к "общей памяти программы". Но даже в самом строгом варианте получается 3-4 ячейки памяти.
  2. Очень простые, как по количеству инструкций, так и когнитивно. Наверное, самое сложное, это поверить, что это вообще может работать, и понять, почему это может довольно хорошо работать. (Я потратил несколько вечеров, чтобы разобраться, почему они работают, и пару недель, пытаясь придумать что-то лучшее — и все еще особо не преуспел).
  3. Автоматически, безо всяких дополнительных усложнений, адаптируются к нестационарностям распределения
  4. Не используют никаких априорных предположений о виде распределения данных в потоке — только само определение квантиля. С одной стороны это недостаток: вкупе с ограничением по используемой памяти получается не очень быстрая сходимость и довольно большая погрешность. А с другой это дает очень высокую устойчивость: "смутить" алгоритм каким-то сложным распределением практически невозможно. Они как в том анекдоте: медленно спускаются с горы, и делают свою работу
Как я понял, авторы разрабатывали эти алгоритмы для чего-то вроде встраиваемых сенсоров, где память и вычислительная мощность очень ограничены, а поток данных может быть большим и зашумленным, и его нужно как-то предобработать, прежде чем выдавать наружу. Но мне кажется, что таким простым и устойчивым алгоритмам найдется применение и много где еще — хотя бы и для построения регуляторов/петель обратной связи.

Frugal1U

Идея алгоритма настолько проста, что кажется, тебя разыгрывают: пусть нужно оценить 50% квантиль (медиану). Медиана — это такое X, что элементы (сэмплы) из потока будут равновероятно оказываться как справа, так и слева от X. Если относительно X сэмплы с одной стороны выпадают чаще, чем с другой — значит X это не медиана, а настоящая медиана лежит как раз с той стороны, куда сэмплы попадают чаще. Так возьмем любое X за начальное приближение, выберем небольшой шаг step, и будем на каждый приходящий сэмпл обновлять X[i+1] -> X[i] +/- step, смотря в какую сторону от X попал текущий сэмпл. Статистически мы будем чаще делать шаг к медиане, чем от нее, так что рано или поздно мы до нее дошагаем, и дальше будем топтаться около.
step = 1
X    = 0   # initial estimation of median
for x in stream:
    if x > X:      
        X += step
    elif x < X: 
        X -= step
Ок, с медианой понятно (понятно же?). А если я хочу 0.9-квантиль? Значение 0.9 квантиля, X0.9, это такая величина, что элементы из потока данных будут с вероятностью 0.9 падать слева от него, и с вероятностью 0.1 справа. Тут авторы предлагают буквально "...выльем чайник на плиту и сведем задачу к предыдущей": давайте сгенерируем дополнительную булевую случайную величину, с "обратным" распределением (0.1 к 0.9), и скомбинируем ее с вероятностью попадания справа-слева (через AND). Для этой комбинированной случайной величины значение X0.9 будет как-бы-медианой, а медиану мы уже искать умеем:
step = 1
Q    = 0.9 # quantile we're about to estimate
Xq   = 0   # initial estimation of Q-th quantile
for x in stream:
    r = random()                   # r in [0,1]
    if x > Xq and r < Q:        # Prob(x > Xq)=0.1, Prob(r < Q) = 0.9
        Xq += step
    elif val < Xq and r > Q:    # Prob(x < Xq)=0.9, Prob(r > Q) = 0.1
        Xq -= step

(Без генератора случайных чисел можно и обойтись: достаточно заметить, что матожидание величины шага вправо будет 0.1*step, а влево 0.9*step. Если заменить "шаг step с вероятностью 0.1" на "шаг 0.1*step всегда", то алгоритм станет проще и ГСЧ будет не нужен. Странно, что авторы статьи не отметили такой возможности: в тестах, что я делал, оба алгоритма ведут себя практически неразличимо, и только при увеличении можно различить чуть разное поведение на уровне отдельных шагов. Мое предположение, что просто анализ такого алгоритма сложнее, и авторы не стали заморачиваться)


Алгоритм выглядит подозрительно просто, у меня сразу возникли два вопроса:
1. Как быстро он сходится?
2. Насколько стабильно?

Про скорость сходимости можно сразу заметить, что алгоритм двигает текущую оценку не более чем на step за итерацию. Так что если между текущей оценкой и истинным значением квантиля дистанция D, то алгоритм сойдется точно не раньше, чем за N=D/step шагов. Более аккуратный анализ (см статью) дает такую оценку: за не более чем $$N\frac{|ln(1-P)|}{e}$$ шагов алгоритм с вероятностью P хотя бы раз попадет в e-окрестность квантиля. Оценка отличается от N только на константу $$\frac{|ln(1-P)|}{e}$$, но константа эта довольно не маленькая: если хочется с вероятностью 90% попасть в 5% окрестность квантиля, то ждать придется "всего лишь" не больше чем N*|ln(1-0.9)|/0.05 =~ 46*N шагов.

Почему так медленно: пусть истинное значение квантиля Q это точка X. Алгоритм сейчас находится в точке X' которая является квантилем Q' (т.е $$Pr(x<X') = Q'$$). Тогда матожидание смещения на текущем шаге будет просто step*(Q'-Q). Конкретный закон эволюции матожидания отсюда не получишь — нужно знать вид функции распределения P(X) — но и по общему виду понятно, что приближение (матожидания) к истинному значению квантиля будет асимптотическим: чем ближе подходим, тем медленнее идем. Если бы надо было "дошагать" матожиданием, то ждать пришлось бы вообще бесконечно, но ближе к концу существенную роль начинает играть накопившийся статистический разброс вокруг среднего: за счет него ждать бесконечно долго нам почти наверняка не придется.

Теперь про стабильность: поскольку алгоритм статистический, то даже сойдясь к значению квантиля он не остановится, а будет продолжать топтаться вокруг. Насколько далеко вокруг?

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

Пусть δ это максимальное значение (дискретной) функции распределения элементов из потока (т.е. максимальная вероятность выпадения какого-то конкретного значения). Тогда вероятность того, что за N шагов алгоритм отклонится от квантиля Q больше, чем на ΔQ оценивается так:
$$Pr(|Q(N)-Q| > \Delta Q) <= N e^-\frac{(2\Delta Q)^2}{\delta}$$


Например: если в потоке 1000 разных равновероятных значений, то δ=1/1000, и если мы хотим ограничиться 5% отклонением от квантиля, то можем быть спокойны: за пределы 5% алгоритм вылезет не чаще, за 10000 шагов. А вот если потребовать 4% коридор, то за него мы будем вылезать уже за 300-400 шагов.

Мне обе оценки показались не очень интуитивны (особенно вторая). Так что я посчитал и численно смоделировал эволюцию распределения вероятностей результатов алгоритма по шагам. Для стабильного распределения входных данных алгоритм сходится к стабильному же распределению вокруг истинной медианы — т.е. дисперсия вырастет до какой-то величины, и дальше расти не будет. На графике результат симуляции для самого простого, равномерного распределения входных данных U[0..128), и шага в 1. Красным показана настоящая медиана (=64), синим — наиболее вероятный результат алгоритма, а пунктир очерчивает интервал, в который алгоритм попадет с 90% вероятностью.


Видно, что наиболее вероятное значение даже после 400 шагов все еще отличается от настоящей медианы, а вот верхняя граница 90% интервала пересекла медиану уже на 120 шаге. На следующем графике — вероятность достижения медианы к шагу N:


Т.е. минимально мы могли бы дошагать до медианы за 64 шага, но с вероятностью 20% дошагаем только к 120-му шагу, с вероятностью 60% к 150, а к 200-му шагу уже почти наверняка дошагаем. Сильно лучше, чем показывает оценка из статьи (там нам обещали не более чем за 40*N), ну так равномерное распределение и не самый сложный случай. С другой стороны разброс вокруг медианы довольно приличный: с вероятностью 10% мы обнаружим алгоритм за пределами интервала (35%, 65%).

А если пересчитать все то же самое с разбросом входных данных в 8 раз больше (0..1024) и тем же шагом 1, то время 90% достижения медианы увеличится до 1700 шагов, зато 90% интервал вокруг медианы сожмется до (45%, 55%)

Виден компромисс между скоростью сходимости и стабильностью. В первом случае шаг составлял 1/64 от дистанции до медианы, и алгоритм почти сошелся за 200 шагов, и держит медиану с точностью +/- 15%. Во втором случае шаг был 1/512 от дистанции до медианы, и алгоритм почти сошелся за 1700 шагов, и держит медиану с точностью +/-5%.

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

Frugal2U

Этот алгоритм расширяет предыдущий: основная логика та же, но к ней добавляется подстройка величины шага. Чтобы организовать подстройку, требуется еще одна ячейка памяти для хранения текущего шага, currentStep, и еще один бит sign для хранения направления предыдущего шага. И идея, снова, очень простая: давайте запоминать, в каком направлении мы шагнули (sign), и увеличивать текущий шаг каждый раз, как мы делаем следующий шаг в одном и том же направлении, что и предыдущий:
step = 1
currentStep=step
sign = 1
Q    = 0.9       # quantile we're about to estimate
Xq   = 0         # initial estimation of Q-th quantile
for x in stream:
  r = np.random.random()
  if x < Xq and r > Q:
      currentStep -= sign * step
      Xq -= max(currentStep, step)
      if value > Xq:  # too much of adjustment
          currentStep += Xq - value
          Xq = value
      if sign > 0 and currentStep > step:          
          currentStep = step              # if sign was changed -> reset currentStep to minimum
      sign = -1
  elif x > Xq and r < Q:
      currentStep += sign * step
      Xq += max(currentStep, step)
      if value < Xq:  # too much of adjustment
          currentStep += value - Xq
          Xq = value
      if sign < 0 and currentStep > step:          
          currentStep = step             # if sign was changed -> reset currentStep to minimum
      sign = 1
(код выглядит громоздко, потому что довольно много места занимает обработка выходов за границы разумности)

Почему это работает? На пальцах: если вероятность пойти в какую-то сторону один раз равна P, то вероятность пойти туда же N раз подряд — P^N, и с такой вероятностью шаг вырастет до N*step. Чем больше P, тем больше вероятность достичь бОльшего шага. Но в нашем алгоритме вероятность P зависит от расстояния до истинного значения квантиля: чем мы дальше от цели, тем больше вероятность шагнуть именно в ее сторону.

Более количественно: пусть мы сделали N шагов в одну сторону подряд — вероятность этого P^N, и шаг вырос до максимума N*step, т.е. средний шаг step*(N+1)/2. То есть с вероятностью P^N мы шли со средним шагом step*(N+1)/2. Просуммируем по всем N (спонсор вычисления бесконечных сумм wolfram alpha), и получим матожидание шага:
$$E[D(P)] = step\cdot\sum_{i=1}^{\infty}P^i \frac{(i+1)}{2} = step\frac{(2-P)*P}{2(1-P)^2}$$
Переводя на русский: схема "увеличиваем шаг пока идем в одну сторону" неявно задает вот такую зависимость среднего размера шага от дистанции до цели (целью у нас выступает медиана, P=0.5).

Я построил на одном графике сразу две зависимости: E[D(P)] и E[D(1-P)], потому что мы ведь из каждой точки можем пойти в обе стороны, и удобно сразу видеть, как меняется матожидание шага в одну, и в другую сторону


Оба графика пересекаются в P=0.5 — это как раз стационарная точка, к которой алгоритм сходится. А вот по мере отклонения от 0.5 графики расходятся, и очень быстро: уже на расстоянии в 0.3 от равновесия средний шаг в направлении равновесия будет >10 единиц. То есть если мы на расстоянии 0.3 от медианы, то приближаться мы будем примерно десятикратными шагами. Похоже, несмотря на простоту, такая схема управления размером шага может вполне хорошо работать!

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

Под конец пару примеров, как алгоритмы ведут себя на тестовых данных.
Пример 1: оценка 80% квантиля на выборке из равномерного распределения. Красным показан "эталон" для сравнения — сглаженный "честный" квантиля на истории из последних 400 элементов:

Видно, насколько быстрее Frugal2U сходится к значению квантиля: почти так же хорошо, как и "честная" оценка квантиля по окну, при этом они гораздо меньше флуктуируют. Если же окно увеличить так, чтобы флуктуации пропали, то пострадает скорость сходимости.

Пример 2: ступеньки + равномерное распределение. Здесь можно лучше рассмотреть скорости перехода — видно, насколько быстро перестраивается Frugal2U, насколько сильно запаздывает Frugal1U.

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

28 июля 2018 г.

Снова про конфигурацию

Одна из проблем с тестированием конфигурации состоит в том, что нет готовой инфраструктуры

Я имею в виду, что когда вы собираетесь написать тест для кода — у вас уже многое есть. У вас есть какая-то доменная модель, у вас есть какие-то API, у вас есть какие-то builders/wizards/DSL. Да, поверх всего этого, обычно, все равно приходится дописать прослойку вспомогательного кода, предназначенного именно для тестирования (aka "test-harness"), но если основной код спроектирован и написан достаточно хорошо, то эта прослойка довольно тонкая. Условно, процентов 50-80 уже написано, и эти проценты очень облегчают начало.

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

Да, везде можно найти свои плюсы: я приводил пример, как поверх примитивной структуры конфигов можно писать такие же примитивные тесты, бьющие по площадям ("все свойства, заканчивающиеся на .port, имеют в качестве значения целое число из диапазона доступных сетевых портов"). Но одними ковровыми бомбардировками каши не сваришь — рано или поздно появится желание (необходимость) проверить что-то конкретное и узкосфокусированное.

И вот тут часто возникает барьер: попытка написать такой тест "с лету" приводит к монструозному спагетти-коду, глядя на который хочется перекреститься "не дай бог коллеги увидят". А создание обвязки, позволяющей писать более-менее понятные тесты — выходит довольно дорого, потому что нет тех самых "50%-80%", и нет и наработанного опыта/понимания, как именно такую обвязку писать. Пару идей, как такую обвязку можно строить я в докладе давал, но все равно это каждый раз боль.

В общем-то, я еще помню как похожие же проблемы возникали лет 10-15 назад с тестированием кода. И в этом случае решением стало распространение идей TDD — что тестирование это неотъемлемая часть разработки, и уже на стадии написания кода необходимо думать о том, как ты его будешь тестировать. Может быть, распространение аналогичной идеи test driven configuration со временем решит аналогичную проблему и для тестов конфигурации. А может быть просто все больше конфигурации будет в виде кода (а тестировать код мы уже научились, так что задача сводится к предыдущей) — мне, как программисту, это кажется более экономным решением

12 июня 2018 г.

Configuration as code

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

Сейчас мне кажется, что выносить конфигурацию приложения в текстовые файлы (в том числе xml/json/yaml…) — это сильно переоцененный прием. Настолько переоцененный, что он уже почти антипаттерн. Ну как синглетон — сам по себе вроде неплох, но был период, когда его пользовали где ни попадя, в хвост и гриву. Так же и с конфигурацией в текстовых файлах: якобы это дает гибкость, но эта гибкость на практике оказывается чаще вредной, чем полезной.

И как раз когда я писал тесты для конфигурации — было очень заметно, насколько много в конфигурации лишней гибкости. Выясняется, что:
  1. Чтобы большая по объему конфигурация была управляемой — необходимы тесты
  2. При написании тестов большую часть времени я занимаюсь тем, что “отменяю” всю гибкость вольного формата текстового файла. Изобретаю заново — в тестах — те вещи, которые уже есть в строго-типизированном языке программирования.
Спрашивается: чего бы сразу не описывать конфигурацию на строго-типизированном языке?

Для меня текстовые конфигурации это наследство tutorial-ов, на которых программисты учатся. Когда я по ним учился, то там в обязательном порядке все, что можно, выносилось в .properties-файл. Но в tutorial-е в этот файл попадает 3-5 свойств, а к концу туториала — файлов становится аж 2, для UAT и для PROD. В реальном приложении к третьему году разработки таких файлов 150, свойств в них 10000, и всё горит, и все в аду, но это так привычно, что кажется just a normal amount of hell.

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

Это как с inversion of control/dependency-injection (очень близкая идея, кстати): ведь IoC/DI не равен тождественно spring-app-context.xml. Есть разные контейнеры, и разные форматы описания того, как контейнер должен собрать из компонентов приложение.

Можно и вообще без контейнера: когда я работал в 1С над Матконструктором, я, как продвинутый хипстер, конечно же сплетал компоненты в приложение через spring. Но у матконструктора была версия в виде апплета, и тащить мегабайт .jar-ников спринга в апплет только ради фазы инициализации было за гранью добра. Поэтому (я уже не помню, кому пришла в голову эта гениальная идея) мы написали xslt, которая из spring-контекста генерировала .java-файл, делающий ровно то, что было задекларировано в контексте. Это оказалось довольно просто сделать, так как мы пользовались только базовыми возможностями spring. И хотя в релизной версии приложения не оставалось никаких следов спринга, паттерн dependency injection сохранялся: сгенерированный класс был тем самым компонентом, ответственностью которого является собрать остальные компоненты в целое приложение.

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

Как я себе вижу конфигурацию в коде? Пока не очень четко :) Скорее всего, как DSL-like API для конфигурирования приложения. Java не самый лучший выбор для создания DSL-ей, но даже ее скупыми средствами вполне можно создать такой набор builder-ов, что многие ошибки конфигурации просто не пройдут компиляцию (а еще ведь остаются рантайм-проверки). А если взять какой-нибудь Котлин, то можно написать и вовсе гарные DSL-и. При этом:
  1. Есть проверка типов (у нас же строго типизированный язык!)
  2. Есть готовая вся система типов из доменной модели приложения, и ее можно расширить типами, специфичными для конфигурации.
  3. Есть поддержка IDE: подсвечивание ошибочных элементов, подсказки допустимых, всплывающие подсказки с описанием смысла параметров и их допустимых значений (если вы позаботились об этом при написании АПИ), переименование/рефакторинг
Поддержка IDE — это очень важный элемент, потому что он сильно сокращает время исправления ошибки. Например, есть немало решений для валидации конфигов, но валидация обнаруживает ошибки либо уже в рантайме, либо в тестировании, а ошибки компиляции современные IDE показывают сразу по ходу написания. А чтобы валидацию подхватила IDE — нужно постараться, и написать к ней специальный плагин, причем такой плагин нужен под каждый механизм валидации свой.

Вообще, мне кажется, сейчас эта идея витает в воздухе — возможно, потому, что появился Kotlin, который очень близко интегрируется с java, но при этом имеет отличные возможности для DSL. Вот пара идейно-близких примеров, которые я нашел сходу: Александр Тарасов рассказывает, как он использует kotlin-DSL чтобы конфигурировать эксперименты, а Иван Осипов — как они DSL-ем готовят параметры для параметризованных тестов.

20 мая 2018 г.

"Тестирование конфигурации для java-разработчиков" (Гейзенбаг 2018, Петербург)


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

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

Но код приложения проходит множество проверок — начиная от компилятора (если вы, конечно, пишете на нормальных языках, а не на JavaScript), и кончая многими уровнями тестов. Конфигурация же, чаще всего, это просто какие-то текстовые файлы (properties, xml, yaml, json...), с очень вольным форматом, практически без валидации. Никаких автоматизированных тестов для нее, как правило, нет.

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

UAT/staging проблемы не решает: конфигурация, как правило, различается для разных environment, поэтому протестировав сервисы в UAT/staging вы протестируете конфигурацию UAT/staging, но не PROD.

Проверить конфигурацию методом пристального взгляда (code review) не очень реально: в более-менее крупном проекте объем конфигурации измеряется сотнями и тысячами строк, и мало кто знает смысл и ограничения всех существующих параметров, и как они взаимодействуют с другими параметрами.

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


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

По моему опыту, самый существенный барьер не технический, а психологический. Выглядят-то тесты конфигурации как юнит-тесты, но фактически лазают по файловой системе, какие-то файлики там читают… Т.е. как юнит-тесты они выглядят странновато и кривовато. Да и вообще сама идея что конфигурацию нужно тестировать так же, как код — требует времени, чтобы к ней привыкнуть. Но это вопрос привычки: вспомните, сколько времени разработчики привыкали к идее, что нужно тестировать код.

А еще конфигурация не заканчивается на .properties/.xml: можно тестировать crontabs, sql, shell-scripts — все то, что важно для работы сервисов, и не проверяется другими способами. Не всегда можно протестировать во всей полноте, но почти всегда можно написать тест, закрывающий путь конкретному классу ошибок, которые больше всего портят жизнь.


Мы пишем тесты конфигурации уже года 3 (спасибо Андрею Сатарину, который принес эту идею — его собственный рассказ про тестирование конфигурации был на московском Гейзенбаге 2017). И за 3 года написания и поддержки мы набрели на несколько удачных решений.

Например, для тестирования взаимозависимостей между параметрами разных сервисов полезно построить модель предметной области — т.е. модель деплоймента приложения. Формализовать в виде программных объектов environments, сервера, сервисы, конфигурационные файлы, и как это все между собой связано в вашем случае. Тогда тесты будут выглядеть не как “пойди в ту папочку, возьми такой файлик…”, а как “для каждого environment-а в конфигурации сервиса ХХХ на primary-сервере те же самые порты, что и в конфигурации того же сервиса ХХХ на backup-сервере того же environment-а". Такая модель полезна сама по себе — в ходе ее создания проясняется много всякого неявного знания о деплойменте.

А еще для тестирования конфигурацию удобно представлять не как Properties, а как Stream из кортежей типа [environment, server, service, configFile, propertyName, propertyValue]. Тесты в таком виде выглядят более единообразно, кроме того если тест падает, то в сообщении об ошибке автоматом будет весь адрес злокозненного свойства.


Ну и на закуску был case-study: тестирование конфигурации как поддержка для рефакторинга конфигурации. Есть сложная и запутанная система конфигурации, доставшаяся в наследство, которую нужно упростить и преобразовать в понятный вид. Как построить достаточно плотную сеть тестов, которая позволит удостоверить, что преобразованная конфигурация по-прежнему корректна?

3 декабря 2017 г.

Про ReentrantReadWriteLock

Отличная история с любимой группы рассылки concurrency-interest.

В библиотеке guava есть класс Striped, предоставляющий разные виды локов, в разбивке по ключам. Сценарий использования, как я его понимаю, такой: есть данные, естественным образом разбитые по ключам К, и эти данные нужно защитить от конкурентного доступа. При этом конкурентный доступ к данным разных ключей вполне допускается. Если использовать одну общую блокировку, то это похоронит весь параллелизм, а заводить по блокировке на каждый ключ может быть слишком накладным, если ключей много. Striped — промежуточный вариант: при создании задается, сколько блокировок вы готовы создать, и дальше все ключи отображаются на этот ограниченный список блокировок. Один и тот же ключ всегда отображается на один и тот же лок, поэтому корректность гарантируется. Разные ключи, очевидно, тоже иногда отображаются на один лок, но не очень часто (~1/stripes). (Если вы смотрели код j.u.c.ConcurrentHashMap, то должны понимать, откуда эта идея, и как примерно она реализована)

Cреди разных вариантов этого Striped есть Striped.lazyWeakReadWriteLock(), где объекты ReentrantReadWriteLock создаются лениво, и удерживаются через слабые ссылки. Вероятно, для сценариев, где потенциально ключей очень много, но в каждый конкретный момент используется лишь небольшое подмножество, и потому какие-то локи периодически простаивают без толку.

И обнаруживается, что в этом варианте корректность нарушается: довольно легко воспроизвести ситуацию, когда к данным одного и того же ключа, защищенным соответствующим локом из Striped.lazyWeakReadWriteLock(), тем не менее получают одновременный доступ два разных потока. Каждый из этих потоков захватил соответствующую блокировку — но это оказываются две разных блокировки!

То, что Striped.lazyWeakReadWriteLock().get(key) может возвращать разные локи для одного и того же ключа — само по себе не удивительно. Если локи создаются лениво, и держатся через слабые ссылки, то в промежутке между двумя вызовами может прийти GC, прибрать тот лок, который был сначала, а на втором вызове взамен его создастся новый лок. Это не кажется проблемой: ведь если GC смог прибрать лок, значит его никто не использовал, никто ничего им не защищал. Но в тестовом сценарии, в котором воспроизводится ошибка, первый лок все это время используется. Как так?

Оказывается, что использование объекта ReentrantReadWriteLock.writeLock() и использование объекта ReentrantReadWriteLock — это две разные вещи. ReentrantReadWriteLock, если посмотреть на его код, выступает лишь фасадом к паре объектов .writeLock() и .readLock(). ReentrantReadWriteLock создает оба этих объекта, связывает их через общий объект Sync (который и реализует внутри себя всю логику блокировки) — и больше ничего и не делает, кроме как предоставляет к ним доступ. Все взаимодействие между .writeLock() и .readLock() идет в обход ReentrantReadWriteLock, и настолько хорошо в обход, что никто из них даже не нуждается в ссылке на родительский объект.

В результате получается, что в коде типа такого
private void readLockedMethod() {
        final Lock readLock = stripedLock.get(key).readLock();
        readLock.lock();
        try {
            //в этот момент со стека есть ссылка только на readLock!
        } finally {
            readLock.unlock();
        }
    }
внутри блокировки только readLock реально используется, и потому достижим (reachable) со стека. Соответствующий же ему ReentrantReadWriteLock внутри и после блокировки никем не используется, и вполне может быть прибран GC. Что и происходит время от времени. И как только это произойдет, при следующем вызове stripedLock.get(key) из другого потока будет создан уже новый ReentrantReadWriteLock, хотя старая блокировка все еще не отпущена.

Интересно разобраться, кто именно совершил ошибку. Авторы guava полагали (неявно), что ReentrantReadWriteLock вместе с его дочерними объектами это такой неразрывный блок (агрегат), все элементы которого имеют одинаковое время жизни, и они либо все живые (достижимый), либо так же все мусор. На деле же оказалось, что связи между частями ReentrantReadWriteLock более слабые, и эти части могут функционировать независимо и иметь разное время жизни. Ни то, ни другое не было явно прописано в контракте RRWLock, но предположить сильную связность (агрегацию) было довольно естественно. И так же естественно для разработчиков j.u.c реализовать слабую связность (ассоциацию): ведь слабое связывание это одна из мантр хорошего дизайна.

Как результат обсуждения, вероятно, в новых версиях джавы связность будет усилена: .writeLock() и .readLock() будут иметь обратную ссылку на родительский ReentrantReadWriteLock. Поведение будет более интуитивным — ценой большего расхода памяти.

23 июня 2017 г.

Shenandoah на JPoint 2017

Запоздалый отклик на рассказ о Shenandoah на JPoint 2017 и последокладные разговоры. Я не буду пересказывать Алексея — лучше Алексея никто Алексея не перескажет, видео наше все. Здесь мои размышления после, и что мне показалось интересным.

Интересного в Shenandoah много. Для меня в первую очередь интересно, что Шенандо — первый GC в джаве, который не основан на гипотезе о поколениях.

Я начну издалека. Базовый алгоритм для сборки мусора это трассировка ссылок: определяем GC Roots, от них идем по ссылкам, и помечаем достижимые объекты как живые. Но на большой куче трассировка потребует много времени. Если мусор собирать в режиме паузы (Stop The World, SWT), то паузы будут долгими.

Как сделать паузы короче? Логично разбить работу на изолированные кусочки, и обрабатывать их по одному. Однако определение достижимости объектов разбить на изолированные задачки оказывается не так-то просто: в общем случае нельзя проанализировать достижимость какого-то подмножества объектов без того, чтобы протрассировать все остальные объекты в куче. Почему? Потому что, в общем случае, на любой объект из нашего подмножества потенциально может ссылаться любой другой объект. Априори нет способа ограничить поиск входящих ссылок каким-то подмножеством кучи.

В общем случае это так, да. Но реальные графы ссылок почти никогда не бывают настолько плотные, чтобы все ссылались на всех. (Хотя бы уже потому, что количество исходящих ссылок из каждого объекта ограничено его размером, и очень мало по сравнению с общим количеством объектов в куче). Кажется вероятным, что реальную кучу все-таки можно разбить на регионы, которые сильно связаны внутри себя, но слабо связаны с другими регионами (связность в смысле входящих ссылок). Когда куча разбита на регионы так, что между собой регионы связаны слабо, то GC сможет быстро собирать такие регионы инкрементально, по одному: чтобы собрать регион Х достаточно просканировать сам регион Х, плюс те регионы, из которых есть ссылки в Х — а таких регионов немного, потому что связность низкая.

Остается придумать, как же разбить кучу на такие удобные регионы?

Один из способов решения этой задачи дают generational GC. Generational GC основаны на паре эмпирических наблюдений: "гипотезах о поколениях". Первая (слабая) гипотеза о поколениях утверждает, что большинство объектов умирает молодыми, вторая (сильная) гипотеза утверждает, что старые объекты редко ссылаются на молодые.

...Когда я впервые познакомился с generational hypothesis, я был уверен, что первая гипотеза самая важная. Ну, не зря же она — первая? Вторая гипотеза несколько лет жила в моей памяти в виде "ну там еще какие-то дополнительные условия, но они не критичны". Именно так я несколько лет отвечал на собеседованиях, и никто не придирался. С тех пор у меня осталось убеждение, что большинство разработчиков тоже так и думает :)

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

Сильная гипотеза как раз дает подсказку, как собрать мусор в молодом регионе не трассируя всю остальную кучу. Сильная гипотеза говорит, что ссылок из старых регионов в молодые — мало. Это то самое утверждение о структуре графа связности регионов, которого не хватает. Если ссылок из старых регионов в молодые мало, то их достаточно отслеживать каким-нибудь грубым но дешевым способом (например: card marking), и при сборке молодого региона останется просмотреть лишь небольшой кусок старых регионов. Так мы получаем знакомую схему NewGen + OldGen

Что изменилось с приходом G1? G1 претендовал на то, чтобы уменьшить паузы при сборке старого поколения (актуально на больших кучах). Для этого и старое и молодое поколение разбито на регионы одинакового размера, G1 отслеживает ссылки между регионами, так что и в старом, и в молодом поколении возможна инкрементальная сборка. В идеале это позволило бы очищать кучу слой за слоем, как луковицу.

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

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

Чтобы уменьшить проблему пришлось увеличивать подробность отслеживания ссылок между регионами: не просто "регион А ссылается на регион Б", а из какой конкретно области региона А есть ссылки на объект из Б (RememberedSet). Чтобы отслеживать ссылки с такой подробностью пришлось написать много хитрого кода, который потребяет ресурсы. Подробная информация о ссылках между регионами занимает много места (до 40% кучи в G1 бывает занято этими RememberedSet-ами). Все это в сумме тратит время и нервы разработчиков — сколько лет уже G1 полируют, и только в 9-ке он, наконец, станет выбором по-умолчанию.

Где в этой картине Shenandoah? Shenandoah делает практически же самое, что G1 только хорошо: разбивает кучу на регионы, отслеживает ссылки между ними, очищает регионы инкрементально. Разница в том, что Shenandoah очищает мусор не в паузах, а параллельно с приложением. И те сценарии, которые для G1 патологические — то есть вызывают неприемлемые паузы в работе приложения — для Shenandoah патологическими уже не являются. Для Shenandoah такие сценарии будут не самыми эффективными по CPU — да, возможно, но не патологическими, потому что паузы в работе приложения остаются минимальными, а повышенное потребление CPU сейчас как правило не критично.

Shenandoah заимствует у G1 всю красоту идеи регионального сборщика мусора, но выбрасывает весь геморрой с RememberedSet-ами, заменяя их на старый-добрый card mark. Конечно, заплатить все равно приходится — в той части, где Shenandoah ухитряется собирать мусор параллельно с работой приложения. Там хватает своих тонкостей и накладных расходов. Но вот региональную часть Шенандо получает практически на сдачу.

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

10 января 2017 г.

GC: golang и прочие

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

Последний месяц-два много шума из-за go. Команда разработчиков go рапортует о том, что в версии 1.5 их GC работает со средними паузами в районе сотен микросекунд, и максимальными < 10 миллисекунд ну и типа это "прорывное решение", "сборщик мусора для следующего десятилетия" и другие громкие заявления. В связи с этим хорошая статья Mike Hearn на medium: Modern Garbage Collection разбирает ситуацию (пока я писал, ее уже перевели на хабре).

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

В частности, нынешний "прорывной" сборщик мусора в go — это concurrent mark-sweep, прямой родственник и аналог OpenJDK-CMS в java. С той только разницей, что нет поколений — да, да, прямо сейчас в go (1.5) не используется сборка по поколениям (хотя это запланировано), собирается вся куча, как единый кусок. При этом, как и в OpenJDK-CMS, в асинхронном режиме нет compaction — куча дефрагментируется только в режим stop-the-world. Как результат: нужен довольно большой запас памяти, чтобы противостоять фрагментации (желательно примерно вдвое больше реально используемой), и на обход кучи тратится довольно заметная часть ресурсов CPU.

CMS в OpenJDK используется для старого поколения, в паре с копирующим сборщиком для молодого поколения. И наибольшие паузы (при правильной настройке), это паузы на сборку молодого поколения. Собирать молодое поколение в асинхронном режиме сложно, потому что сборщик молодого поколения — перемещающий (чтобы отслеживать асинхронно перемещаемые объекты понадобятся read barrier-ы). Но именно сборка молодого поколения позволяет снизить нагрузку на сам CMS — лишь небольшая доля объектов доживают до зрелости. Поэтому в джаве CMS (точнее, комбинация CMS + ParNew) в среднем более эффективен с точки зрения накладных расходов: какой избыток памяти нужен, и какую часть CPU time заберет GC.

В мире realtime java в свое время предлагался Metronome — сборщик мусора для систем реального времени, для которого можно доказать ограничения на величину вносимых им пауз (правда, паузы там все равно были в районе миллисекунд, но это 2003 год). Платить за это приходилось серьезными затратами CPU: сборка мусора съедала аж 50% процессорного времени. В go, вроде бы, все не настолько плохо, но и их GC отъедает десятки процентов CPU в нормальном режиме работы. В джаве нормально настроенный GC обычно ест ~5%

Gil Tene в дискуссии на mechanical sympathy справедливо замечает, что любому техническому решению нужно время, чтобы созреть. Неразумно выносить какие-то окончательные суждения про go GC сейчас, когда весь проект go еще очень молод — он еще 100 раз успеет мутировать. С его точки зрения, пока что главная опасность в нынешнем сборщике мусора go — это отсутствие перемещений объектов. Без перемещения объектов сборка мусора неизбежно будет приводить ко фрагментации, и это станет серьезным камнем преткновения по мере развития платформы. Опасность в том, что такое решение может оказаться зафиксированным просто де-факто — пока это так в нынешней реализации, авторы сторонних библиотек успеют заложиться на фиксированные адреса объектов в памяти, и уже нельзя будет поменять это, не поломав обратной совместимости для большого количества существующего кода.

Чтобы больше погрузиться в тему компромиссов при сборке мусора: хорошая статья A Unified Theory of Garbage Collection. Авторы задались целью показать, как различные подходы к автоматическому управлению памятью на на самом деле представляют собой полюса одного непрерывного спектра решений. И изначально различные реализации по мере обретения зрелости обрастают эвристиками, оптимизациями, становятся все более гибридными, и все меньше отличаются друг от друга. Авторы рассматривают подсчет ссылок (reference counting) и трассировку (tracing) объектов как своего рода взаимо-дополняющие методы управления памятью: где один из них хорош — другой плох. И любая зрелая реализация трассировки со временем обрастет оптимизациями, представляющими собой, по-сути, ограниченный подсчет ссылок — и наоборот. Например, card marking, который используется в generational GC чтобы отслеживать ссылки из старого поколения в молодое — это ни что иное, как вырожденная форма reference counting. Вообще, write barrier-ы — это прямое указание на какую-то форму подсчета ссылок.

Другая весьма старая (но не менее интересная) статья Hans Boehm-а на тему компромиссов: Mark-sweep vs. copying collection and asymptotic complexity. Ханс рассматривает Mark-Sweep и копирующий сборщики, и задается вопросом, насколько их общеизвестные теоретические свойства действительно реализуются в реальных условиях.

Например: считается, что время работы копирующего сборщика пропорционально количеству живых объектов, в то время как для Mark-Sweep это время пропорционально общему объему кучи. Такая оценка Mark-Sweep основана на том, что в sweep-фазе нужно обойти все "мертвые" объекты, чтобы добавить их во free-set. Ханс замечает, что sweep-фаза вообще не является обязательной: можно ставить пометки только на живых объектах, а при аллокации сканировать кучу напропалую, ищя первый кусок памяти без пометки "живой". Этот алгоритм будет эффективен, если значительная (бОльшая) часть кучи после сборки окажется пустой — но ровно же в этом случае и копирующий сборщик становится эффективным!

Ханс рассматривает несколько аналогичных "общепринятых" свойств, и показывает, что на практике не всегда все так очевидно, как кажется.

4 декабря 2016 г.

Так что насчет производительности?..

Значительная часть моих историй про скаляризацию состоит из описания того, как все весело разваливается, чуть что-нибудь где-нибудь недозаинлайнилось. После чего у некоторых читателей возникает ощущение "да ну его в жопу, я лучше сам все закэширую, и все гарантированно будет быстро, и не важно, что там как инлайнится". Честно говоря, мне и самому стало интересно, насколько оно все будет быстро, если плохо заинлайнится, поэтому я написал такой несложный бенчмарк:
public class GCCostBenchmark {


 @Param( { "32", "64", "128", "256", "1024" } )
 public static int SIZE = 128;

 ArrayList<Integer> list = new ArrayList<>();

 @Setup
 public void setup() {
  final ThreadLocalRandom rnd = ThreadLocalRandom.current();
  for( int i = 0; i < SIZE; i++ ) {
   list.add( rnd.nextInt() );
  }
 }


 @Benchmark
 public long sumWithIterator() {
  long sum = 0;
  for( final Integer n : list ) {
   sum += n;
  }
  return sum;
 }

 @Benchmark
 public long sumWithIndex() {
  long sum = 0;
  for( int i = 0; i < list.size(); i++ ) {
   final Integer n = list.get( i );
   sum += n;
  }
  return sum;
 }
}
Просто создаем ArrayList разных размеров, заполняем его случайными числами, и в цикле суммируем. И смотрим на два разных варианта организации цикла: через итератор, и старперский, через индекс.
Benchmark               (SIZE)   Mode  Cnt   Score    Error   Units
sumWithIndex                32  thrpt    5  27.195 ±  3.476  ops/us
sumWithIndex                64  thrpt    5  15.362 ±  0.443  ops/us
sumWithIndex               128  thrpt    5   8.359 ±  0.775  ops/us
sumWithIndex               256  thrpt    5   4.243 ±  0.268  ops/us
sumWithIndex              1024  thrpt    5   1.115 ±  0.029  ops/us
sumWithIterator             32  thrpt    5  24.300 ±  0.244  ops/us
sumWithIterator             64  thrpt    5  12.973 ±  0.056  ops/us
sumWithIterator            128  thrpt    5   7.415 ±  0.035  ops/us
sumWithIterator            256  thrpt    5   4.023 ±  0.392  ops/us
sumWithIterator           1024  thrpt    5   1.138 ±  0.012  ops/us
Видно, что на моей JDK 1.8.0_102 они идут ноздря в ноздрю: вариант с индексом слегка обходит итератор, но различие в пределах погрешностей. Ок, это будет наша реперная точка. Теперь мы запускаем тот же бенчмарк, но с флагом -XX:-EliminateAllocations. В у бенчмарка с итератором, разумеется, появляются строчки gc-profiler-а gc.alloc.rate.norm=32.000±0.001 B/op, но меня интересуют другие цифры:
Benchmark                (SIZE)   Mode  Cnt    Score    Error   Units
sumWithIndex                 32  thrpt    5   27.063 ±  1.527  ops/us
sumWithIndex                 64  thrpt    5   15.571 ±  0.243  ops/us
sumWithIndex                128  thrpt    5    7.795 ±  0.066  ops/us
sumWithIndex                256  thrpt    5    4.213 ±  0.022  ops/us
sumWithIndex               1024  thrpt    5    1.120 ±  0.011  ops/us
sumWithIterator              32  thrpt    5   21.022 ±  1.452  ops/us
sumWithIterator              64  thrpt    5   11.295 ±  2.082  ops/us
sumWithIterator             128  thrpt    5    6.145 ±  0.273  ops/us
sumWithIterator             256  thrpt    5    3.359 ±  0.035  ops/us
sumWithIterator            1024  thrpt    5    0.905 ±  0.032  ops/us
Как и можно было бы ожидать, итерация с индексом почти никак не отреагировала на этот флаг, а итератор стал медленнее, примерно на ~15-20%. Но это я волевым решением отрезал скаляризацию. А давайте сэмулируем отсутствие инлайнинга (и как следствие — скаляризации):
-XX:CompileCommand="dontinline,java.util.AbstractList::*"
-XX:CompileCommand="dontinline,java.util.ArrayList::*"
— я отключаю инлайнинг для всех методов ArrayList/AbstractList (ну, чтобы уж с надежностью):
Benchmark                (SIZE)   Mode  Cnt    Score    Error   Units
sumWithIndex                 32  thrpt    5    2.767 ±  0.033  ops/us
sumWithIndex                 64  thrpt    5    1.410 ±  0.012  ops/us
sumWithIndex                128  thrpt    5    0.709 ±  0.003  ops/us
sumWithIndex                256  thrpt    5    0.357 ±  0.003  ops/us
sumWithIndex               1024  thrpt    5    0.093 ±  0.003  ops/us
sumWithIterator              32  thrpt    5    3.528 ±  0.055  ops/us
sumWithIterator              64  thrpt    5    1.821 ±  0.029  ops/us
sumWithIterator             128  thrpt    5    0.933 ±  0.015  ops/us
sumWithIterator             256  thrpt    5    0.464 ±  0.020  ops/us
sumWithIterator            1024  thrpt    5    0.119 ±  0.003  ops/us
Без инлайнинга производительность цикла просела в 10 раз! (кстати, теперь версия с итератором работает быстрее :)

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

29 ноября 2016 г.

Видео с jug-ekb

Сентябрьский доклад на jug-ekb. Спасибо организаторам:

25 ноября 2016 г.

Скаляризация Map.get(...) -- продолжение

...которое было задумано сразу после, но неожиданно задержалось: сложная политическая обстановка, на работе завал, в Москве пробки, гомеопаты атакуют, а в фейсбуке регулярно кто-то не прав — как тут найти время?

После прочтения предыдущего поста возникает депрессиявопрос: можно ли как-то добиться стабильной скаляризации ключей? Краткий ответ: нет. Более полный ответ: нет, стабильной скаляризации в JVM (HotSpot) добиться невозможно. JIT — это рулетка. Смиритесь.

... Но побарахтаться все-таки можно. Ни один из способов ниже я не готов считать "хорошим" — в том смысле, что они не являются примером хорошего кода, и их вряд ли стоит внедрять в свой обычный стиль программирования. Тем не менее, иметь возможность побарахтаться, мне кажется, всегда лучше, чем не иметь :)

Во-первых, можно просто уменьшить размер метода .equals(). Казалось бы, куда уж меньше:
public boolean equals( final Object o ) {
 if( this == o ) {
  return true;
 }
 if( !( o instanceof StringKey ) ) {
  return false;
 }

 final StringKey key = ( StringKey ) o;

 return item1.equals( key.item1 )
   && item2.equals( key.item2 );
}

(Напомню, что этот метод комплируется в 55 байт, что больше 35 — порога вклеивания для не-горячих методов). Оказывается, однако, что меньше можно:
public boolean equals( final Object o ) {
 if( this == o ) {
  return true;
 }
 if( !( o instanceof StringKey ) ) {
  return false;
 }

 final StringKey key = ( StringKey ) o;

 return equals( key );
}

private boolean equals( final StringKey key ) {
 return item1.equals( key.item1 )
   && item2.equals( key.item2 );
}

Первый .equals(Object) комплируется в 27 байт, второй в 34, и тот и другой проходят под порогом. В данном примере такое разбиение имеет самостоятельный смысл: типизированный .equals(StringKey) может быть полезен сам по себе, но вообще-то надо понимать, что мы здесь используем в своих интересах несовершенство эвристики вклеивания — большие методы нужно декомпозировать чтобы код был читабельным и переиспользуемым, а не чтобы переиграть JIT в очко.

Не стоит забывать так же, что увеличивая глубину стека вызовов мы увеличиваем вероятность наступить на порог инлайнинга по глубине (MaxInlineLevel=9) — в изолированном бенчмарке эта вероятность невелика, но в реальной программе она гораздо выше. Кроме того, хотя маленьким методам уже не обязательно быть горячими, но им все равно нужно выполниться хотя бы 250 раз (MinInliningThreshold) чтобы JIT счел их достойными вклеивания.

Ок, в конце-концов можно взять другую реализацию хэш-таблицы. Я пробовал trove THashMap, и guava ImmutableMap. По моим наблюдениям, в обоих случаях ситуация немного лучше, чем с j.u.HashMap, но именно что немного: да, скаляризация случается чаще, но все равно не всегда. Посмотрим, например, на THashMap:
public V get(Object key) {
    int index = index(key);
    return index < 0 ? null : _values[index];
}

protected int index(Object obj) {
    if (obj == null)
        return indexForNull();

    // From here on we know obj to be non-null
    final int hash = hash(obj) & 0x7fffffff;
    int index = hash % _set.length;
    Object cur = _set[index];


    if (cur == FREE) {
        return -1;
    }

    if (cur == obj || equals(obj, cur)) {
        return index;
    }

    return indexRehashed(obj, index, hash, cur);
}

private int indexRehashed(Object obj, int index, int hash, Object cur) {
    final Object[] set = _set;
    final int length = set.length;

    // NOTE: here it has to be REMOVED or FULL (some user-given value)
    // see Knuth, p. 529
    int probe = 1 + (hash % (length - 2));

    final int loopIndex = index;

    do {
        index -= probe;
        if (index < 0) {
            index += length;
        }
        cur = set[index];
        //
        if (cur == FREE)
            return -1;

        //
        if ((cur == obj || equals(obj, cur)))
            return index;
    } while (index != loopIndex);

    return -1;
}
Я наблюдаю два основных сценария, как здесь обламывается скаляризация: во-первых, какой-то из методов index()/indexRehashed() не вклеивается с диагностикой "already compiled into a big method". Например, вот так (size=1024, hit probability=2%):
  @ 84   ...THashMap::get (21 bytes)   inline (hot)
   \-> TypeProfile (74492/74492 counts) = gnu/trove/map/hash/THashMap
    @ 2   ...TObjectHash::index (72 bytes)   inline (hot)
      @ 11   ...TObjectHash::hash (5 bytes)   inline (hot)
        @ 1   ...$StringKey::hashCode (5 bytes)   accessor
      @ 54   ...TObjectHash::equals (19 bytes)   inline (hot)
        @ 15   ...$StringKey::equals (55 bytes)   inline (hot)
          @ 29   j.l.String::equals (81 bytes)   (intrinsic)
          @ 43   j.l.String::equals (81 bytes)   (intrinsic)
      @ 68   ...TObjectHash::indexRehashed (80 bytes)   already compiled into a big method
В докладе я разбирал точно такой сценарий на примере LinkedList, напомню вкратце: здесь возникает конфликт между двумя разными эвристиками инлайнинга, и итоговое решение зависит от того, какой из методов скомплируется раньше, а какой позже. А раз порядок компиляции недетерминирован, то и результат тоже: один и тот же код при одинаковых параметрах 5 раз подряд покажет успешную скаляризацию, а на 6-й какой-нибудь посторонний процесс оттянет на себя CPU, слегка изменит соотношение времен исполнения задач компиляции, и все, прощай.

Второй же сценарий провала скаляризации напоминает j.u.HashMap: поиск в THashMap тоже распадается на две ветки (см. выше), одна для прямого попадания, и вторая для разрешения коллизий (indexRehashed), и если одна из этих веток сильно доминирует, то вторая просто не разогреется достаточно сильно, чтобы JIT решил ее вклеить, а порог инлайнинга для не-горячих методов .indexRehashed() явно превышает (диагностика "too big").

(guava ImmutableMap я подробно разбирать не буду: стабильной скаляризации нет и там, хотя метод .get() там чуть ли не самый компактный)

8 октября 2016 г.

Скаляризация Map.get(new CompositeKey(key1, key2, ...))

Один из самых интересных примеров из моего последнего доклада на jug-ekb (на JPoint этот пример не влез) это скаляризация композитных ключей в поиске по словарю:
final Map<CompositeKey, V> map = ...;

...
    final CompositeKey key = new CompositeKey( key1, key2, ... );
    final V value = map.get( key );
...
Это весьма частый паттерн: нам нужно отображение вида [key1, key2, key3...] -> value. Наиболее простой и очевидный способ это сделать: как раз таки использовать композитный ключ (кортеж из ключей). Решение отличное по всем показателям, кроме одного: для каждого поиска в словаре придется создавать новый объект.

Иногда хочется этого избежать. Тогда приходится организовывать иерархические словари-словарей-словарей... — я видел много таких примеров (поиск по текущему проекту находит аж 5 различных реализаций чего-то вроде TwoKeyMap/ThreeKeyMap). Это решение мне самому не нравится (хотя 2 из 5 упомянутых реализаций — мои). Например, словарь-словарей это совсем другой тип, нежели словарь-словарей-словарей — расширение ключа на одну позицию не является прозрачным, окружающий код специализирован под конкретное число ключей. У этого решения, как правило, хуже производительность: во-первых, потому что приходится делать 2-3-4... поиска вместо одного, а во-вторых потому, что соответствующие словари обычно получаются очень неравномерно заполненными. Скажем, key1 может иметь всего 3-4 разных значения, а лежать они будут в таблице размером по-умолчанию (16). При этом, скажем, ключей вида ("A", *) всего 2, а вида ("B", *) — 10000. То есть часто образуется много сильно недозаполненных таблиц, вперемешку с несколькими нормальными. Будь все эти ключи в одной таблице — все эти неоднородности сильно сгладились бы.

В общем, хотелось бы и чтобы все было хорошо, и за это не приходилось бы ничего платить. Может ли JIT сам скаляризовать аллокацию ключа в сценарии типа map.get( new CompositeKey( key1, key2, ... ) )?

...Этот сценарий попортил мне немало крови: я несколько раз переписывал код на плюс-минус такой же, и каждый раз получая какие-то новые результаты. Пару раз я готов был включить очередные результаты в презентацию, и только из-за недостатка времени обрезал эту часть, а через недельку обнаруживал, что чуть было не представил неверные результаты. Окончательно (ну, я сейчас так считаю) у меня дошли руки разобраться с ним перед екатеринбургским jug-ом — времени там было точно достаточно, и уже самому хотелось закрыть эту тему.

Как выглядит сам бенчмарк: я генерирую пул строк, из них образую парные композитные ключи (StringKey), которыми наполняю хэш-таблицу. Внутри главного цикла бенчмарка я создаю ключи таким образом, чтобы они присутствовали или отсутствовали в словаре с какой-то вероятностью (hit probability — один из параметров сценария), и запрашиваю у словаря соответствующие значения.

private final Pool<String> keys = poolOf( randomUniqueStrings( 2 * SIZE ) );

private final Pool<String> nonExistentKeys = poolOf( randomUniqueStrings( 2 * SIZE ) );

//...

public long run() {
 final boolean successful = ( rnd.nextDouble() <= SUCCESSFUL_LOOKUPS_PROBABILITY );
 
 final String key1;
 final String key2;
 if( successful ) {
  key1 = keys.next();
  key2 = keys.next();
 } else {
  key1 = nonExistentKeys.next();
  key2 = nonExistentKeys.next();
 }

 final String value = map.get( new StringKey( key1, key2 ) );

 if( value == null ) {
  return 0;
 } else {
  return 1;
 }
}

Что получается на выходе: иногда ключи скаляризуются почти стабильно, для целого спектра размеров таблицы (1,2,4...65) и спектра hit probability=(0%, 50%, 100%). А иногда — почти стабильно не скаляризуются. А иногда вообще какая-то ересь получается: сценарий аллоцирует что-то вроде 120 байт на вызов, вместо обычных 24-х — что уже вообще ни в какие ворота. Поведение меняется от небольших изменений в коде, и от того, использую ли я в качестве ключей свой собственный класс StringKey, или заменяю его на ImmutablePair из apache commons.

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

Начнем с кода HashMap.get(). В 1.8.0_102 он выглядит так:

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
Что мы можем здесь увидеть — помимо того, что автору неплохо бы пересмотреть свой стиль именования переменных? Мы можем увидеть, что здесь две ветки — "прямое попадание", и процедура разрешения коллизий, и внутри второй ветки — еще две ветки (поиск в связном списке или дереве). Чтобы скаляризация имела шанс сработать, нам необходимо (но не достаточно), чтобы заинлайнились все методы, в которые уходит интересующий нас объект (key), до самого низа. В данном случае, как минимум, должны заинлайниться hashCode(), оба вызова .equals() и .getTreeNode().

А что нужно, чтобы метод заинлайнился? О, это большая тема :) Инлайнинг — одна из самых потенциально эффективных оптимизаций в JIT-ах, так что эвристик у нее немало. К счастью, все они нам обычно не нужны, достаточно сильно сокращенной версии:
  1. Если метод-кандидат виртуальный — он должен быть девиртуализован. Для девиртуализации необходимо либо чтобы CHA показал, что сейчас в JVM в принципе загружена только одна реализация, либо чтобы профиль, собранный во время исполнения (TypeProfile) показал, что в данном конкретном месте (вероятно) вызывается не более двух реализаций виртуального метода.
  2. Если метод-кандидат достаточно горячий (горячесть вычисляется как по абсолютному количеству вызовов, так и по тому, насколько часто метод-кандидат вызывается из того метода, в который мы его собираемся вклеивать), то его размер в байт-кодах должен быть не больше FreqInlineSize(=325), и размер в машинных кодах (если он уже был скомпилирован изолированно) не больше SmallInlineSize(=2000).
  3. Если метод недостаточно горячий, то, возможно, он хотя бы маленький (< MaxInlineSize(=35))? Но, при этом, он должен все-таки выполниться хоть сколько-то: как минимум, MinInliningThreshold(=250) раз. А иначе какой смысл вклеивать?
  4. ...Но если какая-то ветка не выполнилась вообще ни разу (за время профилирования), то C2 выкинет ее код вообще, а на случай "а вдруг" поставит вместо нее т.н. uncommon trap: перезапуск выполнения метода в режиме интерпретатора. Эта часть уже не является частью политики инлайнинга, это отдельная, и очень мощная спекулятивная оптимизация, но она очень помогает скаляризации: ведь если весь код ветки выброшен, то он не анализируется на предмет убегания ссылок.
(Обычному java-программисту непривычно думать о размере метода в байт-кодах, поэтому цифры типа 325 и 35 могут выглядеть довольно абстрактно. Точного соотношения между размером джава-кода и размером байт-кода, разумеется, нет, но по порядку величины можно сказать так: 325 байт это довольно большой метод, примерно на полстраницы-страницу, а 35 байт это коротенький метод, на 3-4 строчки)

...Итак, у нас есть код поиска ключа в хэш-таблице, который состоит из нескольких этапов (веток): поиск нужной корзинки (bucket), сравнение (по хэш-коду и по .equals()), поиск по списку коллизий (по хэш-коду и по .equals()) или поиск по дереву коллизий (там вообще мрак и ужас). И поиск может завершиться на любом этапе, но вся идея хэш-таблицы как структуры данных в том, что как правило у нас списки коллизий короткие, или отсутствуют вовсе. То есть, если раскладка данных в хэш-таблице достаточно равномерная (==хэш-функция хорошая), то вероятность завершить поиск на первом же этапе довольно высока, вероятность попасть в ветку разрешения коллизий — заметно меньше, а вероятность наткнуться на список коллизий настолько длинный, чтобы он конвертировался в дерево — совсем маленькая. Более точно, можно выделить такие сценарии:

  1. Попали в пустую корзинку: этот сценарий довольно часто (с вероятностью = 1 - load factor = 25%..60%) будет реализовываться, когда мы будем искать несуществующие в таблице ключи (hit probability << 100%). Здесь вызывается только key.hashCode(), ни один из 2х .equals(), ни .getTreeNode() не вызывается вообще
  2. Попали в корзинку с единственной парой ключ-значение: этих сценариев будет большинство среди тех, когда мы вообще что-то найдем (==ключ присутствует в таблице). В этом случае мы дернем key.hashCode(), и первый .equals(), а второй .equals() и .getTreeNode() все так же не выполняются
  3. Попали в корзинку с несколькими парами ключ-значение, но нашли нужный нам ключ с первой же попытки — наш маршрут через код совпадает с предыдущим
  4. Наконец, мы попали в корзинку с несколькими парами, и нашли нужный ключ не с первой попытки, либо вообще его не нашли, просмотрев весь список коллизий. В этом случае мы успеем дернуть key.hashCode(), и оба .equals(), (.getTreeNode()все так же не у дел)
  5. Для редкостных неудачников: мы попали в корзинку с >8 парами ключ-значение, при общем размере таблицы >64, и обнаружили, что корзинка сконвертирована в TreeBin — тут, наконец, мы заглянем во врата ада.getTreeNode()
Из всего этого уже можно начать рисовать различные сценарии "что может пойти не так с инлайнингом (и, как следствие, скаляризацией)".

Во-первых, очевидно, у нас могут доминировать сценарии №1. В этом варианте может оказаться, что ни один из двух .equals() не набрал достаточного количества вызовов, чтобы оказаться горячим, и тогда код .equals() должен быть ну очень коротким, чтобы пролезть под порогом инлайнинга для не горячих методов (35 байт). Например, такой вот, стандартный

public boolean equals( final Object o ) {
 if( this == o ) {
  return true;
 }
 if( !( o instanceof StringKey ) ) {
  return false;
 }

 final StringKey key = ( StringKey ) o;

 return item1.equals( key.item1 )
   && item2.equals( key.item2 );
}
компилируется в 55 байт, и не пролезает.

Как я уже упоминал, на этот сценарий реальнее всего попасть когда большинство искомых ключей в таблице отсутствуют. В самом деле, запуская сценарий с (HashMap.size=64, hit probability=0%) мы получаем грустную историю дискриминации толстяков:

@ 84   j.u.HashMap::get (23 bytes)   inline (hot)
 \-> TypeProfile (11045/11045 counts) = java/util/HashMap
  @ 2   j.u.HashMap::hash (20 bytes)   inline (hot)
    @ 9   ...StringKey::hashCode (19 bytes)   inline (hot)
      @ 4     j.l.String::hashCode (55 bytes)   inline (hot)
      @ 14    j.l.String::hashCode (55 bytes)   inline (hot)
  @ 6   j.u.HashMap::getNode (148 bytes)   inline (hot)
    @ 59   ...StringKey::equals (55 bytes)   too big       <--- 
    @ 126  ...StringKey::equals (55 bytes)   too big       <--- 
Видно, что ни один из двух .equals() не вклеился. too big это лишь один из вариантов, я наблюдал так же и executed < MinInliningThreshold

Если мы начнем увеличивать hit probability, то очень быстро "разогреем" первый .equals(): (size=64, hit probability=1%, 2%, ... )

@ 84   j.u.HashMap::get (23 bytes)   inline (hot)
 \-> TypeProfile (11045/11045 counts) = java/util/HashMap
  @ 2   j.u.HashMap::hash (20 bytes)   inline (hot)
    @ 9   ...StringKey::hashCode (19 bytes)   inline (hot)
      @ 4     j.l.String::hashCode (55 bytes)   inline (hot)
      @ 14    j.l.String::hashCode (55 bytes)   inline (hot)
  @ 6   j.u.HashMap::getNode (148 bytes)   inline (hot)
    @ 59   ...StringKey::equals (55 bytes)   inline (hot)    <---
      @ 29     j.l.String::equals (81 bytes)   (intrinsic)
      @ 43     j.l.String::equals (81 bytes)   (intrinsic)
    @ 126  ...StringKey::equals (55 bytes)   too big         <---
Увеличивая hit probability дальше, мы в какой-то момент разогреем и второй .equals(). Точный момент указать сложно, потому что ключи каждый раз генерируются заново, и раскладка по корзинкам получается в каждом запуске немного другая (а она зависит еще и от размера таблицы...), да и сбор профиля внутри JVM — тоже не детерминированный процесс. Вот сейчас у меня получилось достичь этого при hit probability=5%:
...
@ 84   j.u.HashMap::get (23 bytes)   inline (hot)
 \-> TypeProfile (112592/112592 counts) = java/util/HashMap
  @ 2   j.u.HashMap::hash (20 bytes)   inline (hot)
    @ 9   ...StringKey::hashCode (19 bytes)   inline (hot)
      @ 4     j.l.String::hashCode (55 bytes)   inline (hot)
      @ 14    j.l.String::hashCode (55 bytes)   inline (hot)
  @ 6   j.u.HashMap::getNode (148 bytes)   inline (hot)
    @ 59   ...StringKey::equals (55 bytes)   inline (hot)   <---
      @ 29     j.l.String::equals (81 bytes)   (intrinsic)
      @ 43     j.l.String::equals (81 bytes)   (intrinsic)
    @ 126  ...StringKey::equals (55 bytes)   inline (hot)   <---
      @ 29     j.l.String::equals (81 bytes)   (intrinsic)
      @ 43     j.l.String::equals (81 bytes)   (intrinsic)
...
И да — бинго! — в этом сценарии ключи начали скаляризоваться, код больше ничего не аллоцирует.

Среди прочего, интересно заметить, что в логе компиляции .getTreeNode() вообще не упоминается. Это все потому, что соответствующая ветка вообще не используется, и JIT заменил ее на uncommon trap — большая любезность с его стороны, а то у нас были бы околонулевые шансы добиться скаляризации в этом примере хоть когда-нибудь.

До сих пор все просто и логично. Вот только я точно помню, что в каких-то старых вариантах бенчмарка наблюдал стабильную скаляризацию для всего спектра hit probability, в том числе и = 0. Как такое могло происходить?

Оказывается (это "оказывается" стоило мне нескольких часов недосыпа), я неаккуратно генерировал ключи. В генерации пула "несуществующих" ключей была ошибка, из-за которой с некоторой заметной вероятностью такие ключи все же находились в словаре — а как мы видели, достаточно небольшой примеси "найденных" ключей, чтобы разогреть холодные ветки. Но этого мало, у меня еще и сами ключи генерировались с очень плохим распределением. Точнее, отдельные-то ключи имели вполне равномерное распределение, но в пары они собирались по порядку, и вот тут-то хэш-код становился буквально кратным 32-м. Это, конечно, создавало очень неравномерное распределение по корзинкам, и длинные списки коллизий, а длинные списки коллизий еще сильнее ускоряли разогрев соответствующей ветки.

Эти же длинные списки коллизий сыграли при переходе на ключи ImmutablePair из apache commons. С ImmutablePair я наблюдал аллокацию аж 120 байт на вызов, которым, вроде, совсем неоткуда там было взяться. А все дело в том, что, в отличие от простого и дубового StringKey, навороченный ImmutablePair implements Comparable, и при превращении цепочки коллизий в дерево, HashMap это пытается использовать, чтобы сделать дерево более красивым. И вот такой код, где-то внутри .getTreeNode():

static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {   // <---- 
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}
что он делает? Дело в том, что даже если key1 instanceof Comparable && key2 instanceof Comparable, нельзя так просто взять, и вызвать key1.compareTo(key2). Нельзя потому, что, возможно, эти Comparable промеж собой не совместимы: может, один из них Comparable<A>, а другой Comparable<B>. Процитированный код как раз пытается понять, чем конкретно параметризован этот Comparable. И вот вызов c.getGenericInterfaces() как раз и порождает загадочные 120 байт

Что получается в итоге? Получается, что успех или неуспех скаляризации зависит от раскладки ключей в хэш-таблице. Интересно что: чем ближе раскладка к идеальной (с точки зрения производительности) "один ключ на одну корзину", тем более вероятно, что ветка разрешения коллизий окажется холодной, и скаляризация не произойдет. Более того, профилирование происходит в начале исполнения кода, и после окончательной компиляции (C2) без веских причин перепрофилирования не будет, а это значит, что версия, скомпилированная по "неудачному" профилю, собранному в начале исполнения, так и будет исполняться дальше, уже независимо от актуального профиля.

P.S. Первопричина многих подобных нестабильностей в том, эвристики инлайнинга жестко заточены на производительность: мы стараемся вклеивать те методы, от вклеивания которых ожидается наибольший прирост скорости исполнения, и не рвемся вклеивать те, от которых заметного прироста не ожидаем. Это не совсем то, что нужно для скаляризации: скаляризация-то срабатывает по принципу "все или ничего": все маршруты конкретного объекта должны быть доступны для анализа, и если хотя бы один, пусть и редкий, маршрут уходит за горизонт (в невклеенный метод), то скаляризации не сможет работать. С точки зрения производительности же вклеивать редкий метод нет смысла: прирост производительности минимальный, а код раздувается. Скаляризация выступает тут бедным родственником, который вынужден довольствоваться тем, что дают: иначе было бы логично явно учитывать и ее интересы в эвристиках инлайнинга (такой EA-guided inlining предлагался, кажется, еще в Choi99).

12 августа 2016 г.

EnumSet scalarization

В эфире очередной выпуск блогопередачи "скаляризуй меня полностью". На этот раз под мою горячую руку попался EnumSet. Первое, что мне про него было интересно — это, конечно, скаляризация итератора. Ну, потому что по любой коллекции очень удобно ходить циклом foreach, но не всегда хочется за это удобство платить, пусть даже и не дорого:
public static enum Enum3 {
 FIRST,
 SECOND,
 THIRD
}

...

final EnumSet set = EnumSet.allOf( Enum3.class );

...

//benchmark start
long sum = 0;
for( final Enum e : set ) {
   sum += e.ordinal();
}
return sum;
//benchmark end
... JIT меня здесь не подвел: как и в большинстве коллекций, которые я до сих пор исследовал, итератор успешно скаляризуется. По-крайней мере, пока количество элементов в перечислении не превышает 64-х. Я не сумел сходу понять, что там такого в JumboEnumSet.EnumSetIterator-е, что смущает скаляризацию, а копать глубже мне немного лениво, потому что ДА ГОСПОДИ ИИСУСЕ КТО Ж ДЕЛАЕТ ПЕРЕЧИСЛЕНИЯ ПО 64+ ЭЛЕМЕНТОВ? Да таких случаев один на 1000, хрен с ней тогда, со скаляризацией, тут о вечном думать пора...

А вот более практичный вопрос: скаляризуется ли сам EnumSet в примере выше? То есть: если внести создание EnumSet.allOf(...) в бенчмарк — сумеет ли JIT спроецировать этот EnumSet в простой скалярный long?

Простой тест показывает, что нет. Но, конечно, гораздо интереснее понять — почему. По первости я грешил на вот этот метод:
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
   Enum[] universe = getUniverse(elementType);
   if (universe == null)
      throw new ClassCastException(elementType + " not an enum");

   if (universe.length <= 64)
      return new RegularEnumSet<>(elementType, universe);
   else
      return new JumboEnumSet<>(elementType, universe);
}
мне казалось довольно логичным, что статически предсказать ветку RegularEnumSet/JumboEnumSet невозможно, и получается уже известный сценарий с merge points. Чтобы это проверить я скопировал весь исходный код EnumSet/RegularEnumSet/JumboEnumSet из java.util к себе, и закомментировал ветку с JumboEnumSet. На удивление, это не помогло, и я пошел копать дальше. После какого-то количества промежуточных экспериментов (я уже, было, начал писать свой собственный SimpleEnumSet — чтобы, начав с крайне простого кода, потом добавлять понемногу функционал, пока скаляризация не сломается) поиск сошелся вот на чем: RegularEnumSet.EnumSetIterator это не-статический внутренний класс. В этом, казалось бы, нет ничего плохого — если только вы не слушали мой доклад на JPoint, где я уже разбирал ровно такой же случай, только на примере Arrays.asList(..)

...Оказывается, из-за загадочного бага в JIT-е, скаляризация ломается (не всегда, но часто), если на потенциально скаляризуемый объект ссылается уже скаляризованный объект. То есть EnumSetIterator успешно скаляризуется, но одно из его полей — неявная ссылка на объект родительского класса, на RegularEnumSet — застревает костью в горле у алгоритма скаляризации, когда этот алгоритм пытается скаляризовать сам RegularEnumSet. Другими словами, вот такой код
...
final EnumSet<Enum3> set = EnumSet.allOf( Enum3.class );
final boolean b = set.contains( Enum3.SECOND );
...
(без итератора) вполне успешно скаляризуется. Как и код с итератором (но без аллокации EnumSet) в самом начале статьи. Проблемы возникают когда мы эти два куска объединяем: когда мы хотим, чтобы одновременно и итератор, и сам RegularEnumSet скаляризовались. Тут нас ждет облом.

К сожалению, ситуация с EnumSet несколько хуже, чем с Arrays.asList(). В последнем случае итератор был не-статическим классом просто по недосмотру — раньше это никого не волновало. Сделать его не статическим ничего особо не стоило, никакой функциональности это не мешало. Благодаря усилиям Тагира Валеева это изменение даже было принято патчем в OpenJDK, так что в 9-ке, вероятно, Arrays.asList() будет скаляризоваться без проблем. А вот с EnumSet такое простое решение не пройдет, итератор здесь не-статический не случайно: доступ к родительскому объекту ему необходим для реализации метода remove(). Остается надеяться только на то, что JDK-8155769 когда-нибудь починят.

P.S. Удивительный факт, который остался немного за кадром: в этом коде
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
   Enum[] universe = getUniverse(elementType);
   if (universe == null)
      throw new ClassCastException(elementType + " not an enum");

   if (universe.length <= 64)
      return new RegularEnumSet<>(elementType, universe);
   else
      return new JumboEnumSet<>(elementType, universe);
}
JIT ухитряется как-то протащить реальный класс перечисления через getUniverse(..), и статически вычислить условие (universe.length <= 64)! Да они там совсем укурились в своем hotspot-dev!


P.P.S. Что меня в теме скаляризации вдохновляет сейчас: когда я начинал ее смотреть, я был готов к сценарию, что тут кромешный адъ и тьма египетская, и без знания наизусть всех кишок компилятора разобраться, или предсказать, или починить скаляризацию невозможно. А оказалось, что странности есть, но пока что все они умещаются в очень небольшой список шаблонов. То есть достаточно помнить по пальцам считанное число граблей (пусть даже не про все из них понятно, откуда они взялись), да знать ключики типа -XX:+PrintCompilation/-XX:+PrintInlining, и в большинстве случаев скаляризацию удается заставить работать, либо обозначить ключевые причины, почему она в таком коде работать и не будет. Пока, по крайней мере, все выглядит так.

30 июня 2016 г.

Tricky scalar replacement: больше-меньше

В предыдущей серии я уже писал, что такой код:
private double allocateConditionally( final ThreadLocalRandom rnd ) {
 final Vector2D v;
 if( rnd.nextBoolean() ) {
  v = new Vector2D( 1, rnd.nextDouble() );
 } else {
  v = new Vector2D( rnd.nextDouble(), 1 );
 }

 return v.length();
}
не скаляризуется — хотя интуитивно кажется, что скаляризация здесь должна быть тривиальной.

А что если немного добавить аллокаций?
private double allocateConditionally2( final ThreadLocalRandom rnd ) {
 final Vector2D result = new Vector2D();

 if( rnd.nextBoolean() ) {
  final Vector2D v = new Vector2D( 1, rnd.nextDouble() );
  result.copyFrom(v);
 } else {
  final Vector2D v = new Vector2D( rnd.nextDouble(), 1 );
  result.copyFrom(v);
 }

 return result.length();
}
В этом коде на одну точку аллокации больше — но все эти аллокации успешно скаляризуются. В общем-то, ничего особо удивительного: здесь каждая ссылочная переменная в любых сценариях исполнения всегда адресует один-единственный объект, поэтому никаких сложностей у скаляризации не возникает :)

21 июня 2016 г.

Escape Analysis & Scalarization (видео с jpoint)

Наконец-то выложили финальное обработанные записи докладов с JPoint. Среди прочих и мой доклад про Escape Analysis и скаляризацию. Кажется, получилось неплохо :)

25 марта 2016 г.

А почему бы не аллоцировать на стеке?

В самом деле: почему? Вот мы прогнали escape analysis на коде метода, обнаружили, что такие-то создаваемые объекты за пределы метода не утекают. Зачем мы их скаляризуем, почему бы нам просто не аллоцировать их на стеке? Ведь скаляризация, на первый взгляд, сложнее аллокации на стеке: отследить, какие операции с полями объектов к именно какому объекту в этот момент относятся, завести под эти поля локальные переменные, преобразовать код, чтобы он обращался к этим переменным, а не к полям объекта, приготовить задел для деоптимизации... Зачем нам весь этот геморрой, когда можно просто выделить кусок памяти на стеке, и впечатать туда объект? И мы получим полноценную ссылку на него, ничем не отличающуюся от ссылки на объект в куче. Ссылку, которую можно запихнуть в любую дырку, куда пролезет обычная ссылка (ну, слишком-то глубоко мы ее не запихаем — мы же знаем, что за пределы метода она не уйдет).

Насколько я понимаю, одного простого ответа на это "почему" нет. Более того, существовали прототипы стековой аллокации — в одной из статей по EA авторы упоминают, что их прототип делал по результатам EA именно стековую аллокацию (правда, тот прототип был на базе IBM JVM).

Но стековая аллокация не так уж проста, когда речь заходит о деталях: JVM (Oracle/Open JDK) знает, сколько памяти выделено ей под кучу — эта информация задается при запуске, и не может быть изменена. И VM этим пользуется: сразу же при старте резервирует у ОС диапазон адресов размером с максимальную кучу (не аллоцирует память, а просто резервирует адреса HEAP_START..HEAP_END = -Xmx реальная же аллокация происходит по необходимости). И с самого первого момента жизни у JVM есть эти два числа [HEAP_START..HEAP_END], между которыми должно лежать значение любого указателя на java-объект, и JVM активно полагается на то, что куча это непрерывный кусок памяти [HEAP_START..HEAP_END]. Например, эти числа можно вклеивать в генерируемый код прямо в виде констант.

Или, например, card marking. Я уже как-то писал о нем в контексте concurrency: generational GC должен как-то отслеживать ссылки между объектами разных поколений. Чтобы собрать молодое поколение, нужно знать, какие ссылки на него существуют в полях объектов старого поколения (они становятся частью root set-а). Разумеется, сканировать старое поколение целиком значит похоронить всю идею generational GC, объем сканирования нужно как-то сузить. Для этого JVM разбивает кучу на блоки-"карты" размером 512 байт, и для каждого такого блока держит однобайтовый признак "была ли в пределах этого блока запись ссылки". Каждая запись ссылки обновляет заодно и card marks: очень грубо, строчка a.f = ref из java-кода превращается примерно в
a.f = ref;
cardMarks[ (addressOf(a.f)-HEAP_START) >> 9 ] = 1
Т.е. мы записали ссылку в поле какого-то объекта, и пометили блок памяти, содержащий этот объект, как модифицированный. (Это относится только к записям ссылок — примитивные типы card marks не обновляют, потому что GC до них нет дела). Перед сборкой молодого поколения GC пройдет все модифицированные блоки, соберет из них ссылки, ведущие в молодое поколение, и добавит их в root set.

Код card marking такой простой потому, что мы заранее знаем начало кучи, какого она размера, и что она непрерывна. Поэтому нам достаточно одного-единственного массива cardMarks, и мы можем уже на старте JVM аллоцировать его нужного размера (= HEAP_SIZE / 512), сразу подо всю, даже еще не аллоцированную, кучу. Очевидно, что если теперь a в коде выше вдруг указывает на объект на стеке, то мы получим выход за границы массива cardMarks, потому что стеки потоков точно никак не попадут в зарезервированный под кучу интервал адресов. Чтобы обрабатывать ссылки на объекты в куче и объекты на стеке одновременно нужно, чтобы код card marking-а был заметно сложнее, скорее всего, содержал какие-то проверки и условные переходы. А это, на минуточку, код записи ссылки — одна из самых базовых операций, из самых часто исполняемых фрагментов кода. Типичная java-программа ссылками оперирует, пожалуй, чаще, чем примитивными типами! Получается, что немного ускорив аллокацию (точнее, де-аллокацию, сборку мусора — аллокация из TLAB в яве и так быстрее некуда) за счет использования стека мы одновременно замедлили один из самых горячих фрагментов кода — запись ссылки. Какой итоговый эффект это окажет на производительность/время отклика приложения в целом — большой и нетривиальный вопрос.

Card marking это только один из примеров того, как неожиданно непросто впихнуть стековые объекты в архитектуру JVM, годами заточенную под манипуляции объектами из кучи. Этот пример простой, но, возможно, уже не самый актуальный — как я понимаю (могу ошибаться), в G1 уже пришлось делить общий массив cardMarks на отдельные массивчики для каждого блока. Возможно, теперь уже не так уж сложно втиснуть в эту схему еще несколько "блоков" для стеков потоков. Но это не единственный такой пример, если судить по переписке в hotspot-dev:

...I tried implementing direct stack allocation in Hotspot a couple of years ago. It was a pain to try to allocate anything outside the heap - there are a lot of checks to make sure that your objects live on the heap. I ended up creating TLAB-like regions in the heap that could hold objects allocated in a stack-like way. It was a lot easier that way, and seemed to give the kinds of performance benefits you would expect. (Jeremy Manson, 01/27/14, @hotspot-dev)

— оказывается, что проще создать свой собственный "стек" с гетерами и панкратионом: откусывать от общей кучи пулы памяти на каждый поток, и использовать их для аллокации неубегающих объектов, на манер стека. И прототип реализации был написан еще два года назад. И где тот стек сейчас?..

...Я сейчас думаю, что, возможно, дело вообще не в сложности технической реализации аллокации на стеке. Дело в том, что непонятно, так ли уж это нужно. В самом деле, чтобы устранить аллокацию в куче нужно а) чтобы алгоритм EA сумел показать, что объект не утекает за границы текущей единицы компиляции б) чтобы алгоритм скаляризации сумел преобразовать все обращения к этому объекту в обращения к его скаляризованной версии. Переход от скаляризации к аллокации на стеке улучшит пункт "б" (сделает его почти 100%-ным). Сейчас, в некоторых случаях, алгоритм скаляризации может спасовать, даже если алгоритм EA и распознал локальность объекта, а с введением аллокации на стеке почти все такие случаи будут обрабатываться. Но вот много ли таких случаев? Точнее: во-первых, в каком проценте случаев скаляризация пасует сейчас, и во-вторых — какой процент от общего числа аллоцированных в программе объектов мы сможем таким образом выиграть? Я экспериментирую сейчас с различными сценариями, и складывается ощущение, что ответ на первый вопрос может быть довольно заметным — ну, скажем, сейчас мы скаляризуем 60-70% объектов, распознанных EA как неубегающие, а будем аллоцировать на стеке все 100%. А вот общий эффект для среднестатистической программы может быть скромным, если вообще заметным.

Вот недавно мне попалась (спасибо твиттеру) свежая статья, про очередной улучшенный алгоритм EA, в конце каковой статьи приведены результаты применения улучшенного алгоритма к разным бенчмаркам из наборов DeCapo и SPECjbb2005. Результат: в среднем устранено примерно ~15% аллокаций в куче. Это довольно продвинутый алгоритм EA, в паре со "стековой" аллокацией — то есть, приблизительно и ориентировочно, можно взять эти 15% аллокаций за оценку сверху возможностей используемого сейчас алгоритма EA. И переход от используемой сейчас скаляризации к какому-нибудь варианту "стековой" аллокации позволит выиграть какую-нибудь треть от этих 15%.

Каким бы совершенным не был "скаляризатор", его поле деятельности ограничено теми не-убегающими аллокациями, которые ему скормит EA. Алгоритм EA в java почти не менялся со времен 1.6. Да и чисто теоретически: возможности EA отыскать не-убегающие аллокации, в свою очередь, тоже ограничены: в пределах одного метода, даже с учетом агрессивного инлайнинга, особо не развернешься, а межпроцедурную оптимизацию JIT сейчас не выполняет. Увеличивать агрессивность инлайнинга? — Неплохой вариант, в основном потому, что дает пинок, наряду со скаляризацией, сразу целому ряду других оптимизаций. И действительно, в 1.8 многие ограничения на инлайнинг ослаблены, и я вижу, как некоторые сценарии, не скаляризовавшиеся в 1.7, в 1.8 начали скаляризоваться. Но особо далеко по этому пути тоже не пройдешь: чрезмерный инлайнинг раздувает код, и с какого-то момента это начинает уже ухудшать производительность. Получается, что существенный прирост можно получить только совершенствуя сразу и скаляризацию, и алгоритм EA, и, по-возможности, увеличивая размер единицы оптимизации, либо подключая межпроцедурную оптимизацию.

В таком рассуждении есть нюанс: когда мы пытаемся оценить профит от улучшений, прогоняя их на существующих уже программах, мы незаметно попадаем в ловушку. Существующие программы написаны с использованием существующих практик написания кода, и в этих практиках — и вообще в опыте разработчиков — уже учтены характерные особенности языка и платформы. Опытные разработчики, сознательно или бессознательно, уже оптимизируют свой код под известные сильные и слабые стороны платформы. Говоря проще: если бы было общеизвестно, что в java есть великолепный EA и скаляризатор, и что редкий временный объект имеет шанс быть аллоцированным в куче — многие программы были бы написаны сильно иначе, чем они написаны сейчас, когда общеизвестно, что да, GC довольно неплохо управляется с короткоживущими объектами, а некоторые объекты даже и скаляризуются, но не всегда, и не все, и вообще как фишка ляжет. В упомянутой выше статье, наряду с набором java-бенчмарков, был взят аналогичный набор Scala-бенчмарков (ScalaDeCapo). И разница очень заметна: (Java)DeCapo от включения EA получает бонус в -5% аллокаций, а ScalaDeCapo — в -15%. Общий прирост производительности (Java)DeCapo: +2.2%, ScalaDeCapo: +9%. В Scala другие наборы best practices, другой компилятор, другая стандартная библиотека...