C ++ Tuple vs Struct

98

Czy jest jakaś różnica między używaniem a std::tuplei tylko danych struct?

typedef std::tuple<int, double, bool> foo_t;

struct bar_t {
    int id;
    double value;
    bool dirty;
}

Z tego, co znalazłem w Internecie, stwierdziłem, że istnieją dwie główne różnice: structjest bardziej czytelny, a tuplema wiele ogólnych funkcji, których można używać. Czy powinna istnieć jakaś znacząca różnica w wydajności? Czy układ danych jest ze sobą kompatybilny (rzutowany zamiennie)?

Alex Koay
źródło
Zwróciłem tylko uwagę, że zapomniałem o rzuconym pytaniu: implementacja tuplejest zdefiniowana, więc zależy to od twojej implementacji. Osobiście nie liczyłbym na to.
Matthieu M.,

Odpowiedzi:

33

Prowadzimy podobną dyskusję na temat krotki i struktury i piszę kilka prostych testów porównawczych z pomocą jednego z moich kolegów, aby zidentyfikować różnice w zakresie wydajności między krotką a strukturą. Najpierw zaczynamy od domyślnej struktury i krotki.

struct StructData {
    int X;
    int Y;
    double Cost;
    std::string Label;

    bool operator==(const StructData &rhs) {
        return std::tie(X,Y,Cost, Label) == std::tie(rhs.X, rhs.Y, rhs.Cost, rhs.Label);
    }

    bool operator<(const StructData &rhs) {
        return X < rhs.X || (X == rhs.X && (Y < rhs.Y || (Y == rhs.Y && (Cost < rhs.Cost || (Cost == rhs.Cost && Label < rhs.Label)))));
    }
};

using TupleData = std::tuple<int, int, double, std::string>;

Następnie używamy Celero do porównania wydajności naszej prostej struktury i krotki. Poniżej znajduje się kod testu porównawczego i wyniki wydajności zebrane za pomocą gcc-4.9.2 i clang-4.0.0:

std::vector<StructData> test_struct_data(const size_t N) {
    std::vector<StructData> data(N);
    std::transform(data.begin(), data.end(), data.begin(), [N](auto item) {
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(0, N);
        item.X = dis(gen);
        item.Y = dis(gen);
        item.Cost = item.X * item.Y;
        item.Label = std::to_string(item.Cost);
        return item;
    });
    return data;
}

std::vector<TupleData> test_tuple_data(const std::vector<StructData> &input) {
    std::vector<TupleData> data(input.size());
    std::transform(input.cbegin(), input.cend(), data.begin(),
                   [](auto item) { return std::tie(item.X, item.Y, item.Cost, item.Label); });
    return data;
}

constexpr int NumberOfSamples = 10;
constexpr int NumberOfIterations = 5;
constexpr size_t N = 1000000;
auto const sdata = test_struct_data(N);
auto const tdata = test_tuple_data(sdata);

CELERO_MAIN

BASELINE(Sort, struct, NumberOfSamples, NumberOfIterations) {
    std::vector<StructData> data(sdata.begin(), sdata.end());
    std::sort(data.begin(), data.end());
    // print(data);

}

BENCHMARK(Sort, tuple, NumberOfSamples, NumberOfIterations) {
    std::vector<TupleData> data(tdata.begin(), tdata.end());
    std::sort(data.begin(), data.end());
    // print(data);
}

Wyniki wydajności zebrane za pomocą clang-4.0.0

Celero
Timer resolution: 0.001000 us
-----------------------------------------------------------------------------------------------------------------------------------------------
     Group      |   Experiment    |   Prob. Space   |     Samples     |   Iterations    |    Baseline     |  us/Iteration   | Iterations/sec  | 
-----------------------------------------------------------------------------------------------------------------------------------------------
Sort            | struct          | Null            |              10 |               5 |         1.00000 |    196663.40000 |            5.08 | 
Sort            | tuple           | Null            |              10 |               5 |         0.92471 |    181857.20000 |            5.50 | 
Complete.

Oraz wyniki wydajności zebrane za pomocą gcc-4.9.2

Celero
Timer resolution: 0.001000 us
-----------------------------------------------------------------------------------------------------------------------------------------------
     Group      |   Experiment    |   Prob. Space   |     Samples     |   Iterations    |    Baseline     |  us/Iteration   | Iterations/sec  | 
