сопрограммы - C/C++

Всем привет

есть такая реализация сопрограмм

#define _WIN32_WINNT 0x400

#include <windows.h>

#include <stdio.h>

////////////////////////////////////////////////////////////////////////////////

// занимается превращением потока в нить и 
// гарантирует, что это будет сделано один раз
class GenBase
{
public:
  static volatile LONG tls_;

  GenBase()
  {
    DWORD newtls = ::TlsAlloc();
    DWORD oldtls = ::InterlockedCompareExchange(&tls_, newtls, 0);
    if (oldtls) ::TlsFree(newtls);

    if (::TlsGetValue(tls_)==0)
    {
      ::TlsSetValue(tls_, (LPVOID)1);
      base_fiber_=::ConvertThreadToFiber(0);
    } else
    {
      base_fiber_=::GetCurrentFiber();
    }
  }

protected:
  LPVOID base_fiber_;
};

////////////////////////////////////////////////////////////////////////////////

// где-то в cpp файле

volatile LONG GenBase::tls_ = 0;


////////////////////////////////////////////////////////////////////////////////

// собственно генератор

template<typename Result>
class Generator : public GenBase
{
public:
  Generator()
  : terminated_(false)
  {
    child_fiber_=::CreateFiber(0, 
      FiberStartProc,
      reinterpret_cast<LPVOID>(this));
  }

  ~Generator()
  {
    DeleteFiber(child_fiber_);
  }

protected:

  void yield(Result res)
  {
    result_ = res;
    SwitchToFiber(base_fiber_);
  }

private:
  static void CALLBACK FiberStartProc(LPVOID context)
  {
    reinterpret_cast<Generator*>(context)->start_fiber();
  }

  virtual void proceed() {}
  void start_fiber()
  {
    proceed();    

    terminated_=true;
    SwitchToFiber(base_fiber_);
  }

public:

  Result operator()()
  {
    // завершение функии нити фатально
    if (terminated_) 
      throw "error";

    ::SwitchToFiber(child_fiber_);
    return result_;
  }


private:
  LPVOID child_fiber_;

  Result result_;
  bool terminated_;
};


class Multi : public Generator<int>
{
public:
  void proceed()
  {
    // функция должна быть вечной
    // если она завершиться это приведет
    // к остановке всего потока
    for(unsigned index=0;; index+=2)
      yield(index);    
  }  
};


int main()
{

  Multi gen;
  Multi gen2;
  for(unsigned index=0; index<100; ++index)
  {
    int a = gen();
    int b = gen2();
    printf("index = %d result = %d %d \n", index, a, b);
  }

  return 0;
}

тут подробнее: http://www.rsdn.ru/forum/cpp/1687242.flat.aspx

есть ли примеры удачного применения из реальной жизни ?
интересно было бы посмотреть или хотя бы интересные мысли..
по удачному применению услышать

Здравствуйте, jyuyjiyuijyu, Вы писали:

J>есть ли примеры удачного применения из реальной жизни ?
J>интересно было бы посмотреть или хотя бы интересные мысли..
J>по удачному применению услышать

Я пишу в том числе для железок, в которых не хватает ресурсов для полноценных потоков, а многозадачность нужна. Использую сопрограммы (реализация своя собственная). Выглядит примерно так (это часть драйвера, управляющего сторонним оборудованием):

CL_line(SomeDriver::lineInit, LINE_INIT) // специальным образом оформленная функция
  
  enum { AfterCalcInit = STEP_USER, WaitClosed, CloseAll, ProductInit };

  CL_step0 
      if (calculatorInitDone())
        return AfterCalcInit;

      sendSomeCommand();
            
  CL_stepN(CloseAll)      // здесь происходит выход из функции и отправка данных устройству
      startCycle();       // После получения и обработки ответа вернемся сюда
      sendSomeCommand2();
  CL_step
      sendSomeCommand3();
  CL_step                 
      if (nextCycle())  
          return CloseAll;
      sendSomeCommand4();
  CL_step
      sendSomeCommand5();
  ...
