Traitement d'un fichier dict avec des mots ASCII de longueur variable.

constexpr int MAXLINE = 1024 * 1024 * 10; // total number of words, one word per line.

Objectif: lire l'intégralité du fichier en mémoire, et pouvoir accéder à chaque mot par index.

Je veux accéder rapidement à chaque mot par index. Nous pouvons utiliser un tableau à deux dimensions pour y parvenir; cependant un MAXLENGTH doit être défini, sans mentionner que MAXLENGTH n'est pas connu à l'avance.

constexpr int MAXLENGTH= 1024; // since I do not have the maximum length of the word
char* aray = new char[MAXLINE * MAXLENGTH];

Le code ci-dessus ne sera PAS compatible avec la mémoire si la plupart des mots sont plus courts que MAXLENGTH; et aussi certains mots peuvent être plus longs que MAXLENGTH, provoquant des erreurs.

Pour un objet de longueur variable, je pense que vector pourrait être le mieux adapté à ce problème. Donc, je propose un vecteur de vecteur pour les stocker.

vector<vector<char>> array(MAXLINE);

Cela semble si prometteur, jusqu'à ce que je réalise que ce n'est pas le cas.

J'ai testé les deux approches sur un fichier dict avec des mots à 4 caractères ASCII MAXLINE (ici tous les mots sont des mots à 4 caractères)

constexpr int MAXLINE = 1024 * 1024 * 10;

Si je nouvel opérateur le tableau à stocker, (ici MAXLENGTH est juste 4)

char* aray = new char[MAXLINE * 4]; 

La consommation de mémoire est d'environ 40 Mo. Cependant, si j'essaye d'utiliser le vecteur pour stocker (j'ai changé le char en int32_t pour juste quatre caractères)

vector<vector<int32_t>> array(MAXLINE);

Vous pouvez également utiliser le vecteur char et réserver de l'espace pour 4 caractères.

vector<vector<char>> array(MAXLINE);
for (auto & c : array) {
    c.reserve(4);
}

La consommation de mémoire grimpe à environ 720 Mo (mode de débogage), 280 Mo (mode de libération), ce qui est si inattendu et quelqu'un peut-il me donner quelques explications pour clarifier pourquoi.

Observation: la taille du vecteur dépend de l'implémentation et si vous compilez en mode débogage.

Comme sur mon système

sizeof(vector<int32_t>) = 16  //  debug mode

Et

sizeof(vector<int32_t>) = 12  // release mode

En mode débogage, la consommation de mémoire est de 720MB pour vector<vector<int32_t>> array(MAXLINE);, alors que le vecteur réel ne prend que sizeof(vector<int32_t>) * MAXLINE = 16 * 10MB = 160 MB

En mode version, la consommation de mémoire est 280MB, mais la valeur attendue est sizeof(vector<int32_t>) * MAXLINE = 12 * 10MB = 120 MB

Quelqu'un peut-il expliquer la grande différence entre la consommation de mémoire réelle et la consommation attendue (calculée à partir de la taille des sous-vecteurs).

Appréciez, et bonne année!

2
phy nju 30 déc. 2017 à 22:44

5 réponses

Meilleure réponse

Pour votre cas:

alors, cela signifie-t-il que le vecteur de vecteurs n'est pas une bonne idée pour stocker de petits objets? -

Généralement non. Un sub-vector imbriqué n'est pas une bonne solution pour stocker une cargaison de petites séquences de taille variable. Vous ne voulez pas représenter un maillage indexé qui autorise des polygones variables (triangles, quads, pentagones, hexagones, n-gons) en utilisant une instance std::vector séparée par polygone, par exemple, sinon vous aurez tendance à faire exploser l'utilisation de la mémoire et avoir une solution vraiment lente: lente car il y a une allocation de tas impliquée pour chaque polygone effrayant, et explosive en mémoire car le vecteur préalloue souvent de la mémoire pour les éléments en plus de stocker la taille et la capacité de manière souvent plus grande que nécessaire si vous avez une cargaison de séquences minuscules.

vector est une excellente structure de données pour stocker un million de choses de manière contiguë, mais pas si excellente pour stocker un million de vecteurs minuscules.

Dans de tels cas, même une liste indexée à un seul lien peut mieux fonctionner avec les indices pointant vers un vecteur plus grand, fonctionnant beaucoup plus rapidement et parfois même utilisant moins de mémoire malgré la surcharge de liaison 32 bits, comme ceci:

enter image description here