-----------------------------------------------------------------------------------------------------------------------------------------------
Sort            | struct          | Null            |              10 |               5 |         1.00000 |    219096.00000 |            4.56 | 
Sort            | tuple           | Null            |              10 |               5 |         0.91463 |    200391.80000 |            4.99 | 
Complete.

Z powyższych wyników wyraźnie to widać

  • Krotka jest szybsza niż domyślna struktura

  • Binarny produkt Clang ma wyższą wydajność niż gcc. Clang-vs-gcc nie jest celem tej dyskusji, więc nie będę zagłębiać się w szczegóły.

Wszyscy wiemy, że napisanie operatora == lub <lub> dla każdej definicji struktury będzie bolesnym i błędnym zadaniem. Zastąpmy nasz niestandardowy komparator za pomocą std :: tie i ponownie uruchom nasz test porównawczy.

bool operator<(const StructData &rhs) {
    return std::tie(X,Y,Cost, Label) < std::tie(rhs.X, rhs.Y, rhs.Cost, rhs.Label);
}

Celero
Timer resolution: 0.001000 us
-----------------------------------------------------------------------------------------------------------------------------------------------
     Group      |   Experiment    |   Prob. Space   |     Samples     |   Iterations    |    Baseline     |  us/Iteration   | Iterations/sec  | 
-----------------------------------------------------------------------------------------------------------------------------------------------
Sort            | struct          | Null            |              10 |               5 |         1.00000 |    200508.20000 |            4.99 | 
Sort            | tuple           | Null            |              10 |               5 |         0.90033 |    180523.80000 |            5.54 | 
Complete.

Teraz widzimy, że użycie std :: tie sprawia, że ​​nasz kod jest bardziej elegancki i trudniej jest popełnić błąd, jednak stracimy około 1% wydajności. Na razie pozostanę przy rozwiązaniu std :: tie, ponieważ otrzymuję również ostrzeżenie o porównywaniu liczb zmiennoprzecinkowych z dostosowanym komparatorem.

Do tej pory nie mamy żadnego rozwiązania, które sprawiłoby, że nasz kod strukturalny działałby szybciej. Przyjrzyjmy się funkcji swap i przepiszmy ją, aby zobaczyć, czy możemy uzyskać jakąkolwiek wydajność:

struct StructData {
    int X;
    int Y;
    double Cost;
    std::string Label;

    bool operator==(const StructData &rhs) {
        return std::tie(X,Y,Cost, Label) == std::tie(rhs.X, rhs.Y, rhs.Cost, rhs.Label);
    }

    void swap(StructData & other)
    {
        std::swap(X, other.X);
        std::swap(Y, other.Y);
        std::swap(Cost, other.Cost);
        std::swap(Label, other.Label);
    }  

    bool operator<(const StructData &rhs) {
        return std::tie(X,Y,Cost, Label) < std::tie(rhs.X, rhs.Y, rhs.Cost, rhs.Label);
    }
};

Wyniki wydajności zebrane przy użyciu clang-4.0.0

Celero
Timer resolution: 0.001000 us
-----------------------------------------------------------------------------------------------------------------------------------------------
     Group      |   Experiment    |   Prob. Space   |     Samples     |   Iterations    |    Baseline     |  us/Iteration   | Iterations/sec  | 
-----------------------------------------------------------------------------------------------------------------------------------------------
Sort            | struct          | Null            |              10 |               5 |         1.00000 |    176308.80000 |            5.67 | 
Sort            | tuple           | Null            |              10 |               5 |         1.02699 |    181067.60000 |            5.52 | 
Complete.

Wyniki wydajności zebrane przy użyciu gcc-4.9.2

Celero
Timer resolution: 0.001000 us
-----------------------------------------------------------------------------------------------------------------------------------------------
     Group      |   Experiment    |   Prob. Space   |     Samples     |   Iterations    |    Baseline     |  us/Iteration   | Iterations/sec  | 
-----------------------------------------------------------------------------------------------------------------------------------------------
Sort            | struct          | Null            |              10 |               5 |         1.00000 |    198844.80000 |            5.03 | 
Sort            | tuple           | Null            |              10 |               5 |         1.00601 |    200039.80000 |            5.00 | 
Complete.

