大掴みBoost.PolyCollection

C++

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

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

続きを読む

FizzBuzz

C++

会話をしていると、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++

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

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

続きを読む

アセンブリ解読　小休止

asm

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

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

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

続きを読む

アセンブリ解読　その4

asm

その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が到達可能ならそこまでの範囲を総和する。到達不能なら知らない。

続きを読む

アセンブリ解読　その3

asm

前回長くなりすぎたので、追記分を分けておくことにした。

前回は簡易fizzbazzを逆アセンブルし、割り算の最適化に関して面白いものを見たのだった。

アセンブリ解読 その2 - in neuro

その続きとして、moduloではなく普通の割り算はどうなるんだろう、と思って以下のようなコードを書いてみた。

#include <stdint.h>

int32_t div_by3(int32_t a)
{
    return a / 3;
}

int32_t div_by4(int32_t a)
{
    return a / 4;
}

int32_t div(int32_t a, int32_t b)
{
    return a / b;
}

逆アセンブルする。予想としては、div_by3は先のマジックナンバーを使った方法を、div_by4はsarで右シフトを、divは普通にidiv命令を使うというものだ。 それがたとえ-O0であったとしても。

続きを読む