Cela dit, pour votre cas particulier avec une grande séquence à accès aléatoire de chaînes de longueur variable, voici ce que je recommande:

// stores the starting index of each null-terminated string
std::vector<int> string_start;

// stores the characters for *all* the strings in one single vector.
std::vector<char> strings;

Cela réduira la surcharge à plus près de 32 bits par entrée de chaîne (en supposant que int est 32 bits) et vous n'aurez plus besoin d'une allocation de tas distincte pour chaque entrée de chaîne que vous ajoutez.

Une fois que vous avez fini de tout lire, vous pouvez minimiser l'utilisation de la mémoire avec un compactage pour tronquer le tableau (en éliminant toute capacité de réserve excessive):

// Compact memory use using copy-and-swap.
vector<int>(string_start).swap(string_start);
vector<char>(strings).swap(strings);

Maintenant, pour récupérer la nième chaîne, vous pouvez faire ceci:

const char* str = strings.data() + string_start[n];

Si vous avez également besoin de capacités de recherche, vous pouvez en fait stocker une cargaison de chaînes et les rechercher rapidement (y compris des choses comme les recherches basées sur les préfixes) en stockant moins de mémoire que même la solution ci-dessus ne prendrait en utilisant un trie compressé. C'est un peu plus une solution complexe, mais cela pourrait valoir la peine si votre logiciel tourne autour de dictionnaires de chaînes et de recherche à travers eux et que vous pourrez peut-être trouver une bibliothèque tierce qui en fournit déjà une pour vous.

std :: string

Juste pour être complet, j'ai pensé ajouter une mention de std::string. Les implémentations récentes sont souvent optimisées pour les petites chaînes en stockant un tampon à l'avance qui n'est pas alloué séparément en tas. Cependant, dans votre cas, cela peut conduire à une utilisation encore plus explosive de la mémoire car cela rend sizeof(string) plus gros, ce qui peut consommer beaucoup plus de mémoire que nécessaire pour des chaînes vraiment courtes. Cela rend std::string plus utile cependant pour les chaînes temporaires, ce qui vous permet d'obtenir quelque chose qui fonctionne parfaitement si vous récupérez std::string à partir de ce grand vecteur de caractères à la demande comme ceci:

std::string str = strings.data() + string_start[n];

... par opposition à:

const char* str = strings.data() + string_start[n];

Cela dit, le grand vecteur de caractères ferait de bien meilleures performances et en termes de mémoire pour stocker toutes les chaînes. De manière générale, les conteneurs généralisés de toute sorte ont tendance à cesser de fonctionner si bien si vous souhaitez stocker des millions de conteneurs minuscules.

Le principal problème conceptuel est que lorsque le désir porte sur un million de séquences de taille variable, la nature de taille variable de l'exigence combinée à la nature généralisée du conteneur impliquera que vous avez un million de gestionnaires de mémoire minuscules, tous devant potentiellement allouer sur le tas ou, sinon, allouer plus de données que nécessaire, en gardant une trace de sa taille / capacité si elle est contiguë, et ainsi de suite. Inévitablement, un million + de gestionnaires de leur propre mémoire deviennent assez chers.

Donc, dans ces cas, il est souvent avantageux de renoncer à la commodité d'un conteneur "complet et indépendant" et d'utiliser à la place un tampon géant, ou un conteneur géant stockant les données de l'élément comme dans le cas de vector<char> strings, avec un autre gros conteneur qui l'indexe ou pointe vers lui, comme dans le cas de vector<int> string_start. Avec cela, vous pouvez représenter le million de chaînes analogiques de longueur variable en utilisant simplement deux grands conteneurs au lieu d'un million de petits.

suppression de la nième chaîne

Votre cas ne semble pas que vous deviez supprimer une entrée de chaîne, il suffit de la charger et d'y accéder, mais si vous avez besoin de supprimer une chaîne, cela peut devenir délicat lorsque toutes les chaînes et tous les index de leurs positions de départ sont stockés dans deux géants tampons.

Ici, je recommande, si vous voulez faire cela, de ne pas supprimer la chaîne immédiatement du tampon. Au lieu de cela, vous pouvez simplement faire ceci:

// Indicate that the nth string has been removed.
string_start[n] = -1;

Lors de l'itération sur les chaînes disponibles, ignorez simplement celles où string_start[n] est -1. Ensuite, de temps en temps pour réduire l'utilisation de la mémoire après la suppression d'un certain nombre de chaînes, procédez comme suit:

void compact_buffers(vector<char>& strings, vector<int>& string_start)
{
    // Create new buffers to hold the new data excluding removed strings.
    vector<char> new_strings;
    vector<int> new_string_start;
    new_strings.reserve(strings.size());
    new_string_start.reserve(string_start.size());

    // Store a write position into the 'new_strings' buffer.
    int write_pos = 0;

    // Copy strings to new buffers, skipping over removed ones.
    for (int start: string_start)
    {
        // If the string has not been removed:
        if (start != -1)
        {
            // Fetch the string from the old buffer.
            const char* str = strings.data() + start;

            // Fetch the size of the string including the null terminator.            
            const size_t len = strlen(str) + 1;

            // Insert the string to the new buffer.
            new_strings.insert(new_strings.end(), str, str + len);

            // Append the current write position to the starting positions
            // of the new strings.
            new_string_start.push_back(write_pos);

            // Increment the write position by the string size.
            write_pos += static_cast<int>(len);
        }
    }

    // Swap compacted new buffers with old ones.
    vector<char>(new_strings).swap(strings);
    vector<int>(new_string_start).swap(string_start);
}

Vous pouvez appeler périodiquement ce qui précède pour compacter l'utilisation de la mémoire après avoir supprimé un certain nombre de chaînes.

Séquence de chaînes

Voici un code rassemblant tous ces éléments que vous pouvez librement utiliser et modifier comme vous le souhaitez.

////////////////////////////////////////////////////////
// StringSequence.hpp:
////////////////////////////////////////////////////////
#ifndef STRING_SEQUENCE_HPP
#define STRING_SEQUENCE_HPP

#include <vector>

/// Stores a sequence of strings.
class StringSequence
{
public:
    /// Creates a new sequence of strings.
    StringSequence();

    /// Inserts a new string to the back of the sequence.
    void insert(const char str[]);

    /// Inserts a new string to the back of the sequence.
    void insert(size_t len, const char str[]);

    /// Removes the nth string.
    void erase(size_t n);

    /// @return The nth string.
    const char* operator[](size_t n) const;

    /// @return The range of indexable strings.
    size_t range() const;

    /// @return True if the nth index is occupied by a string.
    bool occupied(size_t n) const;

    /// Compacts the memory use of the sequence.
    void compact();

    /// Swaps the contents of this sequence with the other.
    void swap(StringSequence& other);

private:
    std::vector<char> buffer;
    std::vector<size_t> start;
    size_t write_pos;
    size_t num_removed;
};

#endif


////////////////////////////////////////////////////////
// StringSequence.cpp:
////////////////////////////////////////////////////////
#include "StringSequence.hpp"
#include <cassert>

StringSequence::StringSequence(): write_pos(1), num_removed(0)
{
    // Reserve the front of the buffer for empty strings.
    // We'll point removed strings here.
    buffer.push_back('\0');
}

void StringSequence::insert(const char str[])
{
    assert(str && "Trying to insert a null string!");
    insert(strlen(str), str);
}

void StringSequence::insert(size_t len, const char str[])
{
    const size_t str_size = len + 1;
    buffer.insert(buffer.end(), str, str + str_size);
    start.push_back(write_pos);
    write_pos += str_size;
}

void StringSequence::erase(size_t n)
{
    assert(occupied(n) && "The nth string has already been removed!");
    start[n] = 0;
    ++num_removed;
}

const char* StringSequence::operator[](size_t n) const
{
    return &buffer[0] + start[n];
}

size_t StringSequence::range() const
{
    return start.size();
}

bool StringSequence::occupied(size_t n) const
{
    return start[n] != 0;
}

void StringSequence::compact()
{
    if (num_removed > 0)
    {
        // Create a new sequence excluding removed strings.
        StringSequence new_seq;
        new_seq.buffer.reserve(buffer.size());
        new_seq.start.reserve(start.size());
        for (size_t j=0; j < range(); ++j)
        {
            const char* str = (*this)[j];
            if (occupied(j))
                new_seq.insert(str);
        }

        // Swap the new sequence with this one.s
        new_seq.swap(*this);
    }

    // Remove excess capacity.
    if (buffer.capacity() > buffer.size())
        std::vector<char>(buffer).swap(buffer);
    if (start.capacity() > start.size())
        std::vector<size_t>(start).swap(start);
}

void StringSequence::swap(StringSequence& other)
{
    buffer.swap(other.buffer);
    start.swap(other.start);
    std::swap(write_pos, other.write_pos);
    std::swap(num_removed, other.num_removed);
}

