Go to Qiita Advent Calendar 2024 Top
LoginSignup
6
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@taqu

C++ std::stringの最適化

Last updated at Posted at 2021-05-08

はじめに

std::mapの高速化に対する一考 が気になって眠れないのと, コメントに書くには長くなるので. また, この時期なのでアンチパターンを教えなければいけないのです.

説明

件の記事は, 連想配列, std::mapやstd::unordered_mapのキーとしてstd::stringを使用するとメモリ確保が発生して遅いから, 高速化するんじゃ！と言っているわけです. 高速化の手段は, Small-String OptimizationとCopy-On-Writeのハイブリッドを提案しています.

ふたつの高速化手法について, 簡単に次のようになります.

  • Small-String Optimization
    • 短い文字列は, 静的配列を使用してコピーする.
    • 長い文字列は, 動的配列を使用してコピーする.
  • Copy-On-Write
    • 文字列の中身が変更されるまで共有する.
    • 変更されるときに動的配列を確保してコピーする.

歴史

N2668によると, C++11より前はCopy-On-Write(COW)での実装が半数であったことがわかります. COWは, 資源を複数で共有する前提なので, マルチスレッドの場合に不利です. 2006年ごろから一般向けCPUもマルチコア化していく中, C++11でCOWは禁止されます.

C++11以降, 各実装はSmall-String Optimization (SSO) に変更されます. 正しくはコンパイラではなく, 付随するライブラリなのですが, SSOの静的配列のサイズは次のようになります.

コンパイラ サイズ
GCC 10.2.1 15
Clang 12.0 22
MSVC 15

shared_basic_string

std::shared_ptrでいいかげんに参照カウントを作ってみた.

shared_basic_string
#ifndef INC_SHARED_BASIC_STRING_H
#define INC_SHARED_BASIC_STRING_H
#include <cstdint>
#include <cstring>
#include <memory>

namespace utils
{
template<class T>
class shared_basic_string
{
public:
    using size_type = size_t;
    using value_type = T;
    using this_type = shared_basic_string<T>;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using iterator = pointer;
    using const_iterator = const_pointer;

    static const size_type npos = static_cast<size_type>(-1);

    shared_basic_string() noexcept;
    shared_basic_string(const this_type& other);
    shared_basic_string(this_type&& other) noexcept;
    explicit shared_basic_string(const_pointer str);
    ~shared_basic_string();

    this_type& operator=(const this_type& other);
    this_type& operator=(this_type&& other) noexcept;
    this_type& operator=(const_pointer str);

    const_pointer c_str() const noexcept;

private:
    static value_type empty;
    size_type length(const_pointer str) const noexcept;

