Загрузка...

Ruby & Rails: веб-разработка с удовольствием

Ruby on Rails — фреймворк для создания веб-приложений. Является открытым программным обеспечением (лицензия MIT). Здесь мы обсуждаем новости RoR, делимся учебными материалами и интересными находками С RoR даже сложные веб-приложения могут быть написаны за считанные дни. Это действительно разработка с удовольствием!
     

6. Metaprogramming patterns — 17 кю. Как параллелить потоки данных и почему в Ruby не нужны колбэки

01.03.09, 00:17
Автор artem.voroztsov

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

Томас Дейв написал статью про то, как используя fibers, можно делать pipelines из обычных итераторов. Но последовательное соединение труб в одну - это классика и халява, а вот можно ли поток данных (итератор) расщеплять на несколько так, чтобы параллельно работало несколько преобразователей/фильтров потока? Расщеплять конечно можно, дописав класс Pipeline. А можно ли это сделать, не модифицируя код этих преобразователей/фильтров, и обеспечить при этом их параллельную работу с одним и тем же потоком данных? Metaprogramming + fibers do the job!

Предыдущие статьи

1. Metaprogramming patterns — 25кю. Метод eval
2. Metaprogramming patterns — 22кю. Reuse в малом — bang!
3. Metaprogramming patterns — 20 кю. Замыкания
4. Metaprogramming patterns 19 кю. Спасение утопающих дело рук самих утопающих
5. Metaprogramming patterns — 18 кю. Примеси

 

Лучше всего привести поясняющий код:

# A really expensive generator on objects 
# (дорогостоящий генератор объектов)
def each_number
  puts "each number orig before"
  (1..5).each do |n|
    yield(n)
  end
  puts "each number orig after"
end
def squares
  puts "squares before"
  each_number do |n|
    puts "s(#{n}) = #{n**2}"
  end
  puts "squares after"
end
def powers
  puts "powers before"
  each_number do |n|
    puts "p(#{n}) = #{2**n}"
  end
  puts "powers after"
end
# Two-pass algorithm (двупроходный алгоритм)
def do_it
  powers
  squares
end


В данном коде итератор each_number будет использован дважды.
Поток чисел генерировался дважды: сначала для однопроходного алгоритма powers, а затем - для однопроходного алгоритма squares:

 

powers before
each number orig before
p(1) = 2
p(2) = 4
p(3) = 8
p(4) = 16
p(5) = 32
each number orig after
powers after
squares before
each number orig before
s(1) = 1
s(2) = 4
s(3) = 9
s(4) = 16
s(5) = 25
each number orig after
squares after

Нельзя ли как-то избежать этого?
Хотелось бы, чтобы метод each_number запускался один раз, и чтобы он подсовывал генерируемые элементы как powers, так и squares.

Зачем это нужно?

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

Каждый из этих алгоритмов использует некоторый итератор each_page, который просто перебирает все документы. Надо сказать, что документов так много, что они не помещаются в оперативную память.
Заметим также, что итератор документов для каждого документа делает довольно сложный и местами дорогостоящий препроцессинг - преобразование формата документа (встречаются документы в форматах pdf, doc, html, txt - все они приводятся к некоторому унифицированному внутреннему представлению), определение его кодировки и конвертация при необходимости в UTF-8, преобразование некоторых специальных символов в упрощённые варианты, и др.

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

Для решения такого сорта задач в ОРП есть паттерн Visitor. Но как практически любой популярный паттерн ООП в Ruby он не популярен и не используется.

Нам помогут в решении этой задачи Fibers.

Что такое Fiber?

Про Fiber можно думать как про блок (некий кусок кода), который может несколько раз приостанавливать свою работу, каждый раз возвращая некоторый результат. Если переменная fiber хранит объект класса Fiber, то запускается он с помощью вызова fiber.resume. Собственно, Fiber и есть блок - последовательность инструкций, которую можно выполнить, с той лишь особенностью, что среди инструкций встречается одна специальная - Fiber.yield(result) - которая приостанавливает вычисления и возвращает результат в то место, где  был запущен fiber.resume.
С помощью очередного вызова метода resume можно продолжить вычисления с того места, где они были приостановлены (начиная с инструкции следующей непосредственно за последней выполненной инструкцией Fiber.yield(result)).

Пример немедленно проливает свет на определение:

fib = Fiber.new do
  f1 = f2 = 1
  loop do
    Fiber.yield f1
    f1, f2 = f2, f1 + f2
  end