CL_end

Когда потребовалось компилировать для десктопа, этот код без изменений заработал "внутри" boost::asio.

Использую такую реализацию уже года 2, потихоньку развиваю. Особых нареканий нет

Здравствуйте, jyuyjiyuijyu, Вы писали:

J>Всем привет

J>есть такая реализация сопрограмм
...
J>есть ли примеры удачного применения из реальной жизни ?
J>интересно было бы посмотреть или хотя бы интересные мысли..
J>по удачному применению услышать

Я использую свою собственную которая не требует threads и соотв. по мегабайту или сколько там аллоцируется стека на каждую сопрограмму.
Я не говорю что приведенная тобой имплементация не нужна или плоха, она просто затратна для большого количества use cases.

Это вот мой вариант: http://www.codeproject.com/Articles/29524/Generators-in-C

Использую это дело достаточно много в своих движках (htmlayout и sciter).
В основном имплементации всяко разных итераторов.

Скажем для прохода по DOM дереву используется такой патерн

void do_something_in(element* root)
{
   each_element it(root);
   for(element* c; it(c);)
     c->do_something();
}

Т.е. в данном случае работа ведется с деревом как с плоским набором. При этом each_element генератор знает как правильно развернуть дерево в каждом случае.

Вот например имплементации генераторов each_element и each_element_backward которые я использую.
Обход вперед и назад несколько несимметрчны. В случае назад посещяем сначала детей потом сам элемент.
Вперед — сам элемент потом детей.

$generator(each_element)
  {
    helement root;
    helement b;
    each_element( element* root_blk, element* start = 0 )
      : root(root_blk),b(start){}
    
    $emit(element*)
       if(!b) b = root->first_element();
       else   b = walk::first_or_next( b,root );
       for(;b; )
       {
           $yield(b); 
           b = walk::first_or_next( b,root );
       }
    $stop
  };

$generator(each_element_backward)
  {
    helement root;
    helement b;
    each_element_backward( element* root_blk, element* end= 0 )
      : root(root_blk), b(end) {}

    $emit(element*)
       if( !b ) b = root->last_element();
       else b = walk::very_last_or_prev( b,root );
       for(;b;)
       {
           $yield(b); 
           b = walk::very_last_or_prev( b,root );
       }
    $stop
  };

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

CALLBACK WndProc(HWND, UINT, WPAERAM, LPARAM)

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

WndProc()
{
    while (TRUE)
    {
        Msg = Next()
        // handling
    }
}

стек всегда под ногами и как по мне более очевидная
модель получения очередного сообщения конечно за
Next() скрывается магия по переключению стека и регистров
но зато как удобно бы стало

Здравствуйте, jyuyjiyuijyu, Вы писали:

J>

J>WndProc()
J>{
J>    while (TRUE)
J>    {
J>        Msg = Next()
J>        // handling
J>    }
J>}
J>

J>стек всегда под ногами и как по мне более очевидная
J>модель получения очередного сообщения конечно за
J>Next() скрывается магия по переключению стека и регистров
J>но зато как удобно бы стало

А какие особые удобства? Разве что переменные класса (или глобальные) переезжают в WndProc.
Преимущество от сопроцедур было бы, если бы сообщения приходили в определенном порядке. Тогда бы преимущество было бы значительным.

Например клиент подключился к серверу, считал документ1, считал документ 2:

void Proc()
{
  Connect(); // тут произойдет выход с сохранением стека, а обратно вернемся после подключения
  for (i = 1; i < 10; ++i)
  {
    readDocument(); // тут тоже выход, возврат после окончания чтения
    doSomething();
  }
}

классический асинхронный код будет выглядеть сильно хуже:

struct Proc
{
  int i;
  void Start() { Connect(bind(&Proc::OnConnect, this)); }
  void OnConnect() { i = 0; readDocument(bind(&Proc::OnRead, this)); }
  void onRead() { 
   doSomething();
   if (++i < 10)
     readDocument(bind(&Proc::OnRead, this));
  }
};

