Насколько сильно «если» заявления влияют на производительность?

c++ algorithm performance if-statement search

176 просмотра

4 ответа

Есть несколько IPTables с различными размерами (например, 255 или 16384 или 512000 !!). Каждая запись каждой таблицы содержит уникальный IP-адрес (в шестнадцатеричном формате) и некоторые другие значения. Общее количество IP-адресов составляет 8 миллионов. Все IP-адреса всех IPTables отсортированы

Нам нужно искать IPTable 300 000 раз в секунду. Наш текущий алгоритм поиска IP выглядит следующим образом:

// 10 <number of IPTables <20
//_rangeCount = number of IPTables 
s_EntryItem* searchIPTable(const uint32_t & ip) {
        for (int i = 0; i < _rangeCount; i++) {
            if (ip > _ipTable[i].start && ip < _ipTable[i].end) {
                int index = ip - _ipTable[i].start;
                    return (_ipTable[i].p_entry + index);
                }
            }
            return NULL;
        }

Как видно, в худшем случае число сравнений для данного IP-адреса равно _rangeCount * 2, а число проверок оператора if - _rangeCount.

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

Итак, количество сравнений для нахождения IP-адреса равно log (8000000), что равно ~ 23.

Вопрос 1:

Как можно видеть, существует небольшой разрыв между количеством сравнений, необходимых для двух алгоритмов (_rangeCount против 23), но в первом методе есть некоторые операторы «если», которые могут повлиять на производительность. Если вы хотите запустить первый алгоритм 10 раз, очевидно, что первый алгоритм имеет лучшую производительность, но я знаю, как запустить два алгоритма 3000 000 раз! какая у тебя идея?

Вопрос 2:

Существует ли более эффективный алгоритм или решение для поиска IP-адресов?

Автор: m.r226 Источник Размещён: 08.11.2019 11:23

Ответы (4)


7 плюса

Решение

Я задал любопытство, я написал тестовую программу (ниже) и запустил ее на своем MacBook.

Предполагается, что наивное решение, основанное на std::unordered_map(время поиска == постоянное время), способно выполнять поиск в таблице адресов ip4 с 8 миллионами записей 5,6 миллиона раз в секунду.

Это легко превосходит требования.

обновление: отвечая моим критикам, я увеличил тестовое пространство до требуемых 8-минутных IP-адресов. Я также увеличил размер теста до 100 миллионов поисковых запросов, 20% из которых будут хитом.

С таким большим тестом мы можем ясно увидеть преимущества производительности при использовании unordered_map по сравнению с упорядоченной картой (поиск по логарифмическому времени).

Все параметры теста настраиваются.

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <random>
#include <tuple>
#include <iomanip>
#include <utility>

namespace detail
{
    template<class T>
    struct has_reserve
    {
        template<class U> static auto test(U*p) -> decltype(p->reserve(std::declval<std::size_t>()), void(), std::true_type());
        template<class U> static auto test(...) -> decltype(std::false_type());

        using type = decltype(test<T>((T*)0));
    };
}

template<class T>
using has_reserve = typename detail::has_reserve<T>::type;


using namespace std::literals;

struct data_associated_with_ip {};
using ip_address = std::uint32_t;

using candidate_vector = std::vector<ip_address>;

static constexpr std::size_t search_space_size = 8'000'000;
static constexpr std::size_t size_of_test = 100'000'000;

std::vector<ip_address> make_random_ip_set(std::size_t size)
{
    std::unordered_set<ip_address> results;
    results.reserve(size);

    std::random_device rd;
    std::default_random_engine eng(rd());
    auto dist = std::uniform_int_distribution<ip_address>(0, 0xffffffff);
    while (results.size() < size)
    {
        auto candidate = dist(eng);
        results.emplace(candidate);
    }

    return { std::begin(results), std::end(results) };
}

template<class T, std::enable_if_t<not has_reserve<T>::value> * = nullptr>
void maybe_reserve(T& container, std::size_t size)
{
    // nop
}

template<class T, std::enable_if_t<has_reserve<T>::value> * = nullptr>
decltype(auto) maybe_reserve(T& container, std::size_t size)
{
    return container.reserve(size);
}

template<class MapType>
void build_ip_map(MapType& result, candidate_vector const& chosen)
{
    maybe_reserve(result, chosen.size());
    result.clear();

    for (auto& ip : chosen)
    {
        result.emplace(ip, data_associated_with_ip{});
    }
}

