Discussion :

[Flodelarab]

Bonjour

Avez-vous des astuces pour allouer 4294967296 booléens, en C++ ? Sur une machine sous Linux, sans préparation spéciale, il veut bien 429496729 booléens (400 millions au lieu de 4 milliards), mais si je rajoute un chiffre 6, 5, 4 ou 0, il plante. 4194967290 le fait déjà planter.

Je ne suis pas fan d'allouer un octet entier pour n'utiliser qu'un seul bit, mais si je multiplexe les données, je devrai me coltiner le démultiplexage.

Quelle solution cela vous inspire-t-il ?

Merci de votre attention.

[Jamatronic]

Si tu as besoin d'autant de booléens, il est insensé de réserver un octet entier pour chacun.

Tu sais comment diviser par huit la taille de données dont tu as besoin, et le faire fait partie des compétences DE BASE d'un développeur.

Pas d'excuse...


D'un autre côté, on serait curieux de savoir pourquoi tu aurais besoin de stocker tout cela en RAM, à un instant donné et en un seul bloc...

Est-ce que le problème ne se situerait pas en amont ?

[jo_link_noir]

Il y a aussi std::bitset qui fait le taff.

[AbsoluteLogic]

Il y a aussi std::bitset qui fait le taff.

Malheureusement, bitset n'accepte que des tailles fixes à la compilation, et de fait, j'imagine que la mémoire est allouée dans la pile, dont la taille est très limitée (j'ai testé avec les 4 Gbits, et ça segfault). Pour de si grandes tailles, on a besoin d'allocations dynamiques. La page https://en.cppreference.com/w/cpp/utility/bitset donne justement un lien vers une implémentation dynamique fournie par Boost.

Mais si on veut éviter l'usage de Boost, comme l'a dit Jamatronic, l'implémentation se fait rapidement soit-même, en utilisant l'orienté objet pour éviter d'avoir à faire soit-même le "démultiplexage". Voici donc une implémentation que j'ai fait vite fait pour tester si les 4 GigaBits sont bien supportés (et ils le sont) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
#include <cstdint>
 
class bitset {
public:
    bitset(size_t n) :
        _data((n + 7) / 8)
    { }
    class bit_handle {
    public:
        bit_handle(uint8_t& byte, uint8_t mask) :
            _byte(byte),
            _mask(mask)
        { }
        bit_handle& operator=(bool bit) {
            if (bit)
                _byte |= _mask;
            else
                _byte &= ~_mask;
            return *this;
        }
        operator bool() const {
            return _byte & _mask;
        }
    private:
        uint8_t& _byte;
        uint8_t _mask;
    };
    bit_handle operator[](size_t i) {
        return bit_handle(
            _data[i / 8],
            1u << (i % 8)
        );
    }
private:
    std::vector<uint8_t> _data;
};
 
#define SIZE 4294967296
 
int main(int, char**) {
    bitset bits(SIZE);
    bits[SIZE / 2] = true;
    std::cout << bits[SIZE / 2] << std::endl;
    bits[SIZE / 2] = false;
    std::cout << bits[SIZE / 2] << std::endl;
    /*for (int i=0; i < SIZE; ++i)
        std::cout << (bits[i] ? 1 : 0);
    std::cout << std::endl;*/
    return 0;
}

[droggo]

Bonjour,

Comme Jamatronic, je me demande à quoi peuvent servir autant de booléens.

[WhiteCrow]

Hello,
4Go ? Linux ? Le premier truc qui me vient à l'esprit est : mmap.
Mais bon … avec des bit-tricks tu passes à 500Mo.

[baragouine]

Bonjour,

Pourquoi pas simplement utiliser un std::vector, d'après ce que j'avais compris std::vector<bool> stocke la valeur du booléen sur un bit, je me trompe ?
En tout cas j'arrive à allouer les 4294967296 de booléens.

[AbsoluteLogic]

Pourquoi pas simplement utiliser un std::vector, d'après ce que j'avais compris std::vector<bool> stocke la valeur du booléen sur un bit, je me trompe ?
En tout cas j'arrive à allouer les 4294967296 de booléens.

Oups, effectivement, ça marche aussi chez moi
Du coup, il est vrai qu'il parle d'une éventuelle optimisation de std::vector<bool> dans la doc : https://en.cppreference.com/w/cpp/container/vector_bool, de sorte que "each element occupies a single bit instead of sizeof(bool) bytes".
Par contre, c'est "implementation defined", l'optimisation n'est pas assurée sur tous les systèmes (sur tous les systèmes Linux ?). Mais si on ne cherche pas cette assurance et que ça fonctionne chez nous, c'est sûr que ça fait très bien l'affaire.

[jo_link_noir]

vector<bool> est critiqué sur son fonctionnement à base de type proxy qui ne permet pas d'avoir de référence sur un bool (ce qui peut amener à certaine surprise). De plus, il est assez lent sur certaines opérations et n'offre pas non plus de fonction de traitement de bit. Il est vraiment pensé uniquement pour réduire l'espace alloué.

libc++ (clang), libstdc++ (gcc) et msvc l'implémentent comme un tableau de respectivement std::allocator_traits<Alloc>::size_type (std::size_t par défaut), unsigned long et unsigned int.

[dalfab]

Bonjour,

Le problème ne semble pas être la taille, puisqu'un std::vector<bool> ne fait que 0,5GO. Mais ça peut être le nombre d'éléments qui devrait tenir dans un std::size_t. Sur un système 32 bits le max dans un std::size_t risque d'être 4294967295u et il risque alors d'en manquer 1.

[Guesset]

Bonjour,

Il est possible d'écrire directement (sauf erreur) des expressions comme :

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
void SetBit(int32_t i)   {   t[i >> 3] |=   1 << (i & 7);    } 
void ResetBit(int32_t i) {   t[i >> 3] &= ~(1 << (i & 7));   } 
bool GetBit(int32_t i)   {   return t[i >> 3] & (1 << (i & 7)); } // ou (t[i >> 3] & (1 << (i & 7))) != 0 pour faire propre

L'usage de l'assembleur et des instructions bts, btr serait plus efficace encore. L'habillage en méthodes dans un objet en rendrait l'usage (relativement) transparent.

Salutations

[Flodelarab]

Merci à tous pour votre participation.

bitset<4294967296> fonctionne.
vector<bool>(4294967296) fonctionne.

Dans les deux cas, c'est long. Mais fonctionnel. Savez-vous si on gagne en vitesse en utilisant un itérateur plutôt que l'opérateur [] ? Si oui, lequel ?

Mon système est 64 bits. Donc en prenant ses précautions (long et non int), 4294967296 n'est pas un problème.

Encore merci. Je note la question résolue.