Использование boost::iostreams::mapped_file_source с std::multimap

У меня достаточно большой объем данных для анализа - каждый файл составляет около 5 гигабайт. Каждый файл имеет следующий формат:

xxxxx yyyyy

И ключ, и значение могут повторяться, но ключи сортируются в порядке возрастания. Я пытаюсь использовать файл с отображенной памятью для этой цели, а затем найти необходимые ключи и работать с ними. Вот что я написал:

if (data_file != "")
{
    clock_start = clock();
    data_file_mapped.open(data_file);

    data_multimap = (std::multimap<double, unsigned int> *)data_file_mapped.data();
    if (data_multimap != NULL)
    {
        std::multimap<double, unsigned int>::iterator it = data_multimap->find(keys_to_find[4]);
        if (it != data_multimap->end())
        {
            std::cout << "Element found.";
            for (std::multimap<double, unsigned int>::iterator it = data_multimap->lower_bound(keys_to_find[4]); it != data_multimap->upper_bound(keys_to_find[5]); ++it)
            {
                std::cout << it->second;
            }
            std::cout << "\n";
            clock_end = clock();

            std::cout << "Time taken to read in the file: " << (clock_end - clock_start)/CLOCKS_PER_SEC << "\n";
        }
        else
            std::cerr << "Element not found at all" << "\n";
    }
    else
        std::cerr << "Nope - no data received."<< "\n";
}

По сути, мне нужно найти диапазоны ключей и вытащить эти куски для работы. Я получаю segfault в первый раз, когда я пытаюсь использовать метод на мультикарте. Например, когда find метод называется. Я попробовал upper_bound, lower_bound и другие методы тоже, и все еще получают segfault.

Это то, что gdb дает мне:

Program received signal SIGSEGV, Segmentation fault.
_M_lower_bound (this=<optimized out>, __k=<optimized out>, __y=<optimized out>, __x=0xa31202030303833) at /usr/include/c++/4.9.2/bits/stl_tree.h:1261
1261            if (!_M_impl._M_key_compare(_S_key(__x), __k))

Может кто-нибудь указать, что я делаю не так? Мне удалось найти только упрощенные примеры для файлов с отображенной памятью - пока ничего подобного. Благодарю.

РЕДАКТИРОВАТЬ: Больше информации:

Файл, который я описал выше, в основном представляет собой текстовый файл с двумя столбцами, который нейронный симулятор дает мне в качестве результата моих симуляций. Это просто так:

$ du -hsc 201501271755.e.ras 
4.9G    201501271755.e.ras
4.9G    total
$ head 201501271755.e.ras 
0.013800  0
0.013800  1
0.013800  10
0.013800  11
0.013800  12
0.013800  13
0.013800  14
0.013800  15
0.013800  16
0.013800  17

Первый столбец - время, второй столбец - нейроны, которые сработали в это время - (это растровый файл с всплеском времени). Фактически, выходные данные - это файл, подобный этому, для каждого ранга MPI, который используется для запуска симуляции. Различные файлы были объединены в этот мастер-файл с помощью sort -g -m, Более подробная информация о формате файла находится здесь: http://www.fzenke.net/auryn/doku.php?id=manual:ras

Чтобы вычислить частоту срабатывания и другие метрики нейрона, установленного в определенные моменты моделирования, мне нужно - найти время в файле, извлечь фрагмент между [время -1, время] и запустить некоторые метрики и т. Д. этот кусок. Этот файл довольно мал, и я ожидаю, что его размер увеличится немного, так как мои симуляции становятся все более сложными и работают в течение более длительных периодов времени. Вот почему я начал изучать файлы, отображенные в памяти. Я надеюсь, что это несколько разъясняет постановку проблемы. Мне нужно только прочитать выходной файл, чтобы обработать информацию, которую он содержит. Мне не нужно изменять этот файл вообще.

Для обработки данных я снова буду использовать несколько потоков, но, поскольку все мои операции на карте предназначены только для чтения, я не ожидаю, что там возникнут проблемы.

Источник

2 ответа

Решение

Вы пытаетесь делать вещи, которые вы на самом деле не понимаете:) Нет проблем.

