😺

std::string でメモリーアロケートが発生しない最大バイト数

2022/10/02に公開

C++

string

tech

std::basic_string の実装は、短い文字列の場合、メモリーアロケートせず、basic_string 型内部のメモリを(工夫して)用いる作りになっていることがあります。

というか、vc++ にしろ g++ にしろ clang++ にしろ、そうなっています。

で、それが何バイトか？というと、実装や環境ごとによりけりだろうで、少し調べてみました。

#include <cstdio>
#include <cstdlib>
#include <type_traits>

std::size_t g_new_count = 0;
std::size_t g_del_count = 0;

template<typename T>
struct my_allocator {
    using value_type = T;
    using is_always_equal = std::true_type;
    using propagate_on_container_move_assignment = std::true_type;
    constexpr my_allocator() noexcept {}
    constexpr my_allocator(const my_allocator&) noexcept {}
    template <class U> constexpr my_allocator(const my_allocator<U>&) noexcept {}
    my_allocator& operator=(const my_allocator&) = default;
    constexpr T* allocate(std::size_t n) { ++g_new_count; return (T*)std::malloc(n*sizeof(T)); }
    constexpr void deallocate(T* p, std::size_t n) { ++g_del_count; std::free(p); }
};
template<typename T> bool operator==(my_allocator<T> const& l, my_allocator<T> const& r) { return true; }
template<typename T> bool operator!=(my_allocator<T> const& l, my_allocator<T> const& r) { return false; }

#include <string>

using my_string = std::basic_string<char, std::char_traits<char>, my_allocator<char>>;

int main() {
    std::printf("sizeof(string)=%zu\n", sizeof(my_string));
    for (std::size_t i = 1; i < 64; ++i) {
        g_new_count = g_del_count = 0;
        {
            my_string s(i, '*');
            std::fprintf(stderr, "%s\n", s.c_str());
        }
        std::printf("%5zu new_count = %zu, del_count = %zu\n", i, g_new_count, g_del_count);
    }
    return 0;
}

単純に allocator を乗っ取って allocate/deallocate の呼び出し回数をカウントして表示するだけです。
（今どきの環境では malloc や operator new が乗っ取りづらい……）

結果

試したのは Windows 10 x64 と ubuntu 22.04(x86_64)、macOS 15.5.1(M1) の64bit環境で、結果は

コンパイラ	sizeof(string)	非アロケート最大文字数	環境	その他
vc++2022 x64	32	15	win10 x64	x86でも同じサイズ
g++11.2/12.1(libstdc++)	32	15	ubuntu / Win10 msys2 mingw64
clang++14.0(llvm libc++)	24	22	ubuntsu / Win10 msys2 clang64 / macOS

もちろん clang でも libstdc++ を使っていたら g++ と同じ結果になります。

c++11 以降、最後の文字の次に null 文字が必須なので、そのサイズと合わせると、内部バッファのサイズは

vc++ 16バイト、libstdc++ 16バイト、libc++ 23バイト

でしょうか。
※ wchar_t とか char16_t, char32_t の文字数はこれを逆算すれば、で。

実装について

string は vector 同様

メモリ先頭へのポインタ(data)
メモリー領域のサイズ(capacity) （あるいは領域終端へのポインタ）
文字数(size) （あるいは使用文字列終端へのポインタ）

の情報が必要で、標準実装としては 64bit CPU では sizeof(void*)*3 の 24バイトが最低限必要でしょう。
全体を32バイトにして単純な作りの内部バッファ追加だと8バイトにしかならないので、いづれの実装も工夫しているようです。

で、結局それぞれの実装をみたのですが。

vc++ では、size と capacity が変数ままで、先頭ポインタと余りメモリを 16 バイトのバッファにしています。アロケートしたかどうかは capacity が 16 より大きいかで判断。
g++/libstdc++ では、先頭ポインタと size は変数のままでペナルティなく、capacity と余りメモリを 16 バイトのバッファにしています。アロケートしたかどうかは先頭ポインタが内部バッファ先頭を指しているかどうかで判断。
clang/libc++ では、1 bit のフラグでメモリの使い方を切り替えています。capacity が 63bit になりますがメモリはヨタ(そこ)まで無いので無問題。アドレス取得やサイズ取得で毎度フラグ判定が必須になりますが、メモリ効率はよいです。

libstdc++, libc++ の実装はトレードオフに納得するのですが、vc++ のはなんで利用頻度の低い capacity でなく頻度の高いポインタ側を内蔵バッファ併用にしてるのでしょうね？ Dinkumware 時代の vc8 のモノをみてもそうなっていたので互換的に変えられないのでしょうが……

終わりに

自分が普段さわっている 64bit 環境(win,ios,android) ならば、実装依存承知で、少なくとも 15 バイト以下はアロケート無しを前提にできそうです。
てか clang が標準の ios, android, mac ならば 22バイト前提でよさそう。

15 桁でも、それで間に合う整数値は多く、浮動小数点数も %e や %g でデフォルト桁数＋α程度なら収まるので、その範囲で std::to_string や std::format 使う分にはアロケートしないだろうと認識できたのはよかったです。

結果

実装について

終わりに

Discussion