Mengoptimalkan alokasi string berlebihan di C ++

Saya memiliki komponen C ++ yang cukup kompleks yang kinerjanya menjadi masalah. Profiling menunjukkan bahwa sebagian besar waktu eksekusi hanya dihabiskan mengalokasikan memori untuk std::strings.

Saya tahu bahwa ada banyak redundansi di antara string-string itu. Sejumlah nilai berulang sangat sering tetapi ada juga banyak nilai unik. String biasanya cukup pendek.

Saya sekarang hanya berpikir apakah akan masuk akal untuk menggunakan kembali alokasi yang sering tersebut. Alih-alih 1000 pointer ke 1000 nilai "foobar" yang berbeda, saya bisa memiliki 1000 pointer ke satu nilai "foobar". Fakta bahwa ini akan lebih hemat memori adalah bonus yang bagus, tetapi saya lebih khawatir tentang latensi di sini.

Saya kira salah satu opsi adalah untuk mempertahankan semacam registri dari nilai yang sudah dialokasikan tetapi apakah mungkin untuk membuat pencarian registri lebih cepat daripada alokasi memori yang berlebihan? Apakah ini pendekatan yang layak?

Saya sangat bergantung pada string yang diinternir seperti yang disarankan Basile, di mana pencarian string diterjemahkan ke indeks 32-bit untuk disimpan dan dibandingkan. Itu berguna dalam kasus saya karena saya kadang-kadang memiliki ratusan ribu hingga jutaan komponen dengan properti bernama "x", misalnya, yang masih harus berupa nama string yang mudah digunakan karena sering diakses oleh skrip dengan nama.

Saya menggunakan trie untuk pencarian (bereksperimen juga dengan unordered_maptetapi tri saya disetel yang didukung oleh kolam memori setidaknya mulai berkinerja lebih baik dan juga lebih mudah untuk membuat thread-aman tanpa hanya mengunci setiap kali struktur diakses) tetapi tidak se cepat untuk konstruksi sebagai menciptakan std::string. Intinya adalah lebih untuk mempercepat operasi selanjutnya seperti memeriksa kesetaraan string yang, dalam kasus saya, hanya bermuara pada memeriksa dua bilangan bulat untuk kesetaraan dan secara drastis mengurangi penggunaan memori.

Saya kira salah satu opsi adalah untuk mempertahankan semacam registri dari nilai yang sudah dialokasikan tetapi apakah mungkin untuk membuat pencarian registri lebih cepat daripada alokasi memori yang berlebihan?

Itu akan sulit untuk melakukan pencarian melalui struktur data jauh lebih cepat daripada satu malloc, misalnya. Jika Anda memiliki kasus di mana Anda membaca sekumpulan string dari input eksternal seperti file, misalnya, maka godaan saya adalah menggunakan pengalokasi berurutan jika memungkinkan. Itu datang dengan downside bahwa Anda tidak dapat membebaskan memori dari string individu. Semua memori yang dikumpulkan oleh pengalokasi harus dibebaskan sekaligus atau tidak sama sekali. Tetapi pengalokasi sekuensial dapat berguna dalam kasus-kasus di mana Anda hanya perlu mengalokasikan satu kapal penuh potongan memori berukuran variabel dalam mode berurutan lurus, hanya untuk kemudian membuang semuanya nanti. Saya tidak tahu apakah itu berlaku dalam kasus Anda atau tidak, tetapi ketika berlaku, ini bisa menjadi cara mudah untuk memperbaiki hotspot terkait dengan alokasi memori yang sering kali lebih kecil (yang mungkin lebih berkaitan dengan kesalahan cache dan kesalahan halaman daripada yang mendasarinya algoritma yang digunakan oleh, katakanlah, malloc).

Alokasi berukuran tetap lebih mudah untuk dipercepat tanpa kendala pengalokasian berurutan yang mencegah Anda membebaskan potongan memori tertentu untuk digunakan kembali nanti. Tetapi membuat alokasi ukuran variabel lebih cepat dari pengalokasi default cukup sulit. Pada dasarnya membuat segala jenis pengalokasi memori yang lebih cepat dari mallocbiasanya sangat sulit jika Anda tidak menerapkan kendala yang mempersempit penerapannya. Salah satu solusinya adalah dengan menggunakan pengalokasi berukuran tetap untuk, katakanlah, semua string yang 8 byte atau kurang jika Anda memiliki muatan kapal dan string yang lebih panjang adalah kasus yang jarang terjadi (di mana Anda dapat menggunakan pengalokasi default). Itu berarti 7 byte terbuang untuk string 1-byte, tetapi harus menghilangkan hotspot terkait alokasi, jika, katakanlah, 95% dari waktu, string Anda sangat pendek.

Solusi lain yang baru saja terpikir oleh saya adalah dengan menggunakan daftar tertaut yang tidak terdaftar yang mungkin terdengar gila tapi dengarkan saya.

Idenya di sini adalah untuk membuat setiap node yang tidak dikontrol menjadi ukuran tetap dan bukan ukuran variabel. Saat Anda melakukannya, Anda dapat menggunakan pengalokasi potongan berukuran sangat cepat yang mengumpulkan memori, mengalokasikan potongan berukuran tetap untuk string berukuran variabel yang dihubungkan bersama. Itu tidak akan mengurangi penggunaan memori, itu akan cenderung menambahnya karena biaya tautan, tetapi Anda dapat bermain dengan ukuran yang tidak terbuka untuk menemukan keseimbangan yang cocok untuk kebutuhan Anda. Ini semacam ide aneh tetapi harus menghilangkan hotspot terkait memori karena sekarang Anda dapat secara efektif menyatukan memori yang sudah dialokasikan di blok-blok besar yang berdekatan dan masih memiliki manfaat membebaskan string secara individual. Berikut ini adalah pengalokasi tetap sederhana yang saya tulis (ilustrasi yang saya buat untuk orang lain, tanpa bulu yang terkait dengan produksi) yang dapat Anda gunakan dengan bebas:

#ifndef FIXED_ALLOCATOR_HPP
#define FIXED_ALLOCATOR_HPP

class FixedAllocator
{
public:
    /// Creates a fixed allocator with the specified type and block size.
    explicit FixedAllocator(int type_size, int block_size = 2048);

    /// Destroys the allocator.
    ~FixedAllocator();

    /// @return A pointer to a newly allocated chunk.
    void* allocate();

    /// Frees the specified chunk.
    void deallocate(void* mem);

private:
    struct Block;
    struct FreeElement;

    FreeElement* free_element;
    Block* head;
    int type_size;
    int num_block_elements;
};

#endif

#include "FixedAllocator.hpp"
#include <cstdlib>

struct FixedAllocator::FreeElement
{
    FreeElement* next_element;
};

struct FixedAllocator::Block
{
    Block* next;
    char* mem;
};

FixedAllocator::FixedAllocator(int type_size, int block_size): free_element(0), head(0)
{
    type_size = type_size > sizeof(FreeElement) ? type_size: sizeof(FreeElement);
    num_block_elements = block_size / type_size;
    if (num_block_elements == 0)
        num_block_elements = 1;
}

FixedAllocator::~FixedAllocator()
{
    // Free each block in the list, popping a block until the stack is empty.
    while (head)
    {
        Block* block = head;
        head = head->next;
        free(block->mem);
        free(block);
    }
    free_element = 0;
}

void* FixedAllocator::allocate()
{
    // Common case: just pop free element and return.
    if (free_element)
    {
        void* mem = free_element;
        free_element = free_element->next_element;
        return mem;
    }

    // Rare case when we're out of free elements.
    // Create new block.
    Block* new_block = static_cast<Block*>(malloc(sizeof(Block)));
    new_block->mem = malloc(type_size * num_block_elements);
    new_block->next = head;
    head = new_block;

    // Push all but one of the new block's elements to the free stack.
    char* mem = new_block->mem;
    for (int j=1; j < num_block_elements; ++j)
    {
        void* ptr = mem + j*type_size;
        FreeElement* element = static_cast<FreeElement*>(ptr);
        element->next_element = free_element;
        free_element = element;
    }
    return mem;
}

void FixedAllocator::deallocate(void* mem)
{
    // Just push a free element to the stack.
    FreeElement* element = static_cast<FreeElement*>(mem);
    element->next_element = free_element;
    free_element = element;
}

Anda mungkin ingin memiliki beberapa mesin string yang diinternir (tetapi string harus tidak berubah, jadi gunakan const std::string-s). Anda bisa menginginkan beberapa simbol . Anda mungkin melihat ke dalam smart pointer (misalnya std :: shared_ptr ). Atau bahkan std :: string_view di C ++ 17.

Sekali waktu dalam konstruksi compiler kami menggunakan sesuatu yang disebut kursi data (bukan bank data, terjemahan bahasa Jerman sehari-hari untuk DB). Ini hanya membuat hash untuk sebuah string dan menggunakannya untuk alokasi. Jadi string apa pun bukanlah sepotong memori pada heap / stack tetapi kode hash ke kursi data ini. Anda bisa menggantinya Stringdengan kelas semacam itu. Perlu beberapa kode ulang, meskipun. Dan tentu saja ini hanya dapat digunakan untuk string r / o.

Perhatikan bagaimana alokasi memori dan memori aktual yang digunakan keduanya berhubungan dengan kinerja yang buruk:

Biaya sebenarnya mengalokasikan memori, tentu saja, sangat tinggi. Karenanya std :: string mungkin sudah menggunakan alokasi di tempat untuk string kecil, dan karena itu jumlah alokasi aktual mungkin lebih rendah daripada yang mungkin Anda asumsikan pertama kali. Jika ukuran buffer ini tidak cukup besar, maka Anda mungkin terinspirasi oleh misalnya kelas string Facebook ( https://github.com/facebook/folly/blob/master/folly/FBString.h ) yang menggunakan 23 karakter internal sebelum mengalokasikan.

Biaya menggunakan banyak memori juga perlu diperhatikan. Ini mungkin pelaku terbesar: Anda mungkin memiliki banyak RAM di mesin Anda, namun, ukuran cache masih cukup kecil sehingga akan merusak kinerja ketika mengakses memori yang belum di-cache. Anda dapat membaca tentang ini di sini: https://en.wikipedia.org/wiki/Locality_of_reference

Alih-alih membuat operasi string lebih cepat, pendekatan lain adalah mengurangi jumlah operasi string. Apakah mungkin untuk mengganti string dengan enum, misalnya?

Pendekatan lain yang mungkin berguna digunakan dalam Kakao: Ada kasus di mana Anda memiliki ratusan atau ribuan kamus, semua dengan kunci yang sama. Jadi mereka membiarkan Anda membuat objek yang merupakan set kunci kamus, dan ada konstruktor kamus yang mengambil objek seperti argumen. Kamus berperilaku sama seperti kamus lainnya, tetapi ketika Anda menambahkan pasangan kunci / nilai dengan kunci di set kunci, kunci tersebut tidak diduplikasi tetapi hanya pointer ke kunci di set kunci yang disimpan. Jadi ribuan kamus ini hanya membutuhkan satu salinan dari setiap string kunci dalam set itu.