    size_type size_;
    std::shared_ptr<value_type> buffer_;
};

template<class T>
typename shared_basic_string<T>::value_type shared_basic_string<T>::empty = static_cast<typename shared_basic_string<T>::value_type>('\0');

template<class T>
shared_basic_string<T>::shared_basic_string() noexcept
    : size_(0)
{
}

template<class T>
shared_basic_string<T>::shared_basic_string(const this_type& other)
    : size_(other.size_)
    , buffer_(other.buffer_)
{
}

template<class T>
shared_basic_string<T>::shared_basic_string(this_type&& other) noexcept
:size_(other.size_)
,buffer_(std::move(other.buffer_))
{
    other.size_ = 0;
}

template<class T>
shared_basic_string<T>::shared_basic_string(const_pointer str)
{
    if(nullptr != str) {
        size_ = length(str);
        buffer_ = std::shared_ptr<value_type>(new value_type[size_+1], std::default_delete<value_type[]>());
        memcpy(buffer_.get(), str, (size_+1)*sizeof(value_type));
    } else {
        size_ = 0;
    }
}

template<class T>
shared_basic_string<T>::~shared_basic_string()
{
    size_ = 0;
}

template<class T>
typename shared_basic_string<T>::this_type& shared_basic_string<T>::operator=(const this_type& other)
{
    if(this != &other) {
        size_ = other.size_;
        buffer_ = other.buffer_;
    }
    return *this;
}

template<class T>
typename shared_basic_string<T>::this_type& shared_basic_string<T>::operator=(this_type&& other) noexcept
{
    if(this != &other) {
        size_ = other.size_;
        other.size_ = 0;
        buffer_ = std::move(other.buffer_);
    }
    return *this;
}

template<class T>
typename shared_basic_string<T>::this_type& shared_basic_string<T>::operator=(const_pointer str)
{
    if(nullptr != str) {
        size_ = length(str);
        buffer_ = std::shared_ptr<value_type>(new value_type[size_+1], std::default_delete<value_type[]>());
        memcpy(buffer_.get(), str, (size_+1)*sizeof(value_type));
    }else{
        size_ = 0;
        buffer_.reset(nullptr);
    }
    return *this;
}

template<class T>
typename shared_basic_string<T>::const_pointer shared_basic_string<T>::c_str() const noexcept
{
    return (0<size_)? buffer_.get() : &empty;
}

template<class T>
typename shared_basic_string<T>::size_type shared_basic_string<T>::length(const_pointer str) const noexcept
{
    size_type length = 0;
    while(empty != *str){
        ++length;
        ++str;
    }
    return length;
}

template <class T>
bool operator<(const shared_basic_string<T>& x0, const shared_basic_string<T>& x1) noexcept
{
    return strcmp(x0.c_str(), x1.c_str())<0;
}

} // namespace utils
#endif //INC_SHARED_BASIC_STRING_H

テスト

元の記事が奇妙過ぎて.

こちらより,

for (auto [key, val] : normal_map) {}

こちらの方が実行時間が短いって奇妙でしょう？

for (auto [key, val] : normal_map) {ss<<val;}

何を測定したいか分からないので, 挿入と参照を測定しました. キーの話をしていたので値は整数です. 合算値を計算して表示しているのは, 削除されないためと, 簡易に正確か確かめるためです.

test
#include <chrono>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <sstream>
#include <string>
#include <vector>

#include "shared_basic_string.h"

struct KeyValue
{
    std::string key_;
    int32_t value_;
};

void generateStrings(std::vector<KeyValue>& pairs, int32_t size, uint32_t seed)
{
    pairs.clear();
    pairs.reserve(size);

    std::mt19937 engine(seed);
    std::uniform_int_distribution<> key_dist(0, size);
    std::uniform_int_distribution<> rank_dist(10, 32);
    std::uniform_int_distribution<> value_dist(0, 10);

    std::stringstream ss;
    for(int32_t i = 0; i < size; ++i) {
        ss.str("");
        ss << std::setfill('0') << std::right << std::setw(rank_dist(engine)) << key_dist(engine);
        pairs.push_back({ss.str(), value_dist(engine)});
    }
}

template<class Key>
void test_insert(const char* name, const std::vector<KeyValue>& pairs)
{
    std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();

    std::map<Key, int> map;
    for(size_t i = 0; i < pairs.size(); ++i) {
        map.insert(std::make_pair(Key(pairs[i].key_.c_str()), pairs[i].value_));
    }

    int64_t total = 0;
    for(const auto& [key, value]: map) {
        total += map[key];
    }

    std::chrono::high_resolution_clock::time_point end = std::chrono::high_resolution_clock::now();
    std::chrono::milliseconds duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "insert: " << name << ": " << duration.count() << " milliseconds : " << total << std::endl;
}

template<class Key>
void test_emplace(const char* name, const std::vector<KeyValue>& pairs)
{
    std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();

    std::map<Key, int> map;
    for(size_t i = 0; i < pairs.size(); ++i) {
        map.emplace(pairs[i].key_.c_str(), pairs[i].value_);
    }

    int64_t total = 0;
    for(const auto& [key, value]: map) {
        total += map[key];
    }

    std::chrono::high_resolution_clock::time_point end = std::chrono::high_resolution_clock::now();
    std::chrono::milliseconds duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "emplace: " << name << ": " << duration.count() << " milliseconds : " << total << std::endl;
}

