Предотвращение рекурсии и ленивые вычисления в Java

[apple_fan]

Очень интересная идея. Пожалуй, о поведении при нахождении рекурсии можно поспорить. Скорее всего, рекурсия вызвана ошибкой в логике программы. Если бы я писал такой класс, то я бы выкинул ошибку наверх: разработчик должен поймать её как можно раньше и избавиться от ошибки. Тихо возвращать значение по умолчанию может привести к большим проблемам далее.

В любом случае, этот код можно несколько улучшить, сделав классы thread-safe. Сейчас код содержит пару проблем:

1. Класс может иногда вернуть устаревшое значение переменной. То есть, если одна нить вызывает invalidate(), а другая в это время вызывает get(), результат непредсказуем.

2. Значание переменной может вычисляться несколько раз, если get() вызывается из разных нитей. Это может привести к очень неприятным ошибкам, если update() меняет какое-либо состояние.

[firexel]

Я думал по поводу потокобезопасности, но тех условиях в которых оно применялось, лишних потоков кроме гуишного не было.
Во всяком случае, это относительно просто вкрутить парочкой блоков synchronized

[tormich]

Благодарю за топик.

[halyavin]

После такого программа-то будет работать, но о попытках разобраться что в ней происходит можно будет забыть. В частности, lv1.get()+lv2.get() может не равняться lv2.get()+lv1.get(). Лично у меня от такого, как математика, голова идет кругом — ведь с точки зрения математики с противоречивыми системами работать нельзя.

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

[Nashev]

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

[firexel]

Спасибо за наводку. Действительно стоит взглянуть

[sody]

Еще можно использовать нечто вроде такой утилитки:

public class Locker {
	private boolean lock;

	/**
	 * Checks if instance is locked.
	 *
	 * @throws IllegalStateException if instance is locked
	 */
	public synchronized void check() {
		if (lock) {
			throw new IllegalStateException("Locked");
		}
	}

	/**
	 * Locks instance to prevent use it again.
	 *
	 * @throws IllegalStateException if instance is locked
	 */
	public synchronized void lock() {
		check();
		lock = true;
	}

	/**
	 * Unlocks instance.
	 */
	public synchronized void unlock() {
		lock = false;
	}
}

тогда метод get будет выглядеть так:

...
try {
  // выполняем обновление
  locker.lock()
  value = update();
  locker.unlock()
}
...

[sody]

Поправка к методу get:

public ValueType get() {
   // выполняем update() только если значение устарело
   if (isInvalid) {
      // этот флаг обязательно нужно снять по выходу из update()
      try {
         locker.lock();
         // выполняем обновление
         value = update();

         // isInvalid станет false только если update()
         // выполнился штатно без эксепшенов
         isInvalid = false;
      } catch (IllegalStateException e) {
        throw new RecursionDetectedException(this, e);
      } finally {
        // снимаем флаг в любом случае, как бы не завершилась get()
        locker.unlock();
      }
   }

   return value;
}

[firexel]

Хорошее решение, но мне все равно не нравится исключение, выбрасывающееся наверх. StackOverflowException мы бы все равно получили, только чуть позже. А так, есть какой-то шанс обработать нормально. Ключевой момент в getDefault() в том, что клиентскому коду совсем не нужно знать о процессах, происходящих в get().

Если у меня в коде в 10 местах стоит get(), мне в десяти местах придется поставить try{}. В getDefault() можно как раз обработать исключение в одном месте. Правда, тогда getDefault() придется назвать по-другому. onRecurtion, например.

[sody]

Ну тогда:

} catch (IllegalStateException e) {
   return getDefault();
}

Но я бы в таком случае воспользовался invalidated значением. Или если оно еще не установлено, то дефолтным:

} catch (IllegalStateException e) {
   return value != null ? value : getDefault();
}

[kibork]

А можно использовате ReadWriteLock или ReentrantLock

[sody]

Они используются для немного другой логики — синхронизации потоков. Когда один поток вызывает lock(), другой будет просто ждать освобождения ресурса. Можно конечно воспользоваться tryLock() с указанием таймаута, но это приведет к потере времени, а следовательно к понижению производительности всего приложения.

[CheatEx]

Ты там чуть ниже пишешь, что для этого он и написан, не?

[sody]

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

[CheatEx]

download.oracle.com/javase/6/docs/api/java/util/concurrent/locks/ReentrantLock.html#tryLock()

А вообще с.м. мой комент ниже.

