yohhoyの日記

C++コルーチン拡張メモ（N4736）

C++, C++2a

プログラミング言語C++のコルーチン(Coroutines)拡張に関するメモ。2018年4月現在、C++2a(C++20)言語仕様での正式採択に向けた検討が進んでいる。

本記事の内容は(PDF)N4736 Working Draft, C++ Extensions for Coroutinesに基づく。

C++コルーチン拡張はコルーチンに関するC++言語仕様と低レベルAPIのみを規定し、他プログラミング言語のような具体的な“コルーチン”機能は何も定義しない。

• C++コルーチンライブラリ実装者は、低レベルAPIを用いてジェネレータ(Generator)や非同期タスク(Asynchronous task)といった具象機能を提供する。
• C++アプリケーション開発者は、co_xxxキーワードを介してコルーチンライブラリを利用する。

要約：

• 新しいキーワード：co_yield, co_return, co_await
• 新しい構文：yield式, co_return文, await式, co_await範囲for文
• 新しいヘッダ：<experimental/coroutine>*1
• コルーチン(coroutine) == 関数途中での中断(suspend)／再開(resume)を追加サポートする関数(function)*2
• コルーチン(coroutine) == 本体にco_yield/co_return/co_awaitキーワードを含む関数*3
  • 制限：main関数、コンストラクタ、デストラクタはコルーチンになれない。関数戻り値型推論とコルーチンは併用不可。コルーチンへのconstexpr指定不可。returnとco_returnは排他的。
• C++コルーチン拡張では、コルーチン動作に関するユーザ定義型のカスタマイゼーション・ポイント(customization point)を定める。*4
  • yield文とco_return文はユーザ定義“コルーチン型(coroutine type)”を介して、await文とco_await範囲for文はユーザ定義“Awaitable型”を介してその振る舞いを定義する。
  • コルーチン外部仕様としては、コルーチン制御フローのための“コルーチンハンドラ(coroutine handler)”*5を内包した“コルーチン型(coroutine type)”を返す。
  • コルーチン内部実装では、ユーザ定義“プロミス型(promise type)”の“プロミスオブジェクト(promise object)”が暗黙に生成され、“コルーチン型(coroutine type)”戻り値との紐付けを行う。
  • コルーチン制御フローはco_yieldやco_awaitによって中断(suspend)され、“コルーチンハンドラ(coroutine handler)”を介して再開(resume)される。
  • コルーチン(coroutine)とスレッド(thread)は直交した機能。あるスレッドで中断(suspend)したコルーチンを、他スレッド上にて再開(resume)可能。*6
• スタックレス・コルーチン(stackless coroutine)のみサポート。
• 非対称(asymmetric)／対称(symmetric)コルーチンいずれもサポート。*7
• コルーチン内部実装では、暗黙に“コルーチン・フレーム(corotuine frame)”動的メモリ確保／解放処理が行われる。ただし、一定条件をみたせばコンパイラによるヒープ確保省略(heap allocation elision)最適化を期待できる。*8

ノート：アプリケーション開発者視点でのC++コルーチン拡張の恩恵は、lewissbaker/cppcoroライブラリやP0975R0 Impact of coroutines on current and upcoming library facilitiesが参考になる。低レベルAPIを用いたナイーブ実装はC++コルーチン拡張メモ参照。

関連URL

• P0978R0 A Response to ”P0973r0: Coroutines TS Use Cases and Design Issues”
• (PDF)await/yield: C++ coroutines
• (PDF)C++ Coroutines - Under The Covers, CppCon 2016
• (PDF)Putting Coroutines to Work with the Windows Runtime, CppCon 2016
• (PDF)Concurrency, Parallelism and Coroutines, CppCon 2017
• (PDF)Coroutines What Can’t They Do, CppCon 2017
• (PDF)Naked Coroutines Live, CppCon 2017
• How C++ coroutines work — kirit.com
• C++ Coroutines: Understanding operator co_await

Permalink | コメント(0) | トラックバック(0)

