четверг, 9 октября 2014 г.

[prog.flame] Очередной CodeSize Battle: CAF/libcppa vs SObjectizer-5.5.1

Продолжу относительно бесполезное занятие, а именно -- сравнивание похожего кода по такому архиважному критерию, как длина :)

На этот раз в сравнении принимают участие C++ Agent Framework (он же CAF, он же libcaf, он же libcppa) и находящаяся в разработке версия 5.5.1 SObjectizer-а. В качестве примера взят код dining_philosophers из CAF-а и реализовано что-то похожее на SO-5.5.1.

Для начала пару слов о том, в чем суть. Этот пример иллюстрирует проблему обедающих философов. Каждый философ -- это агент, который какое-то время думает, потом становится голодным и пытается взять левую и правую вилки, чтобы поесть. Когда ему это удается, он ест, после чего кладет вилки обратно, а сам возвращается к процессу думания. В классической постановке задачи философ сначала должен брать левую от себя вилку, только затем правую. Но в примере из CAF-а делается "оптимизация" -- философ пытается схватить две сразу. Вероятно, этот вариант был выбран специально, для того, чтобы показать переходы между состояниями агента в условиях, когда порядок получения ответов недетерминирован.

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

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

Так же, насколько я понимаю, в коде есть важное отличие. В реализации CAF если философу не удалось взять вилку, он возвращается в состояние thinking, но тут же отсылает себе сообщение eat, т.е. сразу же начинает попытки взять вилки снова. В реализации SObjectizer если агент не смог взять вилки, то он возвращается в состояние st_thinking и какое-то время думает, не пытаясь вернуться к столу. Впрочем, это как раз интересный момент для читателей: насколько просто из каждого примера понять точный алгоритм работы :)

Еще одно замечание перед слайдами. Код CAF написан в своем стиле, с использованием директив using namespace, поэтому в нем используются короткие имена, например, actor и behavior вместо caf::actor и caf::behavior. Тогда как код из SObjectizer написан в своем стиле и using namespace в нем не используются, поэтому там so_5::rt::agent_t вместо agent_t. Я не стал уменьшать объем кода в SObjectizer потому, что это гораздо ближе к реальному использованию SO в больших проектах.

Начнем с самого простого. С кода агентов, которые выступают в качестве вилок. Слева код из CAF, справа из SObjectizer:

void chopstick(event_based_actor* self) {
  self->become(
    on(atom("take"), arg_match) >> [=](const actor& philos) {
      // tell philosopher it took this chopstick
      self->send(philos, atom("taken"), self);
      // await 'put' message and reject other 'take' messages
      self->become(
        // allows us to return to the previous behavior
        keep_behavior,
        on(atom("take"), arg_match) >> [=](const actor& other) {
          self->send(other, atom("busy"), self);
        },
        on(atom("put"), philos) >> [=] {
          // return to previous behaivor, i.e., await next 'take'
          self->unbecome();
        }
      );
    }
  );
}
class a_fork_t : public so_5::rt::agent_t
{
public :
   a_fork_t( so_5::rt::environment_t & env )
      :  so_5::rt::agent_t( env )
   {}

   virtual void
   so_define_agent() override
   {
      this >>= st_free;

      st_free.handle( [=]( const msg_take & evt )
            {
               this >>= st_taken;
               so_5::send< msg_taken >( evt.m_who, so_direct_mbox() );
            } );

      st_taken.handle( []( const msg_take & evt )
            {
               so_5::send< msg_busy >( evt.m_who );
            } )
         .handle< msg_put >( [=]() { this >>= st_free; } );
   }

private :
   const so_5::rt::state_t st_free = so_make_state( "free" );
   const so_5::rt::state_t st_taken = so_make_state( "taken" );
};

Тут нужно сделать одно важное дополнение. Тогда как код из CAF самодостаточный, коду из SObjectizer-а нужны определения структур, которые будут использоваться в качестве сообщений и сигналов. Поэтому код из SObjectizer можно было бы увеличить вот на этот фрагмент:

