yohhoyの日記

2018-04-15

C++コルーチン拡張メモ(N4736)

プログラミング言語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指定不可。returnco_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_yieldco_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

*1:TS(Technical Specification)から正式機能に昇格すれば、ヘッダ<coroutine>に変更される。P0912R0参照。

*2:通常関数(サブルーチン; subroutine)制御フローは呼び出し(call)/戻り(return)のみサポートするのに対し、コルーチン(coroutine)制御フローは呼び出し(call)/中断(suspend)/再開(resume)/戻り(return)に拡張されている。つまりコルーチンはより汎化された関数(サブルーチン)と解釈される。

*3:関数プロトタイプ宣言からは、通常の関数かコルーチンのいずれかを判断できない。

*4:本記事における「ユーザ定義」のユーザは、通常のアプリケーション開発者ではなく、コルーチンライブラリの実装者を意味する。

*5std::experimental::coroutine_handler<Promise>Promiseはプロミス型(promise type))

*6:コルーチンとスレッド併用時のスレッド安全性(thread safety)担保は、これまで同様にコルーチンライブラリ開発者およびアプリケーション開発者の責任となる。

*7http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0913r1.html

*8http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0981r0.html

2018-04-12

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

スレッドセーフ・遅延機構付き・上限なし・データキューの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

2018-03-26

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

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

*1local_daysは特定タイムゾーンと紐づかないローカル時刻の日単位Time point型。

*2:タイムゾーン"America/New_York"のローカル時刻 2016-03-13 02:30:00 は、2016-03-13 02:00:00 EST == 2016-03-13 03:00:00 EDT == 2016-03-13 07:00:00 UTC の隙間に位置するため存在しえない。

*3:タイムゾーン"America/New_York"のローカル時刻 2016-11-06 01:30:00 は、2016-11-06 01:30:00 EDT == 2016-11-06 05:30:00 UTC または 2016-11-06 01:30:00 EST == 2016-11-06 06:30:00 UTC のいずれか。

2018-03-22

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

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

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

まとめ:

  • 型安全(Type safety): 年(year), 月(month), 日(day), 年月日(year_month_day)を型システム上で表現する。数値からの暗黙変換は禁止。
    • 例: 2020年7月24日*1year_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

*1:2020-07-24は東京オリンピックの開会式予定日ですって。特例法で祝日にする(他祝日を変更)とかなんとか。

*2:本文中の floor<D> は名前空間std::chronoで定義されるDuration変換関数(C++17で追加)。daysは日単位を表すDuration型、sys_daysはシステムクロックの日単位Time point型(いずれもC++2aで追加)。

*3:ユーザ定義リテラルは名前空間std::literals::chrono_literals以下で定義される。本文中の例では年(year)を返すoperator""y、日(day)を返すoperator""d、7番目の月(month)を表す定数Julyを利用している。年月日区切りは除算演算子/オーバーロードにより実現される。

*4:月は2桁表記 2020y/07/24 できなくもないが、8月(08)と9月(09)がill-formedな8進数リテラルとなってしまう。おすすめできない。

*5:本文中の例では、月曜日を表す定数Mondayと、last_spec型のタグ定数lastを利用している。いずれも名前空間std::chrono以下で定義される。

*6:Time point型で計算 sys_days{2020y/7/24} - months{3} すると、3ヶ月前は 2020-04-23 16:32:42 になる。日単位の計算ではTime point型への変換が必須となっている。

2018-03-20

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

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


Clock概要基点(epoch)うるう秒
system_clockシステムクロック[C++11]1970-01-01 00:00:00 UTC除外
utc_clock協定世界時(UTC)クロック1970-01-01 00:00:00 UTC含める
tai_clock国際原子時(TAI)クロック1958-01-01 00:00:00 TAI*1挿入なし
gps_clockGPSクロック1980-01 第1日曜 00:00:00 UTC挿入なし
file_clockファイルシステムクロック未規定(unspecified)
steady_clock時間逆行しないクロック[C++11]
high_resolution_clock高分解能クロック[C++11]

表中[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

*1:1958-01-01 00:00:00 TAI == 1957-12-31 23:59:50 UTC

*2:2000-01-01 00:00:00 UTC == 2000-01-01 00:00:32 TAI, 2000-01-01 00:00:00 UTC == 2000-01-01 00:00:13 GPS