Мультикарты не располагаются последовательно в памяти. (Это контейнеры на основе узлов, но я отвлекся). Фактически, даже если бы они были, шансы были бы невелики, что компоновка соответствовала бы расположению ввода текста.

Есть два основных способа сделать эту работу:

  1. Продолжайте использовать multimap но используйте пользовательский распределитель (чтобы все выделения выполнялись в области отображаемой памяти). Это "самый хороший" с точки зрения C++ высокого уровня, но / вам нужно будет перейти на двоичный формат вашего файла.

    Если вы можете, это то, что я бы предложил. Boost Container + Boost Interprocess имеют все необходимое, чтобы сделать это относительно безболезненно.

  2. Вы пишете пользовательский контейнер "абстракция", который работает непосредственно с отображаемыми данными. Вы могли бы либо

    • распознать пару "xxxx yyyy" откуда угодно (конец строки?) или
    • построить индекс всей строки начинается в файле.

    Используя их, вы можете разработать интегратор (Boost Iterator iterator_facade) которые вы можете использовать для реализации операций более высокого уровня (lower_bound, upper_bound а также equal_range).

    После того, как они у вас есть, у вас есть все возможности для запроса этой карты памяти как базы данных значений ключей только для чтения.

    К сожалению, этот вид представления памяти был бы крайне плох для производительности, если вы также хотите поддерживать операции с мутированием (insert, remove).

Если у вас есть пример файла, я мог бы продемонстрировать любой из описанных подходов.

Обновить

Быстрые образцы:

  1. С boost::interprocess вы можете (очень) просто определить желаемую мультикарту:

    namespace shared {
    namespace bc = boost::container;

    template <typename T> using allocator = bip::allocator<T, bip::managed_mapped_file::segment_manager>;
    template <typename K, typename V>
        using multi_map = bc::flat_multimap<
            K, V, std::less<K>, 
            allocator<typename bc::flat_multimap<K, V>::value_type> >;
}

    Заметки:

    • Я выбрал flatmap (flat_multimapна самом деле) потому что он, вероятно, более эффективен при хранении и намного более сопоставим со вторым подходом (приведенным ниже);

      Обратите внимание, что этот выбор влияет на стабильность итераторов / ссылок и довольно сильно благоприятствует операциям только для чтения. Если вам нужна стабильность итератора и / или множество операций мутации, используйте обычные map (или для очень больших объемов hash_map) вместо плоских вариаций.

    • Я выбрал managed_mapped_file сегмент для этой демонстрации (так что вы получите постоянство). Демонстрация показывает, как 10G редко выделяется заранее, но на диске используется только фактически выделенное пространство. Вы могли бы также использовать managed_shared_memory,

      Если у вас есть двоичное постоянство, вы можете вообще отказаться от текстового файла данных.

    • Я анализирую текстовые данные в shared::multi_map<double, unsigned> из mapped_file_source используя Boost Spirit. Реализация полностью универсальная.

    • Там нет необходимости писать iterator классы, start_of_line(), end_of_line(), lower_bound(), upper_bound(), equal_range() или любой из них, так как они уже являются стандартными в multi_map интерфейс, так что все, что нам нужно, это написать main:

    Жить на Колиру

    #define NDEBUG
#undef DEBUG
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
#include <boost/container/flat_map.hpp>
#include <boost/interprocess/managed_mapped_file.hpp>
#include <boost/spirit/include/qi.hpp>
#include <iomanip>

namespace bip = boost::interprocess;
namespace qi = boost::spirit::qi;

namespace shared {
    namespace bc = boost::container;

    template <typename T> using allocator = bip::allocator<T, bip::managed_mapped_file::segment_manager>;
    template <typename K, typename V>
        using multi_map = bc::flat_multimap<
            K, V, std::less<K>, 
            allocator<typename bc::flat_multimap<K, V>::value_type> >;
}

#include <iostream>

bip::managed_mapped_file msm(bip::open_or_create, "lookup.bin", 10ul<<30);

