16

ノードが-1または頂点の名前である負でない整数のいずれかを格納するツリーがあります。各頂点は、ツリー内で最大 1 回出現します。次の関数は、私のコードのボトルネックです。

バージョン A:

void node_vertex_members(node *A, vector<int> *vertexList){
   if(A->contents != -1){
      vertexList->push_back(A->contents);
   }
   else{
      for(int i=0;i<A->children.size();i++){
          node_vertex_members(A->children[i],vertexList);
      }
   }
}

バージョン B:

void node_vertex_members(node *A, vector<int> *vertexList){
   stack<node*> q;
   q.push(A);
   while(!q.empty()){
      int x = q.top()->contents;
      if(x != -1){
         vertexList->push_back(x);
         q.pop();
      }
      else{
         node *temp = q.top();
         q.pop();
         for(int i=temp->children.size()-1; i>=0; --i){
            q.push(temp->children[i]);
         }
      }
   }
}

何らかの理由で、バージョン B はバージョン A よりも実行にかなり時間がかかりますが、これは予想外でした。コンパイラは、私のコードよりもはるかに賢い何をしているのでしょうか? 別の言い方をすれば、私は何をしているので効率が悪いのでしょうか? また、私が困惑しているのは、バージョン B で子のコンテンツが -1 であるかどうかを確認してからスタックに置くなどのことを試みると、劇的に遅くなる (ほぼ 3 倍) ことです。参考までに、Cygwin で -O3 オプションを指定して g++ を使用しています。

アップデート：

次のコード (バージョン C) を使用して、再帰バージョンを一致させることができました。

node *node_list[65536];

void node_vertex_members(node *A, vector<int> *vertex_list){
   int top = 0;
   node_list[top] = A;
   while(top >= 0){
      int x = node_list[top]->contents;
      if(x != -1){
         vertex_list->push_back(x);
         --top;
      }
      else{
         node* temp = node_list[top];
         --top;
         for(int i=temp->children.size()-1; i>=0; --i){
            ++top;
            node_list[top] = temp->children[i];
         }
      }
   }
}

明らかな欠点は、コードの長さとマジック ナンバー (および関連するハード リミット) です。そして、前述したように、これはバージョン A のパフォーマンスにのみ一致します。もちろん、私は再帰バージョンに固執しますが、基本的にSTLのオーバーヘッドが私を悩ませていたので、満足しています。

4

3 に答える 3

13

バージョン A には 1 つの重要な利点があります。それは、コード サイズがはるかに小さいことです。

バージョン B には重大な欠点が 1 つあります。それは、スタック要素のメモリ割り当てです。スタックは最初は空で、要素が 1 つずつプッシュされていると考えてください。場合によっては、基になる両端キューに対して新しい割り当てを行う必要があります。これはコストのかかる操作であり、関数の呼び出しごとに数回繰り返される場合があります。

編集: g++ -O2 -SMac OS で GCC 4.7.3 を使用して生成されたアセンブリを以下に示しc++filtます。

versionA(node*, std::vector<int, std::allocator<int> >*):
LFB609:
        pushq   %r12
LCFI5:
        movq    %rsi, %r12
        pushq   %rbp
LCFI6:
        movq    %rdi, %rbp
        pushq   %rbx
LCFI7:
        movl    (%rdi), %eax
        cmpl    $-1, %eax ; if(A->contents != -1)
        jne     L36 ; vertexList->push_back(A->contents)
        movq    8(%rdi), %rcx
        xorl    %r8d, %r8d
        movl    $1, %ebx
        movq    16(%rdi), %rax
        subq    %rcx, %rax
        sarq    $3, %rax
        testq   %rax, %rax
        jne     L46 ; i < A->children.size()
        jmp     L35
L43: ; for(int i=0;i<A->children.size();i++)
        movq    %rdx, %rbx
L46:
        movq    (%rcx,%r8,8), %rdi
        movq    %r12, %rsi
        call    versionA(node*, std::vector<int, std::allocator<int> >*)
        movq    8(%rbp), %rcx
        leaq    1(%rbx), %rdx
        movq    16(%rbp), %rax
        movq    %rbx, %r8
        subq    %rcx, %rax
        sarq    $3, %rax
        cmpq    %rbx, %rax
        ja      L43 ; continue
L35:
        popq    %rbx
LCFI8:
        popq    %rbp
LCFI9:
        popq    %r12
LCFI10:
        ret

L36: ; vertexList->push_back(A->contents)
LCFI11:
        movq    8(%rsi), %rsi
        cmpq    16(%r12), %rsi ; vector::size == vector::capacity
        je      L39
        testq   %rsi, %rsi
        je      L40
        movl    %eax, (%rsi)
L40:
        popq    %rbx
LCFI12:
        addq    $4, %rsi
        movq    %rsi, 8(%r12)
        popq    %rbp
LCFI13:
        popq    %r12
LCFI14:
        ret
L39: ; slow path for vector to expand capacity
LCFI15:
        movq    %rdi, %rdx
        movq    %r12, %rdi
        call    std::vector<int, std::allocator<int> >::_M_insert_aux(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&)
        jmp     L35

これはかなり簡潔で、一見すると「スピード バンプ」がほとんどないように見えます。-O3 でコンパイルすると、アンロールされたループやその他の楽しいもので、ひどい混乱が生じます。現在、バージョン B に注釈を付ける時間はありませんが、多くの deque 関数とより多くのメモリへの書き込みにより、バージョン B はより複雑になっていると言えば十分です。遅くなっても不思議ではありません。

于 2013-06-23T05:10:17.490 に答える