12 lutego 2020

[C++17] Parallel algorithms

Biblioteka standardowa w C++17 została rozbudowana o algorytmy, których praca może zostać zrównoleglona. O sposobie wykonania decyduje ExecutionPolicy przekazane do funkcji jako argument. Programista musi zapewnić, że funkcja przekazana do "algorytmu", będzie bezpieczna - nie będzie zależności między danymi (np. modyfikowanie danych, które mogą być odczytywane przez inny równoległy wątek). Dobre wytłumaczenie różnic na stackoverflow, a tutaj małe zestawienie:
  • std::execution::seq - standardowe wykonanie sekwencyjne, bez zrównoleglenia.
  • std::execution::par - równoległe wykonanie (choć nie ma obietnicy, że tak się stanie).
  • std::execution::par_unseq - równoległe wykonanie (choć nie ma obietnicy, że tak się stanie). Wymaga silniejszych gwarancji na to że przeplatane wywołanie funkcji będzie bezpieczne także w obrębie jednego wątku. Nowe procesory oferują taką możliwość dzięki instrukcjom do wektoryzacji - SIMD (Single-Instruction, Multiple-Data) parallelism.
Przykład z funkcją std::reduce, która w działaniu przypomina std::accumulate. Zsumowanie wartości w wektorze:
#include <iostream>
#include <numeric>
#include <execution>
#include <vector>

using namespace std;

int main() {
    vector<int> vec{1, 2, 3, 4};

    int result = std::reduce(std::execution::par,
                             begin(vec),
                             end(vec));

    cout << result << endl;
}
W przypadku gcc (9.2.1 20191008) wymagane było zainstalowanie dodatkowej paczki libtbb-dev (Threading Building Blocks).
$ sudo apt-get install libtbb-dev
$ g++ -std=c++17 main.cpp -ltbb
$ ./a.out

10

11 lutego 2020

[C++] Atomics

Nie miałem do tej pory wiele do czynienia z atomic-ami (inny wpis) w prawdziwym życiu i traktuje je jako niskopoziomowy mechanizm, ale inni chyba lepiej potrafią wykorzystać ich możliwości. Pozwalają na pisanie kodu "lock-free", chociaż bez głębszego zrozumienia ich natury, niekoniecznie będzie to kod szybszy od tego opartego na muteksach. Ciekawy wykład na ich temat poprowadził Fedor Pikus na CppCon 2017: C++ atomics, from basic to advanced. What do they really do? Warto obejrzeć więcej niż raz.

Operacje na atomic-ach odzwierciedlają operacje sprzętowe i gwarantują, że zostaną wykonane w jednej transakcji (atomowo). CPU oferuje sporą liczbę mechanizmów, które są z nimi związane, z tego też względu standardowa biblioteka jest całkiem rozbudowana. Atomic-iem, może być każdy prymitywny typ (tylko takie obiekty mogą pojawić się w rejestrach CPU).
Przykłady:
// Dla
std::atomic<int> x{0};

// Operacje:
++x;           // atomowy pre-increment
x++;           // atomowy post-increment
x += 1;        // atomowy increment
int y = x * 2; // atomowy odczyt x
x = y + 2;     // atomowy zapis do x

// Uwaga, ta operacja jest niewspierana 
x *= 2;        // ERROR

// Atomowy odczyt x, po którym następuje atomowy zapis do x (dwie operacje)
x = x * 2;
W przykładzie poniżej, atomic posłużył do blokowania wątków, tak aby funkcje even/odd drukowały naprzemiennie tekst w momencie inkrementacji. Uwaga, nie ma gwarancji, że wartość counter wyświetlana na ekranie będzie zgodna z tym co było sprawdzane w if. Są to dwie atomowe operacje odczytu z pamięci, a wartość counter może się zmienić pomiędzy nimi.
#include <iostream>
#include <thread>
#include <atomic>

using namespace std;

std::atomic<int> counter{0};

