Оптимизирующие память рекурсивные вызовы в C

Question

У меня есть рекурсивная функция, которую можно написать так:

void func(TypeName *dataStructure, LL_Node **accumulator) {
    func(datastructure->left, accumulator);
    func(datastructure->right, accumulator);

    {
        char buffer[1000];
        // do some stuff
    }

    return;
}        

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

Должен ли я использовать внешние глобальные переменные? Вызов вспомогательной функции для принудительного размещения буфера после рекурсивного вызова? То, что я действительно ловлю здесь, это совет относительно самого чистого, самого C-идиоматического способа заставить это поведение.

Редактировать: один дополнительный вопрос. Если одно и то же accumulator будет передаваться при каждом вызове func, разве не случайно оставить указатель accumulator в глобальной переменной, а не помещать его в стек при каждом вызове?

Answer 1

Поскольку он используется только одним вызовом за раз, вы можете просто предварительно выделить его и передать во все вызовы через операнд:

void func(TypeName *dataStructure, LL_Node **accumulator, char *buffer) {
    func(datastructure->left, accumulator, buffer);
    func(datastructure->right, accumulator, buffer);

    {
        // do some stuff
    }

    return;
}  

Answer 2

Один из вариантов - разбить функцию на нерекурсивную «публичную» функцию, которая устанавливает буфер и вызывает приватную рекурсивную функцию, для которой требуется передать буфер:

struct func_buffer {
    char buffer[1000];
};

static 
void func_private(TypeName *dataStructure, LL_Node **accumulator, struct func_buffer* buf)
{
    func_private(datastructure->left, accumulator, buf);
    func_private(datastructure->right, accumulator, buf);

    // do some stuff with *buf

    return;
}


void func(TypeName *dataStructure, LL_Node **accumulator) {
    struct func_buffer buffer;

    func_private( dataStructure, accumulator, &buffer);

    return;
} 

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

Answer 3

Я бы лично выделил буфер в куче в этом сценарии примерно так:

void func(TypeName *dataStructure, LL_Node **accumulator, char *buffer ) {
    bool alloced = false;
    if( buffer == 0 ){
        buffer = (char*) malloc( 1000 );
        alloced = true;
    }
    func(datastructure->left, accumulator, buffer);
    func(datastructure->right, accumulator, buffer);
    {

        // do some stuff
    }
    if( alloced )
        free( buffer );
    return;
}  

Если вы не возражаете против синтаксиса C ++, у вас может быть значение буфера по умолчанию равное нулю, или вы можете искажатьимя функции и добавьте

#define func(a,b) __mangledfunc__(a,b,0)

Кажется, это будет проще всего для вашего приложения.

Answer 4

Вы можете передать ссылку в буфер или использовать глобальную переменную.

Когда вы используете ссылку, как в

void func(TypeName *dataStructure, LL_Node **accumulator, char buffer[]) {
    func(datastructure->left, accumulator, buffer);
    func(datastructure->right, accumulator, buffer);

    {
        char buffer[1000];
        // do some stuff
    }

    return;
}   

void main()
{
   char buffer[1000];

   func (structure, accum, buffer);
}

, вы передаете ссылку, просто указатель наначало массива, поэтому вы должны помнить его длину.

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

char buffer[1000];

void func(TypeName *dataStructure, LL_Node **accumulator) {
        func(datastructure->left, accumulator);
        func(datastructure->right, accumulator);

    {

        // do some stuff
    }

    return;
}   

void main()
{

   func (structure, accum);
}

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

Answer 5

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