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() изнутри самого замыкания не роутит вызов через этот враппер.

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

T-SQL: когда индекс на table variable очень нужен

В мире T-SQL живут и сотрудничают две очень похожие и в тоже время очень разные вещи: табличные переменные (table variables) и временные таблицы (temporary tables). На форумах часто можно встретить темы вида «Что мне лучше использовать и в чем разница?». Но про это я сейчас не расскажу ;)

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

А что делать если такое необходимо сделать с табличной переменной? Все кто пытался хоть раз это сделать знают, что на табличной переменной можно создать тока primary key и нельзя создать индекс. Но если очень хочется, то индекс создать можно :)

Если вы попытаетесь создать индекс напрямую, движок БД недвусмысленно ответит вам, что нельзя на табличных переменных создавать индексы. Давайте подумает что еще у нас ведет себя как индекс, выглядит как индекс, но не индекс? Конечно же это unique constraint. В MS SQL этот тип constraint реализуется как индекс (да и в большинстве других РСУБД тоже). Так что же нам мешает создать unique constraint на таб

личной переменной и наслаждаться жизнью? Абсолютно ничего не мешает:

Поле Id включено в unique constraint потому что комбинация полей может повторяться. Уникальность должна быть уникальной.

Смотрим план запроса:

Index Seek — что можно еще желать?

Oracle insufficient privileges внутри хранимой процедуры

Немного об одной тонкости в системе привилегий Oracle, о которой не все знают, и которая может съесть немало времени на отладку.

Суть в следующем -- 
Для хранимых процедур, триггеров и прочего PL/SQL (но НЕ для анонимных блоков PL/SQL!) привилегии, необходимые для выполения команд динамического SQL (например, execute immediate ('create synonym s1 for table_1')) должны быть даны создателю (тому пользователю, в схеме которого выполняется процедура или триггер) явно, а не через роль. Очень важный момент, речь идет не о привилегии на выполнение процедуры, а о привилегиях, необходимых для выполнения команд динамического SQL. 

Подробности тут - www.sql.ru/faq/faq_topic.aspx

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

sun.misc.Unsafe - немного магии вокруг JVM

Когда-то, выбирая декомпилятор, натолкнулся я на несколько изумительных статей на wasm.ru. Статьи они кажется потерли, или по крайней мере изменили адреса, но сохранили их в виде вордовского файла, который можно загрузить отсюда:



Описывают, что такое Unsafe api, предоставляющее программисту возможность работать с классами, методами и т.п. ниже того уровня , который позволяют штатные средства платформы Java - на фактически на уровне тех самых С-структур, которые используются внутри JVM для предоставления сущностей класс, инстанс класса, метод и т.п.

Что дает возможность делать многие вещи, которые в программировании на Java  "традиционно" считаются невыполнимыми - функция sizeOf, (возвращающая точный размер объекта в памяти , взятый напрямую из поля  структуры, которая представляет этот объект внутри JVM), наследования от final-класса (делается двумя шагами по сути -  в список предков класса добавляется нужный нам класс, и из таблицы модификаторов доступа для этого суперкласса во время выполнения программы удаляется final - и
всего делов ;)).

Ну и уже более изощренные и хакерские штучки - самомодицирующиеся во время выполнения методы..и т.п. Очень рекомендую эти статьи к прочтению :).

Да, конечно -- смещения полей в структурах высчитываются на пальцах, класс sun.mics.Unsafe недокументирован (но присутствует в Java с самого ее начала, и очень навряд ли будет из нее удален - я очень сильно подозреваю, что предоставляемые им низкоуровневые возможности используются инструментами типа отладчиков и т.п.), и в продакшне ни один Project Manager такое использоватьне позволит -- да и не требуется в обычных приложения никогда столь низкоуровневый доступ к JVM. Но знать, как ява-машины работает с классами внутри себя -- полезно и интересно, а знать что из обычной программы на чистой яве можно получать доступ такого уровня -- еще интересней.

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

Я не думаю, что это дыра в системе безопасности Java. Собственно, суммирую и повторю описанное в первой из статей.
Итак. Есть две точки входа для получения инстанса класса Unsafe, который позволит нам творить черную магию:

1) Получить его можно через Unsage.getUnsafe() - НО! только в том случае, если вызывающий класс был загружен первичным класслоадером (www.tedneward.com/files/Papers/BootClasspath /BootClasspath.pdf - тут можно прочитать подробней про иерархию класслоадеров). Это сделать несложно -- всего-то добавить ключ -Xbootclasspath в список стартовых опций ява-машины. Но для этого надо иметь доступ  к среде выполнения.

2) Можно просто взять private переменную theUnsafe - которая хранит инстанс класса Unsafe внутри него. Но если есть Security Manager и установлена для него соответствующая политика запрещения опасной рефлексии , получить значение этой закрытой переменной не удастся.

Соответственно, мой вывод -- это API не является уязвимостью в JVM, вовсе нет.
Потому что точно так же рефлексией (если она не запрещена в политиках безопасности) можно творить безобразия внутри приложения, но и польза от нее может быть большая-- надо просто разумно выставлять политики безопасности в каждом конкретном случае.

Да - Unsafe API дает беспрецедентный уровень доступа к среде выполнения Java из программы. Но чтобы получить доступ к этому апи -- надо либо иметь соотв. права на той машине, где выполняется приложение (например, возможность задавать параметры запуска ява-машины), либо должен быть соответственно сконфигурирован (без учета этой опасности) Security Manager.