Многопоточное программирование
Литература
Стандарты C++
Контейнеры C++
Контейнеры STL
Контейнеры STL
Последовательные контейнеры STL
Ассоциативные контейнеры STL
Красно-черные деревья
Красно-черные деревья
Красно-черные деревья
B-деревья
B-деревья
Контейнеры-адаптеры STL
Псевдоконтейнеры STL
Последовательные контейнеры STL (C++11)
std::array vs. std::vector
std::forward_list
Хэш-таблицы STL (C++11)
Хэш-таблицы STL (C++11)
Хэш-таблицы STL (C++11)
boost::circular_buffer
boost::circular_buffer_space_optimized
Умные указатели
Умные указатели
Умные указатели
std::auto_ptr (C++03)
std::auto_ptr (C++03)
std::auto_ptr (C++03)
std::unique_ptr (C++11)
std::unique_ptr (C++11)
std::shared_ptr (C++11)
std::shared_ptr (C++11)
std::shared_ptr (C++11)
std::weak_ptr (C++11)
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
Аллокаторы
ccmalloc
ccmalloc
ccmalloc
ccmalloc
dmalloc
tcmalloc
Уплотнение памяти
Уплотнение памяти
Уплотнение памяти
Уплотнение памяти
Алгоритм Бейкера
Уплотнение на месте
Разобраться самостоятельно
0.96M
Category: programmingprogramming

Многопоточное программирование (Лекция 1). Стандарты C++, контейнеры C++, красно-черные деревья, B-деревья

1. Многопоточное программирование

Лекция №1
Многопоточное
программирование
Дмитрий Калугин-Балашов

2. Литература

Джеф Элджер. С++: Библиотека
пограммиста
Jeff Alger. C++ for Real Programmers
2

3. Стандарты C++

• C++98/C++03
• Boost
• C++11
• C++14
3

4. Контейнеры C++

• STL
• STL (C++11)
• Boost
4

5. Контейнеры STL

• Последовательные контейнеры
• Ассоциативные контейнеры
• Контейнеры-адаптеры
• Псевдоконтейнеры
5

6. Контейнеры STL

• Последовательные контейнеры
• Ассоциативные контейнеры
• Контейнеры-адаптеры
• Псевдоконтейнеры
6

7. Последовательные контейнеры STL


std::vector
std::list
std::deque
7

8. Ассоциативные контейнеры STL


std::set
std::map
std::multiset
std::multimap
8

9. Красно-черные деревья

9

10. Красно-черные деревья

1
0

11. Красно-черные деревья

http://www.youtube.com/v/vDHFF4wjWY
U
1
1

12. B-деревья

https://code.google.com/p/cppbtree/
1
2

13. B-деревья

• btree_set
• btree_map
• btree_multiset
• btree_multimap
1
3

14. Контейнеры-адаптеры STL

• std::stack
• std::queue
• std::priority_queue
1
4

15. Псевдоконтейнеры STL

• std::bitset
• std::basic_string
• std::valarray
1
5

16. Последовательные контейнеры STL (C++11)

• std::array
• std::forward_list
1
6

17. std::array vs. std::vector

• std::vector хранит все элементы в куче
• std::array хранит все элементы в себе
• std::array не может изменить свой размер
• std::array должен знать свой размер на
этапе компиляции
• std::array работает быстрее
1
7

18. std::forward_list

Итератор может двигаться только в одном направлении.
1. #include <iostream>
2. #include <forward_list>
3. int main ()
4. {
5.
std::forward_list<int> mylist = { 34, 77, 16, 2 };
6.
std::cout << "mylist contains:";
7.
for ( auto it = mylist.begin(); it != mylist.end(); ++it )
8.
std::cout << ' ' << *it;
9.
std::cout << '\n';
10. return 0;
11. }
1
8

19. Хэш-таблицы STL (C++11)

• std::unordered_set
• std::unordered_map
• std::unordered_multiset
• std::unordered_multimap
1
9

20. Хэш-таблицы STL (C++11)

2
0

21. Хэш-таблицы STL (C++11)

2
1

22. boost::circular_buffer

2
2

23. boost::circular_buffer_space_optimized

boost::circular_buffer_space_optimi
zed
2
3

24. Умные указатели

2
4

25. Умные указатели

Пример «самодельного» умного указателя.
1.
2.
3.
4.
5.
6.
7.
8.
9.
class PFoo {
private:
Foo* foo;
public:
PFoo() : foo(NULL) {}
PFoo(Foo* f) : foo(f) {}
operator Foo*() { return foo; }
Foo* operator->() { return foo; }
};
10.
11.
12.
13.
void f(Foo*);
PFoo pf(new Foo);
f(pf);
pf->MemberOfFoo();
2
5

26. Умные указатели

Пример «самодельного» умного указателя.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
template <class Type>
class SP {
private:
Type* pointer;
public:
SP() : pointer(NULL) {}
SP(Type* p) : pointer(p) {}
operator Type*() { return pointer; }
Type* operator->() { return pointer; }
};
11.
12.
13.
14.
void f(Foo*);
Ptr<Foo> pf(new Foo);
f(pf);
pf->MemberOfFoo();
2
6