struct msg_take : public so_5::rt::message_t
{
   const so_5::rt::mbox_ref_t m_who;

   msg_take( so_5::rt::mbox_ref_t who ) : m_who( std::move( who ) ) {}
};

struct msg_busy : public so_5::rt::signal_t {};

struct msg_taken : public so_5::rt::message_t
{
   const so_5::rt::mbox_ref_t m_who;

   msg_taken( so_5::rt::mbox_ref_t who ) : m_who( std::move( who ) ) {}
};

struct msg_put : public so_5::rt::signal_t {};

Но я не стал этого делать потому, что на объем логики агента это никак не влияет. Кроме того, наличие таких определений повышает надежность приложения за счет помощи от компилятора. В коде из CAF компилятор не может помочь проконтролировать, что ему будут отсылать сообщения "take" и "put". Вдруг кто-то по ошибке напишет "Take" и "Put"? Опять же, этот агент отсылает сообщение taken с одним параметром. Компилятор не помогает проверить, а действительно ли у этого сообщения имя taken, а не Taken. И действительно ли в этом сообщении один параметр или два? Или не одного? Если сообщения оформлены в виде структур, как в коде из SObjectizer, то компилятор проверяет и корректность имен, и корректность вызова конструктора и т.д. Т.е. коэффицент спокойного сна у разработчика серьезно повышается :)

Далее самое интересное -- это логика агента-философа. Ниже я приведу лишь фрагменты кода агентов-философов, которые имеют прямое отношение к реализации этой логики (слева CAF, справа SO):

class philosopher : public event_based_actor {
 public:
  philosopher(const std::string& n, const actor& l, const actor& r)
      : name(n), left(l), right(r) {
    // a philosopher that receives {eat} stops thinking and becomes hungry
    thinking = (
      on(atom("eat")) >> [=] {
        become(hungry);
        send(left, atom("take"), this);
        send(right, atom("take"), this);
      }
    );
    // wait for the first answer of a chopstick
    hungry = (
      on(atom("taken"), left) >> [=] {
        become(waiting_for(right));
      },
      on(atom("taken"), right) >> [=] {
        become(waiting_for(left));
      },
      on<atom("busy"), actor>() >> [=] {
        become(denied);
      }
    );
    // philosopher was not able to obtain the first chopstick
    denied = (
      on(atom("taken"), arg_match) >> [=](const actor& ptr) {
        send(ptr, atom("put"), this);
        send(this, atom("eat"));
        become(thinking);
      },
      on<atom("busy"), actor>() >> [=] {
        send(this, atom("eat"));
        become(thinking);
      }
    );
    // philosopher obtained both chopstick and eats (for five seconds)
    eating = (
      on(atom("think")) >> [=] {
        send(left, atom("put"), this);
        send(right, atom("put"), this);
        delayed_send(this, seconds(5), atom("eat"));
        aout(this) << name << " puts down his chopsticks and starts to think\n";
        become(thinking);
      }
    );
  }

 protected:
  behavior make_behavior() override {
    // start thinking
    send(this, atom("think"));
    // philosophers start to think after receiving {think}
    return (
      on(atom("think")) >> [=] {
        aout(this) << name << " starts to think\n";
        delayed_send(this, seconds(5), atom("eat"));
        become(thinking);
      }
    );
  }

