#c #memory #prefetch
#c #память #предварительная выборка
Вопрос:
Я пишу высокооптимизированное дерево AVL, и теперь случилось так, что я решил позаботиться о многочисленных ошибках страниц, которые я получал во время вставок. Оказалось, что я просто пытаюсь получить доступ к другой странице, которая генерирует ошибку страницы. Я попытался использовать встроенные функции предварительной выборки gcc в нескольких комбинациях в разных местах кода вставки, но избавиться от них не удалось. Я также попытался немного поэкспериментировать, *ptr = *ptr
чтобы посмотреть, будет ли это иметь какой-либо эффект ( ptr
это указатель, к которому я хочу получить доступ, который время от времени генерирует ошибку страницы).
Дополнительная информация: я использую malloc
, чтобы получить память для дерева AVL, а затем «продвигаться вперед» в памяти (как в «каждая новая вставка добавляет новый узел в линейном порядке»). Таким образом, естественно, что при каждом x вставках я пытаюсь получить доступ к новой странице и, таким образом, генерирую ошибку страницы. Я попробовал выполнить предварительную выборку самого указателя и указателя через несколько байт после указателя (чтобы убедиться, что он находится на новой странице), я попытался выровнять предварительно выбранный указатель на 64 байта. Возможно, встроенные инструкции предварительной выборки работают только для кэша и на самом деле не загружают страницы, я не знаю.
Цель состоит в том, чтобы поместить эту страницу в память перед доступом к ней, чтобы у меня не было ошибок страницы и не замедлялось (выполнение миллионов вставок за тест, поэтому время от времени на самом деле становится довольно частым, и появляются большие цифры).
GCC 9.2.0 нацелен на mingw32, 64-битный
код Windows 10:
struct net_avl_node {
int sfd;
int balance;
void (*value)(int);
struct net_avl_node* restrict parent;
struct net_avl_node* restrict left;
struct net_avl_node* restrict right;
};
struct net_avl_tree {
struct net_avl_node** parts;
struct net_avl_node* restrict head;
struct net_avl_node* last;
uint32_t count;
uint32_t amount;
uint32_t max_items_per_part;
};
int net_avl_insert(struct net_avl_tree* const tree, const int sfd, void (*callback)(int)) {
void* restrict ptr;
struct net_avl_node* restrict node = tree->head;
struct net_avl_node* restrict temp;
if(tree->amount == 0) { // first object becomes the head
ptr = malloc(sizeof(struct net_avl_node*));
if(ptr == NULL) {
return ENOMEM;
}
tree->parts = ptr;
ptr = malloc(sizeof(struct net_avl_node) * tree->max_items_per_part);
if(ptr == NULL) {
free(tree->parts);
return ENOMEM;
}
//memset(ptr, 0, sizeof(struct net_avl_node) * tree->max_items_per_part);
// didn't change anything
tree->parts[0] = ptr;
tree->parts[0][0] = (struct net_avl_node) {
.sfd = sfd,
.balance = 0,
.value = callback,
.parent = NULL,
.left = NULL,
.right = NULL
};
tree->count = 1;
tree->amount = 1;
tree->head = tree->parts[0];
tree->last = tree->parts[0];
return 0;
} else if(tree->count % tree->max_items_per_part == 0) { // make more space if lacking memory
/* ... */
}
/*
grab the next node (no gaps between them so going
from the lowest address to the highest linearly,
thus going to a new page once a while)
*/
temp = tree->last;
tree->count;
while(1) {
if(sfd > node->sfd) {
if(node->right != NULL) {
node = node->right;
} else {
*temp = (struct net_avl_node) { // a page fault
.sfd = sfd,
.balance = 0,
.value = callback,
.parent = node,
.left = NULL,
.right = NULL
};
node->right = temp;
/* ... */
break;
}
} else {
if(node->left != NULL) {
node = node->left;
} else {
*temp = (struct net_avl_node) { // a page fault
.sfd = sfd,
.balance = 0,
.value = callback,
.parent = node,
.left = NULL,
.right = NULL
};
node->left = temp;
/* ... */
break;
}
}
}
/* rebalancing */
return 0;
}
Я также использую -O3 -Wall -lpsapi -Wno-missing-braces -Wmissing-field-initializers -D_GNU_SOURCE
флаги.
Комментарии:
1. Пожалуйста, отредактируйте свой вопрос и разместите свой [репрезентативный] код в блоке кода здесь. Существует ряд методов смягчения последствий, но для их применения нам понадобится некоторый контекст. Как вы измеряете ошибки страницы и локальность? Я предполагаю, что вы создаете дерево один раз [более или менее] и выполняете много поиска [потому что вы используете дерево AVL]. Если вы выполняете много динамических операций добавления / удаления, я думаю, вместо этого вам нужно дерево RB.
2. Если вы не перераспределите (и, таким образом, измените размер), вы могли бы сделать
memset(ptr, 0, size);
. Это должно вызвать запись страницы и заставить систему выдать вам страницу. Хотя, возможно, его все еще можно вывести на пейджер.3. @CraigEstey Я использую Windows API для печати использования памяти процесса: docs.microsoft.com/en-us/windows/win32/psapi / … и да, я создаю дерево один раз
4.Один из способов — не
malloc(sizeof(struct mynode))
для одного узла. Но, скорее, выделите блок узлов (например)pool = malloc(sizeof(struct mynode) * 1000000)
. Затем перейдите к этому и создайте связанный список свободных узлов. Затем выделите / освободите из / в списке. Опять же, для того, чтобы эффективно применять это, нам нужен контекст.5. Примечание: вы копируете код [в трех местах], используя синтаксис инициализатора [против присваивания]. Я не слишком часто видел это (например).
*temp = (struct net_avl_node) { .sfd = sfd, .balance = 0, ...};
В актерском составе нет необходимости. То, к чему я привык, это:temp->sfd = sfd; temp->balance = 0; ...
. Это просто быстрее и более канонично. Поскольку я [лично] никогда не использовал инициализатор таким образом, я не могу ручаться за его скорость.