27. std::auto_ptr (C++03)

2
7

28. std::auto_ptr (C++03)

Не
использовать!
2
8

29. std::auto_ptr (C++03)

Пример некорректного использования std::auto_ptr
1.
2.
3.
4.
5.
6.
7.
#include <memory>
int func()
{
std::auto_ptr<CFoo> PFoo1(new CFoo());
std::auto_ptr<CFoo> PFoo2;
PFoo2 = PFoo1;
}
2
9

30. std::unique_ptr (C++11)

Невозможность скопировать std::unique_ptr
1.
2.
3.
4.
5.
6.
7.
#include <memory>
int func()
{
std::unique_ptr<CFoo> PFoo1(new CFoo());
std::unique_ptr<CFoo> PFoo2;
PFoo2 = PFoo1; // Ошибка при компиляции
}
3
0

31. std::unique_ptr (C++11)

Перемещение std::unique_ptr
1.
2.
3.
4.
5.
6.
7.
#include <memory>
int func()
{
std::unique_ptr<CFoo> PFoo1(new CFoo());
std::unique_ptr<CFoo> PFoo2;
PFoo2 = std::move(PFoo1);
}
3
1

32. std::shared_ptr (C++11)

Пример использования std::shared_ptr
1.
2.
3.
4.
5.
6.
7.
#include <memory>
int func()
{
std::shared_ptr<CFoo> PFoo1(new CFoo());
std::shared_ptr<CFoo> PFoo2;
PFoo2 = PFoo1;
}
3
2

33. std::shared_ptr (C++11)

3
3

34. std::shared_ptr (C++11)

3
4

35. std::weak_ptr (C++11)

3
5

36. Аллокаторы

3
6

37. Аллокаторы

3
7

38. Аллокаторы

3
8

39. Аллокаторы

3
9

40. Аллокаторы

4
0

41. Аллокаторы

4
1

42. Аллокаторы

4
2

43. Аллокаторы

4
3

44. Аллокаторы

4
4

45. Аллокаторы

4
5

46. Аллокаторы

4
6

47. Аллокаторы

4
7

48. Аллокаторы

• malloc/calloc/realloc/free
• new/delete
• new[]/delete[]
4
8

49. Аллокаторы

• ccmalloc
• dmalloc
• tcmalloc
4
9

50. ccmalloc

Делаем утечки.
1. void Leak(char *inStr)
2. {
3.
char *str = (char *) malloc(strlen(inStr));
4.
memcpy(str, inStr, strlen(inStr));
5. }
6. char *AvoidLeak(char *inStr)
7. {
8.
char *str = (char *) malloc(strlen(inStr));
9.
memcpy(str, inStr, strlen(inStr));
10. return str;
11. }
5
0

51. ccmalloc

Функция main с утечками.
1. int main()
2. {
3.
char *str;
4.
5.
6.
7.
8.
9. }
Leak("This leaks 19 bytes");
str = AvoidLeak("This is not a 26 byte leak");
free(str);
str = AvoidLeak("12 byte leak");
exit(0);
5
1

52. ccmalloc

Результат ccmalloc (1).
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
* 61.3% = 19 Bytes of garbage
|
|
|
|
0x40047306 in
|
|
|
|
0x080493eb in
|
|
at
|
|
|
|
0x0804935c in
|
|
at
|
|
|
`-----> 0x08052fb7 in
|
at
allocated in 1 allocation
<???>
<main>
test1.c:20
<Leak>
test1.c:5
<malloc>
src/wrapper.c:318
5
2

53. ccmalloc

Результат ccmalloc (2).
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
|
* 38.7% = 12 Bytes of garbage allocated in 1 allocation
|
|
|
|
0x40047306 in <???>
|
|
|
|
0x0804941e in <main>
|
|
at test1.c:23
|
|
|
|
0x080493a4 in <AvoidLeak>
|
|
at test1.c:11
|
|
|
`-----> 0x08052fb7 in <malloc>
|
at src/wrapper.c:318
|
`-----------------------------------------------------5
3

54. dmalloc

Результат dmalloc.
1.
2.
3.
4.
5.
not freed: '0x45008' (12 bytes) from 'ra=0x1f8f4'
not freed: '0x45028' (12 bytes) from 'unknown'
not freed: '0x45048' (10 bytes) from 'argv.c:1077'
known memory not freed: 1 pointer, 10 bytes
unknown memory not freed: 2 pointers, 24 bytes
5
4

55. tcmalloc

Работает быстрее, чем malloc из glibc
LD_PRELOAD="/usr/lib/libtcmalloc.so"
5
5

56. Уплотнение памяти

5
6

57. Уплотнение памяти

5
7

58. Уплотнение памяти

5
8

59. Уплотнение памяти

5
9

60. Алгоритм Бейкера

6
0

61. Уплотнение на месте

6
1

62. Разобраться самостоятельно

• git
• make
6
2

63.

Спасибо за
внимание!
Дмитрий Калугин-Балашов
[email protected]
English     Русский Rules