Оптимизация логических выражений в Java

Question

Рассмотрим следующий метод в Java:

public static boolean expensiveComputation() {
    for (int i = 0; i < Integer.MAX_VALUE; ++i);
    return false;
}

И следующий основной метод:

public static void main(String[] args) {
    boolean b = false;
    if (expensiveComputation() && b) {
    }
}

Логическое соединение (такое же как &&) является коммутативной операцией . Так почему же компилятор не оптимизирует код оператора if до эквивалента:

if (b && expensiveComputation()) {
}

, который имеет преимущества использования оценки короткого замыкания ?

Кроме того, пытается ли компилятор сделать другие логические упрощения или перестановку логических значений для генерации более быстрого кода? Если нет, то почему? Конечно, некоторые оптимизации будут очень сложными, но мой пример не прост? Вызов метода всегда должен быть медленнее, чем чтение логического значения, верно?

Заранее спасибо.

Answer 1

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

Например, что, если код был такой

public static boolean expensiveComputation() {
        for (int i = 0; i < Integer.MAX_VALUE; ++i);
        b = false;
        return false;
}

public static boolean b = true;
public static void main(String[] args) {
        if (expensiveComputation() || b) {
        // do stuff
        }
}

Здесь, если компилятор выполнил вашу оптимизацию, //do stuff запустится, если вы не ожидаете этого, посмотрев на код (потому что b, который изначально равен true, вычисляется первым).

Answer 2

Потому что expensiveComputation() может иметь побочные эффекты.

Поскольку Java не стремится быть функционально чистым языком, он не запрещает программистам писать методы, которые имеют побочные эффекты. Таким образом, в компиляторе, вероятно, нет особой ценности, анализирующей функциональную чистоту. И потом, оптимизация, которую вы проводите, вряд ли будет очень полезной на практике, так как expensiveComputation() обычно требуется выполнить в любом случае, чтобы получить побочные эффекты.

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

Answer 3

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

Классический пример:

для (ii = 0; strlen (s)> ii; ii ++) <сделать что-нибудь>

, который оптимизируется до

n = strlen (s); для (ii = 0; n> ii; ii ++) <сделать что-нибудь>

от GCC с уровнем оптимизации 2, по крайней мере, на моей машине.

Answer 4

Версия java, которую я использую, оптимизирует a в выражении a && b, но не с b.

т.е. Если a ложно, b не оценивается, но если b было ложно, оно этого не делало.

Я узнал об этом, когда выполнял проверку в форме веб-сайта: я создал сообщения для отображения на веб-странице с помощью ряда логических методов. Я ожидал, что поля на странице, которые были введены неправильно, станут выделенными, но из-за быстрого взлома Java код выполнялся только до тех пор, пока не было обнаружено первое неправильное поле. После этого Java, должно быть, подумала что-то вроде «ложь && что-либо всегда ложно» и пропустила остальные методы проверки.

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

К сожалению, сложно автоматизировать интеллектуальные решения, особенно с императивными языками (C, C ++, Java, Python, ... то есть обычные языки).

Answer 5

Компилятор оптимизирует это, если вы будете запускать код достаточно часто, возможно, путем включения метода и упрощения полученного логического выражения (но, скорее всего, не путем переупорядочения аргументов &&).

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