Как улучшить производительность улучшенных поисков interval_map

Question

Я использую boost::icl::interval_map сопоставить диапазоны байтов с набором строк. Карта загружается из (отсортированного) файла на диске, и затем я выполняю поиск, используя приведенный ниже код.

Проблема в том, что поиск действительно медленный.

В моем тесте я вставил 66425 диапазонов в карту. Я профилировал код и в основном> 99,9% времени тратится на различные функции Boost (нет особой медленной функции, много времени распределено по многим функциям).

Что можно сделать, чтобы сделать это быстрее?

Является ли мое дерево неуравновешенным (как я узнаю? Как я могу восстановить его?)

Является ли использование set проблемой?

Является ли вычисление пересечения карты и окна проблемой? (Хотя это то, что мне нужно, поэтому я не вижу, как еще это сделать).

using namespace std;
typedef set<string> objects;
typedef boost::icl::interval_map<uint64_t, objects> ranges;
void
find_range (const ranges *map, uint64_t start, uint64_t end,
            void (*f) (uint64_t start, uint64_t end, const char *object,
                       void *opaque),
            void *opaque)
{
  boost::icl::interval<uint64_t>::type window;
  window = boost::icl::interval<uint64_t>::right_open (start, end);

  ranges r = *map & window;

  ranges::iterator iter = r.begin ();
  while (iter != r.end ()) {
    boost::icl::interval<uint64_t>::type range = iter->first;
    uint64_t start = range.lower ();
    uint64_t end = range.upper ();

    objects obj_set = iter->second;
    objects::iterator iter2 = obj_set.begin ();
    while (iter2 != obj_set.end ()) {
      f (start, end, iter2->c_str (), opaque);
      iter2++;
    }
    iter++;
  }
}

Первые несколько записей профиля:

  %   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
  9.77      0.13     0.13 21866814     0.01           boost::icl::interval_bounds::interval_bounds(unsigned char)
  6.02      0.21     0.08  9132134     0.01           boost::icl::interval_traits<boost::icl::discrete_interval<unsigned long, std::less> >::lower(boost::icl::discrete_interval<unsigned long, std::less> const&)
  6.02      0.29     0.08  6004967     0.01           boost::enable_if<boost::icl::is_discrete_interval<boost::icl::discrete_interval<unsigned long, std::less> >, bool>::type boost::icl::is_empty<boost::icl::discrete_interval<unsigned long, std::less> >(boost::icl::discrete_interval<unsigned long, std::less> const&)
  5.26      0.36     0.07 21210093     0.00           boost::icl::discrete_interval<unsigned long, std::less>::bounds() const
  5.26      0.43     0.07 11964109     0.01           std::less<unsigned long>::operator()(unsigned long const&, unsigned long const&) const
  4.51      0.49     0.06 35761849     0.00           std::_Rb_tree<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::_Identity<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::basic_string<char, std::char_traits<char>, std::allocator<char> > > >::_S_left(std::_Rb_tree_node_base const*)
  4.51      0.55     0.06 12009934     0.00           boost::icl::operator==(boost::icl::interval_bounds, boost::icl::interval_bounds)
  3.76      0.60     0.05 12078493     0.00           boost::icl::discrete_interval<unsigned long, std::less>::upper() const
  3.76      0.65     0.05 12077959     0.00           boost::enable_if<boost::icl::is_interval<boost::icl::discrete_interval<unsigned long, std::less> >, boost::icl::interval_traits<boost::icl::discrete_interval<unsigned long, std::less> >::domain_type>::type boost::icl::upper<boost::icl::discrete_interval<unsigned long, std::less> >(boost::icl::discrete_interval<unsigned long, std::less> const&)
  3.76      0.70     0.05  8837475     0.01           boost::icl::interval_bounds::bits() const
  3.76      0.75     0.05  6004967     0.01           boost::enable_if<boost::icl::is_interval<boost::icl::discrete_interval<unsigned long, std::less> >, bool>::type boost::icl::domain_less_equal<boost::icl::discrete_interval<unsigned long, std::less> >(boost::icl::interval_traits<boost::icl::discrete_interval<unsigned long, std::less> >::domain_type const&, boost::icl::interval_traits<boost::icl::discrete_interval<unsigned long, std::less> >::domain_type const&)
  3.01      0.79     0.04  5891650     0.01           boost::icl::is_right_closed(boost::icl::interval_bounds)

Набор данных: http://oirase.annexia.org/tmp/bmap.txt
Полный код: http://git.annexia.org/?p=virt-bmap.git;a=tree

Answer 1

В этом ответе я представляю три оптимизации:

1. замена объектов std::set от boost::container::flat_set для улучшения местоположения (и вероятных затрат на перераспределение, так как большинство наборов объектов <4 элемента)

   ОБНОВЛЕНИЕ В моей окончательной версии ниже, просто заменив boost::container::flat_map вернуться с std::set ухудшается производительность всего find_range в ~2 раза и find_range_ex в ~4 раза в моей тестовой системе

2. замена идентификатора объекта std::string от string_atom (что технически char const* но логически уникальный). Этот метод похож на интернированные строки в различных реализациях виртуальных машин (например, Java/.NET).

   ПРИМЕЧАНИЕ: текущая реализация make_atom чрезвычайно упрощен и никогда не освобождает атомы. Возможно, вы захотите поддержать строки в деке, использовать Boost Flyweights, распределитель пула или какую-то их комбинацию, чтобы сделать ее умнее. Однако, требуется ли это, зависит от ваших случаев использования

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

   _ ОБНОВЛЕНИЕ При применении только этой оптимизации в отдельности, ускорение уже 26 ~30x. Обратите внимание, что использование памяти примерно в два раза составляет ~20 МБ по сравнению с включением всех трех оптимизаций_

Объем и эффективность данных

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

Источник на Колиру

Parsed ok
Histogram of 66425 input lines
d: 3367
f: 20613
p: 21222
v: 21223
ranges size:            6442450944
ranges iterative size:  21223
Min object set:         1.000000
Max object set:         234.000000
Average object set:     3.129859
Min interval width:     1024.000000
Max interval width:     2526265344.000000
Average interval width: 296.445177k
First:                  [0,1048576)
Last:                   [3916185600,6442450944)
String atoms:           23904 unique in 66425 total
Atom efficiency:        35.986451%

Как видите, наборы обычно составляют ~3 предмета, и многие из них дублируются.

С использованием make_atom метод именования объектов с boost::flat_set уменьшено выделение памяти с ~15GiB до ~ 10Gib.

Эта оптимизация также уменьшает сравнение строк до сравнения указателей для вставки набора и стратегии Combiner interval_map поэтому для больших наборов данных это может значительно ускорить работу.

Эффективность запроса

Производительность запросов действительно сильно ограничена частичной копией ввода.

