Использование стека программ в реализации DFS

Question

У меня есть стандартная реализация DFS в моем коде, которая использует динамически выделенный стек для каждого вызова.

Я называю эту функцию много. Часто на небольших узлах (200-1000), но иногда есть большой подключенный компонент с миллионом узлов и более.

Профилировщик показывает, что значительное количество вычислительного времени теряется при распределении стека. Я хочу попытаться повторно использовать существующую память (например, стек вызовов). Однако функция должна оставаться потокобезопасной.

Есть ли эффективный способ динамического использования стека вызовов, не делая функцию рекурсивной?

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

Псевда C:

void dfs(size_t stack_length, void * graph, graphnode_t start_node) { 
    graphnode_t stack[stack_length]; 
    size_t stack_size = 0; 

    for (all nodes) { 
     // do something useful 
     if (stack_size < stack_length) { 
      stack[stack_size++] = new_node; 
     } else { 
      dfs(stack_length * 2, graph, new_node); 
     } 
    } 

} 

Answer 1

Это звучит, как вы описываете, что ваш алгоритм будет работать нормально только с одной graphnode_t массивом для системы (хотя вы вызываете его стек, я не думаю, что это действительно применимо), и единственная реальная проблема заключается в том, что вы не уверены в том, насколько велика она должна быть, когда вы начинаете.

Если это так, я бы предположил сначала, что вы не делаете этот (потенциально огромный) массив локальной переменной, потому что это вызовет проблемы с вашим фактическим стеком программ. Вместо этого пусть это будет статический указатель, который указывает на динамически размерную память, которую вы периодически расширяете, если необходимо.

ensure_size(graphnode_t **not_a_stack_ptr, unsigned long *length_ptr) 
{ 
    if (!*not_a_stack_ptr) 
    { 
     *not_a_stack_ptr = malloc(sizeof(graphnode_t) * MINIMUM_ENTRY_COUNT); 
     *length_ptr = MINIMUM_ENTRY_COUNT; 
    } 
    else if (size needs to double) 
    { 
     *length_ptr *= 2; 
     *not_a_stack_ptr = realloc(*not_a_stack_ptr, sizeof(graphnode_t) * (*length_ptr)); 
    } 
} 


struct thread_arguments { 
    void * graph; 
    graphnode_t start_node; 
} 

dfs_thread(void *void_thread_args) 
{ 
    struct thread_arguments *thread_args = void_thread_args; 
    graphnode_t *not_a_stack = NULL; 
    unsigned long not_a_stack_length = 0; 

    for (all nodes) 
    { 
     ensure_size(&not_a_stack, &not_a_stack_length); 
     stack[stack_size++] = new_node; 
    } 

    if (not_a_stack) free(not_a_stack); 
} 

Примечание: ваш псевдо-код предполагает, что максимальный размер может быть определен на основе числа узлов у вас есть. Вы получите максимальный прирост производительности, используя это, чтобы выполнить только один полноразмерный malloc спереди.