2023-03-06

AoSとSoAなflat_map

std::mapを線形配列に落とし込むことで、イテレータ走査やメモリレイアウトを効率化したflat_mapについては以前説明しました。

flast.hateblo.jp

当時私が実装したflat_mapはArray of Structure(AoS)形式の実装で、構造体を線形配列に配置するものでした。これはキーと値がメモリ上で並んだ位置に配置されるので、キーから検索した直後に値を使う場合にはキャッシュに載っている可能性が高くなる利点があります。

2021-12-08

平らな地図、もといflat_map

C++ ライブラリ関係 Advent Calendar

この記事は C++ Advent Calendar 2021 の8日目です。

ブログもAdvent Calendarも、ものすごく久しぶりになってしまいました。あの頃カラオケで規格書を開いて語り合っていた面子も見なくなり、最近の新しい仕様はよくわからないです。歳をとったものです。

2019-03-19

謎の用語niebloid

C++

cppreference.comは随所に様々アノテーションがついていて大変便利だ。例えば(since C++17)といった感じでこれはC++17以降に登場した定義とかそういうのがひと目でわかる。さっき20での変更に何があるのか適当に眺めていたところ、<algorithms>の変更でConstraind algorithmsというのを見つけた。これはいわゆるRange TSと呼ばれていたもので、Boost.Rangeの標準化みたいなもの（のはず）だ。

よくよく見てみると、これには(niebloid)という見慣れないアノテーションがついている。全くわからない。他の(concept)とかは意味がわかる。これはそのままだ。

適当にぐぐってみるとものすごくヒットが少ない。とはいえ検索結果で目につくのはなんと言ってもEric Nieblerだ。この人はBoost.Rangeのメンテナで、Range TSの担当(?)だ。なるほどなんとなく察しがつく。

I hope this sticks. It would amuse me to no end to hear folks arguing about "niebloids" in a WG21 meeting some day. https://t.co/7abV4BsYkx
— Eric Niebler (@ericniebler) 2018年11月19日

どうもniebloidというのは彼が作った造語で、これらはADLを徹底的に排除した関数呼び出し形式で扱えるなにかを指すらしい。言いたいことはわかるがしかしあまりに唐突すぎる言葉なのでcppreference.comにも何かしらの説明がほしい... cppreference.com内で検索してもヒットしないのはいただけない

ちなみにNieblerはニーブラーと発音するっぽいので、おそらくniebloidはニーブロイドと発音するのだろう。

2017-10-06

msgpackのデバッグをするための何か

C++

msgpackのデータはあるんだけどなんかズレてたりしてデシリアライズ出来なくて困った困ったみたいなとき、目デシリアライズするのも（でかいと）ツライし、そうでなくてもデバッグしてる間に中身を見ようとしてもVSのデフォルトのビジュアライザだと中途半端でつらいものがあった

一応ブラウザで動くビジュアライザもあるらしいがbase64にしないといけないっぽいし、でかいデータでも大丈夫なのかな、、とか、（多分）オフラインだけどちょっと機密データのデバッグには抵抗感がある http://sugendran.github.io/msgpack-visualizer/

Visual Studioのデバッガは優秀（真顔）だけどvisualizerもmsgpack的にはちょっと足りない

つくったもの

msgviwer

https://github.com/Flast/msgviewer

とりあえずバイナリデータをツリー状にして可視化する

単にツリーで見えても修正とかだるかったからオフセットも見えるようにしてる

Qtで作ってるから大体の環境で動くはず

ビルド方法とかドキュメントとか無いのはなんとかしないといけない（使命感）

msgpack-vs-visualizer

https://github.com/Flast/msgpack-vs-visualizer

Visual Studioのデバッガで配列とか中身全部みれるようにするやつ

こっちもドキュメントとか全然ないけど雰囲気でがんばって（適当）

とりあえず配列のようなやつらは全部ちゃんと見えるようになった

余計な via とか見えてるのは気が向いたらそのうちなんとかしたい

2017-04-12

allocaをinline関数で使うと危険である？

C++ GCC

“allocaをinline関数で使うと危険である"という要旨のメールがoss-securityに流れてて、これは一体どういうことだ…と思った。

長い文章でも無いしそんなに難しくもないが、どうやらGCCのオプティマイザの展開順に問題があるようだ。

http://www.openwall.com/lists/oss-security/2017/04/10/18

曰く、alloca(本文ではC(99)のVLAを指していた)を見つけるとGCCはそれを__builtin_allocaに展開した後、そのinline関数をインライン展開するので、ループ中で使うとスタックをガンガン持ってかれるということだった。 allocaは任意のスコープではなく、関数スコープからの離脱でのみスタックの巻き戻しを行うので、ループ本体を一巡したあとに本来巻き戻って欲しいスタックが巻き戻らず、次のallocaが行われてスタックが枯渇する脆弱性になると指摘している。

試しにMLに張られたコードに足りない部分を補完してバイナリを見てみたが、どうにも普通に巻き戻しはしているように見える。 -Oから既にインライン展開は行われるが、いくつかの最適化レベルを眺めてもやはり巻き戻しているように見える。

https://godbolt.org/g/fiofnf

なにか別の要因があるのだろうか…