emptyとsize==0

コンテナが空(要素を持っていない)かどうかを確認するとき、タイトルの2つのメソッドのどちらを使うかという話題で界隈が盛り上がっていたようだ。

私はempty()一択だ。サイズが0かどうかを確認したいなら、size() == 0を使うべきだ。だが、コンテナが空であることを確認できるメソッドがある場合に、コンテナが空であるかを確認するために別のコードを書く理由がない。 その2つが異なる場合があるのか、というのは疑わしい。ただ、未初期化領域を区別できるようなコンテナを作って、過去のSTLの命名を全て無視して関数を命名したなら、場合によっては筋が通った形でemptyかつsize != 0という結果になることはありえるだろう。sizeはnon-zeroだが、確保してある全領域が未初期化のままなのでempty、というように。

C++では実際には、リストのようにsizeを取得するコストが定数でない可能性のあるデータ構造を考えてemptyが作られたのだろうと思われるが、list::sizeが定数時間とされてからはこの点に関してはどうでもよくなった。

問題があるとすれば、emptyの命名だろうか。C++界隈では人々は長年STLに親しんでいるのでこの名前の関数がどう機能するかについて合意しあっているが、そうでない人がこれを見た時にどう反応するかはわからない。 もしこれが、is_emptyempty?のような命名であれば、オブジェクトの状態を取得し、boolを返すというところまで含意できたのだが。

というわけで以下のようにしよう。

#define is .
std::vector<int> vec;
std::cout << std::boolalpha << vec is empty() << std::endl;

言うまでもないがこのコードは冗談だ。

大掴みBoost.PolyCollection

この間、Boost 1.65がリリースされた。リリースノートをざっと見た所、新規ライブラリがいくつか入っている。そのPolyCollectionなるものが気になったのでざっと見てみることにした。これはその覚え書きである。

PolyCollectionは、多相型向けのコンテナだ。基底クラスを指定してその派生クラスを格納したり、anyによってDuckTypingしたり、std::functionに関数ポインタや関数オブジェクトを放り込んだりする際にいちいち生じるヒープアロケーション、それによるキャッシュヒット率の低下と、仮想関数呼び出し時の分岐予測の失敗を解決する。

続きを読む

FizzBuzz

会話をしていると、FizzBuzzの話になった。何かの拍子にFizzBuzzを書いてくださいと言われたらどうするだろうか、と思ってちょっと書いてみることにした。たまには気楽に書けるものもよい。

FizzBuzzを自然に捉えると、数字を文字列に変換していくルールに従って、入ってくる数字の列を変換し順に出力するというものだろう。

ということは、iota的なイテレータtransform_iteratorで覆って、ostream_iteratorに投げ込んでいけばいい。

iota的なことをしてくれるイテレータはないかと探したところ(作れるが演算子定義などが面倒だ)、boost::iterator::counting_iteratorがよいとわかった。

#include <boost/iterator/transform_iterator.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <algorithm>
#include <iostream>
#include <string>

int main(int argc, char** argv)
{
    if(argc != 2)
    {
        std::cerr << "usage: ./fizzbuzz <maximum>" << std::endl;
        return 1;
    }

    const auto fizzbuzz = [](const std::uint64_t i){
        using namespace std::literals::string_literals;
        if(i%3 == 0 && i%5 == 0) return "FizzBuzz"s;
        else if(i%3 == 0)        return "Fizz"s;
        else if(i%5 == 0)        return "Buzz"s;
        else                     return std::to_string(i);
    };

    std::copy(
        boost::make_transform_iterator(
            boost::make_counting_iterator(1ull),
            fizzbuzz),
        boost::make_transform_iterator(
            boost::make_counting_iterator(
                std::stoull(argv[1]) + 1ull),
            fizzbuzz),
        std::ostream_iterator<std::string>(std::cout, ", "));
    std::cout << std::endl;
    return 0;
}

