yohhoyの日記

技術的メモをしていきたい日記

randの既定シード値は1

C

C標準ライブラリ提供の擬似乱数生成関数randでは、既定のシード値は 1 と定義される。

#include <stdlib.h>

int main()
{
  // 暗黙にsrand(1)相当でシード値を設定
  int x = rand();
}

C11 7.22.2.2/p2より引用（下線部は強調）。

The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. If srand is then called with the same seed value, the sequence of pseudo-random numbers shall be repeated. If rand is called before any calls to srand have been made, the same sequence shall be generated as when srand is first called with a seed value of 1.

関連URL

アトミック、ときどきロックフリー

C++ C

C/C++標準ライブラリ提供のアトミック変数atomic<T>, atomic_Tでは、ロックフリー(lock-free)性判定マクロATOMIC_*_LOCK_FREE*1 が3状態 Never／Sometimes／Always を取りうる。

C++11策定当時の提案文書N2427によれば、“ロックリーに振る舞う可能性あり”（ATOMIC_*_LOCK_FREE == 1）選択肢の提供根拠は下記の通り：

  • 動的リンクライブラリのバージョンアップなどで、将来的にはロックフリーに振る舞う可能性を考慮する。
  • やむを得ない “不適切なアライメントをもつアトミック変数” の存在を許容する。
    • 型レベルでのロックフリー保証を諦めることで、適正アライメントのアトミック変数のみを考慮とした効率的な実装が可能となる。

Lock-Free Property

The proposal provides run-time lock-free query functions rather than compile-time constants because subsequent implementations of a platform may upgrade locking operations with lock-free operations, so it is common for systems to abstract such facilities behind dynamic libraries, and we wish to leave that possibility open. Furthermore, we recommend that implementations without hardware atomic support use that technique.

The proposal provides lock-free query functions on individual objects rather than whole types to permit unavoidably misaligned atomic variables without penalizing the performance of aligned atomic variables.

Because consistent use of operations requires that all operations on a type must use the same protocol, all operations are lock-free or none of them are. That is, the lock-free property applies to whole objects, not individual operations.

N2427 C++ Atomic Types and Operations

C++標準規格では、ロックフリー実行(lock-free executions)が定義されている。C++17 4.7.2/2より引用。

Executions of atomic functions that are either defined to be lock-free (32.8) or indicated as lock-free (32.5) are lock-free executions.

  • If there is only one thread that is not blocked (3.6) in a standard library function, a lock-free execution in that thread shall complete. [Note: Concurrently executing threads may prevent progress of a lock-free execution. For example, this situation can occur with load-locked store-conditional implementations. This property is sometimes termed obstruction-free. -- end note]
  • When one or more lock-free executions run concurrently, at least one should complete. [Note: It is diffcult for some implementations to provide absolute guarantees to this effect, since repeated and particularly inopportune interference from other threads may prevent forward progress, e.g., by repeatedly stealing a cache line for unrelated purposes between load-locked and store-conditional instructions. Implementations should ensure that such effects cannot indefinitely delay progress under expected operating conditions, and that such anomalies can therefore safely be ignored by programmers. Outside this document, this property is sometimes termed lock-free. -- end note]

関連URL

*1:*＝BOOL, CHAR, CHAR16_T, CHAR32_T, WCHAR_T, INT, LONG, LLONG, POINTERのいずれか。例：atomic<int>, atomic_int 型にはマクロ ATOMIC_INT_LOCK_FREE が対応。

hardware_{destructive,constructive}_interference_size

C++ MSVC

C++17で標準ライブラリ <new> ヘッダに追加された hardware_destructive_interference_size, hardware_constructive_interference_size について。

hardware_destructive_interference_size
False-Sharing発生を防ぐために必要となる、最小のメモリアドレス距離。2つの変数を異なるキャッシュラインに載せるためのアライメント情報として用いる。
hardware_constructive_interference_size
同一キャッシュラインに載りうる（True-Sharing）、最大のオブジェクトサイズ。複数変数アクセスの時間的局所性が高いときに、アドレス配置の確認情報として用いる。

対象プロセッサのL1キャッシュラインサイズ（相当）を、コンパイル時定数として取得可能。具体的な値は処理系定義(implementation-defined)とされる。通常、両定数値は同一となる。例：x86アーキテクチャでは値64。WebAssemblyなどコンパイル時に対象アーキテクチャが定まらない場合を想定し、保守的に振舞えるよう目的別に分離定義される。

