28 września 2013

[gdb] - debugowanie wyjątków w C++

Kiedy wyjątek zostanie rzucony (i złapany), wszystkie zmienne na stosie zostaną zniszczone [link]. Może się to okazać kłopotliwe, jeżeli chcemy skorzystać z debuggera i odnaleźć przyczynę. GDB oferuje przydatną komendę "catch throw", która zatrzymuje program w momencie rzucenia wyjątku. W ten sposób można podglądnąć oryginalne zmienne na stosie.
#include <iostream>

void test() {
    int a = 5;
    throw std::exception();
}

int main() {
    test();
    return 0;
}
Program niespodziewanie zakończył swoje działanie.
terminate called after throwing an instance of 'std::exception'
  what():  std::exception
The program has unexpectedly finished.
Deguggowanie za pomocą GDB.
$ g++ -g main.cpp
$ gdb a.out

(gdb) catch throw
Catchpoint 1 (throw)
(gdb) r
Starting program: /home/beru/cpp_throw_test/a.out 
Catchpoint 1 (exception thrown), 0xb7f247c0 in __cxa_throw ()
   from /usr/lib/i386-linux-gnu/libstdc++.so.6
(gdb) bt
#0  0xb7f247c0 in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#1  0x080486f8 in test () at main.cpp:5
#2  0x08048703 in main () at main.cpp:9
(gdb) f 1
#1  0x080486f8 in test () at main.cpp:5
5     throw std::exception();
(gdb) p a
$1 = 5

24 września 2013

[C++] Usuwanie elementów z mapy o zadanej wartości

Problem nad, którym od dawna się zastanawiałem, a mianowicie jak najlepiej usunąć elementy o zadanej wartości z mapy. Miałem nadzieje na wykorzystanie, jakiegoś wbudowanego w standard mechanizmu/algorytmu, albo chociaż czegoś z biblioteki boost - niestety. Wyniki poszukiwań poniżej.

Na pierwszy ogień poszedł std::remove_if(), niestety problemem jest tu w jaki sposób mapy przechowują swoje elementy. std::map<K,V>::value_type jest parą std::pair<const K, V>. std::remove_if() przesuwa elementy do usunięcia w taki sposób, że zostają one nadpisane. Ponieważ nie można przypisywać do const, std::remove_if() nie nadaje się do zastosowania na mapach. Wykorzystałem go jednak w zwykłej metodzie nib::erase_if() [linia 21], gdyż świetnie nadaje się dla zwykłych kontenerów. Wątek na stackoveflow, który traktuje o tym problemie:
Z tego co udało mi się wyszukać innym, częstym rozwiązaniem jest skorzystanie z std::remove_copy_if(). Tym razem wszystkie elementy, które nie spełniają naszego kryterium są kopiowane do nowej mapy. Jeżeli mapa jest sporych rozmiarów, a elementów do usunięcia jest stosunkowo dużo, to minusem rozwiązaniem będzie niepotrzebne chwilowe zwiększenie zapotrzebowanie na pamięć. Działanie tego algorytmu zostało zawarte w metodzie nib_test::erase_if() [linia 47].

Ostatnie i najbardziej preferowane rozwiązanie - nib::erase_if [linia 27], to napisanie własnego algorytmu, który podejmie się tego zadania. Szkoda, że nie udało się niczego takiego zaadoptować (albo jeszcze nie znalazłem) w bibliotece standardowej albo w innych popularnych bibliotekach (np. boost).
Po odnalezieniu elementów o zadanej wartości zostaną one usunięty za pomocą metody std::map::erase(). Dobra wiadomość jest taka, że std::map::erase(), unieważnia jedynie referencje i iteratory do usuwanego elementu, pozostałe referencje i iteratory w mapie są nadal ważne: Dwa wątki traktujące o tym rozwiązaniu:
Jak informuje autor, jednego z rozwiązań, w przypadku skorzystania z zapisu "erase(it++)", standard gwarantuje, że wszystkie wyrażenia argumentów, będą wykonane przed wywołaniem funkcji. Prosta inkrementacja zostanie wykonany przed wywołaniem funkcji std::map::erase(), a do niej zostanie przekazana wartość jeszcze niezainkrementowana.
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>