// build a vector of candidates to try against our map
// some percentage of the time we will select a candidate that we know is in the map
candidate_vector build_candidates(candidate_vector const& known)
{
    std::random_device rd;
    std::default_random_engine eng(rd());
    auto ip_dist = std::uniform_int_distribution<ip_address>(0, 0xffffffff);
    auto select_known = std::uniform_int_distribution<std::size_t>(0, known.size() - 1);
    auto chance = std::uniform_real_distribution<double>(0, 1);
    static constexpr double probability_of_hit = 0.2;

    candidate_vector result;
    result.reserve(size_of_test);
    std::generate_n(std::back_inserter(result), size_of_test, [&]
                    {
                        if (chance(eng) < probability_of_hit)
                        {
                            return known[select_known(eng)];
                        }
                        else
                        {
                            return ip_dist(eng);
                        }
                    });

    return result;
}


int main()
{

    candidate_vector known_candidates = make_random_ip_set(search_space_size);
    candidate_vector random_candidates = build_candidates(known_candidates);


    auto run_test = [&known_candidates, &random_candidates]
    (auto const& search_space)
    {

        std::size_t hits = 0;
        auto start_time = std::chrono::high_resolution_clock::now();
        for (auto& candidate : random_candidates)
        {
            auto ifind = search_space.find(candidate);
            if (ifind != std::end(search_space))
            {
                ++hits;
            }
        }
        auto stop_time = std::chrono::high_resolution_clock::now();
        using fns = std::chrono::duration<long double, std::chrono::nanoseconds::period>;
        using fs = std::chrono::duration<long double, std::chrono::seconds::period>;
        auto interval = fns(stop_time - start_time);
        auto time_per_hit = interval / random_candidates.size();
        auto hits_per_sec = fs(1.0) / time_per_hit;

        std::cout << "ip addresses in table: " << search_space.size() << std::endl;
        std::cout << "ip addresses searched: " << random_candidates.size() << std::endl;
        std::cout << "total search hits    : " << hits << std::endl;
        std::cout << "searches per second  : " << std::fixed << hits_per_sec << std::endl;
    };

    {
        std::cout << "building unordered map:" << std::endl;
        std::unordered_map<ip_address, data_associated_with_ip> um;
        build_ip_map(um, known_candidates);
        std::cout << "testing with unordered map:" << std::endl;
        run_test(um);
    }

    {
        std::cout << "\nbuilding ordered map  :" << std::endl;
        std::map<ip_address, data_associated_with_ip> m;
        build_ip_map(m, known_candidates);
        std::cout << "testing with ordered map  :" << std::endl;
        run_test(m);
    }

}

пример результатов:

building unordered map:
testing with unordered map:
ip addresses in table: 8000000
ip addresses searched: 100000000
total search hits    : 21681856
searches per second  : 5602458.505577

building ordered map  :
testing with ordered map  :
ip addresses in table: 8000000
ip addresses searched: 100000000
total search hits    : 21681856
searches per second  : 836123.513710

Условия испытаний:

MacBook Pro (Retina, 15-inch, Mid 2015)
Processor: 2.2 GHz Intel Core i7
Memory: 16 GB 1600 MHz DDR3
Release build (-O2)

Работает от сети.

Автор: Richard Hodges Размещён: 20.08.2016 02:51

0 плюса

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

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

Автор: Sam Varshavchik Размещён: 20.08.2016 01:53

0 плюса

Похоже, что ваша проблема не в производительности ifоператора, а в том, какая структура данных может дать вам ответ на вопрос «содержится ли этот элемент?» Как можно быстрее. Если это правда, как насчет использования фильтра Блума ?

Структуры данных, которые предлагают быстрый поиск (быстрее, чем логарифмическая сложность), являются хеш-таблицами, которые в среднем имеют сложность O (1). Одна из таких реализаций находится в Boost.Unordered .

Автор: Technaton Размещён: 20.08.2016 01:56

0 плюса

Конечно, вам нужно протестировать с реальными данными ... но подумав об IPV4, я бы попробовал сначала другой подход:

EntryItem* searchIPTable(uint32_t ip) {
    EntryItem** tab = master_table[ip >> 16];
    return tab ? tab[ip & 65535] : NULL;
}

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

В зависимости от типа данных другое подразделение вместо 16 + 16 бит может работать лучше (меньше памяти).

Также может иметь смысл иметь подробные страницы, которые будут непосредственно IP-записями, а не указателями на записи.

Автор: 6502 Размещён: 20.08.2016 02:08
Вопросы из категории :
32x32