Ile wyrażeń "jeśli" wpływa na wydajność?

Question

Istnieje kilka IPTables o różnych rozmiarach (np. 255 lub 16384 lub 512000 !!). Każda pozycja w każdej tabeli zawiera unikatowy adres IP (format szesnastkowy) i kilka innych wartości. Całkowita liczba adresów IP wynosi 8 milionów. Wszystkie adresy IP wszystkich IPTables są sortowane

Musimy przeszukać IPTable 300 000 razy na sekundę. Nasz obecny algorytm znajdowania IP jest następująca:

// 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; 
     } 

Jak można zauważyć, w najgorszym przypadku, liczba porównań na dany adres IP jest _rangeCount * 2 i liczby „czy” Sprawdzanie stwierdzenie jest _rangeCount .

Załóżmy, że chcę zmienić searchIPTable i użyć bardziej efektywnego sposobu na znalezienie adresu IP w IPTables. O ile wiem, dla posortowanej tablicy najlepsze oprogramowanie znanego algorytmu wyszukiwania, takiego jak wyszukiwanie binarne, wymaga porównania log (n) (w najgorszym przypadku).

Tak więc liczba porównań do znalezienia adresu IP to log (8000000), który jest równy ~ 23.

Pytanie 1:

Jak Można zauważyć, że jest trochę luka pomiędzy liczbą porównaniu potrzebnej przez dwa algorytmu (_rangeCount vs 23), ale w pierwszej metodzie, istnieją pewne „if”, które mogą wpływać na wydajność. jeśli chcesz uruchomić pierwszy algorytm 10 razy, oczywiście pierwszy algorytm ma lepszą wydajność, ale znam pomysł na uruchomienie dwóch algorytmów na 3000 000 razy! jaki jest Twój pomysł?

Pytanie 2:

Czy jest bardziej efektywny algorytm lub roztwór do wyszukiwania adresów IP?

Answer 1

ciekawość pobudzona, napisałem program testowy (poniżej) i uruchomiłem go na moim macbooku.

Sugeruje to, że rozwiązanie naiwne, oparte na std::unordered_map (czas wyszukiwania == stały czas) jest w stanie przeszukać tabelę adresów IP z 8 milionami wpisów 5,6 milionów razy na sekundę.

To z łatwością przewyższa wymagania.

aktualizacja: w odpowiedzi na moją krytykę, zwiększyłem przestrzeń testową do wymaganych adresów IP o wartości 8m. Zwiększyłem także rozmiar testu do 100 milionów wyszukiwań, z których 20% będzie hitem.

Przy tak dużym teście możemy wyraźnie zobaczyć korzyści związane z korzystaniem z mapy unordered_map w porównaniu do uporządkowanej mapy (logarytmiczne wyszukiwania czasu).

Wszystkie parametry testu można konfigurować.

#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); 
    } 

} 

wyniki przykład: warunki

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 

testowe:

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

zasilany z sieci elektrycznej.

Answer 2

W tego rodzaju sytuacjach jedynym praktycznym sposobem określenia najszybszej implementacji jest wdrożenie obu podejść, a następnie dokonanie porównania każdego z nich.

Czasami szybciej jest to zrobić niż spróbować ustalić, który z nich będzie szybszy. A czasami, jeśli to zrobisz, a następnie przystąpisz do wybranego podejścia, odkryjesz, że myliłeś się.

Answer 3

Wygląda na to, że Twoim problemem nie jest koszt wydajności oświadczenia if, ale raczej struktura danych może dać odpowiedź na pytanie "czy zawierasz ten element?" Tak szybko jak to możliwe. Jeśli to prawda, to może użyć Bloom Filter?

Struktury danych, które oferują szybkie wyszukiwanie (szybciej niż złożoność logarytmiczna), są tabelami mieszającymi, które mają zwykle złożoność O (1). Jedną z takich implementacji jest Boost.Unordered.

Answer 4

Oczywiście trzeba by sprawdzić z prawdziwymi danymi ... ale myśleć IPv4 chciałbym najpierw spróbować innego podejścia:

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

Innymi słowy tabeli mistrz 65536 wpisów, które są wskaźnikami do szczegółowe tabele po 65536 wpisów każdy.

W zależności od rodzaju danych, inny podział zamiast 16 + 16 bitów może działać lepiej (mniej pamięci).

Może również być sensowne, aby strony szczegółowe były bezpośrednimi wpisami IP zamiast wskaźników do wpisów.