Einführung & Praxisreport

Co-Routinen als Generatoren

ADC++ 2018

kurze Geschichte

Rebuild language project

C#

IEnumerable<Token> ScanFile(TextInput input) {
  while (true) {
    switch (input.PeekChar) {
    case '\0':
      yield break;
    case ' ':
    case '\t':
      yield return ScanWhitespace(input);
      continue;
    // …
    }
  }
}

C++17

std::variant<>
std::string_view
…

C++17 Coroutine-TS

Gelesen ?
Ausprobiert?

Kurze Einführung

Co-Routine

ist eine Funktion
mit Unterbrechungen

`await`

bedingte Unterbrechung
kein Resultat

`yield`

eine Unterbrechung
mit return

Generatoren ?

Beispiel

auto generate() {
  return std::array<long, 2>{23, 42};
}

void iterate_it() {
  for (auto v : generate()) {
    std::cout << v << '\n';
  }
}

Co-Routine Generator

auto generate() -> Generator<long> {
  co_yield 23;
  co_yield 42;
}

Iota Generator

auto iota(long n) -> Generator<long> {
  for (auto i = 0u; i < n; ++i) {
    co_yield i;
  }
}

Endloser Generator

auto from(long n) -> Generator<long> {
  while (true) {
    co_yield n++;
  }
}

`Generator<T>` & `co_yield`

Generatoren ohne Co-Routinen

begin() & end()
Input Iterator
Interner Zustand

template<class T>
struct FromGenerator {
  T start;

  struct End {};
  auto end() { return End{}; }

  struct Iter;
  auto begin() { return Iter{start}; }
};

template<class T>
struct FromGenerator<T>::Iter {
  T n{};

  auto operator*() const { return n; }
  auto operator!=(End) const { return true; }
  auto operator++() {
    ++n;
    return *this;
  }
};

Probleme?

Logik
State
State-Machine

Wie funktioniert `co_yield`?

auto fun() -> Generator<long> {
  co_yield 23;
}

namespace std::experimental {
template<class T, class... Vs>
struct coroutine_traits<Generator<T>, Vs...> {
  using promise_type =
      typename Generator<T>::Promise;
};
} // namespace std::experimental

#include <experimental/coroutine>

namespace coro = std::experimental;

template<class T>
struct Generator<T>::Promise {
  auto initial_suspend() {
    return coro::suspend_always{};
  }
  auto final_suspend() {
    return coro::suspend_always{};
  }
  // …
};

template<class T>
struct Generator<T>::Promise {
  // …
  auto yield_value(T v) {
    value = v;
    return coro::suspend_always{};
  }
  T value{};
  // …
};

template<class T>
struct Generator<T>::Promise {
  // …
  auto get_return_object() {
    return Generator{*this};
  }
  auto return_void() {}
  auto unhandled_exception() {}
};

template<class T>
struct Generator {
  struct Promise;
  using H = coro::coroutine_handle<Promise>;
  H h;

  Generator(Promise &p) : h(H::from_promise(p)) {}
  ~Generator() { if (h) h.destroy(); }
  Generator(Generator &&o) : h(o.h) { o.h = {}; }
  Generator(const Generator &) = delete;
};

template<class T>
struct Generator {
  operator bool() const { return h && !h.done(); }
  auto operator*() const -> const T & {
    return h.promise().value;
  }
  auto operator++() -> Generator & {
    if (h) h.resume();
    return *this;
  }
};

Zusammenfassung

coroutine_traits<Ret, Args...>
promise_type
coroutine_handle<Promise>

Praxis

Schreibe einen Tokenizer für Python.

Design

UTF8 kodierter Text
⇒ Unicode Codepoints
⇒ Tokens
⇒ AST

UTF8 Decode

auto utf8Decode(MemoryView)
    -> Generator<Codepoint>;

auto utf8Decode(MemoryView view)
    -> Generator<CodePoint> {
  struct Decoder {
    MemoryView view;
    operator bool() const noexcept {
      return !view.empty();
    }
    auto next() -> Codepoint { /*…*/ }
  };
  return Decoder{view};
}

Als Co-Routine

auto utf8Decode(MemoryView view)
    -> Generator<CodePoint> {
  while (!view.empty()) {
    /* … */
    co_yield /* … */;
    continue;
  }
}

auto utf8Decode(MemoryView view) -> Generator<CodePoint> {
  auto take = [&]() -> CodePoint { return *view.begin++; };
  while (!view.empty()) {
    auto c0 = take();
    if ((c0 & 0x80) != 0x80)
      co_yield c0;
    else if ((c0 & 0xE0) == 0xC0) {
      if (view.empty()) co_return;
      auto c1 = take();
      if ((c1 & 0xC0) != 0x80) co_yield {};
      else co_yield { ((c0 & 0x1Fu) << 6) | (c1 & 0x3Fu) };
    }
    else { /* … */ }
  }
}

Tokenizer

auto tokenize(Generator<CodePoint>)
    -> Generator<Token>