こんなもんだろう。しかしまあ、1からmaxまでの数字の列を作って、それに関数を適用するだけだというのに非常に面倒なことをしないといけないのはやはり辛い。これくらい簡単になってもよいと思うのだが。

#include <algorithm>
#include <iostream>
#include <string>

int main(int argc, char** argv)
{
    if(argc != 2)
    {
        std::cerr << "usage: ./fizzbuzz <maximum>" << std::endl;
        return 1;
    }

    const auto fizzbuzz = [](const std::uint64_t i){
        if(i%3 == 0 && i%5 == 0) return "FizzBuzz"s;
        else if(i%3 == 0)        return "Fizz"s;
        else if(i%5 == 0)        return "Buzz"s;
        else                     return std::to_string(i);
    };
    const auto max = std::stoull(argv[1]);
    (1ull ... max).transform(fizzbuzz).output(std::cout, ", ");
    return 0;
}

と、思った辺りでBoost.rangeの存在を思い出した。

#include <boost/range/algorithm.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <iostream>
#include <cstdint>

int main(int argc, char** argv)
{
    if(argc != 2)
    {
        std::cerr << "usage: ./fizzbuzz <maximum>" << std::endl;
        return 1;
    }

    const auto fizzbuzz = [](const std::uint64_t i){
        using namespace std::literals::string_literals;
        if(i%3 == 0 && i%5 == 0) return "FizzBuzz"s;
        else if(i%3 == 0)        return "Fizz"s;
        else if(i%5 == 0)        return "Buzz"s;
        else                     return std::to_string(i);
    };

    boost::copy(boost::irange(1ull, std::stoull(argv[1]) + 1ull) |
                boost::adaptors::transformed(fizzbuzz),
                std::ostream_iterator<std::string>(std::cout, ", "));
    std::cout << std::endl;
    return 0;
}

やはりこうするとかなりマシだ。

関数型言語としてのC++ Template MetaProgramming入門

C++ではtemplateを使ってコンパイル時に計算を行うことができる。 今回は、関数型言語としての視点からC++テンプレートメタプログラミング(C++-TMP)の簡単な紹介をやってみたい。

注:私はHaskelllispの経験がホンの少しだけあるが、どちらも使いこなせるようになっているわけではない。のでこの記事には関数型への誤解が含まれる恐れがあることを注意していただきたい。

続きを読む

アセンブリ解読 小休止

これまで、4回に渡ってコンパイラ(gcc v5.4.0)の生成するアセンブリコードを解読してきた。これまでの内容は、以下のような感じになる。

  1. その1: レジスタの使い方、関数の定石、初歩的な最適化
  2. その2: 条件分岐、除算の最適化
  3. その3: 除算の最適化と定数伝播、リンク時最適化
  4. その4: ループと自動ベクトル化

これまでは、私が読んでいく過程で何を思ったかをだだ漏れに垂れ流していたので、推敲も何もあったものではなく、読みやすくわかりやすい記事というには程遠かった。 ここで一度小休止してここまでのちょっとしたまとめをしてみよう。ただし、既にそれぞれの記事を読んでいる人にはこれは無意味な記録ということになる。 あと、私にはアセンブリの解説ができるほどの技量はまだないので、そういう方向の期待はあまりしないでほしい。

続きを読む

アセンブリ解読 その4

その2で宣言した通り、今回の対象はループだ。その2に続きが発生したので番号的には飛んでしまっているが、続きという点は変わらない。 しかしループとなると絶対にSIMDとループアンロールが絡んで面倒なことになる、と思っているので少し腰が重いが、最適化の勉強というならむしろこれこそやらねばならない。

今回とりあえずこんなコードを書いた。

#include <stdint.h>

int32_t accum(const int32_t* begin, const int32_t* end)
{
    int32_t sum = 0;
    for(; begin != end; ++begin)
        sum += *begin;
    return sum;
}

beginからendが到達可能ならそこまでの範囲を総和する。到達不能なら知らない。

続きを読む