Итератор дерева, можете ли вы оптимизировать это дальше?

Question

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

Код ниже перебирает двоичное дерево (влево / вправо = дочерний / следующий). Я действительно считаю, что здесь есть место для одного менее условного (down логическое). Самый быстрый ответ выигрывает!

1. Оператор cnt может состоять из нескольких операторов, поэтому давайте убедимся, что он появляется только один раз
2. Функции-члены child() и next() примерно в 30 раз медленнее, чем операции hasChild () и hasNext ().
3. Сохраняйте его итеративным <- отменили это требование, поскольку представленное рекурсивное решение было быстрее. </li>
4. Это код C ++
5. Порядок посещения узлов должен оставаться таким же, как в приведенном ниже примере. (сначала нажмите «родители», затем «потомки», затем «следующие» узлы).
6. BaseNodePtr является boost :: shared_ptr, поскольку, таким образом, назначения медленные, избегайте любых временных переменных BaseNodePtr.

В настоящее время этот код занимает 5897 мс для посещения 62200000 узлов в дереве тестов, вызывая эту функцию 200 000 раз.

void processTree (BaseNodePtr current, unsigned int & cnt )
{
    bool down = true;

    while ( true )
    {
        if ( down )
        {
            while (true) {

                cnt++; // this can/will be multiple statesments

               if (!current->hasChild()) break;
               current = current->child();
            }
        }

        if ( current->hasNext() )
        {
            down = true;
            current = current->next();
        }
        else
        {
            down = false;
            current = current->parent();
            if (!current)
                return; // done.
        }
    }
}

Answer 1

Почему не рекурсивное решение?

void processTree (const BaseNodePtr &current, unsigned int & cnt )
{
  cnt++;

  if (current->hasChild())
    processTree(current->child());
  if (current->hasNext())
    processTree(current->next());
}

Поскольку shared_ptr кажется вашим узким местом, почему бы не улучшить его? Вы используете темы? Если нет, то отмените символ BOOST_HAS_THREADS. Счетчик ссылок shared_ptr защищен мьютексом, что, вероятно, является причиной низкой производительности.

Почему бы не изменить структуру данных, чтобы вообще не использовать shared_ptr? Управлять необработанными указателями самостоятельно? Может быть, вместо этого используйте scoped_ptr? 1011 *

Answer 2

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

например, если у вас есть дерево, определенное следующим образом.

        1
       / \
      2   3
     / \  /\
    4   5 6 7
   /\    /  /\
  8  9  10 11 12
 / \           \
13 14          15

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

1
 2
  4
   8
    13
    14
   9
  5
 3
  6
   10
  7
   11
   12
     15

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

Для создания быстрого итеративного метода посещения всех узлов дерева только один раз и без рекурсии.

unsigned int g_StackDepth = 0;
BaseNodePtr* g_Stack[MAX_STACK_DEPTH];

void processTree (BaseNodePtr root, unsigned int & cnt )
{
    g_Stack[g_StackDepth++] = root;
    while( g_StackDepth > 0 )
    {
        BaseNodePtr curr = g_Stack[--g_StackDepth];
        cnt++;

        if ( curr->HasNext() )
        {
            g_Stack[g_StackDepth++] = curr->Next();
        }


        if ( curr->HasChild() )
        {
            g_Stack[g_StackDepth++] = curr->Child();
        }

    }
}

Насколько мне известно, в сочетании с указанным выше порядком вы должны получить примерно лучшую скорость, какую МОЖЕТЕ набрать.

Очевидно, что у этого есть ограничения, так как вы должны знать, насколько большой ваш стек может вырасти заранее. Хотя вы можете обойти это, используя вместо этого std :: vector. Однако использование std :: vector исключит все преимущества, которые обеспечивает итерационный метод, приведенный выше.

Надеюсь, это поможет:)

Answer 3

Вот как сделать только один рекурсивный вызов вместо двух:

void processTree (const BaseNodePtr &current, unsigned int & cnt )
{
  for(bool gotNext = true; gotNext; current = current->next()) { 
    cnt++;
    if (current->hasChild())
      processTree(current->child());
    gotNext = current->hasNext();
  }
}

Answer 4

I HATE , когда ответы отклоняют вопрос "не делай этого", но здесь я иду ...

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

Сконцентрируйтесь на ускорении вызовов child () и parent (), если вам нужна скорость. В противном случае вы тратите свое время (ИМХО).

EDIT: Возможно, пройдитесь по дереву (с этим «медленным» кодом) ОДИН РАЗ и постройте массив указателей в дереве в нужном порядке. Используйте этот «индекс» позже.

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

Answer 5

Создайте функцию «nextvisit» и продолжайте вызывать ее, чтобы упростить код; Кроме того, используйте константные ссылки на iso value-semantics для указателей общего доступа ... это может сэкономить вам ценные копии shared-ptr:

// define the order of visitation in here
BaseNodePtr& next( const BaseNodePtr& p ) {
    if( p->hasChild() ) return p->child();
    if( p->hasNext() ) return p->next();
    BaseNodePtr ancestor = p->parent();
    while( ancestor != 0 && !ancestor->hasNext() ) ancestor = ancestor->parent();
    return ancestor;
}

void processTree( const BaseNodePtr& p, unsigned int& cnt ) {
   while( p != NULL ) {
     ++cnt;
     p = next(p);
   }        
}

Но для удобства чтения, ясности, удобства обслуживания ... ради бога, используйте рекурсию. Если ваш стек не достаточно большой.