Teraz nasza struktura jest teraz nieco szybsza niż krotka (około 3% z clang i mniej niż 1% z gcc), jednak musimy napisać naszą niestandardową funkcję wymiany dla wszystkich naszych struktur.

Hungptit
źródło
24

Jeśli używasz kilku różnych krotek w swoim kodzie, możesz uciec od skondensowania liczby używanych funktorów. Mówię to, ponieważ często używałem następujących form funktorów:

template<int N>
struct tuple_less{
    template<typename Tuple>
    bool operator()(const Tuple& aLeft, const Tuple& aRight) const{
        typedef typename boost::tuples::element<N, Tuple>::type value_type;
        BOOST_CONCEPT_REQUIRES((boost::LessThanComparable<value_type>));

        return boost::tuples::get<N>(aLeft) < boost::tuples::get<N>(aRight);
    }
};

Może się to wydawać przesadą, ale dla każdego miejsca w strukturze musiałbym stworzyć zupełnie nowy obiekt funktora za pomocą struktury, ale dla krotki po prostu się zmieniam N. Co więcej, mogę to zrobić dla każdej krotki, zamiast tworzyć zupełnie nowy funktor dla każdej struktury i dla każdej zmiennej składowej. Gdybym miał struktury N ze zmiennymi składowymi M, które funktory NxM musiałbym utworzyć (scenariusz gorszy), które można skondensować do jednego małego fragmentu kodu.

Oczywiście, jeśli zamierzasz korzystać z krotki, będziesz musiał również utworzyć wyliczenia do pracy z nimi:

typedef boost::tuples::tuple<double,double,double> JackPot;
enum JackPotIndex{
    MAX_POT,
    CURRENT_POT,
    MIN_POT
};

i bum, twój kod jest całkowicie czytelny:

double guessWhatThisIs = boost::tuples::get<CURRENT_POT>(someJackPotTuple);

ponieważ opisuje siebie, kiedy chcesz uzyskać zawarte w nim elementy.

pszenicy
źródło
8
Uh ... C ++ ma wskaźniki do funkcji, więc template <typename C, typename T, T C::*> struct struct_less { template <typename C> bool operator()(C const&, C const&) const; };powinno być możliwe. Literowanie jest nieco mniej wygodne, ale jest napisane tylko raz.
Matthieu M.,
17

Tuple ma wbudowane domyślne (dla == i! = Porównuje każdy element, dla <. <= ... najpierw porównuje, jeśli to samo porównuje drugie ...) komparatory: http://en.cppreference.com/w/ cpp / utility / tuple / operator_cmp

edit: jak zauważono w komentarzu, operator statku kosmicznego C ++ 20 umożliwia określenie tej funkcji za pomocą jednej (brzydkiej, ale wciąż tylko jednej) linii kodu.

NoSenseEtAl
źródło
1
W C ++ 20 rozwiązano ten problem przy użyciu minimalnego schematu przy użyciu operatora statku kosmicznego .
John McFarlane,
6

Cóż, oto test porównawczy, który nie tworzy wielu krotek wewnątrz operatora struct == (). Okazuje się, że używanie krotki ma dość znaczący wpływ na wydajność, jak można by się spodziewać, biorąc pod uwagę, że używanie POD-ów nie ma żadnego wpływu na wydajność. (Program rozpoznawania adresów znajduje wartość w potoku instrukcji, zanim jednostka logiczna w ogóle ją zobaczy).

Typowe wyniki uruchomienia tego na moim komputerze z VS2015CE przy użyciu domyślnych ustawień „Release”:

Structs took 0.0814905 seconds.
Tuples took 0.282463 seconds.

Proszę, małpuj nim, aż będziesz zadowolony.

#include <iostream>
#include <string>
#include <tuple>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

class Timer {
public:
  Timer() { reset(); }
  void reset() { start = now(); }

  double getElapsedSeconds() {
    std::chrono::duration<double> seconds = now() - start;
    return seconds.count();
  }

private:
  static std::chrono::time_point<std::chrono::high_resolution_clock> now() {
    return std::chrono::high_resolution_clock::now();
  }

  std::chrono::time_point<std::chrono::high_resolution_clock> start;

};

