vector<bool> serialisieren

Erhard Henkes schrieb:

Alle geraden Zahlen würde ich gar nicht in die Bitmaske aufnehmen.

Super Idee!

Genausowenig die Zahlen, die durch 3 teilbar sind.

Der Index für n ist dann n-n/2-n/3+n/6.

Und dann natürlich auch für 5, 7, 11 und 13, musst von Hand schauen, wann aufhören.

Finnegan

Hi nochmal!

Da ich mich schon länger mal mit Memory Mapped IO beschäftigen wollte, habe ich mir zum Feierabend mal die Zeit genommen und einen Prototypen für das von mir vorgeschlagene Bitset implementiert. Wer möchte, kann den Code gerne verwenden/erweitern/reviewen/sich inspirieren lassen oder was auch immer. War ne nette Übung um mal was mit Memory Mapping abseits von GPU-Hardware herumzuspielen

Das Interface orientiert sich größtenteils an std::bitset , und die Klasse sollte bis auf Details nahezu als Drop-In Replacement einsetzbar sein, wenn man mal ganz furchtbar viele Flags benötigen sollte :p.
Natürlich stecken wahrscheinlich noch eine Reihe Fehler drin - extrem grob falsch wird es allerdings hoffentlich nicht sein

Auch wenn ich nur einen simplen Zeittest gemacht habe, scheint die Klasse im linearen Schreiben/Lesen durchaus mit einem std::vector<bool> im Arbeitsspeicher mithalten zu können (siehe Testcode), obwohl die Datenstruktur in eine Datei ausgelagert ist. Der Testcode erstellt die Datenstruktur mit jeweils 10 Milliarden Bits, schreibt alle davon linear und liest sie anschliessend ebenfalls linear. Auf meiner Mühle - Windows 8.1 - kompiliert mit Visual C++ 2013 mit Optimierungen im Release-Modus sieht das ganze etwa so aus:

MemoryMappedBitset:     92.6532 Sekunden (Code siehe unten).
std::vector<bool>:      98.7792 Sekunden (1).
std::bitset (im Heap): 115.5720 Sekunden (2).

1: http://pastebin.com/R3sDkhb6
2: http://pastebin.com/egdsRTtM

Ob sich so eine dateigestützte Datenstruktur wirklich lohnt, sollte man allerdings individuell mit realistischen Zugriffsmustern austesten. Gut möglich, dass das Teil bei mehr "Random Access" noch deutlich absackt. Einen Vorteil hat sie allerdings:
Man muss sich keinen Kopf um den physichen RAM und das nachladen/wegschreiben der Daten machen - Das Testprogramm lümmelt hier bei mir mit 300KiB im Arbeitsspeicher rum - genutzt wird de facto nur der freie Systemspeicher, den das OS grad entbehren kann.

Gruss,
Finnegan

P.S.: Ja, Kommentare sind rar, ich hoffe der Code ist simpel genug dass sich die Funktionsweise aus dem Code erschließt (siehe auch Boost-Doku zu mapped_file ). Mit dem create -Parameter des Konstruktors wird angegeben, ob eine neue Datei erstellt (überschreibt existierende) oder eine vorhandene Datei verwendet werden soll.

#include <cstdint>
#include <iostream>
#include <algorithm>
#include <chrono>
#include <boost/filesystem.hpp>
#include <boost/iostreams/device/mapped_file.hpp>

class MemoryMappedBitset
{
    using mapped_file = boost::iostreams::mapped_file;
    using mapped_file_params = boost::iostreams::mapped_file_params;
    public:
        class reference
        {
            friend class MemoryMappedBitset;
            public:
                void flip();

                reference& operator=(bool value);
                reference& operator=(const reference& other);
                operator bool() const;
                bool operator~() const;

            private:
                MemoryMappedBitset& bitset;
                std::size_t         pos;

                reference(MemoryMappedBitset& bitset, std::size_t pos);
        };

        MemoryMappedBitset(const MemoryMappedBitset&) = delete;
        MemoryMappedBitset& operator=(const MemoryMappedBitset&) = delete;