////////////////////////////////////////////////////////
// Quick demo:
////////////////////////////////////////////////////////
#include "StringSequence.hpp"
#include <iostream>

using namespace std;

int main()
{
    StringSequence seq;
    seq.insert("foo");
    seq.insert("bar");
    seq.insert("baz");
    seq.insert("hello");
    seq.insert("world");
    seq.erase(2);
    seq.erase(3);

    cout << "Before compaction:" << endl;
    for (size_t j=0; j < seq.range(); ++j)
    {
        if (seq.occupied(j))
            cout << j << ": " << seq[j] << endl;
    }
    cout << endl;

    cout << "After compaction:" << endl;
    seq.compact();
    for (size_t j=0; j < seq.range(); ++j)
    {
        if (seq.occupied(j))
            cout << j << ": " << seq[j] << endl;
    }
    cout << endl;
}

Production:

Before compaction:
0: foo
1: bar
4: world

After compaction:
0: foo
1: bar
2: world

Je n'ai pas pris la peine de le rendre conforme aux normes (trop paresseux et le résultat n'est pas nécessairement beaucoup plus utile pour cette situation particulière) mais j'espère que ce n'est pas un besoin important ici.

3
Dragon Energy 6 janv. 2018 à 11:35

La taille du vecteur dépend de l'implémentation et si vous compilez en mode débogage. Normalement, c'est au moins la taille de certains pointeurs internes (début, fin de stockage et fin de mémoire réservée). Sur mon système Linux, le sizeof(vector<int32_t>) est de 24 octets (probablement 3 x 8 octets pour chaque pointeur). Cela signifie que pour vos 10 000 000 articles, il devrait être d'au moins env. 240 Mo.

2
StPiere 30 déc. 2017 à 20:06

Comme d'autres l'ont souligné, le sizeof(vector<int32_t>) est assez grand pour produire de tels nombres lorsque vous initialisez des instances 41943040.

Ce que vous voudrez peut-être, c'est une implémentation de dictionnaire cpp - une carte: https://www.moderncplusplus.com/map/

Il sera toujours grand (encore plus grand), mais moins gênant stylistiquement. Maintenant, si la mémoire est un problème, ne l'utilisez pas.

sizeof(std::map<std::string, std::string>) == 48 on my system.

1
Mindaugas Bernatavičius 30 déc. 2017 à 20:05

Vous créez des 41943040 instances de vector<int32_t>, stockées dans un autre vector. Je suis sûr que 720 Mo est une quantité raisonnable de mémoire pour les membres de données internes de toutes les instances plus le tampon du vecteur externe.

1
Vittorio Romeo 30 déc. 2017 à 19:47

De combien de mémoire un vector<uint32_t> d'une longueur de 1 a-t-il besoin? Voici quelques estimations:

  1. 4 octets pour le uint32_t. C'est ce à quoi vous vous attendiez.

  2. Californie. 8/16 octets de surcharge d'allocation de mémoire dynamique. Les gens oublient toujours que l'implémentation new doit se souvenir de la taille de l'allocation, ainsi que de quelques données de gestion supplémentaires. En règle générale, vous pouvez vous attendre à une surcharge de deux pointeurs, soit 8 octets sur un système 32 bits, 16 octets sur un système 64 bits.

  3. Californie. 4/12 octets pour le remplissage d'alignement. Les allocations dynamiques doivent être alignées pour tout type de données. La quantité requise dépend du processeur, les exigences d'alignement typiques sont de 8 octets (entièrement aligné double) ou 16 octets (pour les instructions vectorielles du processeur). Ainsi, votre implémentation new ajoutera 4/12 octets de remplissage aux 4 octets de charge utile.

  4. Californie. 12/24 octets pour l'objet vector<> lui-même. L'objet vector<> doit stocker trois éléments de la taille du pointeur: le pointeur vers la mémoire dynamique, sa taille et le nombre d'objets réellement utilisés. Multipliez par la taille du pointeur 4/8, et vous obtenez sa taille de.

En résumé, j'arrive à 4 + 8/16 + 4/12 + 12/24 = 28/48 octets qui sont utilisés pour stocker 4 octets.


D'après vos chiffres, je suppose que vous compilez en mode 32 bits et que votre alignement maximum est de 8 octets. En mode débogage, votre implémentation new semble ajouter une surcharge d'allocation supplémentaire pour détecter les erreurs de programmation courantes.

2
cmaster - reinstate monica 6 janv. 2018 à 12:24