Здравствуйте, enji, Вы писали:

E>Преимущество от сопроцедур было бы, если бы сообщения приходили в определенном порядке. Тогда бы преимущество было бы значительным.

E>Например клиент подключился к серверу, считал документ1, считал документ 2:
E>классический асинхронный код будет выглядеть сильно хуже:

http://blog.think-async.com/2009/07/wife-says-i-cant-believe-it-works.html

благо, в составе boost-1.50 появятся сопрограммы (boost.context) с управляемым переключением контекста

Здравствуйте, enji, Вы писали:

>>>А какие особые удобства? Разве что переменные класса (или глобальные) переезжают в WndProc

ну хотя бы это сейчас в основном или юзают static в оконной процедуре
если надо сохронить состояние или глобальные переменные или как то прикрепляют
к данным класса окна и все эти извращения только из за того что по сути
программа живет в каллбеке а так бы жила в своем стеке и в цикле
(что на мой взгяд очевиднее) получала бы сообщения
а вообще я тут подумал на счет WndProc конечно там
такая реализация в силу многих причин и впринципе было бы сложно
сейчас реализовать модель получения сообщений в виде сопрограмм но если бы
это изначально закладывалось в архитеуктуру и проектировалось с этой
целью тогда может что и придумали бы

Здравствуйте, c-smile, Вы писали:

CS>Это вот мой вариант: http://www.codeproject.com/Articles/29524/Generators-in-C

круто раньше не было времени оценить )

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

а как такие написанные генераторы по проекту передвигаются в хидере ?

и еще как бы от while (0) избавиться

warning C4127: conditional expression is constant

так чтобы и статические анализаторы не ругались

Здравствуйте, jyuyjiyuijyu, Вы писали:

J>минус нельзя использовать рекурсивный генератор в отличии от примера в начале темы

Какой конкретно пример?

Если я правильно понял термин "рекурсивный генератор" то вот такое обсуждалось уже
http://rsdn.ru/forum/cpp/2971321.1.aspx

J>а вообще интересно в бусте сделают со своим стеком сопрограммы или нет если нет то это опять же ограниченно а если со своим то наверное через fiber'ы сделают переключение по крайней мере на винде иначе придется писать на ассемблере для каждой архитектуры свой переключатель

fiber это thread в смысле хранения вычислительного контекста, аллокации стека и пр.
Т.е. fiber это достаточно накладный механизм в плане потребления памяти (by default 2mb on stack or so) и CPU (thread context switch).

Делать генераторы/итераторы в стиле моего $generator на fibers черезвычайно накладно.
Для всех других применений coroutines вполне себе достаточно существующего мезанизма threads поэтому fibers "не пошли".

Здравствуйте, c-smile, Вы писали:

CS>Какой конкретно пример?

вот например вместо вызова каллбека можно было бы вызывать $yield

void traverse(rb_node *cur)
{
    if (cur->rb_left)
        traverse(cur->rb_left);
    $yield(cur);
    // callback(cur);
    if (cur->rb_right)
        traverse(cur->rb_right);
}

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

class rb_iterator : public Generator<rb_node*>
{
    rb_root *root_;

public:
    rb_iterator(rb_root *root) 
        : root_(root)
    {}

private:
    void proceed()
    {
        traverse(root_->rb_node);
    }  

    void traverse(rb_node *cur)
    {
        if (cur->rb_left)
            traverse(cur->rb_left);
        
        yield(cur);
        
        if (cur->rb_right)
            traverse(cur->rb_right);
    }
};

struct stuff
{
    unsigned int data;
    rb_node link;
};

int main()
{
    rb_root root = RB_ROOT;

    srand(GetTickCount());
    
    for (int i = 0; i < 10; i++)
    {
        stuff *p = new stuff;
        
        p->data = rand();
        
        rb_insert(&root, p);
    }

    rb_iterator iter(&root);
    rb_node *cur;

    while (iter(cur))
    {
        printf("%d\n", rb_entry(cur, stuff, link)->data);
    }

    // delete skipped
}