struct ST {
  int X;
  int Y;
  double Cost;
  std::string Label;

  bool operator==(const ST &rhs) {
    return
      (X == rhs.X) &&
      (Y == rhs.Y) &&
      (Cost == rhs.Cost) &&
      (Label == rhs.Label);
  }

  bool operator<(const ST &rhs) {
    if(X > rhs.X) { return false; }
    if(Y > rhs.Y) { return false; }
    if(Cost > rhs.Cost) { return false; }
    if(Label >= rhs.Label) { return false; }
    return true;
  }
};

using TP = std::tuple<int, int, double, std::string>;

std::pair<std::vector<ST>, std::vector<TP>> generate() {
  std::mt19937 mt(std::random_device{}());
  std::uniform_int_distribution<int> dist;

  constexpr size_t SZ = 1000000;

  std::pair<std::vector<ST>, std::vector<TP>> p;
  auto& s = p.first;
  auto& d = p.second;
  s.reserve(SZ);
  d.reserve(SZ);

  for(size_t i = 0; i < SZ; i++) {
    s.emplace_back();
    auto& sb = s.back();
    sb.X = dist(mt);
    sb.Y = dist(mt);
    sb.Cost = sb.X * sb.Y;
    sb.Label = std::to_string(sb.Cost);

    d.emplace_back(std::tie(sb.X, sb.Y, sb.Cost, sb.Label));
  }

  return p;
}

int main() {
  Timer timer;

  auto p = generate();
  auto& structs = p.first;
  auto& tuples = p.second;

  timer.reset();
  std::sort(structs.begin(), structs.end());
  double stSecs = timer.getElapsedSeconds();

  timer.reset();
  std::sort(tuples.begin(), tuples.end());
  double tpSecs = timer.getElapsedSeconds();

  std::cout << "Structs took " << stSecs << " seconds.\nTuples took " << tpSecs << " seconds.\n";

  std::cin.get();
}
Khatharr
źródło
Dzięki za to. Zauważyłem, że po optymalizacji z -O3, tupleszajęło mniej czasu niż structs.
Simog
3

Cóż, struktura POD może być często (ab) używana w ciągłym odczytywaniu i serializowaniu fragmentów niskiego poziomu. Jak powiedziałeś, krotka może być bardziej zoptymalizowana w pewnych sytuacjach i obsługiwać więcej funkcji.

Użyj tego, co jest bardziej odpowiednie w danej sytuacji, nie ma ogólnych preferencji. Myślę (ale nie testowałem tego), że różnice w wydajności nie będą znaczące. Układ danych najprawdopodobniej nie jest zgodny i nie jest związany z implementacją.

orlp
źródło
3

Jeśli chodzi o „funkcję ogólną”, Boost.Fusion zasługuje na trochę miłości ... a zwłaszcza BOOST_FUSION_ADAPT_STRUCT .

Zgrywanie ze strony: ABRACADBRA

namespace demo
{
    struct employee
    {
        std::string name;
        int age;
    };
}

// demo::employee is now a Fusion sequence
BOOST_FUSION_ADAPT_STRUCT(
    demo::employee
    (std::string, name)
    (int, age))

Oznacza to, że wszystkie algorytmy Fusion mają teraz zastosowanie do struktury demo::employee.


EDYCJA : Jeśli chodzi o różnicę w wydajności lub zgodność układu, tupleukład jest zdefiniowany jako implementacja, więc nie jest kompatybilny (a zatem nie należy rzutować między żadną reprezentacją) i ogólnie nie spodziewałbym się żadnej różnicy pod względem wydajności (przynajmniej w wydaniu) dzięki inlining z get<N>.

Matthieu M.
źródło
16
Nie sądzę, aby to była najczęściej głosowana odpowiedź. Nawet nie odpowiada na pytanie. Pytanie dotyczy tuplesiatek, a structnie wzmocnienia!
gsamaras
@ G.Samaras: Pytanie dotyczy różnicy między krotkami struct, a zwłaszcza obfitości algorytmów do manipulowania krotkami wbrew braku algorytmów do manipulowania strukturami (zaczynając od iteracji po ich polach). Ta odpowiedź pokazuje, że tę lukę można zlikwidować za pomocą Boost.Fusion, uzyskując structtyle algorytmów, ile jest na krotkach. Dodałem krótką notkę dokładnie na dwa zadane pytania.
Matthieu M.
3

