Coroutine demo source

Question

Voici un exemple de programme, où les coroutines contribuent vraiment à simplifier les choses l'algorithme - à mon avis, il n'est guère possible de l'implémenter autrement. J'ai également essayé de choisir une tâche utile pour la démo - cet utilitaire convertit un fichier binaire en une séquence de symboles A-Z (et vice-versa), sans aucune redondance significative, et il a la capacité de travailler avec n'importe quel alphabet spécifié (voir la ligne M.Init). En fait, il s'agit d'une sorte de base64 généralisée. Le code est testé et fonctionne avec MSC, IntelC et gcc/mingw.

Mise à jour : l'algorithme est basé sur un codage arithmétique précis, il ne s'agit donc pas d'une ligne unique par défaut. Il peut être possible de le réduire de moitié en utilisant les entrées/sorties de fichiers putc/getc. (il ne resterait alors qu'une classe rangecoder modifiée et do_process()), mais ce serait alors très limité (par exemple, il ne serait pas possible de décoder un décoder un bloc mémoire ou un flux réseau). En fait, les coroutines sont utilisées ici pour optimiser la vitesse, et c'est l'objet de ce billet. Malheureusement, je n'ai pas d'application plus simple pour le démontrer correctement. Je pourrais écrire un compresseur de modélisation de contexte à la place, mais cela reviendrait à 100 lignes de plus.

Questions :
1) Comment remplacer la macro INCLUDE_PROCESS_TEMPLATE par du code C++ approprié ?
2) Existe-t-il un moyen d'implémenter ceci sans coroutines ?
(mais toujours avec un encodage en mémoire et des entrées/sorties de fichiers en mémoire tampon)
3) Des corrections/améliorations ?

#include <io.h>
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include <setjmp.h>
#define NOINLINE __declspec(noinline)

typedef unsigned int   uint;
typedef unsigned char  byte;
typedef unsigned long long int qword;

enum{ STKPAD=1<<16 };
struct coroutine {
  volatile int   state;
  volatile byte* inpptr;
  volatile byte* inpbeg;
  volatile byte* inpend;
  volatile byte* outptr;
  volatile byte* outbeg;
  volatile byte* outend;
  jmp_buf PointA, PointB;
  void yield( int value ) { if( setjmp(PointB)==0 ) { state=value; longjmp(PointA,value); } }
  void chkinp( void ) { if( inpptr>=inpend ) yield(1), inpptr=*&inpptr; }
  void chkout( void ) { if( outptr>=outend ) yield(2); }
  template <int f> byte get( void ) { if( f ) chkinp(); return *inpptr++; }
  template <int f> void put( uint c ) { *outptr++ = c; if( f ) chkout(); }
  void coro_init( void ) { inpptr=inpbeg=inpend=0; outptr=outbeg=outend=0; state=0; }
  void addinp( byte* inp,uint inplen ) { inpbeg=inpptr=inp; inpend=&inp[inplen]; }
  void addout( byte* out,uint outlen ) { outbeg=outptr=out; outend=&out[outlen]; }
};

#define INCLUDE_PROCESS_TEMPLATE \
NOINLINE void call_do_process() { byte stktmp[STKPAD]; state=ptrdiff_t(stktmp); do_process(); } \
int coro_process( void ) { if( setjmp(PointA)==0 ) if( state ) longjmp(PointB,3); else call_do_process(); return state; } 

struct Rangecoder_SH1x : coroutine {
  enum { SCALElog=15, SCALE=1<<SCALElog };
  enum { NUM=4, sTOP=0x01000000U, Thres=0xFF000000U };
  uint f_decode; // 0=encode, 1=decode;
  uint range, Cache, FFNum;
  union {
    struct { uint low; uint Carry; };
    qword lowc;
    uint  code; 
  };
  uint rc_BProcess( uint freq, uint bit ) { 
    uint rnew = (range>>SCALElog)*freq;
    if( f_decode ) bit = (code>=rnew);
    range = ((range-rnew-rnew)&(-bit)) + rnew;
    rnew &= -bit;
    if( f_decode ) code-=rnew; else lowc+=rnew;
    if( f_decode ) while( range<sTOP ) range<<=8, (code<<=8)+=get<1>();
    else while( range<sTOP ) range<<=8, ShiftLow();
    return bit;
  }
  void ShiftLow( void ) {
    if( low<Thres || Carry ) {
      put<1>( Cache+Carry );
      for(; FFNum!=0; FFNum-- ) put<1>( Carry-1 );
      Cache=low>>24; Carry=0;
    } else FFNum++;
    low<<=8;
  }
  void rc_Init( int DECODE ) {
    f_decode=DECODE; range=-1; lowc=FFNum=Cache=0;
    if( f_decode ) for(int _=0; _<NUM+0; _++) (code<<=8)+=get<1>(); 
  }
};