end
puts "Первые 10 чисел фибоначчи:"
10.times { puts fib.resume }
puts "И еще 5 следующих:"
5.times { puts fib.resume }

 

В результате мы увидим первые 15 чисел Фибоначчи: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610.
Это пример объекта fiber, который не заканчивает свою работу - он представляет собой цикл, который генерирует сколь угодно много чисел Фибоначчи. На каждой итерации цикла он отдает результат наружу - очередное найденное им число - и приостанавливает вычисление до момента, пока не будет вызван его метод resume.

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

require 'fiber'
fib = Fiber.new do |f1,f2|
  loop do
    Fiber.yield f1
    f1, f2 = f2, f1 + f2
  end
end

 

Fibers do the job

Итак, давайте превратим наш двупроходный алгоритм в однопроходный.

require 'fiber'
alias :orig_each_number :each_number
def each_number
  puts "each number before "
  @iterator ||= Fiber.new{ orig_each_number{|n| 2.times {Fiber.yield(n)} } }
  while true
    begin
      yield(@iterator.resume)
      Fiber.yield
    rescue Exception=>e
      break
    end
  end
  puts "each number after"
end
def do_it
  @p = Fiber.new { powers }
  @s = Fiber.new { squares }
  while true
    begin
      @p.resume; @s.resume;
    rescue Exception=>e
      break
    end
  end
end
do_it

 

Задача для самостоятельного решения

Задача 1. Пусть есть некоторый модуль A, в котором есть метод-итератор each_object, и набор методов a, b, c, ... , которые используют этот итератор, и которые по сути есть некоторые однопроходные алгоритмы, обрабатывающие последовательность элементов, выдаваемых методом each_object:

module A
  def each_object(*args, &block)
    # ...
  end
 
  def a
    # ...
  end
  def b
    # ...
  end
 
  def c
    # ...
  end
end



Напишите такой модуль share_iterator, предоставляющий метод share_iterator, который позволял бы несколько однопроходных алгоритмов "упаковывать" в один однопроходный:

 

 

require 'share_iterator' 
A.class_eval { share_iterator :each_object, :each_object_shared_for  }
include A
each_object_shared_for [:a, :b, :c] # параллельный запуск методов a, b и с

 

Сложным моментом при решении этой задачи является обеспечение неизменяемости метода each_object - он во всех контекстах должен работать также как и раньше, как до, так и после выполнения указанных методов (как share_iterator, так и each_page_shared_for), а также во время их выполнения (если, конечно, используются нити (threads)).

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

Удачи!

Почему в Ruby не нужны колбэки

Итак, партизанскими методами N-проходные алгоритмы можно превращать в однопроходные.
Какое фундаментальное понимание даёт нам этот пример?
Во-первых, давайте вспомним, как аналогичные вещи делаются в языке C++/Java:
Каждый разработчик однопроходного алгоритма пишет некоторый класс, удовлетворяющий интерфейсу Visitor (обработчик), который имеет методы initialize, visit(object), finalize. Имея такой интерфейс, несложно запараллелить несколько обработчиков. Для этого создается некоторый итератор объектов, в котором регистрируются различные обработчики (visitors), затем этот итератор запускает методы initialize различных зарегистрированных в нём обработчиков (visitors), потом итерирует объекты и каждый объект подсовывает функции visit каждого обработчика, а по окончании итерирования вызывает методы finalize у каждого обработчика.

В принципе это несложно, и при желании всё это можно оформить красиво и кратко, но не думаю, что получится короче представленных выше 4 строчек кода.

Разнообразные комбинирования (последовательное применение, распараллеливание, слияние и др) итераторов, обработчиков, фильтров и т.д. мне видятся важнейшими, часто используемыми задачами, и использование удобных механизмов, подобных share_iterator, способно сделать ткань кода более ясной и краткой.

Visitor - это типичный шаблон обычного программирования. И мы видим, что этот шаблон оказывается просто не нужен в динамических языках.
Есть возможность не усложнять абстракцию однопроходного алгоритма (не требовать наличия трёх функций вместо одной).
Можно говорить разработчикам однопроходных алгоритмов, чтобы они не беспокоились о том, как работа их обработчика будет параллелиться с другими. Разработчики однопроходных алгоритмов могут думать, что они одни во вселенной, и писать лишь один метод, в котором как-либо используется некоторый внешний итератор each_object.

Прикрепил файл с простейшей реализацией класса Fiber на основе класса Thread.

список файлов:
fiber.rb

Комментарии

Войдите, чтобы оставить комментарий