Эффективный способ обработки/определения массива struct pollfd для опроса syscall

Question

Я использую опрос для реализации серверной части модели клиент-сервер с мультиплексированием.

Существует основной цикл работы сервера.
В каждом цикле я проверяю все fds в массиве struct pollfd, пока не найду n сокеты, у которых есть контент для меня (где n - это номер, который вызвал опрос).
Кроме того, опрос используется без таймаута (-1 в качестве аргумента).

Так что если в гнездо прослушивания запрашивается новое соединение, я вставляю сокет и некоторую информацию о клиенте в список активных соединений, который я сохраняю.

Каков наиболее эффективный способ обработки массива опросов?

Должен ли я определить небольшой массив размером 10 и если больше клиентов повторно выделяет память для массива размером 20 или 50?

Или должен: (a) освободить массив типа struct pollfd и (b) перераспределить его с размером, равным размеру списка (+1 для прослушивающего сокета) => каждый раз, когда клиент закрывает соединение (и, следовательно, я должен удалить элемент из массива (возможно, установив сокет на -1, чтобы опрос его игнорировал), что привело к неиспользуемому пространству в массиве)

Что вы рекомендуете?

Спасибо за ваше время

---

Edit: Я думаю, я нашел решение с перераспределить и сдвигая с memmove каждый раз, когда клиент отсоединяется, чтобы покрыть его гнездо в массиве FDS.

Answer 1

Каков наиболее эффективный способ обработки массива опросов?

Реализация определена. Не оптимизируйте, пока не узнаете, что вам нужно; Это называется преждевременной оптимизацией, и это пустая трата времени.

Должен ли я определить небольшой массив размера 10, и если есть больше клиентов повторно выделить память для массива размера 20 или 50?

Если профайлер определяет, что ваши pollfd s являются существенным препятствием в вашей программе, и ваш босс (или профессор) говорит, что программа «не хватает быстро», пойти на это. Если наибольший ваш список будет равен 50, то просто используйте статический массив, установите fd членов в -1, не беспокойтесь, переставляя вещи, когда вы удаляете из массива ... Узкие места, о которых вы говорите, будут незначительными для такого небольшого числа.

Если вы пытаетесь обрабатывать гораздо большее количество клиентов в худшем случае, вы можете быть обеспокоены неиспользуемым пространством, переходящим массив при обработке меньших чисел ... и, следовательно, выберете масштабируемый массив pollfd.

Или я должен: (а) освободить массив типа структура pollfd, и (б) перераспределить его с размером, который равен размеру списка (+1 для сокете) => каждый раз, когда клиент закрывает соединение (и, таким образом, я должен удалить элемент из массива (вероятно, устанавливающего сокета к -1, так что опрос игнорирует его), в результате неиспользованного пространства в массиве )

Самый простой алгоритм, который я могу придумать, удваивает пространство при изменении размера. Возможно, наиболее значительным преимуществом удвоения при изменении размера является уменьшение количества звонков до realloc по сравнению с линейным изменением размера; Вместо того, чтобы принимать 1024 подключения и вызывать realloc 1024 раза, я бы предпочел принять 1024 подключения и позвонить realloc 10 или 11 раз. Мне также кажется более простым, потому что нет необходимости хранить емкость массива отдельно для используемого счета; Вы можете использовать свойство двоичных чисел в ваших интересах: (n - 1) & n == 0, когда n - это сила двух.

#define is_power_of_two(n) !(((n) - 1) & (n)) 

struct pollfd *pollfd_array_resize(struct pollfd *array, size_t size) { 
    const size_t max_size = SIZE_MAX/sizeof *array; 
    if (size == max_size) { return NULL; } 
    if (is_power_of_two(size)) { 
     array = realloc(array, (size > 0 ? size * 2 : 1) * sizeof *array); 
    } 
    return array; 
} 

Edit: Я думаю, я нашел решение с перераспределить и сдвигая с memmove каждый раз, когда клиент отсоединяется, чтобы покрыть его гнездо на FDS массива.

Это похоже на довольно хорошее исправление. Он увеличивает местность кеша, но ценой необходимости звонить memmove и realloc каждый раз, когда клиент отключается.

Я бы даже не подумал об «дефрагментации» массива, пока мой профилировщик не покажет, что poll использует слишком много процессорного времени. Когда это произойдет, я бы подумал о том, чтобы установить член fd на что-то отрицательное (поскольку вы были делали перед вашим редактированием) и помещали индекс элемента для удаления в стек recently_freed. При вставке я бы выбрал элементы из этого стека, если это возможно. Если вы должны дефрагментировать, я предлагаю сделать это на основе размера этого стека.

size_t pollfd_array_defrag(struct pollfd *array, size_t size) { 
    size_t new_size = 0; 
    for (size_t x = 0; x + 1 < size; x++) { 
     if (array[x].fd < 0) { 
      continue; 
     } 

     array[new_size++] = array[x]; 
    } 
    return new_size; 
} 

int main(void) { 
    size_t size = 0, index; 
    struct pollfd *array = NULL; 
    struct index_stack *recently_freed = NULL; 

    /*----------------------------* 
    * ... snip for insertion ... */ 
    if (recently_freed && recently_freed->size > 0) { 
     index = index_stack_pop(&recently_freed); 
    } 
    else { 
     struct pollfd *temp = pollfd_array_resize(array, size); 

     if (temp == NULL) { 
      /* TODO: Handle memory allocation errors */ 
     } 

     array = temp; 
     index = size++; 
    } 

    array[index] = (struct pollfd) { .fd = your_fd, 
            .events = your_events, 
            .revents = your_revents }; 

    /*--------------------------* 
    * ... snip for removal ... */ 
    index_stack_push(&recently_freed, index); 
    array[index] = -1; 

    /*----------------------------------* 
    * ... snip for defragmentation ... */ 
    if (is_power_of_two(recently_freed->size) && recently_freed->size * 2 + 1 > size) { 
     size = pollfd_array_defrag(array); 
     /* array will shrink in future insertions */ 
     index_stack_destroy(&recently_freed); 
     recently_freed = NULL; 
    } 
}