а вот сами изменения которые сделал (маленько в механике маленько в логике)

#include <windows.h>

#include <stdio.h>

////////////////////////////////////////////////////////////////////////////////

// занимается превращением потока в нить и 
// гарантирует, что это будет сделано один раз
class GenBase
{
public:
    static volatile LONG tls_;

    GenBase()
    {
        DWORD newtls = ::TlsAlloc();
        DWORD oldtls = ::InterlockedCompareExchange(&tls_, newtls, 0);
        if (oldtls) ::TlsFree(newtls);

        if (::TlsGetValue(tls_)==0)
        {
            ::TlsSetValue(tls_, (LPVOID)1);
            base_fiber_=::ConvertThreadToFiber(0);
        } else
        {
            base_fiber_=::GetCurrentFiber();
        }
    }

protected:
    LPVOID base_fiber_;
};

////////////////////////////////////////////////////////////////////////////////

// где-то в cpp файле

volatile LONG GenBase::tls_ = 0;


////////////////////////////////////////////////////////////////////////////////

// собственно генератор

template<typename Result>
class Generator : public GenBase
{
public:
    Generator()
        : terminated_(false)
    {
        child_fiber_=::CreateFiber(0, 
            FiberStartProc,
            reinterpret_cast<LPVOID>(this));
    }

    ~Generator()
    {
        DeleteFiber(child_fiber_);
    }

protected:

    void yield(Result res)
    {
        *result_ = res;
        SwitchToFiber(base_fiber_);
    }

private:
    static void CALLBACK FiberStartProc(LPVOID context)
    {
        reinterpret_cast<Generator*>(context)->start_fiber();
    }

    virtual void proceed() {}
    void start_fiber()
    {
        proceed();    

        terminated_=true;
        SwitchToFiber(base_fiber_);
    }

public:

    bool operator()(Result& res)
    {
        result_ = &res;

        if (terminated_) 
            return false;

        ::SwitchToFiber(child_fiber_);
        
        if (terminated_)
            return false;

        return true;
    }


private:
    LPVOID child_fiber_;

    Result *result_;
    bool terminated_;
};

Здравствуйте, c-smile, Вы писали:

CS>Делать генераторы/итераторы в стиле моего $generator на fibers черезвычайно накладно.
CS>Для всех других применений coroutines вполне себе достаточно существующего мезанизма threads поэтому fibers "не пошли".

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

;++
;
; VOID
; SwitchToFiber(
;    PFIBER NewFiber
;    )
;
; Routine Description:
;
;    This function saves the state of the current fiber and switches
;    to the new fiber.
;
; Arguments:
;
;    NewFiber (TOS+4) - Supplies the address of the new fiber.
;
; Return Value:
;
;    None
;
;--

cPublicProc _SwitchToFiber,1

        mov     edx,fs:[PcTeb]              ; edx is flat TEB
        mov     eax,[edx]+TbFiberData       ; eax points to current fiber


        ;
        ; Setup and save nonvolitile state
        ;


        mov     ecx,esp

        mov     [eax]+FbFiberContext+CsEbx,ebx
        mov     [eax]+FbFiberContext+CsEdi,edi
        mov     [eax]+FbFiberContext+CsEsi,esi
        mov     [eax]+FbFiberContext+CsEbp,ebp

        mov     ebx,[esp]                   ; get return address

        add     ecx,8                       ; adjust esp to account for args + ra
        mov     [eax]+FbFiberContext+CsEsp,ecx

        mov     [eax]+FbFiberContext+CsEip,ebx

        ;
        ; Save exception list, stack base, stack limit
        ;

        mov     ecx,[edx]+PcExceptionList
        mov     ebx,[edx]+PcStackLimit

        mov     [eax]+FbExceptionList,ecx
        mov     [eax]+FbStackLimit,ebx


        ;
        ; Now restore the new fiber
        ;

        mov     eax,[esp]+4                 ; eax is new fiber


        ;
        ; now restore new fiber TEB state
        ;

        mov     ecx,[eax]+FbExceptionList
        mov     ebx,[eax]+FbStackBase
        mov     esi,[eax]+FbStackLimit
        mov     edi,[eax]+FbDeallocationStack

        mov     [edx]+PcExceptionList,ecx
        mov     [edx]+PcInitialStack,ebx
        mov     [edx]+PcStackLimit,esi
        mov     [edx]+TbDeallocationStack,edi

        ;
        ; Restore FiberData
        ;

        mov     [edx]+TbFiberData,eax

        ;
        ; Restore new fiber nonvolitile state
        ;

        mov     edi,[eax]+FbFiberContext+CsEdi
        mov     esi,[eax]+FbFiberContext+CsEsi
        mov     ebp,[eax]+FbFiberContext+CsEbp
        mov     ebx,[eax]+FbFiberContext+CsEbx
        mov     ecx,[eax]+FbFiberContext+CsEip
        mov     esp,[eax]+FbFiberContext+CsEsp

        jmp     ecx

