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

Рассмотрим следующий метод в 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()) {
}

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

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

Заранее благодарю вас.

5 2
compiler-construction optimization boolean-logic boolean-expression

5 ответов:

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

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

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, который изначально истинен, вычисляется первым).

15

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

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

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

8

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

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

For (ii = 0; strlen (s) > ii; ii++)

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

N = strlen (s); for (ii = 0; n > ii; ii++)

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

2

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

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

0

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

То есть, если a ложно, b не получает оценку, но если b было ложно, то это не делалось.

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

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

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

0