template <typename Key, typename Value>
std::ostream& operator<<(std::ostream& out, const std::pair<Key, Value>& p) {
    return out << "[" << p.first << "]" << "=" << p.second;
}

template <typename Container>
void print_container(const Container& container) {
    for(const auto& v : container)
        std::cout << v << std::endl;
}

namespace nib
{

template <typename Container, typename Predicate>
void erase_if(Container& container, const Predicate& predicate) {
    container.erase(std::remove_if(begin(container), end(container), predicate),
                    end(container));
}

template <typename Key, typename Value, typename Predicate>
void erase_if(std::map<Key, Value>& dict, const Predicate& predicate) {
    auto it = begin(dict);
    while(it != end(dict)) {
        if (predicate(*it)) {
            // Standard zapewnia, ze it++ zostanie obliczone, zanim samo "it"
            // zostanie przekazane do funkcji
            dict.erase(it++);
        }
        else {
            ++it;
        }
    }
}

} // namespace nib

namespace nib_test
{

template <typename Key, typename Value, typename Predicate>
void erase_if(std::map<Key, Value>& dict, const Predicate& predicate) {
    typedef typename std::remove_reference<decltype(dict)>::type Map;
    Map tmp;
    std::remove_copy_if(begin(dict), end(dict),
                        std::inserter(tmp, begin(tmp)),
                        predicate);
    dict = tmp;
}

} // namespace nib_test

int main() {
    std::vector<int> vec { 1, 2, 1, 4, 1, 5 };
    auto val_to_erase = [] (int& v) { return v == 1; };
    nib::erase_if(vec, val_to_erase);
    print_container(vec);

    typedef std::map<int, std::string> Dict;
    Dict dict { {1, "a"}, {2, "b"}, {3, "c"}, {7, "b"} };

    auto val_to_erase_in_map = [] (typename Dict::value_type& v) { return v.second == "b"; };
    nib::erase_if(dict, val_to_erase_in_map);
//  nib_test::erase_if(dict, val_to_erase_in_map);
    print_container(dict);

    return 0;
}
Wyniki:
2
4
5
[1]=a
[3]=c
Aby się upewnić co do kosumpcji pamięci przez oba rozwiązania, przeprowadziłem prostą weryfikacją za pomocą valgrinda.
int main() {
    typedef std::map<int, std::string> Dict;
    Dict dict { {1, "a"}, {2, "b"}, {3, "c"}, {7, "b"} };

    for(int i = 0; i < 10000; ++i)
        dict.insert(std::make_pair(5000 + i, "x"));
//      dict.emplace(5000 + i, "x"); - Nie dziala w GCC 4.7!!!

    auto val_to_erase_in_map = [] (typename Dict::value_type& v) { return v.second == "b"; };
//  nib::erase_if(dict, val_to_erase_in_map);
    nib_test::erase_if(dict, val_to_erase_in_map);
    print_container(dict);

    return 0;
}
Wersja nib::erase_if(), odnotowała peak na poziomie 558272 bajtów, natomiast dla nib_test::erase_if() (korzystająca z std::remove_copy_if()) peak ten wynosił 874376 bajty.

5 września 2013

[C++11] std::shared_ptr vs std::make_shared

Od wielu osób, słyszałem o wyższości stosowania dedykowanych metod w celu tworzenia inteligentnych wskaźników. Nadszedł czas przyjrzeć się tym dwóm mechanizmom bliżej, jak zawsze na bazie własnych testów, by ze świadomością móc korzystać z ich dobrodziejstw.

Swoje przemyślenia oparłem na "C++ Primer" oraz na artykule Herba Shuttera:

Kilka punktów, które mogą okazać się pomocne w przyszłości.
  • std::unique_ptr powinien być zawsze preferowany przed std::shared_ptr
  • std::shared_ptr i std::unique_ptr powinno być wybierane, tylko gdy chcemy skorzystać z własnego deletera (std::make_shared tego nie umożliwia), albo gdy adaptujemy stary kod i chcemy zarządzać surowym wskaźnikiem.
  • W innych przypadkach powinno się korzystać z std::make_unique i std::make_shared.
