ぷろみん

プログラミング的な内容を扱ってます

rust-trace-event-profilerでtokio::runtime

最近のRustではThread制御までライブラリに任せられるようなので、その機能を使って前回作ったTrace Eventを作るやつで挙動を可視化してみました。

let mut rt = tokio::runtime::Builder::new()
    .core_threads(6)
    .threaded_scheduler()
    .build()
    .unwrap();

rt.block_on(async move {
    let events = put_ten_block().await;
    save_file("flow.json", events);
});

f:id:torini:20200704195314p:plain

async fn put_ten_block(item: TimelineItem) -> Vec<TraceEvent>;

async関数を利用するだけでタスクを適切にスレッドに割り振ってくれています。素晴らしい。

Rustでプロファイリングの可視化

github.com

Rustのプロファイラを書きました。
正直Rustの知識が浅いのでまともなプロファイラが書けるとは思っていないのでプロファイラ部分はおまけでTrace Event Formatへのシリアライズ定義が本体かなと思っています。
タイムスタンプにオフセットかけたりしたかったのですがserdeでシリアライズ可能にしたTrace Event Format定義が複雑過ぎて悩んでいます。
現状だとPhase毎に追加しないといけなくなりそう。

derive_builderがenum定義のビルドがそのままではできないことも難しい。

rust-derive-builder/build_method.rs at v0.9.0 · colin-kiegel/rust-derive-builder · GitHub

の定義だと

enum Type {
  A { value: u32 },
  B { value: u64 },
}

のような定義、T::Aのビルダーを作成することができない。
struct定義をenumの外部に配置するとできるが、今度はserdeによる自動シリアライズが上手くいかない。

文字列の管理に関してもラベルテーブルのようなものを用意して割り当てることが妥当だがシリアライズとの兼ね合いが難しい。

しかし、Rustの構文木を変更できるマクロやアトリビュートには可能性を感じますね。 RustでRustのコードを生成している様子はリフレクションの未来を感じました。

喜びは映像にしないと半分も伝わらない

2015年のジャーナルですが面白かったので紹介します。

音声に含まれる感情の認識(pdf)

日常的な事柄を例に使っており非常に読みやすいので、直接読む方が良いかもしれません。
特に興味深かった箇所を引用します。

「悲 しみ」の よ うに 音声 だ け で あっ て も 60%程 度伝 わ る もの が あ る 一方 ,「喜 び」で は ,映像等すべ て 見 れ ば 69%程 度伝 わ る の に, 音声 だ け で は 32% しか伝わ らない

私達が小さな小窓であっても顔映像を好むのは、この37%の喜びを理解できるからかもしれませんね。

MSVCでも頑張ってC++20で導入されるspanを使う

wandboxではspanを利用できるので動作確認だけならそちらが簡単です。

何故人はstringを使わないのか

stringは内部バッファに文字列を蓄えるので例えば

std::vector<std::string> Split(const std::string& text);

みたいな関数があった時に入力のテキストと出力の分割文字列で重複があるので無駄が多いと感じます。
そこで、区間を表す構造体が欲しくなります。

span

struct Span{
  char* pointer;
  size_t size;
};
std::vector<Span> Split(const std::string& text);

これで最小限の情報だけで関数を表現できたが、区間を入手したらその区間をイテレートしたいと思うのは自然なことでしょう。
分割したいアイテムが文字列じゃない場合を想定してテンプレートでSpanを書きたくなるかもしれません。
自分で書くのが億劫になってきました。

ちなみに文字列用のspanとして専用の<string_view>が存在するので、本来ならこっちを使うべきです。
MSVCの最新版では現在でも利用することができます。
string_viewをstring_spanにする案もあったそうですが、通らなかったんですかね。
string_viewはstringとほぼ同じ動作をし、無駄なnull終端を管理しません。
文字列を扱う場合はstring_viewを使いましょう。

#include <iostream>
#include <span>
#include <string_view>

template<class T>
void Print(T&& t){
    std::cout << t.size();
    for(auto i : t){
        std::cout << ",[" << i << "]";
    }
    std::cout << std::endl;
}

int main(){
    const char text[] = "ab";
    Print(std::span(text));
    Print(std::string_view(text));
}

//出力
//3,[a],[b],[]
//2,[a],[b]

utf8

更に横にそれますが、C++20になってchar8_tというutf8用の型が提供されるようになったので実際に使われる文字列はstd::u8string_viewが多くなるでしょう。

spanの使い道

コンテナの一部区間を出力したり、バイナリのチャンク分けの際に活躍します。
これらは上記と同じ問題が発生します。そこでspanの出番です。

ただ、概念を考えれば分かる通りspanやviewのスコープは参照元よりも短い必要があります。

現在のMSVCの最新版でもまだspanは導入されていません。C++20で入ることを考えると待っていたらリリースされそうではありますが、今欲しいとなると中々面倒です。

spanの導入

spanはCppCoreGuidelinesで提案されている概念の実装であるGSL (Guidelines Support Library)に含まれています。
今回はその中でもMicrosoftによる実装であるms-gslを利用します。

$ git init
$ git submodule add https://github.com/microsoft/vcpkg
$ cd vcpkg
$ ./bootstrap-vcpkg.bat
$ ./vcpkg.exe install ms-gsl
$ cd ..
$ touch main.cpp
$ touch CMakeLists.txt
$ cmake . -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake
$ cmake --build .

cmakeがinstall済みではない場合vcpkgが使っているものが以下にあります。
vcpkg\downloads\tools\cmake-3.14.0-windows\cmake-3.14.0-win32-x86\bin\cmake.exe

// main.cpp
#include <gsl/span>
// 上記と重複部分省略

int main() {
  Print(gsl::make_span("ab"));
}
# CMakeLists.txt
cmake_minimum_required(VERSION 3.1)

find_path(include_root_dir NAMES gsl/span)
include_directories(${include_root_dir})

add_executable(main main.cpp)

Texture Atlasの生成

Texture Atlas

1回のレンダリングで利用できるテクスチャの枚数は限られているので、複数のテクスチャを1枚のテクスチャにまとめることは非常に重要です。
この色々なテクスチャをまとめたテクスチャをTexture Atlasと呼びます。
今回はこれの作り方をいくつかメモしておきます。

Knapsack problem

入れ物に可能な限り多くのテクスチャを格納するという観点から考えるとナップサック問題として取り扱えるように思えます。
更にMulti-dimensional knapsack problemの項目を読むと2Dナップサック問題の解法としてIHS (Increasing Height Shelf) algorithmというものが存在しているらしいです。

Increasing Height Shelf

まだ論文をちらっと眺めただけですが、最大の高さのアイテムに合わせたラインにそって並べる方法のように見えます。
下記で実装されている方法がそのような挙動っぽいので下記アルゴリズムとの違いを調査したいところです。

下が揃っているラインを複数段作っていくからShelfなんですね。面白いネーミング。

Skyline Bottom-Left algorithm

https://github.com/nothings/stb/blob/master/stb_rect_pack.h
上記ではSkyline Bottom-Left algorithmを利用しているそうです。