遅延機構付きデータキュー

C++

スレッドセーフ・遅延機構付き・上限なし・データキューのC++実装。Java標準ライブラリ java.util.concurrent.DelayQueue に相当。

通常のデータキューと異なり、キューへの要素追加時に“有効時刻”を指定する。該当要素はその有効時刻を過ぎるまではキュー内に滞留し、キューからの取り出し操作の対象とはならない（遅延機構）。

enqueue操作

有効時刻を指定した要素値をキューに格納する。キュー容量は上限無しのため、enqueue操作は常に成功する。

dequeue操作

現在時刻より小さく、かつ最古の有効時刻を持つ要素値をキューから取り出す。有効な要素が存在しない場合、dequeue操作はブロッキングする。

close操作

データ終端を通知する。close操作以後のenqueue操作は失敗する。キューが空になった後のdequeue操作は無効値を返す。

#include <chrono>
#include <condition_variable>
#include <mutex>
#include <utility>
#include <vector>

struct closed_queue : std::exception {};

template <typename T, typename Clock = std::chrono::system_clock>
class delay_queue {
public:
  using value_type = T;
  using time_point = typename Clock::time_point;

  delay_queue() = default;
  explicit delay_queue(std::size_t initial_capacity)
    { q_.reserve(initial_capacity); }
  ~delay_queue() = default;

  delay_queue(const delay_queue&) = delete;
  delay_queue& operator=(const delay_queue&) = delete;

  void enqueue(value_type v, time_point tp)
  {
    std::lock_guard<decltype(mtx_)> lk(mtx_);
    if (closed_)
      throw closed_queue{};
    q_.emplace_back(std::move(v), tp);
    // descending sort on time_point
    std::sort(begin(q_), end(q_),
              [](auto&& a, auto&& b) { return a.second > b.second; });
    cv_.notify_one();
  }

  value_type dequeue()
  {
    std::unique_lock<decltype(mtx_)> lk(mtx_);
    auto now = Clock::now();
    // wait condition: (empty && closed) || (!empty && back.tp <= now)
    while (!(q_.empty() && closed_) && !(!q_.empty() && q_.back().second <= now)) {
      if (q_.empty())
        cv_.wait(lk);
      else
        cv_.wait_until(lk, q_.back().second);
      now = Clock::now();
    }
    if (q_.empty() && closed_)
      return {};  // invalid value
    value_type ret = std::move(q_.back().first);
    q_.pop_back();
    if (q_.empty() && closed_)
      cv_.notify_all();
    return ret;
  }

  void close()
  {
    std::lock_guard<decltype(mtx_)> lk(mtx_);
    closed_ = true;  
    cv_.notify_all();
  }

private:
  std::vector<std::pair<value_type, time_point>> q_;
  bool closed_ = false;
  std::mutex mtx_;
  std::condition_variable cv_;
};

利用サンプルコード：

template <typename T>
void dump(const T& v, std::chrono::system_clock::time_point epoch)
{
  using namespace std::chrono;
  auto elapsed = duration_cast<milliseconds>(system_clock::now() - epoch).count() / 1000.;
  std::cout << elapsed << ":" << v << std::endl;
}

int main()
{
  auto base = std::chrono::system_clock::now();
  constexpr std::size_t capacity = 5;
  delay_queue<std::unique_ptr<std::string>> q{capacity};

  auto f = std::async(std::launch::async, [&q, base] {
    using namespace std::chrono_literals;
    q.enqueue(std::make_unique<std::string>("two"),   base + 2s);
    q.enqueue(std::make_unique<std::string>("three"), base + 3s);
    q.enqueue(std::make_unique<std::string>("one"),   base + 1s);
    q.close();
  });

  dump("start", base);
  dump(*q.dequeue(), base);  // "one"
  dump(*q.dequeue(), base);  // "two"
  dump(*q.dequeue(), base);  // "three"
  assert(q.dequeue() == nullptr);  // end of data
}

関連URL

