Блог

Я пишу высокооптимизированное дерево 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 флаги.