void odd(size_t n) {
    for (size_t i = 0; i < n; i++) {
        if (counter % 2 == 1) {
            cout << "Odd  increment: " << counter << endl;
            counter++;
        } else {
            cout << "Odd  check: " << counter << endl;   // wartość mogła się zmienić
        }

        std::this_thread::sleep_for(std::chrono::milliseconds{20});
    }
}

void even(size_t n) {
    for (size_t i = 0; i < n; i++) {
        if (counter % 2 == 0) {
            cout << "Even increment: " << counter << endl;
            counter++;
        } else {
            cout << "Even check: " << counter << endl;   // wartość mogła się zmienić
        }
        std::this_thread::sleep_for(std::chrono::milliseconds{40});
    }
}

int main() {
    constexpr size_t steps{6};
    std::thread t1{odd, steps};
    std::thread t2{even, steps};

    t1.join();
    t2.join();
}

Wynik:
Odd  check: 0
Even increment: 0
Odd  increment: 1
Even increment: 2
Odd  increment: 3
Odd  check: 4
Even increment: 4
Odd  increment: 5
Odd  check: 6
Even increment: 6
Even check: 7
Even check: 7

8 lutego 2020

[C++17] std::variant i std::vist

Nowa funkcja std::visit w C++17 umożliwia wywołanie funkcji na rzecz jakiegoś obiektu. Mając wiele takich obiektów (np. "odwiedzając" w pętli obiekty zachowane w jakimś kontenerze) mamy gotowy wzorzec wizytator (odwiedzający). Typowym sposobem implementacji takiego wzorca w C++ było skorzystanie z polimorfizmu. std::visit pozwala jednak na wywołanie funkcji na dowolnym obiekcie. Klasy nie muszą mieć wspólnego interfejsu, ale trzeba będzie skorzystać z znanego z biblioteki boost std::variant. W ten sposób można przechowywać obiekty alternatywnych typów (type-safe union).
#include <iostream>
#include <vector>
#include <variant>

using namespace std;

struct Circle {
    void show() const { cout << "Circle" << endl; }
};

struct Rect {
    void show() const { cout << "Rect" << endl; }
};

int main() {
    using Variant = std::variant<Circle, Rect>;

    vector<Variant> vec;
    vec.push_back(Circle{});
    vec.push_back(Rect{});

    for (const auto& v : vec) {
        std::visit([](const auto& obj){ obj.show(); }, v);
    }
}
Wynik:
Circle
Rect

7 lutego 2020

[C++11/17] enable_if vs. if constexpr

enable_if pojawiło się w C++11 i miało za zadanie uelastycznić mechanizm metaprogramowania w szablonach, pozwalając na tworzenie specjalizacji typu, tylko gdy typ spełniał określone warunki. Wraz z type_traits dało się stworzyć naprawdę trudny w zrozumieniu i utrzymaniu kod. Obecnie sam core guadline zaleca, aby jego używanie ograniczyć do minimum, wymieniając enable_if jako przykład złego kodu. Na szczęście wszystko wskazuje na to, że społeczność chce wreszcie zabić nieszczęsne metaprogramowanie w szablonach. Do tego jeszcze jednak długa droga.

Oryginalnym mechanizmem metaprogramowania w C++ były znane z języka C makra, lecz pewnego dnia, Erwin Unruh, przez przypadek odkrył mechanizm dziś znany jako SFINAE (Substitution Failure Is Not An Error). W skrócie, jeżeli kompilatorowi nie uda się wyspecjalizować szablonu będzie próbował dalej. W jego przykładzie wywołując rekursywną specjalizację szablonów, dokonał obliczeń w czasie kompilacji, choć kompilacja zakończyła się niepowodzeniem. Być może, właśnie przez to, że mechanizm ten pojawił się przypadkiem, a nie został wprowadzony z premedytacją, nie jest on przemyślany składniowo, sprawia że wiele osób odrzuca i dzieli społeczność C++ na dwa obozy.