Czy układ danych jest ze sobą kompatybilny (rzutowany zamiennie)?

Co dziwne, nie widzę bezpośredniej odpowiedzi na tę część pytania.

Odpowiedź brzmi: nie . A przynajmniej nie niezawodnie, ponieważ układ krotki jest nieokreślony.

Po pierwsze, twoja struktura jest standardowym typem układu . Kolejność, wypełnienie i wyrównanie elementów członkowskich są dobrze zdefiniowane przez połączenie standardu i platformy ABI.

Gdyby krotka była standardowym typem układu i wiedzieliśmy, że pola zostały ułożone w kolejności, w jakiej są określone typy, moglibyśmy mieć pewność, że będzie pasować do struktury.

Krotka jest zwykle implementowana przy użyciu dziedziczenia na jeden z dwóch sposobów: stary styl rekurencyjny Loki / Modern C ++ Design lub nowszy styl wariadyczny. Żaden z nich nie jest typem układu standardowego, ponieważ oba naruszają następujące warunki:

  1. (przed C ++ 14)

    • nie ma klas bazowych z niestatycznymi składowymi danych lub

    • nie ma niestatycznych elementów członkowskich danych w klasie najbardziej pochodnej i co najwyżej jednej klasy bazowej z niestatycznymi składowymi danych

  2. (dla C ++ 14 i nowszych)

    • Ma wszystkie niestatyczne składowe danych i pola bitowe zadeklarowane w tej samej klasie (wszystkie w pochodnej lub wszystkie w jakiejś bazie)

ponieważ każda klasa bazowa liścia zawiera pojedynczy element krotki (uwaga: krotka jednoelementowa jest prawdopodobnie standardowym typem układu, aczkolwiek niezbyt użytecznym). Tak więc wiemy, że standard nie gwarantuje, że krotka ma takie samo dopełnienie lub wyrównanie jak struktura.

Ponadto warto zauważyć, że starsza krotka w stylu rekurencyjnym generalnie układa elementy składowe danych w odwrotnej kolejności.

Anegdotycznie, czasami działało w praktyce dla niektórych kompilatorów i kombinacji typów pól w przeszłości (w jednym przypadku przy użyciu krotek rekurencyjnych po odwróceniu kolejności pól). Zdecydowanie nie działa teraz niezawodnie (między kompilatorami, wersjami itp.) I nigdy nie było gwarantowane.

Bezużyteczny
źródło
2

Z mojego doświadczenia wynika, że ​​z biegiem czasu funkcjonalność zaczyna pełzać na typach (takich jak struktury POD), które były zwykłymi posiadaczami danych. Rzeczy takie jak pewne modyfikacje, które nie powinny wymagać wewnętrznej wiedzy o danych, utrzymywanie niezmienników itp.

To jest dobra rzecz; to podstawa orientacji obiektu. To jest powód, dla którego wymyślono C z klasami. Używanie czystych zbiorów danych, takich jak krotki, nie jest otwarte na takie logiczne rozszerzenie; struktury są. Dlatego prawie zawsze wybrałbym struktury.

Podobnie jak wszystkie „obiekty otwartych danych”, krotki naruszają paradygmat ukrywania informacji. Nie możesz tego później zmienić bez wyrzucenia hurtowej krotki. Struct umożliwia stopniowe przechodzenie do funkcji dostępu.

Kolejną kwestią jest bezpieczeństwo typów i samodokumentujący się kod. Jeśli twoja funkcja otrzymuje obiekt typu inbound_telegramlub location_3Djest to jasne; jeśli otrzyma unsigned char *lub nie otrzyma tuple<double, double, double>: telegram może być wysyłany, a krotka może być tłumaczeniem zamiast lokalizacji lub być może minimalnymi odczytami temperatury z długiego weekendu. Tak, możesz napisać na klawiaturze, aby jasno określić intencje, ale w rzeczywistości nie zapobiega to przechodzeniu temperatur.