• https://gist.github.com/yohhoy/a5ec6d4aeeb4c60d3e4f3adfd1df9ebf

Permalink | コメント(0) | トラックバック(0)

C++標準ライブラリのタイムゾーン(Time Zone)

C++, C++2a

C++2a(C++20)標準ライブラリ <chrono> ヘッダに追加される タイムゾーン(Time Zone) サポートについてざっくりメモ。

本記事では簡単のため名前空間std::chronoを省略する。カレンダー(Calendar)については id:yohhoy:20180322 参照。

まとめ：

• タイムゾーン時刻(zoned_time)＝タイムゾーン指定＋ローカル時刻(Time Point)*1
  • 例: auto zt = zoned_time{"Asia/Tokyo", local_days{2020y/7/24} + 13h};
• タイムゾーン指定＝タイムゾーン名 or タイムゾーン(time_zone)構造体。現タイムゾーンの取得(current_zone())やタイムゾーン検索(locate_zone())を提供。
  • 例: auto zt_now = zoned_time{current_zone(), system_clock::now()};
• UTC⇔タイムゾーン時刻の相互変換、異なるタイムゾーン時刻間の相互変換をサポート。
  • 例1: auto zt_tokyo = zoned_time{"Asia/Tokyo", system_clock::now()};
  • 例2: auto tp_utc = system_clock::time_point{zt_tokyo};
  • 例3: auto zt_paris = zoned_time{"Europe/Paris", zt_tokyo};
• 夏時間(サマータイム; Daylight Saving Time)サポートあり。
  • 夏時間の開始／終了付近において“存在しないローカル時間*2”“重複するローカル時間*3”という概念が生じるため、例外nonexistent_local_time, ambiguous_local_timeが提供される。
  • “重複するローカル時間”からUTCへの変換時は、丸めモード(choose::earliest, choose::latest)明示指定で例外発生を回避できる。
  • やはり夏時間は悪い文明!!粉砕する!!
• タイムゾーンデータベース(tzdb)はライブラリ埋め込み。タイムゾーン情報・うるう秒(leap seconds)情報から構成される。
  • タイムゾーンデータベース・リスト(tzdb_list)をシングルトン提供する。
  • タイムゾーンデータベースの動的更新サポートあり。
  
  

ノート：C++2a標準ライブラリ準拠するにはタイムゾーンデータベースを内包せざるをえないため、データサイズ肥大化の一因になりそう。更新が必要なデータベースなのは確かだが、C++標準ライブラリに「遠隔(remote)データベースからの情報取得」という文言が入ってくるのはなかなか衝撃的。

関連URL

• P0355R7 Extending <chrono> to Calendars and Time Zones
• reddit: the front page of the internet
• IANA Time Zone Database
• wikipedia:en:List_of_tz_database_time_zones
• id:yohhoy:20180320, id:yohhoy:20180322

Permalink | コメント(0) | トラックバック(0)

C++標準ライブラリのカレンダー(Calendar)

C++, C++2a

C++2a(C++20)標準ライブラリ <chrono> ヘッダに追加される カレンダー(Calendar) サポートについてざっくりメモ。

本記事では簡単のため名前空間std::chronoを省略する。またタイムゾーン(Time Zone)サポートには言及しない。

まとめ：

• 型安全(Type safety)： 年(year), 月(month), 日(day), 年月日(year_month_day)を型システム上で表現する。数値からの暗黙変換は禁止。
  • 例： 2020年7月24日*1は year_month_day{2020, 7, 24} ではなく year_month_day{year{2020}, month{7}, day{24}} のように記述する。
• 既存chronoライブラリとの統合： 年月日(year_month_day) と システム時刻(system_clock::time_point) は相互変換可能。年月日はフィールド単純保持、システム時刻は実在するTime pointを表す。*2
  • 例1： auto tp = sys_days{2020y/July/24} + 9h + 30min + 15s; year_month_day ymd{floor<days>(tp)};
  • 例2： 2018年3月32日は2018年4月1日 sys_days{2018y/3/32} == sys_days{2018y/4/1}