Przykłady poniżej oparłem na prezentacji Nicolai Josuttis - C++17 - The Best Features. Na początek wersja kodu wykorzystująca enable_if przez zwracany typ (drugi parametr - w naszym przypadku std::string).
#include <iostream>
#include <type_traits>

using namespace std;

template<typename T>
std::enable_if_t<std::is_arithmetic_v<T>,
                 std::string>
as_string1(T x) {
    return std::to_string(x) + " [is_arithmetic_v]";
}

template<typename T>
std::enable_if_t<std::is_same_v<T, std::string>,
                 std::string>
as_string1(T x) {
    return x + " [is_same_v]";
}

template<typename T>
std::enable_if_t<!std::is_same_v<T, std::string> && !std::is_arithmetic_v<T>,
                 std::string>
as_string1(T x) {
    return std::string(x) + " [!is_same_v && !is_arithmetic_v]";
}

int main() {
    cout << as_string1(11) << endl;
    cout << as_string1(std::string("12")) << endl;
    cout << as_string1("13") << endl;
}
Wynik:
11 [is_arithmetic_v]
12 [is_same_v]
13 [!is_same_v && !is_arithmetic_v]
Inna wersja, gdzie enable_if pojawia się jako parametr szablonowy. Domyślne argumenty szablonowe, nie są częścią sygnatury funkcji szablonowej, trzeba więc do enable_if przekazać jeszcze dummy typ (int), nie wiem czemu trzeba przypisać do tego 0. Dziwny hack.
#include <iostream>
#include <type_traits>

using namespace std;

template<typename T, std::enable_if_t<std::is_arithmetic_v<T>,
                                      int> = 0>
std::string as_string2(T x) {
    return std::to_string(x) + " [is_arithmetic_v]";
}

template<typename T, std::enable_if_t<std::is_same_v<T, std::string>,
                                     int> = 0>
std::string as_string2(T x) {
    return x + " [is_same_v]";
}

template<typename T, std::enable_if_t<!std::is_same_v<T, std::string> && !std::is_arithmetic_v<T>,
                                      int> = 0>
std::string as_string2(T x) {
    return std::string(x) + " [!is_same_v && !is_arithmetic_v]";
}

int main() {
    cout << as_string2(21) << endl;
    cout << as_string2(std::string("22")) << endl;
    cout << as_string2("23") << endl;
}
Wynik:
21 [is_arithmetic_v]
22 [is_same_v]
23 [!is_same_v && !is_arithmetic_v]
Są jeszcze inne formy zapisu enable_if np. jako parametr funkcji, ale w tej chwili nie jest to istotne. W C++17 pojawił się ciekawy mechanizm if constexpr, który pozwala radzić sobie z dużą liczbą takich specjalizacji, a kod wygląda znacznie bardziej czytelnie.
#include <iostream>
#include <type_traits>

using namespace std;

template<typename T>
std::string as_string3(T x) {
    if constexpr(std::is_arithmetic_v<T>) {
         return std::to_string(x) + " [is_arithmetic_v]";
    } else if constexpr(std::is_same_v<T, std::string>) {
         return x + " [is_same_v]";
    } else {
         return std::string(x)  + " [!is_same_v && !is_arithmetic_v]";
    }
}

int main() {
    cout << as_string3(31) << endl;
    cout << as_string3(std::string("32")) << endl;
    cout << as_string3("33") << endl;
}
Wynik:
31 [is_arithmetic_v]
32 [is_same_v]
33 [!is_same_v && !is_arithmetic_v]

5 lutego 2020

[C++] problemy z rzutowaniem

Chociaż static_cast i dynamic_cast (i inne) w C++ miały być lepszą wersją "surowego" rzutowania znanego z języka C, nie rozwiązały wszystkich problemów. dynamic_cast można stosować tylko tam, gdzie mamy do czynienia z polimorfizmem, w dodatku angażując to RTTI (Run Time Type Information), które może zaważyć na czasie wykonania programu. static_cast z kolei, posiada niezdefiniowane zachowanie jeżeli próbujemy rzutować obiekt w dół hierarchii.