template <typename K, typename V>
shared::multi_map<K,V>& get_or_load(const char* fname) {
    using Map = shared::multi_map<K, V>;
    Map* lookup = msm.find_or_construct<Map>("lookup")(msm.get_segment_manager());

    if (lookup->empty()) { 
        // only read input file if not already loaded
        boost::iostreams::mapped_file_source input(fname);
        auto f(input.data()), l(f + input.size());

        bool ok = qi::phrase_parse(f, l,
                (qi::auto_ >> qi::auto_) % qi::eol >> *qi::eol, 
                qi::blank, *lookup);

        if (!ok || (f!=l))
            throw std::runtime_error("Error during parsing at position #" + std::to_string(f - input.data()));
    }

    return *lookup;
}

int main() {
    // parse text file into shared memory binary representation
    auto const& lookup = get_or_load<double, unsigned int>("input.txt");
    auto const e = lookup.end();

    for(auto&& line : lookup)
    {
        std::cout << line.first << "\t" << line.second << "\n";

        auto er = lookup.equal_range(line.first);

        if (er.first  != e) std::cout << " lower: " << er.first->first  << "\t" << er.first->second  << "\n";
        if (er.second != e) std::cout << " upper: " << er.second->first << "\t" << er.second->second << "\n";
    }
}

  2. Я реализовал это точно так, как я описал:

    • простой контейнер над сырым const char* регион нанесен на карту;
    • с помощью boost::iterator_facade сделать итератор, который разбирает текст по разыменованию;
    • для печати строк ввода я использую boost::string_ref - что позволяет избежать динамического выделения для копирования строк.

    • парсинг выполняется с помощью Spirit Qi:

      if (!qi::phrase_parse(
            b, _data.end,
            qi::auto_ >> qi::auto_ >> qi::eoi,
            qi::space,
            _data.key, _data.value))

      Ци был выбран для скорости и универсальности: вы можете выбрать Key а также Value типы во время создания экземпляра:

      text_multi_lookup<double, unsigned int> tml(map.data(), map.data() + map.size());

    • Я реализовал lower_bound, upper_bound а также equal_range функции-члены, использующие преимущества основного смежного хранилища. Хотя "линия" iterator не произвольный доступ, а двунаправленный, мы все еще можем перейти к mid_point такого диапазона итератора, потому что мы можем получить start_of_line от любого const char* в основной картированный регион. Это делает бинарный поиск эффективным.

    Обратите внимание, что это решение анализирует строки при разыменовании iterator, Это может быть неэффективно, если одни и те же строки разыменовываются много раз.

    Но для нечастых поисков или поисков, которые не типичны для одной и той же области входных данных, это примерно настолько эффективно, насколько это возможно (выполнение только минимально необходимого анализа и O(log n) бинарный поиск), все время полностью обходя начальное время загрузки, сопоставляя файл (нет доступа означает, что ничего не нужно загружать).

    Live On Coliru (включая данные испытаний)

    #define NDEBUG
#undef DEBUG
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/utility/string_ref.hpp>
#include <boost/optional.hpp>
#include <boost/spirit/include/qi.hpp>
#include <thread>
#include <iomanip>

namespace io = boost::iostreams;
namespace qi = boost::spirit::qi;

template <typename Key, typename Value> 
struct text_multi_lookup {
    text_multi_lookup(char const* begin, char const* end)
        : _map_begin(begin), 
          _map_end(end)
    {
    }

  private:
    friend struct iterator;
    enum : char { nl = '\n' };

    using rawit = char const*;
    rawit _map_begin, _map_end;

    rawit start_of_line(rawit it) const {
        while (it > _map_begin) if (*--it == nl) return it+1;
        assert(it == _map_begin);
        return it;
    }

    rawit end_of_line(rawit it) const {
        while (it < _map_end) if (*it++ == nl) return it;
        assert(it == _map_end);
        return it;
    }

  public:
    struct value_type final {
        rawit beg, end;
        Key   key;
        Value value;

        boost::string_ref str() const { return { beg, size_t(end-beg) }; }
    };

    struct iterator : boost::iterator_facade<iterator, boost::string_ref, boost::bidirectional_traversal_tag, value_type> {