Zalety:
  • Upraszcza to kod. W jednej instrukcji zawarte jest tworzenie inteligentnego wskaźnika i chowany jest new (std::shared_ptr + new), który może rzucać trudne do wykrycia wyjątki. std::make_shared nas przed tym chroni (w C++17 został zmieniony sposób ewaluacji argumentów funkcji i nie jest to już problemem).
  • std::make_shared daje istotne optymalizacyjne usprawnienia. std::shared_ptr jedynie tworzy wskaźnik na zasób którym ma zarządzać (który zostanie stworzony przez new) i nie wie, czy to co mu podlega zostało stworzone specjalnie dla niego, czy ma do czynienia z surowym wskaźnikiem. Zasób taki będzie najprawdopodobniej w innym bloku pamięci + kompilator jak zawsze doda kilka ekstra bajtów, przy alokowaniu.
Wady:
  • Nie testowałem, aczkolwiek ma to sens. Ponieważ std::make_shared stworzy obiekt, a także reference counters w jednym bloku pamięci, pamięć taka będzie zwolniona dopiero, gdy nie będzie już żadnych std::weak_ptr wskazujących na ten obiekt. Tworzenie obiektu za pomocą std::shared_ptr ma tu taką przewagę, że będzie mógł on zwolnić zasób, którym zarządza i pozostawić przy życiu jedynie reference counters dla std::weak_ptr. Jeżeli zarządzany obiekt będzie duży, może się to odbić na wydajności.
std::make_shared zatroszczy się o to by wszystko zostało stworzone po kolei (ładnie to ilustrują obrazki zamieszczone przez Herba Shutter na jego stronie).
Dla dużej ilości małych obiektów, może to istotne przyśpieszyć działanie programu, ponieważ zmniejsza się czas dostępu do cache procesora. Właśnie to chciałem przetestować w swoim teście.
#include <iostream>
#include <memory>
#include <boost/date_time/posix_time/posix_time.hpp>

using namespace boost::posix_time;

struct MyObject {
    MyObject(std::string n): name(n) { }
    std::string name;
};

void fun(const std::shared_ptr<MyObject> &sp) {
    if (sp->name == "xxx")
        std::cout << "xxx" << std::endl;
}

int main() {
    const ptime time_start = microsec_clock::local_time();

    for (int i = 0; i < 100000000; ++i) {
#ifdef TEST_SHARED_PTR
        fun(std::shared_ptr<MyObject>(new MyObject("shared")));
#else
        fun(std::make_shared<MyObject>("make_shared"));
#endif
    }

    const ptime time_stop = microsec_clock::local_time();
    std::cout << "Time: " << time_start - time_stop << std::endl;

    return 0;
}
Kompilacja.
$ g++ main.cpp -std=c++11 -O2 -DTEST_SHARED_PTR
Poniżej zestawienie wyników dla gcc i clang-a. Zrobiłem też testy bez użycia flag optymalizacyjnych (-O2) i co ciekawe wyniki były zupełnie odwrotne! Nie wynikałem już w przyczynę tego stanu rzeczy. Może kiedyś rozwikłam tą zagadkę.

3 września 2013

Lista pomocnych wtyczek do Firefoxa

Aby mi nie wyparowało, postanowiłem stworzyć sobie małą listę przydatnych wtyczek, które może nie ułatwiają codziennej pracy, ale na pewno są pomocne, w szczególnych zastosowaniach.

