Странная ветвящаяся производительность

Результаты моего теста показывают, что производительность хуже, если в отрасли есть вероятность 15% (или 85%) процентов, а не 50%.

Любое объяснение?

Код слишком длинный, но соответствующие части находятся здесь:

private int diff(char c) { return TABLE[(145538857 * c) >>> 27] - c; } @Benchmark int timeBranching(int reps) { int result = 0; while (reps-->0) { for (final char c : queries) { if (diff(c) == 0) { ++result; } } } return result; }

Он подсчитывает количество символов BREAKING_WHITESPACE в данной строке. Результаты показывают внезапное падение времени (увеличение производительности), когда вероятность ветвления достигает около 0,20.

Подробнее о падении. Изменение семени показывает более странные вещи. Обратите внимание, что черная линия, обозначающая минимальное и максимальное значения, очень короткая, кроме как близко к скале.

утес

Это похоже на небольшую ошибку JIT. Для вероятности небольшой ветви он генерирует что-то вроде следующего, намного сложнее из-за разворачивания (я упрощаю много):

 movzwl 0x16(%r8,%r10,2),%r9d

Получить char: int r9d = queries[r10]

 imul $0x8acbf29,%r9d,%ebx

Умножить: ebx = 145538857 * r9d

 shr $0x1b,%ebx

Shift: ebx >>>= 27

 cmp %edx,%ebx jae somewhere

Оценки границ: if (ebx > edx || ebx < 0) goto somewhere (и выбросить там IndexOutOfBoundsException .

 cmp %r9d,%ebx jne back

Возвращайтесь к началу цикла, если не равны: if (r9d != ebx) goto back

 inc %eax

Увеличение результата: eax++

 jne back

Просто goto back

Мы можем видеть одну умную и одну тупость:

Проверка привязки выполняется оптимально с помощью одного сравнения без знака .
Это полностью избыточно, так как x >>> 27 всегда положителен и меньше длины таблицы (32).

Для вероятности ветвления выше 20% эти три инструкции

 cmp %r9d,%ebx jne back inc %eax

замените что-то вроде

 mov %eax,%ecx // ecx = result inc %ecx // ecx++ cmp %r9d,%ebx // if (r9b == index) cmoveq %ecx,%ebx // result = ecx

используя условную инструкцию перемещения . Это еще одна инструкция, но не разветвление и, следовательно, отсутствие штрафа за неверное предсказание отрасли.

Это объясняет очень постоянное время в диапазоне 20-80%. Резкое падение ниже 20% явно связано с неверными предсказаниями отрасли.

Таким образом, похоже, что JIT не использует правильный порог около 0,04, а не 0,18.

Чет