stdENDP _SwitchToFiber



WINBASEAPI
LPVOID
WINAPI
CreateFiber(
    DWORD dwStackSize,
    LPFIBER_START_ROUTINE lpStartAddress,
    LPVOID lpParameter
    )
{

    NTSTATUS Status;
    PFIBER Fiber;
    INITIAL_TEB InitialTeb;

    Fiber = RtlAllocateHeap( RtlProcessHeap(), MAKE_TAG( TMP_TAG ), sizeof(*Fiber) );
    if ( !Fiber ) {
        SetLastError(ERROR_NOT_ENOUGH_MEMORY);
        return Fiber;
        }

    Status = BaseCreateStack(
                NtCurrentProcess(),
                dwStackSize,
                0L,
                &InitialTeb
                );

    if ( !NT_SUCCESS(Status) ) {
        BaseSetLastNTError(Status);
        RtlFreeHeap(RtlProcessHeap(), 0, Fiber);
        return NULL;
        }

    Fiber->FiberData = lpParameter;
    Fiber->StackBase = InitialTeb.StackBase;
    Fiber->StackLimit = InitialTeb.StackLimit;
    Fiber->DeallocationStack = InitialTeb.StackAllocationBase;
    Fiber->ExceptionList = (struct _EXCEPTION_REGISTRATION_RECORD *)-1;
    Fiber->Wx86Tib = NULL;

#ifdef _IA64_

    Fiber->BStoreLimit = InitialTeb.BStoreLimit;
    Fiber->DeallocationBStore = InitialTeb.StackAllocationBase;

#endif // _IA64_

    //
    // Create an initial context for the new fiber.
    //

    BaseInitializeContext(
        &Fiber->FiberContext,
        lpParameter,
        (PVOID)lpStartAddress,
        InitialTeb.StackBase,
        BaseContextTypeFiber
        );

    return Fiber;
}

WINBASEAPI
VOID
WINAPI
DeleteFiber(
    LPVOID lpFiber
    )
{
    SIZE_T dwStackSize;
    PFIBER Fiber = lpFiber;



    //
    // If the current fiber makes this call, then it's just a thread exit
    //

    if ( NtCurrentTeb()->NtTib.FiberData == Fiber ) {
        ExitThread(1);
        }

    dwStackSize = 0;

    NtFreeVirtualMemory( NtCurrentProcess(),
                        &Fiber->DeallocationStack,
                        &dwStackSize,
                        MEM_RELEASE
                        );

#if defined (WX86)

    if (Fiber->Wx86Tib && Fiber->Wx86Tib->Size == sizeof(WX86TIB)) {
        PVOID BaseAddress = Fiber->Wx86Tib->DeallocationStack;

        dwStackSize = 0;

        NtFreeVirtualMemory( NtCurrentProcess(),
                            &BaseAddress,
                            &dwStackSize,
                            MEM_RELEASE
                            );
        }
#endif

    RtlFreeHeap(RtlProcessHeap(),0,Fiber);
}