• 日付リテラルの表記順は 年/月/日, 月/日/年［アメリカ式］, 日/月/年［イギリス式］ をサポート。*3
  • 例: 2020年7月24日は 2020y/July/24, 2020y/7/24, July/24/2020, 24d/July/2020, 24d/7/2020*4
• 曜日(weekday), 最終日(last_spec)を用いて、“ある月の最終日”、“ある月の第N X曜日”、“ある月の最終X曜日”も表現可能。*5
  • 例： 2020年7月の最終日 2020y/7/last == 2020y/7/31、2020年7月の第1月曜日 2020y/7/Monday[1] == 2020y/7/6、2020年7月の最終月曜日 2020y/7/Monday[last] == 2020y/7/27
• 日付計算サポート： N年(years), N月(months), N週(weeks), N日(days) 前／後を計算可能。
  • 注意： 一年years{1}は 146097/400 日(≒365.24日)、一ヶ月months{1}は 1/12 年(≒30.43日) のDurationと定義される。年月日(year_month_day)またはシステム時刻(Time point)のいずれの型で計算するかで結果が異なる。
  • 例: 3ヶ月前(2020-04-24) 2020y/7/24 - months{3}、16日後(2020-08-09) sys_days{2020y/7/24} + days{16}*6
• IOストリーム出力(operator<<)、書式指定出力(to_stream)、書式指定入力(from_stream)を追加提供。
  • 例: std::cout << 2020y/7/24; は "2020-07-24" を出力。
• グレゴリオ歴(Gregorian calendar)のみサポート。要件を満たせば独自の暦との相互運用可。
  • （当然ながら）国・地域・文化で異なる“祝日”のサポートはない。
  
  

おまけ：任意月のカレンダーを出力するサンプルプログラム。

// C++2a
#include <chrono>
#include <iostream>
#include <iomanip>

void print_calendar(std::ostream& os, const std::chrono::year_month& ym)
{
  using namespace std::chrono;

  unsigned weekday_offset{ weekday{sys_days{ym/1}} };
  unsigned lastday_in_month{ (ym/last).day() };

  os << "      " << ym << "\n"
     << "Su Mo Tu We Th Fr Sa\n";
  unsigned wd = 0;
  while (wd++ < weekday_offset)
    os << "   ";
  for (unsigned d = 1; d <= lastday_in_month; ++d, ++wd)
    os << std::setw(2) << d << (wd % 7 == 0 ? '\n' : ' ');
}

int main()
{
  using namespace std::chrono_literals;
  print_calendar(std::cout, 2018y/3);
}
/*
      2018/Mar
Su Mo Tu We Th Fr Sa
             1  2  3
 4  5  6  7  8  9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
*/

関連URL

• P0355R7 Extending <chrono> to Calendars and Time Zones
• reddit: the front page of the internet
• https://github.com/HowardHinnant/date
• id:yohhoy:20180320

Permalink | コメント(0) | トラックバック(0)

C++標準ライブラリの時計(Clock)

C++, C++2a

C++2a(C++20)標準ライブラリ <chrono> ヘッダに追加される 時計(Clock) クラス一覧。いずれもstd::chrono名前空間に属する。

表中［C++11］はC++11標準ライブラリ時点で追加されたクラスを、「−」はC++2aライブラリ仕様上の規定なしを表す。TAIクロックとGPSクロックは、UTCへうるう秒(leap second)が挿入されるたびに1秒先行していく。*2

C++2a標準ライブラリには“型TがClock要件を満たすか否か”を判定するメタ関数std::chrono::is_clock<T>, std::chrono::is_clock_v<T>があわせて追加される。

関連URL

• P0355R7 Extending <chrono> to Calendars and Time Zones
• reddit: the front page of the internet
• IANA Time Zone Database
• 標準時・周波数標準のＱ＆Ａ うるう秒に関するＱ＆Ａ

Permalink | コメント(0) | トラックバック(0)