struct Model : Rangecoder_SH1x {
  uint DECODE, f_quit;
  enum{ lCNUM=8, CNUM=1<<lCNUM, ROWSIZE=80 };
  uint count[2*CNUM];
  enum{ inpbufsize=1<<16, outbufsize=1<<16 };
  byte inpbuf[inpbufsize], outbuf[outbufsize];

  void Init( const char* s ) {
    uint i,j;
    uint (&p)[CNUM] = (uint(&)[CNUM])count[CNUM];
    for( i=0; i<2*CNUM; i++) count[i]=0;
    for( i=0; s[i]; i++ ) p[byte(s[i])]++;
    for( j=0; j<lCNUM; j++ ) for( i=(CNUM>>j); i<((CNUM+CNUM)>>j); i++ ) count[i>>1] += count[i];
  }

  INCLUDE_PROCESS_TEMPLATE
  void do_process( void ) {
    uint i,j;
    rc_Init(1-DECODE);
    for( i=0; !f_quit; i++ ) {
      uint c=0, ctx=1;
      if( DECODE ) do c=get<1>(); while( c==10 );
      for( j=lCNUM-1; j!=-1; j-- ) {
        uint freq = count[ctx*2+0]*SCALE/(count[ctx*2+0]+count[ctx*2+1]);
        ctx += ctx + ((freq==0) ? 1 : (freq==SCALE) ? 0 : rc_BProcess(freq,(c>>j)&1));
      }
      if( !DECODE ) put<1>(ctx), (((i+1)%ROWSIZE==0)?put<1>(10),0:0);
    }
    yield(0);
  }

  void ProcessFile( uint Mode, FILE* f, FILE* g ) {
    volatile uint r; volatile qword g_len=0; uint f_len=0;
    DECODE=Mode; f_quit=0;
    if( DECODE ) addout( (byte*)&g_len, sizeof(f_len)+1 ), r=1;
    else f_len=filelength(fileno(f)), addinp( (byte*)&f_len, sizeof(f_len) ),addout(0,0), r=2;
    do {
      if( r==1 ) {
        uint l = fread( inpbuf, 1, inpbufsize, f );
        if( l>0 ) {
          addinp( inpbuf, l );
        } else {
          if( inpbeg==inpbuf+1 ) f_quit=1;
          memset( inpbuf, 0x80, inpbufsize );
          addinp( inpbuf+1, 5 ); 
        }
      } else if( r==2 ) {
        if( outbeg==outbuf ) fwrite( outbuf, 1, outptr-outbeg, g ); else g_len>>=8;
        addout( outbuf, outbufsize );
      }
      r = coro_process(); 
    } while(r);
    fwrite( outbuf, 1,outptr-outbuf, g ); // flush
    if( DECODE==0 ) fputc( 10, g ); else fflush(g), chsize( fileno(g), g_len );
  }

} M;