        MemoryMappedBitset(std::string file_name);
        MemoryMappedBitset(std::string file_name, std::size_t number_of_bits, bool create = false);
        ~MemoryMappedBitset();

        const std::string& getFileName() const;
        std::size_t size() const;
        bool test(std::size_t pos);
        void set(std::size_t pos, bool value = true);
        void reset(std::size_t pos);
        void flip(std::size_t pos);

        bool operator[](std::size_t pos) const;
        reference operator[](std::size_t pos);

    private:
        mapped_file_params  params;
        mapped_file         file;
        std::size_t         number_of_bits;
        unsigned char*      data;

        bool testUnchecked(std::size_t pos) const;
        void setUnchecked(std::size_t pos, bool value);
        void flipUnchecked(std::size_t pos);
};

MemoryMappedBitset::reference::reference(MemoryMappedBitset& bitset, std::size_t pos)
: bitset(bitset), pos(pos)
{
}

void MemoryMappedBitset::reference::flip()
{
    bitset.flipUnchecked(pos);
}

MemoryMappedBitset::reference& MemoryMappedBitset::reference::operator=(bool value)
{
    bitset.setUnchecked(pos, value);
    return *this;
}

MemoryMappedBitset::reference& MemoryMappedBitset::reference::operator=(const reference& other)
{
    bitset.setUnchecked(pos, other);
    return *this;
}

MemoryMappedBitset::reference::operator bool() const
{
    return bitset.testUnchecked(pos);
}

bool MemoryMappedBitset::reference::operator~() const
{
    return !bitset.testUnchecked(pos);
}

MemoryMappedBitset::MemoryMappedBitset(std::string file_name)
: MemoryMappedBitset(std::move(file_name), 0, false)
{
}

MemoryMappedBitset::MemoryMappedBitset(std::string file_name, std::size_t number_of_bits, bool create)
: data(nullptr)
{
    params.path = std::move(file_name);
    params.mode = std::ios_base::binary | std::ios_base::in | std::ios_base::out;

    // Size of the memory map in bytes.
    std::size_t map_size = number_of_bits / 8;
    // One extra byte for additional bits.
    if (number_of_bits % 8 > 0)
        map_size += 1;
    // Map size must be multiple of (OS) page alignment.
    std::size_t non_aligned = map_size % mapped_file::alignment();
    if (non_aligned > 0)
        map_size += mapped_file::alignment() - non_aligned;

    // Create new (overwrite) or re-use file.
    if (create)
    {
        params.new_file_size = map_size;
        params.length = map_size;
    }
    else
    {
        // Map requested number of bits unless file is not large enough.
        map_size = std::min(static_cast<std::uintmax_t>(map_size), boost::filesystem::file_size(params.path));
        // Ensure that map size is still multiple of (OS) page alignment 
        // (if file size was not) and not larger than file size.
        non_aligned = map_size % mapped_file::alignment();
        if (non_aligned > 0)
             map_size -= non_aligned;

        params.new_file_size = 0;
        params.length = map_size;
    }

    // Set actual number of bits. This is at least the requested number of bits
    // unless we re-used an existing file which was not large enough.
    MemoryMappedBitset::number_of_bits = map_size * 8;

    file.open(params);
    data = reinterpret_cast<unsigned char*>(file.data());
    assert(data != nullptr);
}

MemoryMappedBitset::~MemoryMappedBitset()
{
    if (file.is_open())
        file.close();
}

const std::string& MemoryMappedBitset::getFileName() const
{
    return params.path;
}

std::size_t MemoryMappedBitset::size() const
{
    return number_of_bits;
}

bool MemoryMappedBitset::test(std::size_t pos)
{
    if (pos >= size())
        throw std::out_of_range("Bit position out of range.");

    return testUnchecked(pos);
}

void MemoryMappedBitset::set(std::size_t pos, bool value)
{
    if (pos >= size())
        throw std::out_of_range("Bit position out of range.");

    setUnchecked(pos, value);
}