C++17 21.6.5よりExampleコード片を引用（一部改変）。

#include <new>

// hardware_destructive_interference_size利用例
struct keep_apart {
  alignas(hardware_destructive_interference_size) atomic<int> cat;
  alignas(hardware_destructive_interference_size) atomic<int> dog;
};

// hardware_constructive_interference_size利用例
struct together {
  atomic<int> dog;
  int puppy;
};
struct kennel {
  // Other data members...
  alignas(sizeof(together)) together pack;
  // Other data members...
};
static_assert(sizeof(together) <= hardware_constructive_interference_size);

2018年8月現在、MSVC 14.11(VisualStudio 2017 15.3)*1＋/std:c++17オプション でのみ実装を確認*2。GCC(trunk)/libstdc++*3, Clang(trunk)/libc++*4は未対応*5。

おまけ：システムプログラミング言語であるRustにも同様の定数値が提案されている。

どうでもいいメモ：C++17現在、hardware_constructive_interference_size は atomic_compare_exchange_strong_explicit と並んでC++標準ライブラリ内で最も長い識別子名となっている。39文字。

関連URL

*1:https://cpprefjp.github.io/implementation.html#visual_cpp

*2:https://blogs.msdn.microsoft.com/vcblog/2018/05/07/announcing-msvc-conforms-to-the-c-standard/

*3:https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/testsuite/18_support/headers/new/synopsis.cc

*4:http://libcxx.llvm.org/cxx1z_status.html

*5:https://en.cppreference.com/w/cpp/compiler_support

C++標準ライブラリへのnodiscard属性

C++ C++2a

C++標準ライブラリにおけるnodiscard属性の使われ方についてメモ。

関数戻り値の誤った破棄を警告する目的でC++17言語仕様に導入された。標準ライブラリではC++2a(C++20)からの利用となる。2018年8月現在、下記関数がnodiscard属性付与対象となっている。

C++標準ライブラリ中でのnodiscard利用に関する提案文書P0600R1では、下記の基本ルールを定めている。

  • 属性付与すべきケース：
    • 戻り値の未使用が常に “重大なミス(huge mistake)” となるケースに付与する。メモリ確保系の関数。
    • 戻り値の未使用がトラブルの元となり、かつ容易に起こりうるケースに付与する。empty, async, lanuderなどはこちら。
  • 属性付与すべきでないケース：
    • 一部の入力値に対しては戻り値未使用が合理的であるケースには付与しない。reallocへのサイズ0指定など（free相当の動作）。
    • 戻り値の未使用は無意味だが実害が無く、通常は失敗しないケースには付しない。printf系, コンテナアダプタのtop, スマートポインタのreleaseなど。
    • Cライブラリ互換APIには付与しない。mallocは対象外。

関連URL

文字列ビューstd::string_view 利用ガイド

C++

C++17標準ライブラリ文字列ビューstd::string_viewクラス*1利用上の注意点についてメモ。

まとめ：

  • string_viewクラス＝文字列に対する読取専用のビュー。
    • std::stringと同じくヌル終端文字列以外も正しく取り扱える。ヌル文字を途中に含むことができる。
  • string_viewクラスは参照先文字列の所有権を管理しない。
    • 古き良き “生ポインタ(raw pointer)” 相当ととらえ、ダングリング(dangling)・ビュー*2には十分注意する。
  • 関数パラメータ型におけるstring_view利用は安全。（→id:yohhoy:20171113）
    • ヌル終端文字列(const char*)もしくは文字列(const std::string&)へのビューを統一的・効率的に扱える。
    • 関数実装で所有権が必要になったらstd::stringへ格納（＝文字列実体をコピー）する。
    • std::stringと異なり、string_view::dataメンバ関数はヌル終端文字列を保証しないため（→id:yohhoy:20120601）、ヌル終端文字列を要求するレガシーAPI呼び出し用途には適さない。
  • 関数戻り値型やクラスデータメンバとしてのstring_view利用には十分留意する。ダングリング・ビューのリスク有り。
    • 参照先オブジェクトの生存期間(lifetime)をドキュメント化すること。
  • 一時文字列オブジェクトを指すstring_view変数を明示的に作らないこと。
    • ローカル変数にはstring_view型ではなくauto&&利用を検討すべき。
