Продолжения

[thedeemon]

В свежем номере ПФП замечательная статья про продолжения. К сожалению, в качестве примеров там зачем-то приведены дампы памяти интерпретатора плохо типизированного лямбда-исчисления, формат которых некоторые ошибочно называют языком программирования. К счастью, история знает пример настоящего языка программирования с поддержкой продолжений - Руби версий до 1.8 включительно (поскольку поддержка продолжений была одной из причин тормознутости интерпретатора, а сами продолжения никому не нужны, то в версии 1.9 их выкинули).

Посмотрим, как на Руби выглядит пример с поиском общего префикса у деревьев. По условию задачи у нас есть некая структура данных (в данном случае дерево) и для нее есть функция, которая последовательно обходит элементы и для каждого вызывает наш callback. Т.е. это активный итератор в стиле Руби, в отличие от пассивных итераторов в стиле С++/C#/Java. Пусть наше дерево представлено массивом, элементы которого могут быть либо листьями дерева, либо такими же массивами-деревьями:
tree1 = [1, [2,3], [[[4,5], 6]], 7, 8]
tree2 = [[1,2], [[3,4], 0,0], 1]
Тогда итератор выглядит так:

def iterate_tree(tree, &f)
if tree.is_a? Array
tree.each{|x| iterate_tree(x, &f) }
else
yield tree
end
end
Чтобы вывести последовательно все элементы дерева его можно использовать так:

iterate_tree(tree1) {|x| print x}

Теперь мы хотим определить для двух деревьев длину общего префикса - число совпадающих при последовательном обходе с начала листьев, используя такие итераторы, но не обходя деревья целиком. Для этого при создании колбэка сохраним контекст вычисления главного потока в виде продолжения с именем main_thread, вызванный итератором колбэк будет вызывать это продолжение, тем самым передавая управление главному потоку, а также передавая ему параметром собственное продолжение под именем iteration_thread, которое, будучи вызванным из главного потока, продолжит работу колбэка, чтобы итератор продолжил работу и пошел на следующую итерацию, где все повторится. Главный поток на каждой итерации цикла передает свое продолжение main_thread, которое колбэк внутри себя обновляет, чтобы возвращаться не в начало обхода, а в нужное место. Звучит страшно, но код довольно короткий:

def start_iteration(tree, main_thread)
  iterate_tree(tree) {|x| 
    main_thread = callcc {|iteration_thread| 
      main_thread.call(x, iteration_thread) 
    }
  }
  main_thread.call(nil, nil)
end

def loop(iter1, iter2, n)
  x1, it1 = callcc { |main_thread|  iter1.call(main_thread) }
  x2, it2 = callcc { |main_thread|  iter2.call(main_thread) }  
  if x1 && x2 && x1==x2 then loop(it1, it2, n+1) else n end
end

def prefix_length(tr1, tr2)
  loop( lambda {|c| start_iteration(tr1,c)}, lambda {|c| start_iteration(tr2,c)}, 0 )
end

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

Если вызвать prefix_length для описанных выше tree1 и tree2 и вывести результат,

p prefix_length(tree1, tree2)

будет выведено 4.

Comments

[soonts.livejournal.com]

Почитал раздел "Продолжения в практике".
Да я понимаю "зачем", не понимаю "зачем так".
Готов спорить на пиво, что моё решение на C# + async CTP (async CTP кстати очень полезное для подобных задач расширение C#) займёт столько же или меньше строк кода по сравнению с его схемой, при этом на том же железе будет работать минимум в полтора раза быстрее (какие на фиг селекты для серверов — в мире Windows IOCP, в *nix epoll, в BSD kqueue)

[thedeemon.livejournal.com]

Ну нужно было придумать какое-то применение продолжениям. :)

[usovalx.livejournal.com]

На продолжениях аналог async CTP делается абсолютно элементарно.

Да и на чистом C# 4.0 его вполне можно сделать: диспетчер, самодельный аналог ITask<> и yield return. Синтаксис правда будет тот ещё.

Так что смысл вашего коментария судя по всему сводится к тому, что у C# виртуальная машина вылизаннее и быстрее. Ну так с этим вроде никто и не спорит. Или я что-то большое пропустил?

[soonts.livejournal.com]

>на чистом C# 4.0 его вполне можно сделать: диспетчер
async CTP ощутимо сложнее диспетчера (который просто очередь для единственного потока). Например 2 async функции (если ты обе запустишь в CLR thread pool) могут исполняться сначала одновременно на ядрах 1 и 2, потом (после операторов await в каждой из них) легко могут попасть наоборот на ядра 2 и 1. Такой гибкости в использовании ресурсов с сохранением ± логической целостности кода (= instruction pointer, call stack, local variables) не получишь никакими yields.

>что-то большое пропустил?
IMO разница скорости VM в данном случае фигня, основная проблема неверно выбранная socket I/O strategy..

[usovalx.livejournal.com]

Пункт 1 дополнительно обосновать можешь? Потому как вся семантика логической целостности кода и т.п. уже обеспечивается yield return'ом.

2 - это о том что в примере используется select вместо православных epoll/kqueue/чего там в винде? Так то что нарисовано в статье должно довольно тривиально обобщаться до любого из этих вариантов (или libev/libevent).

[usovalx.livejournal.com]

Да, ещё момент касательно C# -- в условиях когда клиентов не особенно много (50-100, чтобы select не совсем уж проседал) я бы скорее поставил на версию с select на линуксах чем async CTP на винде ;) И сеть и IO в винде весьма тормознутые.

[soonts.livejournal.com]

>И сеть и IO в винде весьма тормознутые.
Bullshit. Например IIS выигрывает у apache на том же железе на десятки процентов.

Касательно C# — весь асинхронный I/O в C# использует I/O completion port, встроенный в чезвычайно эффективный CLR thread pool.

[usovalx.livejournal.com]

Блин, ну нафиг мне этот IIS/apache.

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

[soonts.livejournal.com]

1. Семантика может и обеспечивается. Однако чтобы на её основе сделать насколько эффективный scheduler как это сделано в CTP, надо написать довольно много кода. Например в ряде случаев return напрямую вызывает того, кто ждёт на await, без всяких kernel calls / context switches. Async CTP .DLL занимает 100kb — для managed сборки это довольно много.

2. Да. И кстати, I/O completion ports: windows NT 3.5, 1994 год. Kqueue: BSD 4.1, 2000 год. Epoll: linux kernel 2.5.44, 2002 год. Характерно, что у разработчиков ядра linux на то чтобы спиздить хорошую design-идею ушло 8 лет — прекрасный показатель по которому можно оценить отставание open source технологий.

[usovalx.livejournal.com]

1. Если я правильно понимаю их семантику, то вложенные await должны исполняться без переключения контекстов. И только возвращение значения в основной поток будет протаскиваться в ITask через thread barrier. Точнее не так -- пересекать thread barrier также прийдётся и при ожидании нескольких асинхронных задач.

2. Весьма радикальное мнение. Как по мне востребованность в них была не особенно острой. В той-же солярке /dev/poll появился только в 99м.