17.12.2015, 12:58. Показов 860. Ответов 0
Помнится в какой-то теме были задачи одного из собеседований озвучены. Из-за давности той темы отдельно создал новую. Заинтересовала меня тогда одна задача. Определить сколько памяти израсходовал map при выделении 1000000 разных записей. Вот я нашел решение, которое годится для общего случая со своими allocator например.
Кликните здесь для просмотра всего текста
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <crtdbg.h>
#pragma push_macro("_DEBUG")
#undef _DEBUG
#include <map>
#include <vector>
#pragma pop_macro("_DEBUG")
#include <iostream>
static size_t TotalAlloc;
int YourAllocHook(int allocType, void *userData, size_t size, int
blockType, long requestNumber, const unsigned char *filename, int
lineNumber)
{
if (allocType == 1)
{
TotalAlloc += size;
}
return true;
}
int main()
{
_CrtSetAllocHook(YourAllocHook);
std::map<int, int> mapii;
for (int i = 1; i <= 1000000; ++i)
{
mapii.insert(std::pair<int, int>(i, 2));
}
_CrtSetAllocHook(NULL);
std::cout << "Alloc = " << TotalAlloc << " bytes" << std::endl;
system("pause");
return 0;
} |
|
Добавлено через 2 часа 5 минут
Это без служебной информации, чистые данные, диспетчер показывает 84 МБ, а печатает
Alloc = 24000024 bytes.
То есть служебной информации на всякие таблицы где какой блок хранится больше чем самих данных в три раза.
Добавлено через 1 час 33 минуты
Дополнил код
Кликните здесь для просмотра всего текста
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <crtdbg.h>
#include <Windows.h>
#pragma push_macro("_DEBUG")
#undef _DEBUG
#include <map>
#include <vector>
#pragma pop_macro("_DEBUG")
#include <iostream>
static size_t TotalAlloc;
int YourAllocHook(int allocType, void *userData, size_t size, int
blockType, long requestNumber, const unsigned char *filename, int
lineNumber)
{
if (allocType == 1)
{
TotalAlloc += size;
}
return true;
}
int main()
{
SIZE_T HeapAllocTotal = 0;
HANDLE hHeap = GetProcessHeap();
LPCVOID lpMem;
_PROCESS_HEAP_ENTRY Entry = {};
LPPROCESS_HEAP_ENTRY lpEntry = &Entry;
LPPROCESS_HEAP_ENTRY lplastEntry;
lpEntry->lpData = NULL;
while (HeapWalk(hHeap, lpEntry));
lplastEntry = lpEntry;
_CrtSetAllocHook(YourAllocHook);
std::map<int, int> mapii;
for (int i = 1; i <= 1000000; ++i)
{
mapii.insert(std::pair<int, int>(i, 2));
}
_CrtSetAllocHook(NULL);
while (HeapWalk(hHeap, lpEntry))
{
HeapAllocTotal += lpEntry->cbData;
HeapAllocTotal += lpEntry->cbOverhead;
}
std::cout << "AllocData = " << TotalAlloc << " bytes" << std::endl;
std::cout << "HeapAllocTotal" << HeapAllocTotal << std::endl;
system("pause");
return 0;
} |
|
Добавлено через 6 минут
Как я выяснил причина перерасхода памяти не в служебной информации.
TotalAlloc += size; //здесь size = 18, а тут
HeapAllocTotal += lpEntry->cbData; // 60
HeapAllocTotal += lpEntry->cbOverhead; //28, что совпадает с sizeof(_PROCESS_HEAP_ENTRY)
То есть 42 байта выделяется сверх необходимого и не используются при каждом вызове new для размещения элемента
| C++ |
1
| std::pair<int, int>(i, 2) |
|
.
Добавлено через 50 минут
size 24 - это видимо hex был 18.
Что-то не работает HeapAllocTotal, 0 выдает при маленьком числе элементов map, такое ощущение, что он сначала выделяет в той области, что была выделена ещё до main(). Но для миллиона примерно то что надо показывает.
Добавлено через 2 часа 19 минут
Исправил
Кликните здесь для просмотра всего текста
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <Windows.h>
#include <iostream>
#pragma push_macro("_DEBUG")
#undef _DEBUG
#include <map>
#include <vector>
#pragma pop_macro("_DEBUG")
#include <crtdbg.h>
static size_t TotalAlloc;
int YourAllocHook(int allocType, void *userData, size_t size, int
blockType, long requestNumber, const unsigned char *filename, int
lineNumber)
{
if (allocType == 1)
{
TotalAlloc += size;
}
return true;
}
int main()
{
SIZE_T HeapAllocStart = 0;
SIZE_T HeapAllocTotal = 0;
HANDLE hHeap = GetProcessHeap();
LPCVOID lpMem;
_PROCESS_HEAP_ENTRY Entry = {};
LPPROCESS_HEAP_ENTRY lpEntry = &Entry;
lpEntry->lpData = NULL;
_PROCESS_HEAP_ENTRY Arr_HEAP_ENTRY[200];
while (HeapWalk(hHeap, lpEntry))
{
if (lpEntry->wFlags == 1)
{
HeapAllocStart += lpEntry->Region.dwCommittedSize;
}
else
{
HeapAllocStart += lpEntry->cbData;
HeapAllocStart += lpEntry->cbOverhead;
}
}
_CrtSetAllocHook(YourAllocHook);
std::map<int, int> mapii;
for (int i = 1; i <= 10; ++i)
{
mapii.insert(std::pair<int, int>(i, 2));
}
_CrtSetAllocHook(NULL);
bool check = false;
Entry = {};
lpEntry = &Entry;
lpEntry->lpData = NULL;
_PROCESS_HEAP_ENTRY tmp;
while (HeapWalk(hHeap, lpEntry))
{
if (lpEntry->wFlags == 1)
{
HeapAllocTotal += lpEntry->Region.dwCommittedSize;
}
else
{
HeapAllocTotal += lpEntry->cbData;
HeapAllocTotal += lpEntry->cbOverhead;
}
}
std::cout << "AllocData = " << TotalAlloc << " bytes" << std::endl;
std::cout << "HeapAllocForMap = " << HeapAllocTotal - HeapAllocStart << std::endl;
system("pause");
return 0;
} |
|
Добавлено через 7 минут
при 1 элементе получаем HeapAllocForMap = 0, при 10 уже 4096. Где-то до 12000 элементов выделяется без создания новой цепи в HeapWalk, а потом почему-то перестает работать первый механизм выделения памяти и начинается для каждого new отдельная цепь в HeapWalk.
Добавлено через 8 минут
Хотелось бы ещё, чтобы *filename и lineNumber были не пустыми. Вроде за это должен отвечать макрос _CRTDBG_MAP_ALLOC, но с ним всё равно секция define для нужных функций выделяется как не активная.
Добавлено через 10 часов 0 минут
Много показывает, внес изменения исправляющие это
Кликните здесь для просмотра всего текста
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| #include <Windows.h>
#include <iostream>
#pragma push_macro("_DEBUG")
#undef _DEBUG
#include <map>
#include <vector>
#pragma pop_macro("_DEBUG")
#include <crtdbg.h>
static size_t TotalAlloc;
static size_t _heapwalkSize;
int YourAllocHook(int allocType, void *userData, size_t size, int
blockType, long requestNumber, const unsigned char *filename, int
lineNumber)
{
if (allocType == 1)
{
TotalAlloc += size;
}
return true;
}
void heapdump(void)
{
_HEAPINFO hinfo;
int heapstatus;
int numLoops;
hinfo._pentry = NULL;
numLoops = 0;
while ((heapstatus = _heapwalk(&hinfo)) == _HEAPOK)
{
_heapwalkSize += hinfo._size;
numLoops++;
}
}
int main()
{
SIZE_T HeapAllocStart = 0;
SIZE_T HeapAllocTotal = 0;
HANDLE hHeap = GetProcessHeap();
LPCVOID lpMem;
_PROCESS_HEAP_ENTRY Entry = {};
LPPROCESS_HEAP_ENTRY lpEntry = &Entry;
lpEntry->lpData = NULL;
LPPROCESS_HEAP_ENTRY lpPrevEntry = lpEntry;
if (HeapLock(hHeap))
{
while (HeapWalk(hHeap, lpEntry))
{
while ((Entry.wFlags & PROCESS_HEAP_ENTRY_BUSY) != 0)
{
lpEntry = lpPrevEntry;
HeapWalk(hHeap, lpEntry);
}
lpPrevEntry = lpEntry;
if ((Entry.wFlags & PROCESS_HEAP_ENTRY_BUSY) == 0)
{
if ((lpEntry->wFlags & PROCESS_HEAP_REGION) != 0)
{
HeapAllocStart+= lpEntry->Region.dwCommittedSize;
}
else
{
HeapAllocStart += lpEntry->cbData;
HeapAllocStart += lpEntry->cbOverhead;
}
}
}
HeapUnlock(hHeap);
}
heapdump();
size_t _heapwalkStart = _heapwalkSize;
_CrtSetAllocHook(YourAllocHook);
std::map<int, int> mapii;
for (int i = 1; i <= 10; ++i)
{
mapii.insert(std::pair<int, int>(i, 2));
}
_CrtSetAllocHook(NULL);
Entry = {};
lpEntry = &Entry;
lpEntry->lpData = NULL;
lpPrevEntry = lpEntry;
if( HeapLock(hHeap))
{
while (HeapWalk(hHeap, lpEntry))
{
while ((Entry.wFlags & PROCESS_HEAP_ENTRY_BUSY) != 0)
{
lpEntry = lpPrevEntry;
HeapWalk(hHeap, lpEntry);
}
lpPrevEntry = lpEntry;
if ((Entry.wFlags & PROCESS_HEAP_ENTRY_BUSY) == 0)
{
if ((lpEntry->wFlags & PROCESS_HEAP_REGION) != 0)
{
HeapAllocTotal += lpEntry->Region.dwCommittedSize;
}
else
{
HeapAllocTotal += lpEntry->cbData;
HeapAllocTotal += lpEntry->cbOverhead;
}
}
}
HeapUnlock(hHeap);
}
heapdump();
std::cout << "AllocData = " << TotalAlloc << " bytes" << std::endl;
std::cout << "HeapAllocForMap = " << HeapAllocTotal - HeapAllocStart << std::endl;
std::cout << "_heapAllocForMap = " << _heapwalkSize - _heapwalkStart << std::endl;
system("pause");
return 0;
} |
|
Добавлено через 6 минут
Получилось так, что и в первом и во втором цикле попадаем во внутренний где ждем, чтобы был сброшен флаг PROCESS_HEAP_ENTRY_BUSY. Так как в итоге происходят изменения которые вносятся не только map, выходит, что HeapAllocTotal < HeapAllocStart при маленьком числе элементов.
Добавлено через 41 минуту
неправильно с указателями отработал
Кликните здесь для просмотра всего текста
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| SIZE_T HeapAllocStart = 0;
SIZE_T HeapAllocTotal = 0;
HANDLE hHeap = GetProcessHeap();
LPCVOID lpMem;
_PROCESS_HEAP_ENTRY Entry = {};
LPPROCESS_HEAP_ENTRY lpEntry = &Entry;
lpEntry->lpData = NULL;
_PROCESS_HEAP_ENTRY PrevEntry = {};
LPPROCESS_HEAP_ENTRY lpPrevEntry = &PrevEntry;
lpPrevEntry->lpData = NULL;
if (HeapLock(hHeap))
{
while (HeapWalk(hHeap, lpEntry))
{
while ((Entry.wFlags & PROCESS_HEAP_ENTRY_BUSY) != 0)
{
lpEntry->Block.hMem = lpPrevEntry->Block.hMem;
lpEntry->cbData = lpPrevEntry->cbData;
lpEntry->cbOverhead = lpPrevEntry->cbOverhead;
lpEntry->iRegionIndex = lpPrevEntry->iRegionIndex;
lpEntry->lpData = lpPrevEntry->lpData;
lpEntry->Region.dwCommittedSize = lpPrevEntry->Region.dwCommittedSize;
lpEntry->Region.dwUnCommittedSize = lpPrevEntry->Region.dwUnCommittedSize;
lpEntry->Region.lpFirstBlock = lpPrevEntry->Region.lpFirstBlock;
lpEntry->Region.lpLastBlock = lpPrevEntry->Region.lpLastBlock;
lpEntry->wFlags = lpPrevEntry->wFlags;
HeapWalk(hHeap, lpEntry);
}
lpPrevEntry->Block.hMem = lpEntry->Block.hMem;
lpPrevEntry->cbData = lpEntry->cbData;
lpPrevEntry->cbOverhead = lpEntry->cbOverhead;
lpPrevEntry->iRegionIndex = lpEntry->iRegionIndex;
lpPrevEntry->lpData = lpEntry->lpData;
lpPrevEntry->Region.dwCommittedSize = lpEntry->Region.dwCommittedSize;
lpPrevEntry->Region.dwUnCommittedSize = lpEntry->Region.dwUnCommittedSize;
lpPrevEntry->Region.lpFirstBlock = lpEntry->Region.lpFirstBlock;
lpPrevEntry->Region.lpLastBlock = lpEntry->Region.lpLastBlock;
lpPrevEntry->wFlags = lpEntry->wFlags;
if ((Entry.wFlags & PROCESS_HEAP_ENTRY_BUSY) == 0)
{
if ((lpEntry->wFlags & PROCESS_HEAP_REGION) != 0)
{
HeapAllocStart+= lpEntry->Region.dwCommittedSize;
}
else
{
HeapAllocStart += lpEntry->cbData;
HeapAllocStart += lpEntry->cbOverhead;
}
}
}
HeapUnlock(hHeap);
} |
|
Добавлено через 2 минуты
Выяснилось, что она всегда занята и что с ними делать просто пропускать?
Добавлено через 3 часа 55 минут
Разобрался с wFlags, работает теперь исправно для любого числа элементов map
Кликните здесь для просмотра всего текста
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include <Windows.h>
#include <iostream>
#pragma push_macro("_DEBUG")
#undef _DEBUG
#include <map>
#include <vector>
#pragma pop_macro("_DEBUG")
#include <crtdbg.h>
static size_t TotalAlloc;
static size_t _heapwalkSize;
int YourAllocHook(int allocType, void *userData, size_t size, int
blockType, long requestNumber, const unsigned char *filename, int
lineNumber)
{
if (allocType == 1)
{
TotalAlloc += size;
}
return true;
}
void heapdump(void)
{
_HEAPINFO hinfo;
int heapstatus;
int numLoops;
hinfo._pentry = NULL;
numLoops = 0;
while ((heapstatus = _heapwalk(&hinfo)) == _HEAPOK)
{
_heapwalkSize += hinfo._size;
numLoops++;
}
}
int main()
{
SIZE_T HeapAllocStart = 0;
SIZE_T HeapAllocTotal = 0;
SIZE_T HeapAllocCommitStart = 0;
SIZE_T HeapAllocCommitTotal = 0;
HANDLE hHeap = GetProcessHeap();
LPCVOID lpMem;
_PROCESS_HEAP_ENTRY Entry = {};
LPPROCESS_HEAP_ENTRY lpEntry = &Entry;
lpEntry->lpData = NULL;
_PROCESS_HEAP_ENTRY PrevEntry = {};
LPPROCESS_HEAP_ENTRY lpPrevEntry = &PrevEntry;
lpPrevEntry->lpData = NULL;
if (HeapLock(hHeap))
{
while (HeapWalk(hHeap, lpEntry))
{
if ((Entry.wFlags & PROCESS_HEAP_ENTRY_BUSY) != 0)
{
HeapAllocStart += lpEntry->cbData;
HeapAllocStart += lpEntry->cbOverhead;
}
else
{
if ((lpEntry->wFlags & PROCESS_HEAP_REGION) != 0)
{
HeapAllocCommitStart += lpEntry->Region.dwCommittedSize;
}
}
}
HeapUnlock(hHeap);
}
heapdump();
size_t _heapwalkStart = _heapwalkSize;
_CrtSetAllocHook(YourAllocHook);
std::map<int, int> mapii;
for (int i = 1; i <= 10; ++i)
{
mapii.insert(std::pair<int, int>(i, 2));
}
_CrtSetAllocHook(NULL);
Entry = {};
lpEntry = &Entry;
lpEntry->lpData = NULL;
lpPrevEntry = lpEntry;
int count = 0;
if (HeapLock(hHeap))
{
while (HeapWalk(hHeap, lpEntry))
{
if ((Entry.wFlags & PROCESS_HEAP_ENTRY_BUSY) != 0)
{
HeapAllocTotal += lpEntry->cbData;
HeapAllocTotal += lpEntry->cbOverhead;
}
else
{
if ((lpEntry->wFlags & PROCESS_HEAP_REGION) != 0)
{
HeapAllocCommitTotal += lpEntry->Region.dwCommittedSize;
}
}
}
HeapUnlock(hHeap);
}
heapdump();
std::cout << "AllocData = " << TotalAlloc << " bytes" << std::endl;
std::cout << "HeapAllocForMap = " << HeapAllocTotal - HeapAllocStart << std::endl;
std::cout << "HeapAllocCommitForMap = " << HeapAllocCommitTotal - HeapAllocCommitStart << std::endl;
std::cout << "_heapAllocForMap = " << _heapwalkSize - _heapwalkStart << std::endl;
system("pause");
return 0;
} |
|
Добавлено через 8 минут
Забыл добавить, если wFlags 0, то блок свободен, но служебная информация о нём есть значит надо добавить cbOverhead. В этой задаче такие блоки были, но они сокращаются в HeapAllocTotal - HeapAllocStart.
Добавлено через 3 часа 59 минут
Надо добавить, я тут про перерасход памяти говорил
(debug 60 for data 24) for heap_entry 28
(release 24 for data 24) for heap_entry 24
Так что не всё так печально. В Release только +100% на служебную информацию.
(