        iterator(text_multi_lookup const& d, rawit it) : _region(&d), _data { it, nullptr, Key{}, Value{} } { 
            assert(_data.beg == _region->start_of_line(_data.beg));
        }

      private:
        friend text_multi_lookup;

        text_multi_lookup const* _region;
        value_type mutable _data;

        void ensure_parsed() const {
            if (!_data.end) 
            {
                assert(_data.beg == _region->start_of_line(_data.beg));
                auto b = _data.beg;
                _data.end = _region->end_of_line(_data.beg);

                if (!qi::phrase_parse(
                            b, _data.end,
                            qi::auto_ >> qi::auto_ >> qi::eoi,
                            qi::space,
                            _data.key, _data.value)) 
                {
                    std::cerr << "Problem in: " << std::string(_data.beg, _data.end) 
                              << "at:         " << std::setw(_data.end-_data.beg) << std::right << std::string(_data.beg,_data.end);
                    assert(false);
                }
            }
        }

        static iterator mid_point(iterator const& a, iterator const& b) {
            assert(a._region == b._region);
            return { *a._region, a._region->start_of_line(a._data.beg + (b._data.beg -a._data.beg)/2) };
        }

      public:
        value_type const& dereference() const {
            ensure_parsed();
            return _data;
        }

        bool equal(iterator const& o) const {
            return (_region == o._region) && (_data.beg == o._data.beg);
        }

        void increment() {
            _data = { _region->end_of_line(_data.beg), nullptr, Key{}, Value{} };
            assert(_data.beg == _region->start_of_line(_data.beg));
        }
    };

    using const_iterator = iterator;

    const_iterator begin()  const { return { *this, _map_begin }; }
    const_iterator end()    const { return { *this, _map_end   }; }
    const_iterator cbegin() const { return { *this, _map_begin }; }
    const_iterator cend()   const { return { *this, _map_end   }; }

    template <typename CompatibleKey>
    const_iterator lower_bound(CompatibleKey const& key) const {
        auto f(begin()), l(end());
        while (f!=l) {
            auto m = iterator::mid_point(f,l);

            if (m->key < key) {
                f = m;
                ++f;
            }
            else {
                l = m;
            }
        }
        return f;
    }

    template <typename CompatibleKey>
    const_iterator upper_bound(CompatibleKey const& key) const {
        return upper_bound(key, begin());
    }

  private:
    template <typename CompatibleKey>
    const_iterator upper_bound(CompatibleKey const& key, const_iterator f) const {
        auto l(end());
        while (f!=l) {
            auto m = iterator::mid_point(f,l);

            if (key < m->key) {
                l = m;
            }
            else {
                f = m;
                ++f;
            }
        }
        return f;
    }

  public:
    template <typename CompatibleKey>
    std::pair<const_iterator, const_iterator> equal_range(CompatibleKey const& key) const {
        auto lb = lower_bound(key);
        return { lb, upper_bound(key, lb) };
    }

};

#include <iostream>

int main() {
    io::mapped_file_source map("input.txt");
    text_multi_lookup<double, unsigned int> tml(map.data(), map.data() + map.size());

    auto const e = tml.end();

    for(auto&& line : tml)
    {
        std::cout << line.str();

        auto er = tml.equal_range(line.key);

        if (er.first  != e) std::cout << " lower: " << er.first->str();
        if (er.second != e) std::cout << " upper: " << er.second->str();
    }
}

    Для любопытных: вот разборка. Обратите внимание, как все алгоритмические вещи встроены прямо в main: http://paste.ubuntu.com/9946135/

Источник

data_multimap = (std::multimap<double, unsigned int> *)data_file_mapped.data();Насколько я могу судить по документации Boost, вы неправильно поняли эту функцию, что приведение не будет работать, вам нужно заполнить мультикарту символом *, предоставленным data()

Я редактирую, чтобы добавить немного более подробный контент, например, после сопоставления, вы можете сделать

std::getline(data_file_mapped, oneString);

И после этого доставьте содержимое в строку (вы можете использовать поток строк для этой задачи) и заполните свою мультикарту.

Повторите процесс до конца файла.

Источник
Другие вопросы по тегам