// 文字列型stringを返す関数
std::string f();

std::string_view s1 = f();
// NG: 関数戻り値（一時文字列オブジェクト）は破棄済みのため
//     この時点でs1はダングリングビューとなっている。

auto&& s2 = f();
// OK: 関数戻り値（一時文字列オブジェクト）を右辺値参照型で受けると
//     その生存期間は変数s2のスコープが切れるまで延長される。

関連URL

*1:厳密には std::basic_string_view<charT, traits> クラステンプレート。簡単のため本文中ではクラスとして説明する。

*2:今作った造語。参照先オブジェクトの生存期間が終了しており既に無効値となってるポインタ型(T*)変数や参照型(T&)変数は、一般にダングリング・ポインタ(dangling pointer)やダングリング参照(dangling reference)と呼ばれる。wikipedia:en:Dangling_pointer

入れ子Optionの平坦化(flatten)

Rust

プログラミング言語RustにおいてOption<Option<T>>からOption<T>へ変換する方法。

// ナイーブな実装
fn flatten<T>(x: Option<Option<T>>) -> Option<T>
  match x {
    Some(x) => x,
    None => None,
  }
}

// and_thenコンビネータ
fn flatten<T>(x: Option<Option<T>>) -> Option<T>
{
  x.and_then(|x| x)
}

// ? (Try)オペレータ［Rust 1.22以降］
fn flatten<T>(x: Option<Option<T>>) -> Option<T>
{
  x?
}

let x : Option<Option<i32>> = Some(Some(42));
let y : Option<Option<i32>> = Some(None);
let z : Option<Option<i32>> = None;
assert_eq!(flatten(x), Some(42));
assert_eq!(flatten(y), None);
assert_eq!(flatten(z), None);

関連URL

C++標準ライブラリのビット処理関数群

C++ C++2a

C++2a(C++20)標準ライブラリに追加される <bit> ヘッダについてメモ。

2020-05-11追記：(PDF)P1956R1が採択され*1、関数名が大幅に変更（ispow2→has_single_bit／ceil2→bit_ceil／floor2→bit_floor／log2p1→bit_width）された。"2の冪乗(powers of two)" への言及回避が目的とのこと...*2

// C++2a <bit>ヘッダ
namespace std {
  // sizeof(To) == sizeof(From)
  template<typename To, typename From>
    constexpr To bit_cast(const From& from) noexcept;

  // T = 符号なし整数型
  template <class T>
    constexpr bool has_single_bit(T x) noexcept;
  template <class T>
    constexpr T bit_ceil(T x);  // P1355R2変更
  template <class T>
    constexpr T bit_floor(T x) noexcept;
  template <class T>
    constexpr T bit_width(T x) noexcept;
}

2019-08-30追記：2019年7月会合で採択されたP1355R2によりceil2関数テンプレートからnoexcept指定が削除された。

関数 効果
bit_cast<To>(n) ビット表現を維持した型キャスト
（安全なreinterpret_cast）
has_single_bit(n) nが "2の冪乗" か否かを判定
bit_ceil(n) n以上で最小の "2の冪乗"
bit_floor(n) n以下で最大の "2の冪乗"
bit_width(n) 1 + floor(log2(n)) の整数演算*3
（ビット幅長）

入力値nと関数戻り値（n=0..16）：

n has_single_bit bit_ceil bit_floor bit_width
0 false 1 0 0
1 true 1 1 1
2 true 2 2 2
3 false 4 2 2
4 true 4 4 3
5..7 false 8 4 3
8 true 8 8 4
9..15 false 16 8 4
16 true 16 16 5

関連URL

*1:https://github.com/cplusplus/draft/pull/3780

*2:P1956R1引用："LEWG voted to rename some of the bit manipulation functions in order to avoid references to powers of two since manipulating bits should work in the future on bytes and machine words that are not numbers and for which numeric operations are not defined"

*3:初期提案P0556R0では “前提条件(Requires) n>0 あり log2(n) 関数” と定義されていたが、log2p1 に改名されC++標準ライブラリの広い契約(Wide Contracts)を満たす（→id:yohhoy:20180127）よう仕様変更された。