Изменение размера динамического стека в C ++

Question

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

Текущий У меня есть узел с двумя дочерними элементами слева и справа, затем во время travel (), если какое-то условие, в этом примере intersect (), посещают дочерние элементы:

class BoundingBoxNode{
    BoundingBoxNode* left, *right;
    void travel(param &p);
    inline bool intersect(param &p){...};
};

void BoundingBoxNode::travel(param &p){
    if(this->intersect(p)){
        if(left)
            left->travel(p);
        if(right)
            right->travel(p);
    }
}

В этом подходе используются рекурсивные вызовы методов, однако мне нужно максимально оптимизировать этот код ... А согласно справочному руководству по оптимизации для IA-32 вызовы функций глубже 16 могут быть очень дорогими, поэтому я бы хотел сделать это, используя цикл while вместо рекурсивных вызовов. Но я НЕ хочу делать динамическое выделение кучи, поскольку это дорого. Поэтому я подумал, что, возможно, я мог бы использовать тот факт, что каждый раз, когда цикл while начинается над стеком, будет в одной и той же позиции. В следующем очень уродливом хаке я полагаюсь на alloca (), чтобы всегда выделять один и тот же адрес:

class BoundingBoxNode{
    BoundingBoxNode* left, right;
    inline void travel(param &p){
        int stack_size = 0;
        BoundingBoxNode* current = this;
        while(stack_size >= 0){
            BoundingBoxNode* stack = alloca(stack_size * 4 + 2*4);
            if(current->intersect(p)){
                if(current->left){
                    stack[stack_size] = current->left;
                    stack_size++;
                }
                if(current->right){
                    stack[stack_size] = current->right;
                    stack_size++;
                }
            }
            stack_size--;
            current = stack[stack_size];
        }
    };
    inline bool intersect(param &p){...};
};

Как ни удивительно, но такой подход может не сработать :) Но он работает до тех пор, пока размер стека меньше 4 или 5 ... Я также вполне уверен, что такой подход возможен, просто я действительно нуждаюсь в некоторой помощи для его правильной реализации.

Итак, как я могу манипулировать стеком вручную из C ++, возможно ли, что я могу использовать какое-то расширение компилятора ... Или я должен сделать это на ассемблере, и если да, то как мне написать ассемблер, который может быть скомпилирован с обоими GCC и ICC.

Надеюсь, кто-нибудь сможет мне помочь ... Мне не нужно идеальное решение, просто взлом, если оно работает, этого достаточно для этого:)

С уважением, Джонас Финнеманн Дженсен

Answer 1

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

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

Если стек достаточно мал, чтобы поместиться в кэш, он останется горячим, и тот факт, что его нет в реальном стеке C ++, не будет иметь значения.

После того, как вы выполнили весь этот профиль в обоих направлениях и посмотрите, имеет ли это какое-то значение - сохраните более быструю версию.

Answer 2

Распределение стека не может быть изменено.

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

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

Если вы знаете верхнюю границу для требуемой памяти, выделение - это просто приращение указателя:

class CPool
{
    std::vector<char> m_data;
    size_t m_head;
  public:
    CPool(size_t size) : m_data(size()), m_head(0) {}
    void * Alloc(size_t size)
    {
      if (m_data.size() - head < size)
        throw bad_alloc();
      void * result = &(m_data[m_head]);
      m_head += size;      
      return result;
    }
    void Free(void * p) {} // free is free ;)
};

Если у вас нет верхней границы для общего размера, используйте «пул на веревке» - т.е. когда большой кусок памяти заканчивается, найдите новый и поместите эти куски в список. *

Answer 3

Вам не нужен стек , вам просто нужен a стек. Вы, вероятно, можете использовать std::stack<BoundingBoxNode* >, если я посмотрю на ваш код.

Answer 4

Использовать структуру данных C ++. Вы используете C ++ в конце концов. Std :: vector <> может быть предварительно выделен порциями по амортизированной стоимости, равной почти нулю. И это также безопасно (как вы заметили, что использование обычного стека не подходит. Особенно, когда вы используете потоки)

И нет, это не дорого. Это так же быстро, как распределение стека.

std :: list <> да, это будет дорого. Но это потому, что вы не можете предварительно выделить это. std :: vector <> выделяется по частям по умолчанию.

Answer 5

Судя по вашему вопросу, многое еще нужно изучить.

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

Функция «alloca» выделяет кусок памяти из стека, размер стека увеличивается (путем перемещения указателя стека). Каждый вызов 'alloca' создает новый кусок памяти, пока вы не исчерпаете пространство стека, он не будет повторно использовать ранее выделенную память, данные, на которые указывал 'stack', будут потеряны, когда вы выделите другой кусок памяти и назначить его на «стек». Это утечка памяти. В этом случае память автоматически освобождается при выходе из функции, поэтому это не является серьезной утечкой, но вы потеряли данные.

Я бы оставил «Справочное руководство по оптимизации для IA-32» в покое. Предполагается, что вы точно знаете, как работает процессор. Пусть компилятор будет беспокоиться об оптимизации, он будет достаточно хорош для того, что вы делаете - авторы компилятора, надеюсь, знают эту ссылку наизнанку. На современных ПК общим узким местом для производительности обычно является пропускная способность памяти.

Я полагаю, что вызовы функции «16 глубоких» дорогие связаны с тем, как процессор управляет своим стеком, и это только руководство. Центральный процессор удерживает верхнюю часть стека во встроенной кэш-памяти. Когда кэш заполнен, нижняя часть стека выгружается в ОЗУ, где производительность начинает снижаться. Функции с большим количеством аргументов не будут вкладываться так глубоко, как функции без аргументов. И это не только вызовы функций, это также локальные переменные и память, выделенная с помощью alloca. Фактически, использование alloca - это, вероятно, снижение производительности, поскольку ЦП будет спроектирован так, чтобы оптимизировать свой стек для общих случаев использования - нескольких параметров и нескольких локальных переменных. Отходите от обычного случая и производительность падает.

Попробуйте использовать std :: stack, как MSalters предложил выше. Получите это работает.

Answer 6

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

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

Answer 7

Поскольку выделения ресурсов накапливаются, я предлагаю вам сделать первый резерв для хранения указателя «this», став, таким образом, «основой» стека, отслеживайте, сколько элементов может удерживать ваш стек, и выделяйте только необходимый размер :

inline void travel(param &p){

    BoundingBoxNode* stack = alloca(sizeof(BoundingBoxNode*)*3);
    int stack_size = 3, stack_idx = 0;
    stack[stk_idx] = this;

    do {
            BoundingBoxNode* current = stack[stk_idx];
            if( current->intersect(p)){
                    int need = current->left ? ( current->right ? 2 : 1 ) : 0;
                    if ( stack-size - stk_idx < need ) {
                         // Let us simplify and always allocate enough for two
                         alloca(sizeof(BoundingBoxNode*)*2);
                         stack_size += 2;
                    }
                    if(current->left){
                            stack[stack_idx++] = current->left;
                    }
                    if(current->right){
                            stack[stack_idx++] = current->right;
                    }
            }
            stack_idx--;
    } while(stack_idx > 0)
};

Answer 8

Стандарт C ++ не предоставляет никаких средств для манипулирования стеком - он даже не требует наличия стека. Вы действительно измерили производительность вашего кода с помощью динамического выделения?