[sody]

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

P.S. хотел было топик опубликовать, но оказалось кармы недостаточно, уйду домой злой :E

[CheatEx]

Почитай джавадок, то, что надо будет.

[sody]

Я предложил решение проблеммы методом велосипеда, любишь читать джавадоки — предложи свой рабочий вариант используя стандартные средства

[CheatEx]

Зачем synchronized?

[sody]

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

[xappymah]

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

Например, метод check():
зная, что в 90% случаях вызова этого метода срабатывает случай (lock == false), то получится, что синхронизация происходит зазря большую часть времени.

Оптимизировать это очень легко:
ну, во-первых, вместо boolean можно(лучше) использовать AtomicBoolean.
А код сделать примерно таким:
public void check() {
__if (check) {
____synchronized(lock) {
______if (check) {/* Some code here */}
____}
__}
}

[xappymah]

Поправка: if(check) -> if(lock.get())

[sody]

ну check метод вобщем-то можно и не делать synchronized, в нем переменная не модифицируется

[xappymah]

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

[sody]

Cпасибо за совет, буду иметь ввиду, только synchronized секция вроде как тоже не нужна, просто:

public void check() {
   if (lock.get()) {
      /* Some code here */
   }
}

[xappymah]

Взятие значения из лока — атомарное действие. Но вот промежуток между моментом финиша сравнения (то есть значения взято, там увидели true и собираемся выполнить код) и /*Some code*/ отнюдь не атомарен.
Если другой тред в это время успеет сменить значение лока, а /* Some code */ заточен на то, что (lock.get() == true) (ну, например, банальный отладочный assert lock.get() в конструторе выкидываемого исключения), то будет плохо.

[sody]

ясно, узнал много нового, раньше никогда не работал с AtomicBlablabla классами.

[sody]

забыл уточнить, unlock метода на самом деле нет, это только для этого примера вставил, т.е. если lock.get() == true, то оно уже не станет false.

[CheatEx]

Так лок может освободится и между выбрасываем исключения и перехватом его в обработчике :)

Народ, вы пишете неоптимальные и откровенно опасные велики. Почитайте умные книжки, или хотябы статейки на тему.

[xappymah]

Ну, я не говорил, что выброс асинхронного исключения — это хорошо:)
Но если вместо /* Some code here */ был бы просто некоторый обрабатывающий код, то все впорядке.

Ну а метод оптимизации взят с доклада сотрудников интел на CodeFest (ну и ранее я его встречал еще в коде каких-то проектов)

[CheatEx]

То есть ты написал свой лок, только c бОльшими накладными расходами и со странным поведением?

[xappymah]

Если я правильно понимаю, то один из случаев возникновения рекурсии — зависимость двух значений при инициализации друг от друга, так?
Тогда получается, что от порядка инициализации зависит то, какое значение будет валидным, а какое еще нет. Причем, как отмечалось выше, эти значения еще будут и разными в зависимости от порядка. Даже более того, неправильными, т.к. первое значение при инициализации получит вместо второго некоторый «дефолтный вариант», а второе значение — уже не совсем верное первое.

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

[firexel]

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

[CheatEx]

Если такая ситуация однажды сложится, то всегда будет повторятся. Можно сразу брать значение по умолчанию :)

[xappymah]

Посмотрел ваш код повнимательнее — вы правы: вне зависимости от порядка инициализации значения будут одинаковыми. Но, скорее всего, дефолтными. Всегда.

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

Таким образом, если никому из двух объектов не задать значение через set, то всегда будет возвращаться дефолтное.

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

[firexel]

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

Вот пример. Есть класс, который рисует математическую формулу. В число возможных элементов входят скобки и степень. Степень чтобы вычислить свою высоту берет высоту предыдущего элемента и прибавляет к ней какое-то число. Открывающая скобка так зависит от высоты следующего за ней элемента. Когда класс-контейнер пытается вычислить собственную высоту, он перебирает все свои элементы и запрашивает их высоту. В выражении "(^" возникнет рекурсия обновлений, которую никто не предвидел. Это быстро вылечивается одним ифом и рекурсии больше не возникает в том месте. Однако она может появиться в других местах.

[xappymah]

> Ее (рекурсию) никто не предусматривал в том месте где она возникла.
То есть была некоторая логическая ошибка, которая привела к неожиданной рекурсии.

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

[Nashev]

Это очень похоже на реализацию функционального языка программирования