W przykładzie poniżej kompilator nie zaprotestuje, gdy zrzutujemy obiekt klasy Base na klasę Derived. Problem w tym, że obiekt base rezerwuje mniej pamięci (nie ma pola value_b) niż obiekt derived. W konsekwencji, pisane do pola value_b, będzie skutkowało pisaniem po pamięci.
#include <iostream>

using namespace std;

struct Base {
    void fun() { printf("Base method\n"); }
    int value_a;
};

struct Derived : public Base {
    void fun() { printf("Derived method\n"); }
    int value_b;
};


int main() {
    Base* base = new Base{};
    Derived* derived = static_cast<Derived*>(base); // no-error!

    derived->value_a = 1;
    derived->value_b = 2;       // pisanie po pamięci!

    cout << derived->value_a << endl;
    cout << derived->value_b << endl;
}
Tutaj dopisało nam szczęści, program wykonał się prawidłowo.
$ clang++ -std=c++17  main.cpp
$ ./a.out 
1
2
Sprawa wygląda inaczej, gdy dołączymy address sanitizer.
$ clang++ -std=c++17 -fsanitize=address main.cpp
$ ./a.out
==23018==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000014 at pc 0x0000004c63ba bp 0x7fff3301c9b0 sp 0x7fff3301c9a8
WRITE of size 4 at 0x602000000014 thread T0
...

Sanitizer potrafi wykryć tego typu problem, tylko gdy zaczynamy pisać po nie swojej pamięci. Naukowcy: Byoungyoung Lee, Chengyu Song, Taesoo Kim i Wenke Lee z Georgia Institute of Technology, stworzyli jeszcze inne narzędzie do detekcji tego typu problemów. Oparte na LLVM, dodaje do każdego static_cast tablicę z informacjami o hierarchii dziedziczenia (czyli coś w rodzaju tego co posiada dynamic_cast) i w zgrabny sposób informuje gdzie obiekt został stworzony i gdzie źle rzutowany, gdy tylko takie rzutowanie nastąpi. Za swoją pracę zostali nagrodzeni przez Facebooka fajną nagrodą pieniężną.

2 lutego 2020

[C++17] nowy if

Nowy standard wprowadził kilka nowych form zapisu instrukcji warunkowej "if". Jedna z nich będzie przydatna, gdy będziemy chcieli potwierdzić, że inicjalizacja zakończyła się sukcesem.
Stary zapis:
bool success = init(x);
if (success) {
    cout << "x new value: " << x << endl;
}
Nowy zapis ze średnikiem (od C++17):
if (bool success = init(x); success) {
    cout << "x new value: " << x << endl;
}
Nie widziałem niczego podobnego w innych językach, ale wydaje się całkiem eleganckie. Poniżej przykład z std::map::insert, który zwraca dwie wartości: iterator na element (świeżo wstawiony lub stary o tym samym kluczu) oraz flagę informującą czy wstawienia się powiodło.
#include <iostream>
#include <string>
#include <map>

using namespace std;

void insert_to_map(std::map<int, string>& m, std::pair<int, string> p) {
    if (auto [it, success] = m.insert(p); success) {
        cout << "success, new elem: " << it->first << " -> " << it->second << endl;
    } else {
        cout << "fail, old elem:    " << it->first << " -> " << it->second << endl;
    }
}

int main() {
    std::map<int, string> m = { {1, "aaa"} } ;

    auto b = std::make_pair(2, "bbb");
    insert_to_map(m, std::move(b));

    auto c = std::make_pair(1, "ccc");
    insert_to_map(m, std::move(c));

    for (const auto& v : m) {
        cout << v.first << " " << v.second << endl;
    }
}
Wynik:
success, new elem: 2 -> bbb
fail, old elem:    1 -> aaa
1 aaa
2 bbb