 private:
  // wait for second chopstick
  behavior waiting_for(const actor& what) {
    return {
      on(atom("taken"), what) >> [=] {
        aout(this) << name
                   << " has picked up chopsticks with IDs "
                   << left->id() << " and " << right->id()
                   << " and starts to eat\n";
        // eat some time
        delayed_send(this, seconds(5), atom("think"));
        become(eating);
      },
      on(atom("busy"), what) >> [=] {
        send((what == left) ? right : left, atom("put"), this);
        send(this, atom("eat"));
        become(thinking);
      }
    };
  }
class a_philosopher_t : public so_5::rt::agent_t
{
   struct msg_stop_thinking : public so_5::rt::signal_t {};
   struct msg_stop_eating : public so_5::rt::signal_t {};

public :
   a_philosopher_t(
      so_5::rt::environment_t & env,
      std::string name,
      so_5::rt::mbox_ref_t left_fork,
      so_5::rt::mbox_ref_t right_fork )
      :  so_5::rt::agent_t( env )
      ,  m_name( std::move( name ) )
      ,  m_left_fork( std::move( left_fork ) )
      ,  m_right_fork( std::move( right_fork ) )
   {}

   virtual void
   so_define_agent() override
   {
      st_thinking.handle< msg_stop_thinking >( [=]{
            show_msg( "become hungry, try to take forks" );
            this >>= st_hungry;

            so_5::send< msg_take >( m_left_fork, so_direct_mbox() );
            so_5::send< msg_take >( m_right_fork, so_direct_mbox() );
         } );

      st_hungry.handle( [=]( const msg_taken & evt ) {
            show_msg( fork_name( evt.m_who ) + " fork taken" );
            m_first_taken = evt.m_who;
            this >>= st_one_taken;
         } )
         .handle< msg_busy >( [=]{ this >>= st_denied; } );

      st_one_taken.handle( [=]( const msg_taken & evt ) {
            show_msg( fork_name( evt.m_who ) + " fork taken" );
            show_msg( "take both forks, start eating" );
            this >>= st_eating;
            so_5::send_delayed_to_agent< msg_stop_eating >(
               *this, random_pause() );
         } )
         .handle< msg_busy >( [=]{
            show_msg( "put " + fork_name( m_first_taken ) +
               " down because " + opposite_fork_name( m_first_taken ) +
               " denied" );
            so_5::send< msg_put >( m_first_taken );
            think();
         } );

      st_denied.handle( [=]( const msg_taken & evt ) {
            show_msg( "put " + fork_name( evt.m_who ) +
               " down because " + opposite_fork_name( evt.m_who ) +
               " denied" );
            so_5::send< msg_put >( evt.m_who );
            think();
         } )
         .handle< msg_busy >( [=]{
            show_msg( "both forks busy" );
            think();
         } );

      st_eating.handle< msg_stop_eating >( [=]{
            show_msg( "stop eating, put forks, return to thinking" );
            so_5::send< msg_put >( m_right_fork );
            so_5::send< msg_put >( m_left_fork );
            think();
         } );
   }

   virtual void
   so_evt_start() override
   {
      think();
   }

Не берусь пересказывать логику работы агента из CAF, поэтому объясню на пальцах, как работает агент из SO.

После старта агент входит в состояние st_thinking и отсылает себе отложенное сообщение msg_stop_thinking. Когда это сообщение приходит он переходит в st_hungry и посылает вилкам запрос msg_take. Когда приходит первый успешный ответ, агент переходит в состояние st_one_taken. Если первым приходит отрицательный ответ, то агент переходит в st_denied. В состоянии st_one_taken агент ждет либо положительного ответа от второй вилки (тогда он уходит в st_eating), либо отрицательного (тогда первая вилка кладется на стол, а философ уходит в st_thinking). В состоянии st_denied агент ждет любого ответа: если отрицательный, то просто идет в st_thinking, если положительный, то эта вилка сначала кладется на стол, а уже потом возвращается в st_thinking. В состоянии же st_eating философ ждет отложенного сообщения msg_stop_eating после чего возвращается в st_thinking.

Кроме кода, реализующего основную логику агентов, в классах агентов есть еще и вспомогательный код. Вот он (слева CAF, справа SO):

std::string name;   // the name of this philosopher
actor       left;   // left chopstick
actor       right;  // right chopstick
behavior    thinking;
behavior    hungry; // tries to take chopsticks
behavior    denied; // could not get chopsticks
behavior    eating; // wait for some time, then go thinking again
private :
   const so_5::rt::state_t st_thinking = so_make_state();
   const so_5::rt::state_t st_hungry = so_make_state();
   const so_5::rt::state_t st_denied = so_make_state();
   const so_5::rt::state_t st_one_taken = so_make_state();
   const so_5::rt::state_t st_eating = so_make_state();