Kwestie te mają zwykle znaczenie w projektach, które przekraczają pewien rozmiar; wady krotek i zalety skomplikowanych klas stają się niewidoczne i rzeczywiście stanowią narzut w małych projektach. Rozpoczynanie od odpowiednich klas nawet dla niepozornych, małych agregatów danych opłaca się późno.

Oczywiście jedną realną strategią byłoby użycie czystego posiadacza danych jako podstawowego dostawcy danych dla opakowania klasy, które zapewnia operacje na tych danych.

Peter - przywróć Monikę
źródło
2

Sądząc po innych odpowiedziach, względy wydajności są w najlepszym przypadku minimalne.

Więc to naprawdę powinno sprowadzać się do praktyczności, czytelności i łatwości konserwacji. I structjest na ogół lepsza, ponieważ tworzy typy, które są łatwiejsze do odczytania i zrozumienia.

Czasami std::tuple(a nawet std::pair) może być konieczne, aby poradzić sobie z kodem w bardzo ogólny sposób. Na przykład niektóre operacje związane ze zmiennymi pakietami parametrów byłyby niemożliwe bez czegoś takiego std::tuple. std::tiejest doskonałym przykładem tego, kiedy std::tuplemożna ulepszyć kod (przed C ++ 20).

Ale wszędzie tam, gdzie można używać struct, prawdopodobnie należy użyć struct. Nadaje semantyczne znaczenie elementom twojego typu. To nieocenione w zrozumieniu i używaniu czcionki. To z kolei może pomóc uniknąć głupich błędów:

// hard to get wrong; easy to understand
cat.arms = 0;
cat.legs = 4;

// easy to get wrong; hard to understand
std::get<0>(cat) = 0;
std::get<1>(cat) = 4;
John McFarlane
źródło
1

Nie powinno być różnicy w wydajności (nawet nieznacznej). Przynajmniej w normalnym przypadku dadzą one taki sam układ pamięci. Niemniej jednak, rzutowanie między nimi prawdopodobnie nie jest wymagane do pracy (chociaż sądzę, że jest całkiem spora szansa, że ​​normalnie tak się stanie).

Jerry Coffin
źródło
4
Właściwie myślę, że może być niewielka różnica. structMusi przeznaczyć co najmniej 1 bajt dla każdej podobiektu natomiast myślę, że tuplemoże uciec z optymalizacją z pustych obiektów. Ponadto, w odniesieniu do pakowania i wyrównania, może się zdarzyć, że krotki mają większą swobodę.
Matthieu M.
1

Nie martw się o szybkość ani układ, to nano-optymalizacja i zależy od kompilatora, a różnica nigdy nie jest wystarczająca, aby wpłynąć na twoją decyzję.

Używasz struktury dla rzeczy, które w znaczący sposób należą do siebie, tworząc całość.

Używasz krotki dla rzeczy, które są razem przypadkowo. Możesz spontanicznie użyć krotki w swoim kodzie.

gnasher729
źródło
0

Wiem, że to stary temat, ale teraz mam zamiar podjąć decyzję dotyczącą części mojego projektu: czy powinienem iść drogą krotkową, czy strukturalną. Po przeczytaniu tego wątku mam kilka pomysłów.

  1. O pszenicy i teście wydajności: pamiętaj, że zwykle możesz używać memcpy, memset i podobnych sztuczek do struktur. To sprawi, że wydajność ZNACZNIE lepsza niż w przypadku krotek.

  2. Widzę kilka zalet w krotkach:

    • Możesz użyć krotek, aby zwrócić kolekcję zmiennych z funkcji lub metody i zmniejszyć liczbę używanych typów.
    • Opierając się na fakcie, że krotka ma predefiniowane operatory <, ==,>, możesz również użyć krotki jako klucza w mapie lub hash_map, co jest znacznie bardziej opłacalne niż struktura, w której musisz zaimplementować te operatory.

Przeszukałem sieć i ostatecznie dotarłem na tę stronę: https://arne-mertz.de/2017/03/smelly-pair-tuple/

Generalnie zgadzam się z końcowym wnioskiem z góry.

Tom K.
źródło
1
To brzmi bardziej jak to, nad czym pracujesz, a nie odpowiedź na to konkretne pytanie, lub?
Dieter Meemken
Nic nie stoi na przeszkodzie, aby używać memcpy z krotkami.
Peter - Przywróć Monikę