int main(void)
{
    static const int32_t Samples = 20000000;
    std::random_device seed_gen;
    uint32_t seed = seed_gen();

    std::vector<KeyValue> pairs;
    generateStrings(pairs, Samples, seed);
    test_insert<utils::shared_basic_string<char>>("shared_basic_string<char>", pairs);
    test_insert<std::string>("std::string", pairs);
    test_emplace<utils::shared_basic_string<char>>("shared_basic_string<char>", pairs);
    test_emplace<std::string>("std::string", pairs);
    return 0;
}
環境
CPU Core i5-10210U
RAM DDR4-2666 16 GB
コンパイラ GCC 10.2.1

コンパイラオプションは, -std=c++17 -O2 -Wall. ターボブーストは無効です.

実行時間 合算値
insert shared_basic_string 101206 milliseconds 97846179
insert std::string 69081 milliseconds 97846179
emplace shared_basic_string 103825 milliseconds 97846179
emplace std::string 69215 milliseconds 97846179

追記

常に少し時間をおいて見返しますが, 足りてませんね.

テストデータについて

値については本文のとおり, 元の記事がキーの話をしているので, なるべく影響のないように整数です. キーの桁数が [10 32] なのは理由がないです. 理由がない理由は, テストしたい環境がわからないからです. 私のプロダクトでは, この範囲が大半だと思われるのと, 最大値はClang (libc++) を超えるからです. 実装を知っていると, 例えば文字数17に固定すれば, const_basic_stringよりlibc++のstd::stringが勝るでしょう.

STLの実装について

次は各実装の引用です, 軽く調べていますよということです.
この程度の長さなら, 出自を示して引用であることが誰にでも理解できるようにしていれば大丈夫です.
どれも1バイト, フラグに使用しているはずです, 読み違いしていたらごめんなさい. あ, 早速, GCCは別で持ってますか.

GCC 10.2.1 bits/basic_string
enum { _S_local_capacity = 15 / sizeof(_CharT) };
Clang 12.0 string
struct __long
{
    pointer   __data_;
    size_type __size_;
    size_type __cap_;
};
enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
                      (sizeof(__long) - 1)/sizeof(value_type) : 2};
MSVC 2019 xstring
// length of internal buffer, [1, 16]:
static constexpr size_type _BUF_SIZE = 16 / sizeof(value_type) < 1 ? 1 : 16 / sizeof(value_type);

アンチパターンについて

最初はまとめに入れていたのですが, 辛辣かなと思ったので削除しました. 攻撃するつもりはなく, 研究屋や言語仕様屋ではない, プロダクト屋としての立場からの意見と思っていただきたいです.

  • 使用しないincludeを入れてはいけない
  • 理由のないinlineを使ってはいけない
  • API, インターフェイスにautoが漏れてはいけない
  • 一般的でない名前の省略をしてはいけない
  • 使わない, 使われない機能を入れてはいけない

追記２

特定の環境用に, 高速化した実装を示すことは否定していません. 実際, 私はAndroid 1.6, NDKが出た時代にSTLを捨てたので.
もし研究者ならば追試できるように, 十分な情報を示さなければならないでしょう.

マルチコア化によるソフトウェアの変化

このあたりの歴史は, mallocの実装にも当てはまります. Doug Leaのmalloc dlmallocより後に出たmalloc実装は, 全てマルチコアを想定した実装になった, といっていいです.

まとめ

もっとまじめに実装すれば, shared_basic_stringはもう少し速くなります.

教訓は次です.

  • 言語仕様を正しく理解しなければいけない
  • ライブラリ, APIは正しく理解しなければいけない
  • 単体テスト, プロファイルはその測定方法が正しいか, 何度も確認しなければいけない
  • 愚者は経験に学び, 賢者は歴史に学ぶ
6
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?