С++ Интересные фишки
Добавлено: Чт, 7 августа 2014, 10:04:59
Просмотр ассемблерного кода компиляторов.
https://godbolt.org/
https://godbolt.org/
http://freehabr.ru/blog/cpp/1757.html
- Спойлер
- С++
Для незнакомых с этой очень интересной тематикой советую посмотреть обзор на вики. Для более полного понимания проблемы: детальный обзор у Кнута в 1 томе Искусство программирования в разделе 2.5 Динамическое выделение памяти, на хабре, а также одну из лучших реализаций на C/C++ Hans Boehm.
Сразу оговорюсь, предлагаемый мною подход принципиально отличается от вышеизложенных и основан на реализации ООП в C++. В топики приведено описание готовой библиотеки и ссылка на исходники.
Основные положения
Вот цитата из ссылки на вики: Сборщик мусора может нормально функционировать только тогда, когда он может точно отследить все ссылки на все созданные объекты. Очевидно, если язык допускает преобразование ссылок (указателей) в другие типы данных (целые числа, массивы байтов и так далее), такой как Си/Си++, отследить использование таких преобразованных ссылок становится невозможно, и сборка мусора становится бессмысленной — она не защищает от «повисания» ссылок и утечек памяти. Поэтому языки, ориентированные на использование сборки мусора, обычно существенно ограничивают свободу использования указателей, адресной арифметики, преобразований типов указателей к другим типам данных. В части из них вообще нет типа данных «указатель», в части он есть, но не допускает ни преобразований типа, ни изменения.
Я предлагаю следующую альтернативу, ограничить использование указателей внутри класса C++ объявив их в закрытой области видимости. При правильной технологии ООП, а это свойство называется инкапсуляцией, это и так надо делать, пользователь не должен видеть как реализован класс, он должен использовать только его интерфейс. Во-вторых, в C++ имеется выделенный конструктор копирования, который позволяет построить копию объекта. Осталось для выбранного класса определить функцию swap, для подмены объекта на его копию, и можно организовывать «сборку мусора» на C++.
Пример использования
Рассмотрим простейший класс с динамическим выделением памяти, линейный однонаправленный список целых чисел.
01 #include "allocator.h"
02
03 class List {
04 struct Node {
05 int mData;
06 Node* mNext;
07
08 Node(int data, Node* next=NULL):
09 mData(data),
10 mNext(next) {
11 }
12 ~Node() {}
13 };
14
15 Allocator* mAllocator;
16 Node* mHead;
17
Основное отличие от обычного кода строчка 15, где содержится объявление переменной указателя на тип Allocator. В строках 23 и 27 показано его использование для выделения и освобождения памяти. Освобождение использует шаблонную функцию, поскольку перегрузку стандартого delete дополнительными аргументами позволяют не все компиляторы C++. Для базовых типов и классов, для которых в принципе не нужен вызов деструктора, определена шаблонная функция dealloc. Destroy и dealloc могут также дополнительно вызываться с дополнительным целочисленным аргументом для удаления массивов.
18 public:
19 List(Allocator *allocator):
20 …
21 List(const List& a, Allocator *allocator):
22 …
23 *mLink = new(mAllocator) Node(i, *mLink);
24 …
25 Node* tmp=*mLink;
26 *mLink = tmp->mNext;
27 mAllocator->destroy(tmp);
28 …
29 void swap(List &a) {
30 Allocator *tmp1=mAllocator;
31 mAllocator = a.mAllocator;
32 a.mAllocator = tmp1;
33
34 Node* tmp2 = mHead;
35 mHead = a.mHead;
36 a.mHead = tmp2;
37 }
38 …
39 };
В строчках 21 и 29 содержатся заголовки конструктора-копирования и функции swap, которые необходимы для замены текущего объекта на его копию. Если Вы хотите для своего класса использовать оператор =, то его тоже необходимо реализовать. Он, как известно, не наследуется, но поддержка в классе шаблона GC имеется.
Ниже дан пример его использования. На строке 41 объявляем новый тип GCList. Затем вызываем на строке 43 конструктор по умолчанию. Предположим на строке 44 производим массовые операции по выделению/освобождению памяти. Память выделяется блоками, кратными размеру страницы памяти, затем раздается внутри конкретного объекта класса List. Если процент не используемой памяти высок, то вызов reallocate на строке 45 приведет к построению копии объекта, с его последующей заменой на первоначальную переменную a.
40
41 typedef GC<List> GCList;
42 …
43 GCList a;
44 …
45 a.reallocate();
46 …
47
Естественно, вызов reallocate может происходит неоднократно, согласуясь с логикой программы. Также, за счет показанных в следующем разделе очень простых решений попутно выполняются учет работы времени GC, текущая память, максимальная память и в debug версии программы проверки на утечки памяти.
Выделение памяти большими блоками очень выгодно, особенно для большего количества мелких объектов. Стандартные new, delete, malloc, free должны хранить на каждое выделение информацию о начале и конце куска памяти. В данном подходе этого не нужно, поскольку конкретный объект может с помощью конструктора-копирования построить свою копию и обратно очистить используемую память.
Замечу, что предлагаемый подход, позволяет собирать объект из «кирпичиков» с общим Allocator-ом. Лишь бы в каждом инкапсулированом объекте память выделялась/освобождалась с помощью указателя на общий Allocator и были определены, соответствующие конструкторы-копирования и функция swap.
Можно также, как показано ниже, определять Allocator вначале блока и затем его использовать для работы с автоматическими переменными, использующими Allocator. После закрытия блока вся занятая ими память будет возвращена в систему.
{
Allocator a[1];
…
List lst(a);
…
}
Одной из причин, побудивших меня написать такую библиотеку, было заманчивое предложение использовать в качестве менеджера памяти следующей реализации Google. Мои первые тесты сразу показали ускорение на 10-20%, но сразу пришло и разочарование. При многих плюсах самой библиотеки, оказалось, что ускорение достигается за счет вынесения выделения памяти в отдельные потоки и если все процессоры были заняты, то ускорения практически не было. Предлагаемый подход лишен этого недостатка. Память в нем выделяется блоками, а затем уже раздается внутри объекта, поэтому при распараллеливании программы резко снижается количество обращений к глобальной памяти и его менеджеру. Т.е. уменьшается количество переключений между потоками.
Здесь приведены времена работы GC на разных примерах для задачи построения базисов Грёбнера булевых полиномов, которые решают SAT — задачи. Например, использование стандартных malloc и free замедлило, по сравнению с предлагаемым подходом, время расчета примера ezfact32_4.shuffled.cnf c 354.57 сек («сборка мусора» +1.31 сек) до 669.32 сек. В проекте много динамических структур данных и все они используют эту реализацию GC: мономы (в виде массивов номеров переменных разной длины), всевозможные списки, красно-черные деревья, деревья Janet и ZDD-диаграммы.
Ссылка на исходники. Следующий раздел описывает, если интересно, подробности реализации.
Технические детали
В приведенных ниже листингах приведены наглядные комментарии и я думаю не трудно понять, при чтении, основные элементы реализации. Для простоты в коде удаленно использование таймера и код ответственный за переключение на стандартные malloc, free.
01 #include <cstdlib>
02 #include <cassert>
03
04 class Allocator {
05 static size_t sCurrMemory; // Текущая память
06 static size_t sMaxMemory; // Максимальная память
07
08 struct Node {
09 void* mPointer; // Указатель на блок памяти
10 Node* mNext; // Следующий блок памяти
11
12 Node(size_t size, Node* next=NULL):
13 mPointer(malloc(size)),
14 mNext(next) {
15 }
16 ~Node() { free(mPointer); }
17 };
18
19 size_t mAlloc; // Выделенная память
20 size_t mSize; // Используемая память
21 Node* mRoot; // Список блоков памяти
22 size_t mNodeAlloc; // Выделенная память для последнего блока
23 size_t mNodeSize; // Используемая память для последнего блока
24
25 public:
26 static size_t maxMemory() { return sMaxMemory; }
27 static size_t currMemory() { return sCurrMemory; }
28
29 Allocator();
30 Allocator(const Allocator& a);
31 ~Allocator();
32
33 void* allocate(size_t n); // низкоуровневое выделение памяти
34 void deallocate(void* ptr, size_t n); // низкоуровневое освобождение памяти
35
36 template <typename T>
37 inline void dealloc(T *ptr) { // освобождение памяти
38 deallocate(ptr, sizeof(T));
39 }
40 template <typename T>
41 inline void dealloc(T *ptr, size_t n) { // освобождение памяти для массива
42 assert(n > 0);
43 deallocate(ptr, sizeof(T)*n);
44 }
45 template <typename T>
46 inline void destroy(T *ptr) { // освобождение памяти с вызовом деструктора
47 ptr->~T();
48 deallocate(ptr, sizeof(T));
49 }
50 template <typename T>
51 inline void destroy(T *ptr, size_t n) { // освобождение памяти с вызовом деструктора для массива
52 assert(n > 0);
53 for(int i=0; i < n; i++)
54 ptr[i].~T();
55 deallocate(ptr, sizeof(T)*n);
56 }
57
58 size_t alloc() const { return mAlloc; }
59 size_t size() const { return mSize; }
60 bool isGC() const; // возвращает true если нужно делать "сборку мусора"
61 };
62
Вспомогательный класс на строке 63, нужен только потому, что вызов конструктора наследуемого класса происходит раньше, чем для полей конструируемого класса, а деструкторов в обратном порядке. Другими словами конструктор AllocatorPtr будет вызван первым при создании класса GC, а его деструктор соответственно последним.
Кстати, этот пример показывает для чего нужно множественное наследование. А так пришлось бы вводить промежуточный класс, тем самым излишне усложняя код.
63 class AllocatorPtr { // Вспомогательный класс
64 Allocator* mAllocator;
65
66 public:
67 AllocatorPtr():
68 mAllocator(new Allocator) {
69 }
70 AllocatorPtr(const AllocatorPtr& a):
71 mAllocator(new Allocator(*a.mAllocator)) {
72 }
73 ~AllocatorPtr() { delete mAllocator; }
74
75 const Allocator* allocator() const { return mAllocator; }
76 Allocator* allocator() { return mAllocator; }
77
78 void swap(AllocatorPtr& a) {
79 Allocator *tmp=mAllocator;
80 mAllocator = a.mAllocator;
81 a.mAllocator = tmp;
82 }
83 };
84
85 template <typename T>
86 class GC: protected AllocatorPtr, public T {
87 public:
88 GC():
89 AllocatorPtr(),
90 T(allocator()) {
91 }
92 GC(const GC &a):
93 AllocatorPtr(a),
94 T(a, allocator()) {
95 }
96 GC(const T &a):
97 AllocatorPtr(),
98 T(a, allocator()) {
99 }
100 ~GC() {}
101
102 void operator=(const GC &a) {
103 assert(this != &a);
104 T::operator=(a);
105 }
106 void swap(GC &a) {
107 AllocatorPtr::swap(a);
108 T::swap(a);
109 }
110 void reallocate() {
111 if (allocator()->isGC()) {
112 GC a(*this);
113 swap(a);
114 }
115 }
116
117 size_t alloc() const { return allocator()->alloc(); }
118 size_t size() const { return allocator()->size(); }
119 bool isGC() const { return allocator()->isGC(); }
120 };
121
122 using namespace std;
123
124 inline void* operator new(size_t size, GInv::Allocator* allocator) {
125 return allocator->allocate(size);
126 }
127
128 inline void* operator new[](size_t size, GInv::Allocator* allocator) {
129 return allocator->allocate(size);
130 }
131
Здесь реализация в файле allocator.cpp
01 #include "allocator.h"
02
03 const size_t memoryPageSize=4096; // размер страницы
04
05 Allocator::Allocator():
06 mAlloc(0),
07 mSize(0),
08 mRoot(NULL),
09 mNodeAlloc(0),
10 mNodeSize(0) {
11 }
12
13 Allocator::Allocator(const Allocator& a):
14 mAlloc(0),
15 mSize(0),
16 mRoot(NULL),
17 mNodeAlloc(0),
18 mNodeSize(0) {
19 mNodeAlloc = memoryPageSize;
20 mAlloc = mNodeAlloc;
21 mRoot = new Node(mNodeAlloc);
22 sCurrMemory += mNodeAlloc;
23 sMaxMemory = (sMaxMemory > sCurrMemory) ? sMaxMemory: sCurrMemory;
24 }
25
26 Allocator::~Allocator() {
27 assert(mSize == 0);
28 sCurrMemory -= mAlloc;
29 while(mRoot) { // очистка списка блоков памяти
30 Node *tmp = mRoot;
31 mRoot = mRoot->mNext;
32 delete tmp;
33 }
34 }
35
36 void* Allocator::allocate(size_t n) {
37 assert(n > 0);
38 if (mNodeSize + n > mNodeAlloc) { // если памяти в текущем блоке мало
39 mNodeAlloc = ((n + memoryPageSize) / memoryPageSize)*memoryPageSize;
40 mAlloc += mNodeAlloc;
41 mRoot = new Node(mNodeAlloc, mRoot);
42 mNodeSize = 0;
43 sCurrMemory += mNodeAlloc;
44 sMaxMemory = (sMaxMemory >= sCurrMemory) ? sMaxMemory: sCurrMemory;
45 }
46 assert(mNodeSize + n <= mNodeAlloc);
47 void *r=(char*)mRoot->mPointer + mNodeSize;
48 mSize += n;
49 mNodeSize += n;
50 return r;
51 }
52
53 void Allocator::deallocate(void*, size_t n) {
54 assert(n > 0);
55 assert(mSize >= n);
56 mSize -= n;
57 }
58
59 bool Allocator::isGC() const { // чисто эмпирические соображения
60 return mAlloc > memoryPageSize && mAlloc > mSize*2;
61 }
Переопределение new и delete и глюки при вызове из .NET
http://habrahabr.ru/post/99142/
- Спойлер
- Проблема глобального переопределения new/delete в C++/CLI
C++*
Как известно, C++ позволяет глобально переопределять операторы new и delete. Обычно такое переопределение используется для диагностики, поиска утечек памяти и более эффективного распределения памяти.
Все это мы используем в нашем крупном проекте. Однако у нас есть часть, написанная на C#, которая с помощью C++/CLI взаимодействует с основной частью на C++. И вот тут появились проблемы. У нас получались утечки памяти там, где их быть ну никак не могло.
Все сводилось к тому, что вызывался наш new, но delete был crt’шный.
Чтобы разобраться с проблемой, я создал тестовый solution, где смоделировал ситуацию. Для простоты переопределенные функции выглядят так:
void* __cdecl operator new( size_t size )
{
printf("New\n");
return malloc(size);
}
void __cdecl operator delete( void *p )
{
printf("Delete\n");
free(p);
}
Значит, мы должны получить одинаковое количество New и Delete в выводе, равное количеству пар new/delete.
Вот код, который вызывает new/delete:
//managed.h
namespace Managed
{
public ref class ManagedClass
{
public:
ManagedClass()
{
NativeClass* cl = new NativeClass();
delete cl;
int* a = new int();
delete a;
}
};
}
//native.cpp
NativeClass::NativeClass()
{
int* a = new int();
delete a;
}
Из C# мы создаем ManagedClass так:
static void Main( string[] args )
{
ManagedClass cl = new ManagedClass();
}
Еще есть класс Foo, который лежит в отдельном файле basic.h, причем он никак не используется в этих классах. Просто его определение помещается в Precompiled Header.
Этот “плохой” класс не несет функциональности, однако одно наличие его приводит к очень странному результату. Если комментируешь конструктор копирования класса, то все работает отлично:
#pragma once
class Foo
{
public:
Foo() {}
//Foo( const Foo& ) {}
Foo& operator = ( const Foo& ) { return *this; }
virtual ~Foo() {}
};
Вывод:
New
New
Delete
Delete
New
Delete
3 new – 3 delete. Все хорошо.
Если же конструктор копирования не закомментирован, то не всем нашим new соответствует наш delete:
#pragma once
class Foo
{
public:
Foo() {}
Foo( const Foo& ) {}
Foo& operator = ( const Foo& ) { return *this; }
virtual ~Foo() {}
};
Вывод:
New
New
Delete
New
3 new – 1 delete. Все плохо.
Итог: мы имеем ошибку выбора функции удаления, которая зависит от “положения луны”. Самое время начать гуглить.
В ходе поисков был найден документ, предположительно описывающий нашу проблему:
http://support.microsoft.com/kb/122675.
К сожалению, после детального прочтения документа, выясняется, что наш случай отличается от рассмотренного. Более того, в pure-C++ проекте такого поведения не наблюдается. Проблема в C++/CLI.
Продолжим наши исследования. Если деструктор сделать не виртуальным, то опять все работает, как надо:
#pragma once
class Foo
{
public:
Foo() {}
Foo( const Foo& ) {}
Foo& operator = ( const Foo& ) { return *this; }
~Foo() {}
};
Вывод:
New
New
Delete
Delete
New
Delete
Стоит заметить, что этот класс никак не используется в нашей программе. Просто само его наличие приводит к багу.
Т.к. баг проявляется только в C++/CLI, то попробуем пометить этот класс как unmanaged:
#pragma managed(push,off)
#include "../System/basic.h" // h файл с “плохим” классом Foo
#pragma managed(pop)
Вывод:
New
New
Delete
Delete
New
Delete
Получилось! Однако, это не решение проблемы. Будем копать дальше.
Может быть проблема в Precompiled Headers? Однако если basic.h из Stdafx.h, но вставить его в любой другой *.h файл, который попадает в проект, то проблема повторится.
Посмотрим более подробно, что делает linker. Для этого включим режим вывода дополнительной информации у linker’а:
image
Ого! Он нашел delete в MSVCRTD.lib, вот почему delete используется не наш:
image
В случае же, когда мы делаем деструктор не виртуальным или комментируем конструктор копирования, получаем такой выход linker’а:
image
Более того, если оставить конструктор копирования, сделать деструктор не виртуальным, но добавить виртуальную функцию, опять delete начинает глючить.
Хотя исследования были в Debug сборке, но и в Release наблюдается то же самое поведение.
К сожалению, данную проблему пока не удалось решить, что приводит к невозможности простого поиска утечек памяти в проекте.
В итоге имеем, что при наличии класса, у которого есть виртуальная таблица и конструктор копирования (причем этот класс компилируется в managed), linker линкует стандартный delete, хотя у нас и есть переопределенный delete в dll.
PS. Кому интересно самостоятельно поработать с простейшим тестовым solution с проблемой и, возможно, помочь советом, могут скачать его вот здесь: https://mysvn.ru/Lof/NewDeleteProblem