WINBASEAPI
LPVOID
WINAPI
ConvertThreadToFiber(
    LPVOID lpParameter
    )
{

    PFIBER Fiber;
    PTEB Teb;

    Fiber = RtlAllocateHeap( RtlProcessHeap(), MAKE_TAG( TMP_TAG ), sizeof(*Fiber) );
    if ( !Fiber ) {
        SetLastError(ERROR_NOT_ENOUGH_MEMORY);
        return Fiber;
        }
    Teb = NtCurrentTeb();
    Fiber->FiberData = lpParameter;
    Fiber->StackBase = Teb->NtTib.StackBase;
    Fiber->StackLimit = Teb->NtTib.StackLimit;
    Fiber->DeallocationStack = Teb->DeallocationStack;
    Fiber->ExceptionList = Teb->NtTib.ExceptionList;
    Fiber->Wx86Tib = NULL;
    Teb->NtTib.FiberData = Fiber;


    return Fiber;
}

Здравствуйте, jyuyjiyuijyu, Вы писали:

J>вот при небольшом изменении кода с первого поста как
J>бы выглядел рекурсивный генератор для обхода
J>интрузивного красно черного дерева

Рекомендую написать простейший speed test для начала.
Чтобы понять сколько стоит ::SwitchToFiber(child_fiber_); со товарищи.

Здравствуйте, c-smile, Вы писали:

CS>Рекомендую написать простейший speed test для начала.
CS>Чтобы понять сколько стоит ::SwitchToFiber(child_fiber_); со товарищи.

выходит ::SwitchToFiber(child_fiber_); вообще ничего не стоит
если конечно не заниматься микрооптимизацией и не считать что
структуры FIBER не окажется в кеше процессора при переключении

зато как забавно становится писать и просто пользоваться
вот например два итератора rb_iterator и rb_reverse_iterator

class rb_iterator : public Generator<rb_node*>
{
    rb_root *root_;

public:
    rb_iterator(rb_root *root) 
        : root_(root)
    {}

private:
    void proceed()
    {
        traverse(root_->rb_node);
    }  

    void traverse(rb_node *cur)
    {
        if (cur->rb_left)
            traverse(cur->rb_left);
        
        yield(cur);
        
        if (cur->rb_right)
            traverse(cur->rb_right);
    }
};

class rb_reverse_iterator : public Generator<rb_node*>
{
    rb_root *root_;

public:
    rb_reverse_iterator(rb_root *root) 
        : root_(root)
    {}

private:
    void proceed()
    {
        traverse(root_->rb_node);
    }  

    void traverse(rb_node *cur)
    {
        if (cur->rb_right)
            traverse(cur->rb_right);

        yield(cur);

        if (cur->rb_left)
            traverse(cur->rb_left);
    }
};

int main()
{
    rb_root root = RB_ROOT;

    srand(GetTickCount());
    
    for (int i = 0; i < 10; i++)
    {
        stuff *p = new stuff;
        
        p->data = rand();
        
        rb_insert(&root, p);
    }

    rb_iterator iter(&root);
    rb_node *cur;

    while (iter(cur))
    {
        printf("%d\n", rb_entry(cur, stuff, link)->data);
    }

    puts("//////////////////////////////////");

    rb_reverse_iterator r_iter(&root);

    while (r_iter(cur))
    {
        printf("%d\n", rb_entry(cur, stuff, link)->data);
    }

    // delete skipped
}

	От:	jyuyjiyuijyu
	Дата:	16.03.12 00:08
	Оценка:

	От:	enji
	Дата:	16.03.12 05:49
	Оценка:

От:	c-smile	http://terrainformatica.com
Дата:	16.03.12 05:50
Оценка:	14 (2)

	От:	jyuyjiyuijyu
	Дата:	16.03.12 22:52
	Оценка:

	От:	enji
	Дата:	17.03.12 06:13
	Оценка:

От:	jazzer	Skype: enerjazzer
Дата:	17.03.12 06:54
Оценка:	10 (1)

От:	niXman	https://github.com/niXman
Дата:	17.03.12 18:59
Оценка:	2 (1)