auto tokenize(Generator<CodePoint> &&input)
    -> Generator<Token> {
  struct Scanner {
    Generator<CodePoint> input;
    TextPosition position{};
    CodePoint cp{};
    operator bool() const { /* ? */ }
    auto next() -> Token { /* … */ }
  };
  return Scanner{std::move(input)};
}

auto tokenize(Generator<CodePoint> &input) -> Generator<Token> {
  auto position = TextPosition{};
  auto next = [&] { return (++input) ? *input : CodePoint{}; };
  auto cp = next();
  while (cp) {
    auto token = [begin = position, end = &position](auto data) {
      return Token{TextRange{begin, end}, data};
    };
    if (cp == ':') {
      cp = next(); position.column++;
      co_yield token(Colon{});
      continue;
    }
    // …
  }
}

Zusammenfassung

Andere Denkweise
Clean Code
Performance?

Performance

clang
-std=c++2a -O3
-stdlib=libc++ -fcoroutines-ts
Compiler Explorer

template<size_t N>
auto fixedSum() {
    auto sum = 0u;
    for (auto v : iota(N + 1)) sum += v;
    return sum;
}

auto fixedTest() {
    return fixedSum<100>();
}

fixedTest():
        mov     eax, 5050
        ret

auto simpleSum(size_t n) {
    auto sum = 0u;
    for (auto v = 0; v <= n; ++v) sum += v;
    return sum;
}

simpleSum(unsigned long):         ; rdi = n
        lea     rax, [rdi - 1]    ; rax = rdi - 1
        imul    rax, rdi          ; rax *= rdi
        shr     rax, 1            ; rax /= 2
        add     edi, eax          ; edi += eax
        mov     eax, edi          ; eax = edi
        ret                       ; return eax

auto dynSum(size_t n) {
    auto sum = 0u;
    for (auto v : iota(n + 1)) sum += v;
    return sum;
}

dynSum(unsigned long):            ; rdi = n
        add     rdi, 1            ; rdi += 1
        sete    cl                ; cl = rdi == 0
        je      .LBB1_1           ; if (rdi == 0) goto LBB1_1
        xor     eax, eax          ; eax = 0
        xor     esi, esi          ; esi = 0
.LBB1_4:
        mov     edx, esi          ; edx = esi
        add     eax, esi          ; eax += esi
        mov     esi, 0            ; esi = 0
        test    cl, 1             ; cl & 1 <=> 0
        mov     ecx, 0            ; ecx = 0
        jne     .LBB1_4           ; if (cl != 0) goto LBB1_4
        add     edx, 1            ; edx += 1
        xor     ecx, ecx          ; ecx = 0
        mov     esi, edx          ; esi = edx
        cmp     rdi, rdx          ; rdi <=> rdx
        ja      .LBB1_4           ; if (rdi > rdx) goto LBB1_4
        ret                       ; return eax
.LBB1_1:
        xor     eax, eax          ; eax = 0
        ret                       ; return eax

Resultat

Godbolt Link
use noexcept
Klappt nicht perfekt
Wird besser!

`co_yield` expression

N4736

… the yield-expression is equivalent to the expression co_await p.yield_value(e).

auto repeater(int v) -> CoYield<int, int> {
  while (true) {
    v = co_yield v;
  }
}

template<class Out, class In>
struct CoYield<Out, In>::Promise {
  // …
  auto yield_value(Out o) -> Awaitable & {
    out = o;
    return awaitable;
  }
  Out out;
  Awaitable awaitable;
};

template<class Out, class In>
struct CoYield<Out, In>::Awaitable {
  In in;

  auto await_ready() const noexcept { return false; }
  auto await_resume() noexcept { return in; }
  void await_suspend(const H &) noexcept {}
};

Einführung & Praxisreport

Co-Routinen als Generatoren

kurze Geschichte

C#

C++17

C++17 Coroutine-TS

Kurze Einführung

Co-Routine

`await`

`yield`

Generatoren ?

Beispiel

Co-Routine Generator

Iota Generator

Endloser Generator

`Generator<T>` & `co_yield`

Generatoren ohne Co-Routinen

Probleme?

Wie funktioniert `co_yield`?

Zusammenfassung

Praxis

Design

UTF8 Decode

Als Co-Routine

Tokenizer

Zusammenfassung

Performance

Resultat

`co_yield` expression

N4736

Zusammenfassung

Vorteile

Nachteile

Links

Probiert mehr aus!

Probiert Co-Routinen aus!

Photo Credits

Danke!

kurze Geschichte

C#

C++17

C++17 Coroutine-TS

Kurze Einführung

Co-Routine

await

yield

Generatoren ?

Beispiel

Co-Routine Generator

Iota Generator

Endloser Generator

Generator<T> & co_yield

Generatoren ohne Co-Routinen

Probleme?

Wie funktioniert co_yield?

Zusammenfassung

Praxis

Design

UTF8 Decode

Als Co-Routine

Tokenizer

Zusammenfassung

Performance

Resultat

co_yield expression

N4736

Zusammenfassung

Vorteile

Nachteile

Links

Probiert mehr aus!

Probiert Co-Routinen aus!

Photo Credits

Danke!

`await`

`yield`

`Generator<T>` & `co_yield`

Wie funktioniert `co_yield`?

`co_yield` expression