   const std::string m_name;

   const so_5::rt::mbox_ref_t m_left_fork;
   const so_5::rt::mbox_ref_t m_right_fork;

   so_5::rt::mbox_ref_t m_first_taken;

   std::string
   fork_name( const so_5::rt::mbox_ref_t & fork ) const
   {
      return (m_left_fork == fork ? "left" : "right");
   }

   std::string
   opposite_fork_name( const so_5::rt::mbox_ref_t & fork ) const
   {
      return (m_left_fork == fork ? "right" : "left");
   }

   void
   show_msg( const std::string & msg ) const
   {
      std::cout << "[" << m_name << "] " << msg << std::endl;
   }

   void
   think()
   {
      show_msg( "start thinking" );
      this >>= st_thinking;
      so_5::send_delayed_to_agent< msg_stop_thinking >( *this, random_pause() );
   }

   static std::chrono::milliseconds
   random_pause()
   {
      return std::chrono::milliseconds( 250 + (std::rand() % 250) );
   }

В заключение можно еще и привести код запуска тестов, просто так, для чистоты эксперимента (слева CAF, справа SO):

void dining_philosophers() {
  scoped_actor self;
  // create five chopsticks
  aout(self) << "chopstick ids are:";
  std::vector<actor> chopsticks;
  for (size_t i = 0; i < 5; ++i) {
    chopsticks.push_back(spawn(chopstick));
    aout(self) << " " << chopsticks.back()->id();
  }
  aout(self) << endl;
  // spawn five philosophers
  std::vector<std::string> names {"Plato""Hume""Kant",
                                   "Nietzsche""Descartes"};
  for (size_t i = 0; i < 5; ++i) {
    spawn<philosopher>(names[i], chopsticks[i], chopsticks[(i + 1) % 5]);
  }
}
void
init( so_5::rt::environment_t & env )
{
   const std::size_t count = 5;

   auto coop = env.create_coop( "dining_philosophers" );

   std::vector< so_5::rt::agent_t * > forks( count, nullptr );
   for( std::size_t i = 0; i != count; ++i )
      forks[ i ] = coop->add_agent( new a_fork_t( env ) );

   for( std::size_t i = 0; i != count; ++i )
      coop->add_agent(
         new a_philosopher_t( env,
            std::to_string( i ),
            forks[ i ]->so_direct_mbox(),
            forks[ (i + 1) % count ]->so_direct_mbox() ) );

   env.register_coop( std::move( coop ) );

   std::this_thread::sleep_for( std::chrono::seconds(20) );
   env.stop();
}

Полные тексты примеров можно найти в репозиториях проектов: CAF, SObjectizer.

Ну а теперь, собственно, итоги. Пока SObjectizer значительно отстает в лаконичности от CAF. Хотя в значительной (как мне кажется) степени это компенсируется большим контролем за происходящим со стороны компилятора. О понятности каждого из вариантов каждый читатель пусть судит сам. Лично мне код из CAF представляется менее понятным, чем код из SObjectizer.

Кроме того, если читатель планирует плотно пользоваться C++ в ближайшие годы, то пусть знает, что его ждет :) Авторы CAF его сейчас активно пиарят и лелеют планы по добавлению в Boost. Ну а то, что попадает в Boost... Так что не исключено, что кому-то из читателей через пару-тройку лет волей-неволей придется разбираться, что такое become и unbecome и в какой именно момент начинает исполняться behavior ;)

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