Dodatek pozwalający oszukać/ustawić wartość, document.referrer (JavaScript).
  • https://addons.mozilla.org/pl/firefox/addon/refcontrol/

  • Bardzo popularny dodatek. Pozwala testować JavaScript, przekopać się w poszukiwaniu interesujących treści na stronie itd.
  • https://addons.mozilla.org/pl/firefox/addon/firebug/

  • Jedna z kilku wtyczek, którą testowałem, ale tylko w tej doszedłem do tego jak można zaciągnąć film z Facebook-a.
  • https://addons.mozilla.org/pl/firefox/addon/netvideohunter-video-downloade/
  • 1 września 2013

    [C++11] Dynamiczna pamięć (new + inteligentne wskaźniki)

    Nowy standard, dostarczy kilka mechanizmów pozwalających lepiej radzić sobie z zarządzaniem obiektami w pamięci dynamicznej. Prócz nowości, opisałem kilka już istniejących mechanizmów, które zawsze wylatują mi z głowy.

    new


    Operator new, umożliwia nie tylko alokowanie pamięci pod nowo tworzone obiekty, ale również pod wskazany przez nas (wcześniej zaalokowany) obszar pamięci.
    #include <iostream>
    
    int main() {
        int int_in_memory = 5;
        std::cout << "Memory (val)  " << int_in_memory << std::endl;
        std::cout << "Memory (addr) " << &int_in_memory << std::endl;
    
        int *ptr = new (&int_in_memory) int(2);
        std::cout << "Ptr    (val)  " << *ptr << std::endl;
        std::cout << "Ptr    (addr) " << ptr << std::endl;
    
        return 0;
    }
    
    W takim przypadku, new zawsze zwróci ten sam adres, który został mu przekazany. Nie można łączyć tego rodzaju inicjalizacji z nothrow (wersja która nie rzuca wyjątku)
    Memory (val)  5
    Memory (addr) 0xbf9c26f8
    Ptr    (val)  2
    Ptr    (addr) 0xbf9c26f8
    
    Każda pamięć jawnie zaalokowana przez nas musi być później zwolniona. W przypadku tablic trzeba użyć specjalnej formy delete [], aby wywołać destruktory obiektów, które się w niej znajdują.
    #include <iostream>
    
    struct MyObject {
        MyObject(std::string n): name(n) { std::cout << "Constructor: " << name << std::endl; }
        ~MyObject() noexcept { std::cout << "Destructor:  " << name << std::endl; }
        std::string name;
    };
    
    int main() {
        MyObject *tab = new MyObject[3] { {"Elem1"},
                                          {"Elem2"},
                                          {"Elem3"} };
    
        delete tab;
    //  delete [] tab;
    
        return 0;
    }
    
    Jeżeli skorzystamy ze zwykłego delete, bez podania pustych nawiasów, zachowanie jest niezdefiniowane.
    Constructor: Elem1
    Constructor: Elem2
    Constructor: Elem3
    Destructor:  Elem1
    The program has unexpectedly finished.
    
    Nowy standard dodaje, wersje operatora new z nothrow i w razie wystąpienia błędu przy inicjalizacji pamięci zamiast wyjątku operator zwróci nullptr, aby poinformować nas o problemie.
    #include <iostream>
    #include <memory>
    
    int main() {
        try {
            int *ptr = new int[1000000000];
        }
        catch (std::bad_alloc& exception) {
            std::cout << "Exception: " << exception.what() << std::endl;
        }
    
        int *ptr = new (std::nothrow) int[1000000000];
        if (ptr == nullptr)
            std::cout << "Not allocated" << std::endl;
    
        return 0;
    }
    
    Poniżej wyniki działania programu, w pierwszej wersji zwracany jest wyjątek, w drugiej jesteśmy informowani przez zwrócenie nullptr.
    Exception: std::bad_alloc
    Not allocated
    
    Co ciekawe, rzadko można w kodzie zauważyć sytuacje, gdy programista próbuje przestrzec się przed tego typu zdarzeniami (blok try-catch). W Linuxie jest to związane z domyślnie włączonym mechanizmem "opportunistic memory allocation", który nie sprawdza, czy pamięć jest dostępna gdy próbujemy ją zaalokować. W momencie, gdy próbujemy się do niej odwołać, a w systemie jej zabraknie program zostaje zterminowany. Ustawienie można sprawdzić przez:
    cat /proc/sys/vm/overcommit_memory
    0
    

    smart pointers


    W standardzie pojawiły się nowe inteligentne wskaźniki, zaczerpnięte z biblioteki boost. Są to unique_ptr (zdaje się odpowiednik boost::scoped_ptr), shared_ptr oraz weak_ptr. Herb Shutter daje kilka porad, odnośnie tego jaki i kiedy je stosować.
    Można to podsumować w ten sposób. W nowoczesnym C++ zawsze powinno się używać inteligentnych wskaźników oraz surowych wskaźników nie posiadających prawa własności. unique_ptr powinno być preferowane nad shared_ptr (zawsze można będzie na niego przejść, jeżeli nasz zasób będzie musiał być współdzielony między komponentami o różnym czasie życia, albo gdy chcemy skorzystać z własnej metody do usunięcia zasobu z pamięci). Poniżej program, w którym m.in. shared_ptr, korzysta z funkcji "usuwającej" zasób z pamięci dostarczonej przez nas.
    #include <iostream>
    #include <memory>
    
    struct MyObject {
        MyObject(std::string n): name(n) { std::cout << "Constructor: " << name << std::endl; }
        ~MyObject() noexcept { std::cout << "Destructor:  " << name << std::endl; }
        std::string name;
    };
    
    void myDeleter(MyObject* p) {
        std::cout << "Deleter:     " << p->name << std::endl;
    }
    
    int main() {
        std::shared_ptr<MyObject> sha(new MyObject("shared"), myDeleter);
    
        std::unique_ptr<MyObject> uni1(new MyObject("unique"));
        std::unique_ptr<MyObject> uni2(uni1.release());
    
        std::cout << "Uni1 -> " << (uni1 ? "exist" : "not exist") << std::endl;
        std::cout << "Uni2 -> " << (uni2 ? "exist" : "not exist") << std::endl;
    
        auto store = std::make_shared<MyObject>("weak");
        std::weak_ptr<MyObject> wea(store);
    
        if (std::shared_ptr<MyObject> sp = wea.lock())
            std::cout << "Locked:      " << sp->name << std::endl;
    
        return 0;
    }
    
    A oto kolejność wywołania destruktorów dla dynamicznie stworzonych zasobów.
    Constructor: shared
    Constructor: unique
    Uni1 -> not exist
    Uni2 -> exist
    Constructor: weak
    Locked:      weak
    Destructor:  weak
    Destructor:  unique
    Deleter:     shared
    
    Shutter (i nie tylko) zaleca tworzenie inteligentnych wskaźników za pomocą metod make_*. Ale to postanowiłem przetestować sobie w innym wpisie.

    std::allocator


    Ostatnią rzeczą, którą testowałem są alokatory. Pozwalają nam one na odseparowanie procesu alokowania od konstruowania. W przykładzie poniżej, szykujemy pamięć pod trzy elementy typu MyObject. Najpierw pamięć jest alokowana, a my uzyskujemy wskaźnik pod adres, gdzie powinien być skonstruowany pierwszy z naszych obiektów. Następnie korzystają z metody construct(), oraz przesuwając wskaźnik następuje proces konstruowania. Aby zniszczyć obiekt, należy skorzystać z metody destroy().
    #include <iostream>
    #include <memory>
    
    
    struct MyObject {
        MyObject(std::string n): name(n) { std::cout << "Constructor: " << name << std::endl; }
        ~MyObject() noexcept { std::cout << "Destructor:  " << name << std::endl; }
        std::string name;
    };
    
    int main() {
        std::allocator<MyObject> alloc;
        std::cout << "Allocate" << std::endl;
        MyObject *ptr = alloc.allocate(3);
    
        std::cout << "Address:     " << ptr << std::endl;
        alloc.construct(ptr, "Elem1");
    
        ptr++;
        std::cout << "Address:     " << ptr << std::endl;
        alloc.construct(ptr, "Elem2");
    
        return 0;
    }
    
    Wynik działania.
    Allocate
    Address:     0x8b2a008
    Constructor: Elem1
    Address:     0x8b2a00c
    Constructor: Elem2