int main( int argc, char** argv ) {
  if( argc<4 ) return 1;
  int DECODE = argv[1][0]=='d';
  FILE* f = fopen( argv[2], "rb" ); if( f==0 ) return 2;
  FILE* g = fopen( argv[3], "wb" ); if( g==0 ) return 3;
  M.Init( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
  M.ProcessFile( DECODE, f, g );
}

Answer 1

Juste pour le plaisir, voici une idée approximative de la façon dont je traiterais la partie qui encode vers/décode à partir d'un alphabet arbitraire. Comme promis, l'encodage/décodage proprement dit se résume à une douzaine de lignes de code. La taille globale est plus grande, en grande partie parce que j'ai utilisé des templates tout au long du code, donc les nombres peuvent être un type entier arbitraire, et les caractères peuvent être un type de caractère arbitraire, et il utilise des itérateurs pour les deux, donc il peut lire/écrire dans des collections arbitraires (streams, stringstreams, vecteurs, etc.).

Edit : modification du code pour lire l'entrée d'un fichier et écrire la sortie dans un fichier (et correction d'une ou deux erreurs mineures) :

#include <iterator>
#include <iostream>
#include <string>
#include <limits>
#include <vector>
#include <fstream>
#include <time.h>
#include <math.h>
#include <stdlib.h>

template <class intT>
intT log2(intT input) { 
    return intT(log10((double)input) / log10(2.0));
}

template <class intT>
class coder { 
    std::string alphabet;   
    size_t range;
    unsigned ratio;
public:
    coder(std::string const &alpha) : alphabet(alpha), range(alpha.size()) {
        ratio = ceil(double(log2(std::numeric_limits<intT>::max())/log2(range)));
    }

    template <class inIt, class outIt>
    void encode(inIt begin, inIt end, outIt out) { 
        while (begin != end) {
            intT val = *begin++;
            for (int i=0; i<ratio; i++) {
                *out++ = alphabet[val % range];
                val /= range;
            }
        }
    }

    template <class inIt, class outIt>
    void decode(inIt begin, inIt end, outIt out) { 
        while (begin != end) {
            int temp = 0;
            for (int i=0; i<ratio; i++)
                temp += alphabet.find(*begin++) * pow((double)range, i);
            *out++ = temp;
        }
    }
};

int main(int argc, char **argv) {
    if (argc != 3) {
        std::cerr << "Usage: encode <infile> <outfile>\n";
        return EXIT_FAILURE;
    }

    coder<unsigned> enc("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
    std::ifstream in(argv[1], std::ios::binary);
    std::ofstream out(argv[2]);
    clock_t start = clock();
    enc.encode(std::istream_iterator<char>(in), 
        std::istream_iterator<char>(), 
        std::ostream_iterator<char>(out, ""));
    clock_t stop = clock();
    std::cerr << "Processing time: " << double(stop-start)/CLOCKS_PER_SEC << "\n";
    return 0;
}

Au moins pour le moment, j'ai ignoré la partie codage arithmétique, mais il devrait (au moins IMO) suivre une structure similaire afin que vous puissiez facilement enchaîner des choses plus ou moins arbitrairement.

En ce qui concerne la comparaison de la vitesse et de la taille, il faut garder à l'esprit qu'il n'y a pas de compression (du tout), juste l'encodage baseX -- ceci étant le cas, essayer de comparer avec quelque chose qui fait de la compression n'a pas vraiment de sens (sauf, par exemple, pour avoir une idée de l'efficacité de la compression -- mais si elle est efficace du tout, elle produira évidemment un résultat plus petit).

En ce qui concerne la taille de l'exécutable, tout ce que je peux dire, c'est que gcc ne m'a jamais surpris en produisant de gros exécutables. En utilisant MS VC++, j'obtiens un exécutable de 9 728 octets pour le code ci-dessus.

Answer 2

Implémenter des coroutines de manière portable est une tâche difficile. Veuillez envisager d'utiliser Boost.coroutine candidat. Aquí sont des mises à jour de la bibliothèque.

Je l'ai beaucoup utilisé sous OS X et Linux avec boost::asio et ils se sont avérés très robustes et constituent une abstraction très utile des threads avec le comportement déterministe d'un programme séquentiel.

Je ne sais pas pourquoi il n'a pas encore été ajouté à la distribution principale de boost. Je pense qu'il y a un argument politique déguisé en argument technique derrière ce fait, bien que vous soyez encouragés à prendre ma paranoïa avec un grain de sel.

EDIT : il y a un nouveau candidat boost dans le coffre-fort boost appelé Boost.Context, et il fait partie d'une bibliothèque plus large appelée Boost.Fiber. Elle n'a pas encore de page web, donc je ne vais pas la lier ici. Il semble avoir un meilleur support

Answer 3

Ok, voici ce que j'ai demandé en fait (voir [1]) - l'astuce pour appeler statiquement une fonction à partir d'une classe enfant. tl;dr est apparemment un pouvoir puissant, donc voici votre générateur de fibonacci coroutine standard lisible cette fois. Il y a une petite différence cependant - nous n'avons pas vraiment besoin de coroutines pour générer ces nombres, mais c'est vraiment difficile (et c'est une bonne chose) de le faire. ces nombres, mais il est vraiment difficile (si possible) de faire une implémentation plus rapide de mon premier programme sans coroutines.

#include <stdio.h>
#include <stddef.h>
#include <setjmp.h>

// without noinline some compilers tend to allocate the array before setjmp()
#ifdef __GNUC__
 #define NOINLINE __attribute__((noinline))
#else
 #define NOINLINE __declspec(noinline)
#endif

enum{ STKPAD=1<<16 };
struct coroutine {
  volatile unsigned state;
  jmp_buf PointA, PointB;
  void yield( int value ) { if( setjmp(PointB)==0 ) { state=value; longjmp(PointA,value); } }
  template <typename T> NOINLINE void call_do_process() {
    char stktmp[STKPAD]; state=ptrdiff_t(stktmp); ((T*)this)->do_process();
  }
  template <typename T> unsigned coro_process( T* ) {
    if( setjmp(PointA)==0 ) if( state ) longjmp(PointB,3); else call_do_process<T>();
    return state;
  }
};

struct fibonacci : coroutine {

  void do_process( void ) {
    unsigned a=0,b=1;
    while(1) {
      yield( b );
      b = b + a;
      a = b - a;
    }
  }

  unsigned get( void ) {
    return coro_process(this); 
  }

} F;

int main( int argc, char** argv ) {

  for( int i=0; i<20; i++ ) {
    printf( "%i ", F.get() );
  } printf( "\n" );

  return 0;
}

Et comme la version alternative de Jerry Coffin ne produit toujours pas de résultats significatifs, voici quelques repères de flux plus simples. C'est dommage, car je m'attendais à ce qu'il soit encore plus encore plus lent avec les itérateurs.

En fait, j'ai testé toutes sortes d'approches avec des codeurs arithmétiques - de simples méthodes virtuelles getc/putc, méthodes virtuelles, pointeurs de fonctions simples, classes de type itérateur, et il est clair que qu'il y a une grande différence. Pour l'instant, les coroutines se sont avérées être le meilleur moyen pour cela. il n'y a pas de logique complexe encapsulée dans les appels d'octets d'entrée/sortie (contrairement aux itérateurs), et le traitement n'a pas à se soucier des détails de l'entrée-sortie. Bien sûr, il y a encore d'autres optimisations, mais j'ai seulement essayé de démontrer les avantages de l'approche coroutine ici...

#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_DISABLE_PERFCRIT_LOCKS

#include <stdio.h>
#include <time.h>
#include <fstream>

int main( int argc, char** argv ) {
  if( argc<3 ) return 1;

  { 
    clock_t start = clock();
    FILE* f = fopen( argv[1], "rb" ); if( f==0 ) return 2;
    FILE* g = fopen( argv[2], "wb" ); if( g==0 ) return 3;
    while(1) {
      int c = getc(f);
      if( c<0 ) break;
      putc(c,g);
    }
    fclose(f);
    fclose(g);
    clock_t stop = clock();
    printf( "            File copy via stdio getc/putc - %7.3fs\n", float(stop-start)/CLOCKS_PER_SEC );
  }

  {
    clock_t start = clock();
    FILE* f = fopen( argv[1], "rb" ); if( f==0 ) return 2;
    FILE* g = fopen( argv[2], "wb" ); if( g==0 ) return 3;
    while(1) {
      static char buf[1<<16];
      int l = fread( buf, 1,sizeof(buf), f ); if( l<=0 ) break;
      fwrite( buf, 1,l, g ); if( l<sizeof(buf) ) break;
    }
    fclose(f);
    fclose(g);
    clock_t stop = clock();
    printf( "     File copy via stdio 64k fread/fwrite - %7.3fs\n", float(stop-start)/CLOCKS_PER_SEC );
  }

  {
    clock_t start = clock();
    std::ifstream f(argv[1],std::ios::in|std::ios::binary); if( !f.is_open() ) return 2;
    std::ofstream g(argv[2],std::ios::out|std::ios::binary); if( !g.is_open() ) return 3;
    while(1) {
      int c = f.get();
      if( c<0 ) break;
      g.put(c);
    }
    f.close();
    g.close();
    clock_t stop = clock();
    printf( "File copy via ifstream::get/ofstream::put - %.3fs\n", float(stop-start)/CLOCKS_PER_SEC );
  }

}

\----- 100,000,000 byte file ----- 
\[ GCC 4.5 \]
            File copy via stdio getc/putc -   0.546s
     File copy via stdio 64k fread/fwrite -   0.188s
File copy via ifstream::get/ofstream::put -  10.578s

\[ IntelC 11.1 / VS 2005 \]
            File copy via stdio getc/putc -   0.500s
     File copy via stdio 64k fread/fwrite -   0.156s
File copy via ifstream::get/ofstream::put -  14.656s

\[ MSC 14.0 / VS 2005 \]
            File copy via stdio getc/putc -   0.609s
     File copy via stdio 64k fread/fwrite -   0.156s
File copy via ifstream::get/ofstream::put -  19.063s

----- 1,000,000,000 byte file ----- 
\[ GCC 4.5 \]
            File copy via stdio getc/putc -   7.468s
     File copy via stdio 64k fread/fwrite -   1.828s
File copy via ifstream::get/ofstream::put - 109.891s

\[ IntelC 11.1 / VS 2005 \]
            File copy via stdio getc/putc -   6.718s
     File copy via stdio 64k fread/fwrite -   1.672s
File copy via ifstream::get/ofstream::put - 145.500s

\[ MSC 14.0 / VS 2005 \]
            File copy via stdio getc/putc -   6.453s
     File copy via stdio 64k fread/fwrite -   1.609s
File copy via ifstream::get/ofstream::put - 191.031s