Не копируйте, вместо этого просмотрите перекрывающийся диапазон, просто заменив:

  const ranges r = *map & window;
  ranges::const_iterator iter = r.begin ();
  while (iter != r.end ()) {

с

  auto r = map->equal_range(window);
  ranges::const_iterator iter = r.first;
  while (iter != r.second) {

В моей системе выполнение 10000 одинаковых рандомизированных запросов с обеими версиями приводит к ускорению в 32 раза:

10000 'random' OLD lookups resulted in 156729884 callbacks in 29148ms
10000 'random' NEW lookups resulted in 156729884 callbacks in 897ms

real    0m31.715s
user    0m31.664s
sys 0m0.012s

Во время выполнения теперь преобладает анализ / статистика. Полный код теста здесь: на Coliru

#define BOOST_RESULT_OF_USE_DECTYPE
#define BOOST_SPIRIT_USE_PHOENIX_V3

/* virt-bmap examiner plugin
 * Copyright (C) 2014 Red Hat Inc.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <assert.h>

#include <boost/icl/interval.hpp>
#include <boost/icl/interval_set.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/container/flat_set.hpp>

using namespace std;

/* Maps intervals (uint64_t, uint64_t) to a set of strings, where each
 * string represents an object that covers that range.
 */

static size_t atoms_requested = 0;
static size_t atoms_unique_created = 0;

using string_atom = const char*;
string_atom make_atom(std::string&& s)
{
    static std::set<std::string> s_atoms;
    atoms_requested += 1;

    auto it = s_atoms.find(s);
    if (it != s_atoms.end())
        return it->c_str();

    atoms_unique_created += 1;
    return s_atoms.insert(std::move(s)).first->c_str();
}

typedef boost::container::flat_set<string_atom> objects;
typedef boost::icl::interval_map<uint64_t, objects> ranges;

ranges*
new_ranges (void)
{
  return new ranges ();
}

void
free_ranges (ranges *mapv)
{
  ranges *map = (ranges *) mapv;
  delete map;
}

extern "C" void
insert_range (void *mapv, uint64_t start, uint64_t end, const char *object)
{
  ranges *map = (ranges *) mapv;
  objects obj_set;
  obj_set.insert (obj_set.end(), object);
  map->add (std::make_pair (boost::icl::interval<uint64_t>::right_open (start, end), // SEHE added std::
                       obj_set));
}

extern "C" void
iter_range (void *mapv, void (*f) (uint64_t start, uint64_t end, const char *object, void *opaque), void *opaque)
{
  ranges *map = (ranges *) mapv;
  ranges::iterator iter = map->begin ();
  while (iter != map->end ()) {
    boost::icl::interval<uint64_t>::type range = iter->first;
    uint64_t start = range.lower ();
    uint64_t end = range.upper ();

    objects obj_set = iter->second;
    objects::iterator iter2 = obj_set.begin ();
    while (iter2 != obj_set.end ()) {
      f (start, end, *iter2/*->c_str ()*/, opaque); // SEHE
      iter2++;
    }
    iter++;
  }
}

extern "C" void
find_range (void const *mapv, uint64_t start, uint64_t end, void (*f) (uint64_t start, uint64_t end, const char *object, void *opaque), void *opaque)
{
  const ranges *map = (const ranges *) mapv;

  boost::icl::interval<uint64_t>::type window;
  window = boost::icl::interval<uint64_t>::right_open (start, end);

  const ranges r = *map & window;

  ranges::const_iterator iter = r.begin ();
  while (iter != r.end ()) {
    boost::icl::interval<uint64_t>::type range = iter->first;
    uint64_t start = range.lower ();
    uint64_t end = range.upper ();

    objects obj_set = iter->second;
    objects::iterator iter2 = obj_set.begin ();
    while (iter2 != obj_set.end ()) {
      f (start, end, *iter2/*->c_str ()*/, opaque); // SEHE
      iter2++;
    }
    iter++;
  }
}

extern "C" void
find_range_ex (void const *mapv, uint64_t start, uint64_t end, void (*f) (uint64_t start, uint64_t end, const char *object, void *opaque), void *opaque)
{
  const ranges *map = (const ranges *) mapv;

  boost::icl::interval<uint64_t>::type window;
  window = boost::icl::interval<uint64_t>::right_open (start, end);

#if 0
  const ranges r = *map & window;
  ranges::const_iterator iter = r.begin ();
  while (iter != r.end ()) {
#else
  auto r = map->equal_range(window);
  ranges::const_iterator iter = r.first;
  while (iter != r.second) {
#endif

    boost::icl::interval<uint64_t>::type range = iter->first;
    uint64_t start = range.lower ();
    uint64_t end = range.upper ();

    objects obj_set = iter->second;
    objects::iterator iter2 = obj_set.begin ();
    while (iter2 != obj_set.end ()) {
      f (start, end, *iter2/*->c_str ()*/, opaque); // SEHE
      iter2++;
    }
    iter++;
  }
}

#include <memory>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics.hpp>
#include <fstream>
#include <chrono>

std::map<char, size_t> histo;

bool insert_line_of_input(ranges& bmap_data, uint64_t b, uint64_t e, char type, std::string& object) {
    if (!object.empty())
        histo[type]++;
    //std::cout << std::hex << b << " " << e << " " << type << " " << object << "\n";

#if 0
    object.insert(object.begin(), ':');
    object.insert(object.begin(), type);
#endif
    insert_range(&bmap_data, b, e, make_atom(std::move(object)));
    return true;
}

std::vector<std::pair<uint64_t, uint64_t> > generate_test_queries(ranges const& bmap_data, size_t n) {
    std::vector<std::pair<uint64_t, uint64_t> > queries;
    queries.reserve(n);

    for (size_t i = 0; i < n; ++i)
    {
        auto start = (static_cast<uint64_t>(rand()) * rand()) % bmap_data.size();
        auto end   = start + rand();

        queries.emplace_back(start,end);
    }

    return queries;
}

ranges read_mapfile(const char* fname) {
    std::ifstream ifs(fname);
    boost::spirit::istream_iterator f(ifs >> std::noskipws), l;

    ranges bmap_data;

    namespace phx = boost::phoenix;
    using namespace boost::spirit::qi;
    uint_parser<uint64_t, 16> offset;
    if (!phrase_parse(f,l,
                ("1 " >> offset >> offset >> char_("pvdf") >> as_string[lexeme[+graph] >> attr('/') >> lexeme[*~char_("\r\n")]]) 
                [ _pass = phx::bind(insert_line_of_input, phx::ref(bmap_data), _1, _2, _3, _4) ] % eol >> *eol, 
                blank))
    {
        exit(255);
    } else
    {
        std::cout << "Parsed ok\n";
    }

    if (f!=l)
        std::cout << "Warning: remaining input '" << std::string(f,l) << "\n";

    return bmap_data;
}

void report_statistics(ranges const& bmap_data) {
    size_t total = 0;
    for (auto e : histo) total += e.second;

    std::cout << "Histogram of " << total << " input lines\n";

    for (auto e : histo)
        std::cout << e.first << ": " << e.second << "\n";

    namespace ba = boost::accumulators;
    ba::accumulator_set<double, ba::stats<ba::tag::mean, ba::tag::max, ba::tag::min> > 
        object_sets, interval_widths;

    for (auto const& r : bmap_data)
    {
        auto width = r.first.upper() - r.first.lower();
        assert(width % 1024 == 0);

        interval_widths(width);
        object_sets(r.second.size());
    }

    std::cout << std::fixed;
    std::cout << "ranges size:            " << bmap_data.size()                 << "\n";
    std::cout << "ranges iterative size:  " << bmap_data.iterative_size()       << "\n";

    std::cout << "Min object set:         " << ba::min(object_sets)             << "\n" ;
    std::cout << "Max object set:         " << ba::max(object_sets)             << "\n" ;
    std::cout << "Average object set:     " << ba::mean(object_sets)            << "\n" ;
    std::cout << "Min interval width:     " << ba::min(interval_widths)         << "\n" ;
    std::cout << "Max interval width:     " << ba::max(interval_widths)         << "\n" ;
    std::cout << "Average interval width: " << ba::mean(interval_widths)/1024.0 << "k\n" ;
    std::cout << "First:                  " << bmap_data.begin()->first         << "\n" ;
    std::cout << "Last:                   " << bmap_data.rbegin()->first        << "\n" ;

    std::cout << "String atoms:           " << atoms_unique_created << " unique in " << atoms_requested << " total\n";
    std::cout << "Atom efficiency:        " << (atoms_unique_created*100.0/atoms_requested) << "%\n";
}

void perform_comparative_benchmarks(ranges const& bmap_data, size_t number_of_queries) {
    srand(42);
    auto const queries = generate_test_queries(bmap_data, number_of_queries);

    using hrc = std::chrono::high_resolution_clock;
    {
        auto start = hrc::now();
        size_t callbacks = 0;

        for (auto const& q: queries)
        {
            find_range(&bmap_data, q.first, q.second, 
                    [](uint64_t start, uint64_t end, const char *object, void *opaque) {
                    ++(*static_cast<size_t*>(opaque));
                    }, &callbacks);
        }
        std::cout << number_of_queries << " 'random' OLD lookups resulted in " << callbacks 
                  << " callbacks in " << std::chrono::duration_cast<std::chrono::milliseconds>((hrc::now()-start)).count() << "ms\n";
    }

    {
        auto start = hrc::now();
        size_t callbacks = 0;

        for (auto const& q: queries)
        {
            find_range_ex(&bmap_data, q.first, q.second, 
                    [](uint64_t start, uint64_t end, const char *object, void *opaque) {
                    ++(*static_cast<size_t*>(opaque));
                    }, &callbacks);
        }
        std::cout << number_of_queries << " 'random' NEW lookups resulted in " << callbacks 
                  << " callbacks in " << std::chrono::duration_cast<std::chrono::milliseconds>((hrc::now()-start)).count() << "ms\n";
    }
}

int main() {
    auto bmap = read_mapfile("bmap.txt");

    report_statistics(bmap);

    perform_comparative_benchmarks(bmap, 1000);

#if 0 // to dump ranges to console
    for (auto const& r : bmap)
    {
        std::cout << r.first << "\t" << r.second.size() << "\t";
        std::copy(r.second.begin(), r.second.end(), std::ostream_iterator<std::string>(std::cout, "\t"));
        std::cout << "\n";
    }
#endif
}

Answer 2

У вас есть все шансы против вас с этим кодом.

1. Использование памяти.
   С диапазонами 66425 вы проходите через кеш L1, а с включенным набором строк вы также получаете L2D и даже превышаете L3. Это означает, что у вас часто будет задержка в 50-200 циклов ЦП для каждого доступа к данным, а выполнение по неработоспособности будет охватывать всего ~32 цикла, а это означает, что ЦП будет фактически все время останавливаться. Это значительно уменьшается, если доступ ко всей памяти осуществляется последовательно через аппаратные средства предварительной выборки.

2. Указатель гонится по карте.
   Карты и наборы обычно реализуются как rb_tree с указателями. (интервал_карта может отличаться?). Чтобы еще больше усугубить проблему, доступ к указателям обеспечит отсутствие последовательного доступа к данным, что означает, что вы столкнетесь с высокой задержкой.

3. Вызов указателя функции / виртуальной функции. Удивительно, но это не отображается в топ-12, если вы не используете больше функций интервала внутри f, Позже, когда вы решите другие проблемы, вы можете увидеть, что каждый вызов этой функции будет вводить задержку X циклов для каждого вызова, где X - длина конвейера ЦП.

Если вы используете perf для получения данных о производительности, пожалуйста, добавьте результат запуска с perf stat -d, Это должно показать проблемы, упомянутые выше, с большим количеством кеш-памяти и неактивным процессором.

Использование set<string> плохо, потому что его указатель гонится, вы должны использовать vector<string> вместо этого вам нужно будет разобраться в этом самостоятельно. Это должно ускорить доступ в f, но не смягчает другие проблемы.

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