воскресенье, 13 марта 2011 г.

Groovy - глюк при мемоизации рекурсивных замыканий

Задумал тут написать статью о том, как в Groovy работает мемоизация замыканий.

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

О ней, в частности, как об одной из интересных фич грядущего Groovy 1.8 писал в своем блоге один раз разработчиков Groovy Рошан Дорани (Roshan Dawrani).

И внезапно, экспериментируя, натолкнулся на следующий, не знаю пока, баг или нет, но нечто странное точно. Итак, пишем рекурсивную лямбда-функцию, считающую факториал, добавляем туда вызова sleep(time), чтобы разница в количестве вызовов была заметна и измерима, и пробуем мемоизировать все это дело. Тестировать online можно тут - http://groovyconsole.appspot.com/script/439003.

Пример 1:


def startTime = System.currentTimeMillis()
def fact = {it -> sleep(100); it ? it * call(it - 1g) : 1g}
println fact(50)
println fact(50)
println ((System.currentTimeMillis() - startTime) / 1000.


Никакой мемоизации здесь нет, и скрипт работает 10.391 секунд.
Теперь попробуем мемоизировать функцию. Для чего вызываем на объекте замыкания (да, я использую термин "замыкание" вместо "лямбда функция", пуристы - простите меня) memoize(), и присваиваем переменной fact ссылку на враппер, который возвращает метод memoise().
Пример 2:

ddef startTime = System.currentTimeMillis()
def fact = {it -> sleep(100); it ? it * call(it - 1g) : 1g}
fact = fact.memoize()
println fact(50)
println fact(50)
println ((System.currentTimeMillis() - startTime) / 1000.0)


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

Пример 3:

def startTime = System.currentTimeMillis()
def fact = {it -> sleep(100); it ? it * call(it - 1g) : 1g}
fact = fact.memoize()
println fact(50)
println fact(51)
println ((System.currentTimeMillis() - startTime) / 1000.0)

В приведенном случае я ожидал бы, что скрипт отработает за 5 с небольшим секунд, т.к. он начнет вычислять fact (51) = 51 * fact(50), то что выделено жирным уже должно быть вычислен о строчкой выше. Правда, логично и ожидаемо? Ан-нет, скрипт отработал за 10.519 секунд.

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

Написал вопрос в девелоперскую рассылку, жду.. Если подтвердят, что баг - может патч написать?

Комментариев нет:

Отправить комментарий