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

Question

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

тока я узел с двумя детьми влево и вправо, а затем во время движения(), если какое-то условие, в этом примере пересекаются(), дети посетили:

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.

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

С уважением Jonas Finnemann Jensen

Answer 1

The Стандарт 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

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

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 4

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

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

Answer 5

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

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

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

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

Answer 6

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

Answer 7

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

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

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

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

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

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

Answer 8

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

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

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