void MemoryMappedBitset::reset(std::size_t pos)
{
    set(pos, false);
}

void MemoryMappedBitset::flip(std::size_t pos)
{
    if (pos >= size())
        throw std::out_of_range("Bit position out of range.");

    flipUnchecked(pos);
}

bool MemoryMappedBitset::operator[](std::size_t pos) const
{
    return testUnchecked(pos);
}

MemoryMappedBitset::reference MemoryMappedBitset::operator[](std::size_t pos)
{
    return reference(*this, pos);
}

bool MemoryMappedBitset::testUnchecked(std::size_t pos) const
{
    return (data[pos / 8] & (1 << (pos % 8))) != 0;
}

void MemoryMappedBitset::setUnchecked(std::size_t pos, bool value)
{
    std::size_t index = pos / 8;
    std::size_t bit = pos % 8;
    if (value)
        data[index] |= 1 << bit;
    else
        data[index] &= ~(1 << bit);
}

void MemoryMappedBitset::flipUnchecked(std::size_t pos)
{
    data[pos / 8] ^= 1 << (pos % 8);
}

int main()
{
    const std::size_t number_of_bits = 10000000000;
    const std::uint32_t test_pattern = 0xaaaaaaaa;
    const std::uint32_t use_pattern_bits = 7;

    auto start_time = std::chrono::high_resolution_clock::now();

    try
    {
        std::cout << "Erstelle Bitset mit " << number_of_bits << " Bits ..." << std::endl;
        MemoryMappedBitset mbs("bitset.dat", number_of_bits, true);

        std::cout << "Schreibe Bits ...";
        for (std::size_t i = 0; i < number_of_bits; ++i)
        {
            mbs[i] = (test_pattern & (1 << (i % use_pattern_bits))) != 0;
            if (i % (number_of_bits / 100) == 0)
                std::cout << ".";
        }

        std::cout << "\nLese Bits ...";
        std::uint32_t value = 0;
        for (std::size_t i = 0; i < number_of_bits; ++i)
        {
            std::uint32_t shift = (i % use_pattern_bits);
            value |= mbs[i] << shift;
            if (shift == use_pattern_bits - 1)
            {
                assert(value == (test_pattern & (1 << use_pattern_bits) - 1));
                value = 0;
            }
            if (i % (number_of_bits / 100) == 0)
                std::cout << ".";
        }

        std::cout << "\nfertig!" << std::endl;

    }
    catch (const std::exception& e)
    {
        std::cout << "ERROR: " << e.what() << std::endl;    	
    }

    std::cout << std::chrono::duration<double>(
        std::chrono::high_resolution_clock::now() - start_time).count() << " Sekunden." << std::endl;
}

Code benötigt Boost und muss gegen boost_filesystem , boost_system und boost_iostreams gelinkt werden.

Finnegan schrieb:

char*               data;

Ich würde das auf unsigned char ändern, auch wenn du dann einmal casten musst.

Finnegan

ubbot schrieb:

würde das auf unsigned char ändern, auch wenn du dann einmal casten musst.

Gern. Die mag ich auch lieber wenn ich mit Bits hantiere. Ist halt das was man von Boost bekommt...

volkard

andrepeat schrieb:

Erhard Henkes schrieb:

Alle geraden Zahlen würde ich gar nicht in die Bitmaske aufnehmen.

Super Idee!

Genausowenig die Zahlen, die durch 3 teilbar sind.

Der Index für n ist dann n-n/2-n/3+n/6.

Und dann natürlich auch für 5, 7, 11 und 13, musst von Hand schauen, wann aufhören.

Da gibt es, finde ich, ein natürliches Optimum: 2,3und5 nehmen.
Rechnet man eine Zahl modulo 30, gibt es 8 mögliche Divisionsreste, die Primzahlen erlauben. Und 8 Bit hat ein Byte, wodurch der Zugriff ganz geschmeidig bleibt.

TGGC

First rule of IOB: You are wrong.

vector&lt;bool&gt; serialisieren

vector<bool> serialisieren