2

テンプレートを不注意に使用すると、肥大化する可能性があります。その肥大化を回避する 1 つの方法は、タイプセーフではない非テンプレート コードをラップするシン タイプ セーフ テンプレートを使用することです。これを行うには、ラッパーは、テンプレート以外のコードが何も知らないものにアクセスするための何らかの方法を提供する必要があります。

たとえば、データ構造では、ラッパーはノード構造体を定義します。アンセーフ コードはノードの読み取りと書き込みを行う必要がありますが、ラッパーによって指定された何らかの種類のインターフェイスを介して間接的に行う必要があります。

このインターフェイスを実装する 1 つの方法は、ラッパーによって決定される関数ポインターや定数などの詳細を構造体 (アンセーフ コードによって定義される) に入力することです。関連する定数の 1 つに、特定のフィールドの (何らかの構造内の) オフセットがあります。アンセーフ コードは、そのオフセット (およびいくつかのポインター演算) を使用して、そのフィールドに直接アクセスできます。

ただし、これは問題になりつつあります。オプティマイザーがより積極的になると、ポインター エイリアスの問題が発生する可能性があります。これは、ノードがライブラリをエスケープできる場合に特に当てはまります。たとえば、ノードを二分木から抽出し、再リンクしてリンク リストを形成することができます。もう 1 つの例は、厄介なことに、単体テストのときに発生します。

私は現在、これらの方針に沿ってコンテナ ライブラリを作成していますが、現時点ではこれらの問題は発生していませんが、まもなく問題が発生する可能性があります。これらの問題を回避する理由は、すべての単体テストが (基になるコードではなく) コンテナーに適用され、ノードがコンテナーを決してエスケープしないためです。つまり、ノードは常に同じポインター演算方法でアクセスされるため、ポインター エイリアスの最適化の問題は発生しません。

残念ながら、コンテナからノードを抽出できるようにする必要がすぐに出てきます。おそらく、基になるアンセーフ コードの単体テストも必要になるでしょう。

この特定のライブラリを扱うのではなく、同じ問題を抱えている古いバイナリ ツリー ライブラリからのより単純な抜粋をここに示します。VC++9 では、それは機能します。MinGW GCC 4.4.0 を使用すると、デバッグ ビルドは機能しますが、リリース ビルドは失敗します。問題は、インライン化と、オプティマイザーがポインター エイリアスを見つけられないことが混在していることです。

はっきりさせておきますが、ここでは「WTF - GOTO!!!」は使いたくありません。または何でも。問題は、最適化/ポインターの問題を解決することです。ただし、適切に構造化され、それを達成するために隠し/偽装された goto を使用しない方法を見つけることができればTree_To_List、私は興味があります。

また、テンプレートベースの抽象化のレイヤーが欠落しています (テンプレート c_Bin_Tree_Tool はすべての仕事を行うわけではありません - c_Tool はラッピングを終了しますが、再利用可能な形式ではなく、使用ごとの方法で行います。これは単なる副作用です関連するコードを抽出します。

このコードが行うことは、ノードを 1 つずつ挿入して不均衡なバイナリ ツリーを作成し、そのツリーのバランスをとることです。バランシングは、ツリーをリストに変換し (ある意味では既にそうです)、リストをツリーに変換することによって機能します。ツリーはバランス調整の前後に stdio にダンプされます。

bintree.h...

inline void* Ptr_Add  (void* p1, std::ptrdiff_t p2)  {  return (void*) (((std::ptrdiff_t) p1) + p2);  }

struct c_Bin_Tree_Closure
{
  typedef int (*c_Node_Comp) (void* p_Node1, void* p_Node2);

  c_Node_Comp    m_Node_Comp;
  std::ptrdiff_t m_Left, m_Right;
};

class c_BT_Policy_Closure
{
  private:
    const c_Bin_Tree_Closure* m_Closure;

  protected:
    void** Left_Of  (void* p)  {  return ((void**) Ptr_Add (p, m_Closure->m_Left ));  }
    void** Right_Of (void* p)  {  return ((void**) Ptr_Add (p, m_Closure->m_Right));  }

    int Compare_Node (void* p_Node1, void* p_Node2) const
    {
      return m_Closure->m_Node_Comp (p_Node1, p_Node2);
    }

  public:
    c_BT_Policy_Closure ()
    {
      m_Closure = 0;
    }

    void Set_Closure (const c_Bin_Tree_Closure& p_Closure)
    {
      m_Closure = &p_Closure;
    }
};

template<class tc_Policy>
class c_Bin_Tree_Tool : public tc_Policy
{
  public:
    c_Bin_Tree_Tool ()
    {
    }

    void *List_To_Tree (size_t p_Size, void* &p_List);
    void  Tree_To_List (void* p_Root, void* &p_First, void* &p_Last, size_t &p_Size);
    void  Balance      (void* &p);
    void  Insert       (void* &p_Tree, void* p_Node);
};

template<class tc_Policy>
void* c_Bin_Tree_Tool<tc_Policy>::List_To_Tree (size_t p_Size, void* &p_List)
{
  if (p_Size == 0)  return 0;

  size_t l_Size = p_Size / 2;
  void*  l_Ptr  = List_To_Tree (l_Size, p_List);

  void* l_This = p_List;
  p_List = *tc_Policy::Right_Of (l_This);

  *tc_Policy::Left_Of (l_This) = l_Ptr;

  l_Size = p_Size - (l_Size + 1);
  *tc_Policy::Right_Of (l_This) = List_To_Tree (l_Size, p_List);

  return l_This;
}

template<class tc_Policy>
void c_Bin_Tree_Tool<tc_Policy>::Tree_To_List (void* p_Root, void* &p_First, void* &p_Last, size_t &p_Size)
{
  //  Use left links as prev links and right links as next links

  void*  l_Start    = 0;         //  first-item-in-list pointer
  void*  l_Prev     = 0;         //  previous node in list
  void** l_Prev_Ptr = &l_Start;  //  points to the next (ie right) pointer for the next node.
  void*  l_Pos      = p_Root;
  void*  l_Next;
  void*  l_Parent   = 0;
  size_t l_Count    = 0;

  p_Last = 0;

  TOP_OF_LOOP:
    l_Next = *tc_Policy::Left_Of (l_Pos);

    if (l_Next != 0)
    {
      *tc_Policy::Left_Of (l_Pos) = l_Parent;  //  So we can find our way back up the tree
      l_Parent = l_Pos;
      l_Pos    = l_Next;
      goto TOP_OF_LOOP;
    }

  AFTER_STEP_PARENT:
    l_Next = *tc_Policy::Right_Of (l_Pos);

    *tc_Policy::Left_Of (l_Pos) = l_Prev;

    p_Last      = l_Pos;
    l_Prev      = l_Pos;
    *l_Prev_Ptr = l_Pos;
    l_Prev_Ptr  = tc_Policy::Right_Of (l_Pos);
    l_Count++;

    if (l_Next != 0)
    {
      l_Pos = l_Next;
      goto TOP_OF_LOOP;
    }

    if (l_Parent != 0)
    {
      l_Pos    = l_Parent;
      l_Parent = *tc_Policy::Left_Of (l_Pos);
      goto AFTER_STEP_PARENT;
    }

  *l_Prev_Ptr = 0;
  p_First     = l_Start;
  p_Size      = l_Count;
}

template<class tc_Policy>
void c_Bin_Tree_Tool<tc_Policy>::Balance (void* &p)
{
  void   *l_First, *l_Last;
  size_t l_Count;

  Tree_To_List (p, l_First, l_Last, l_Count);
  p = List_To_Tree (l_Count, l_First);
}

template<class tc_Policy>
void c_Bin_Tree_Tool<tc_Policy>::Insert (void* &p_Tree, void* p_Node)
{
  void** l_Tree = &p_Tree;

  while (*l_Tree != 0)
  {
    int l_Compare = tc_Policy::Compare_Node (*l_Tree, p_Node);
    l_Tree = ((l_Compare < 0) ? tc_Policy::Right_Of (*l_Tree) : tc_Policy::Left_Of (*l_Tree));
  }

  *l_Tree = p_Node;
  *tc_Policy::Right_Of (p_Node) = 0;
  *tc_Policy::Left_Of  (p_Node) = 0;
};

test_bintree.cpp...

#include <iostream>

#include "bintree.h"

struct c_Node
{
  c_Node *m_Left, *m_Right;
  int    m_Data;
};

c_Node g_Node0001 = { 0, 0,  1 };  c_Node g_Node0002 = { 0, 0,  2 };
c_Node g_Node0003 = { 0, 0,  3 };  c_Node g_Node0004 = { 0, 0,  4 };
c_Node g_Node0005 = { 0, 0,  5 };  c_Node g_Node0006 = { 0, 0,  6 };
c_Node g_Node0007 = { 0, 0,  7 };  c_Node g_Node0008 = { 0, 0,  8 };
c_Node g_Node0009 = { 0, 0,  9 };  c_Node g_Node0010 = { 0, 0, 10 };

int Node_Compare (void* p1, void* p2)
{
  return (((c_Node*) p1)->m_Data - ((c_Node*) p2)->m_Data);
}

c_Bin_Tree_Closure  g_Closure =
{
  (c_Bin_Tree_Closure::c_Node_Comp) Node_Compare,
  offsetof (c_Node, m_Left ),  offsetof (c_Node, m_Right)
};

class c_Tool : public c_Bin_Tree_Tool<c_BT_Policy_Closure>
{
  protected:
    typedef c_Bin_Tree_Tool<c_BT_Policy_Closure> c_Base;
  public:
    c_Tool ()  {  Set_Closure (g_Closure);  }
    void Insert  (c_Node* &p_Tree, c_Node* p_Node)  {  c_Base::Insert ((void*&) p_Tree, p_Node);  }
    void Balance (c_Node* &p)  {  c_Base::Balance ((void*&) p);  }
};

void BT_Dump (size_t p_Depth, c_Node* p_Node)
{
  if (p_Node != 0)
  {
    BT_Dump (p_Depth + 1, p_Node->m_Left);
    for (size_t i = 0; i < p_Depth; i++)  std::cout << " .";
    std::cout << " " << p_Node->m_Data << std::endl;
    BT_Dump (p_Depth + 1, p_Node->m_Right);
  }
}

int main (int argc, char* argv[])
{
  c_Tool  l_Tool;
  c_Node *l_Root = 0;

  l_Tool.Insert (l_Root, &g_Node0001);
  l_Tool.Insert (l_Root, &g_Node0002);
  l_Tool.Insert (l_Root, &g_Node0003);
  l_Tool.Insert (l_Root, &g_Node0004);
  l_Tool.Insert (l_Root, &g_Node0005);
  l_Tool.Insert (l_Root, &g_Node0006);
  l_Tool.Insert (l_Root, &g_Node0007);
  l_Tool.Insert (l_Root, &g_Node0008);
  l_Tool.Insert (l_Root, &g_Node0009);
  l_Tool.Insert (l_Root, &g_Node0010);

  BT_Dump (0, l_Root);  std::cout << "----------" << std::endl;

  l_Tool.Balance (l_Root);
  BT_Dump (0, l_Root);

  return 0;
}

期待される結果は...

 1
 . 2
 . . 3
 . . . 4
 . . . . 5
 . . . . . 6
 . . . . . . 7
 . . . . . . . 8
 . . . . . . . . 9
 . . . . . . . . . 10
----------
 . . . 1
 . . 2
 . 3
 . . . 4
 . . 5
 6
 . . . 7
 . . 8
 . 9
 . . 10

実際に何が起こるか (MinGW GCC 4.4.0、最適化されたリリース ビルド)...

 1
 . 2
 . . 3
 . . . 4
 . . . . 5
 . . . . . 6
 . . . . . . 7
 . . . . . . . 8
 . . . . . . . . 9
 . . . . . . . . . 10
----------
 1

私が知る限り、Balance 操作は正しく実行されますが、BT_Dump 関数はフィールドm_Leftとm_Rightフィールドへのすべての変更を確認できません。

編集それは間違っています-そうでなければ、ノード1を新しいルートと見なすのはなぜですか。数か月前に行われた調査の記憶に頼りすぎると、それが起こると思います。

編集実際には、ルートとしてのノード 1 は問題ですが、それは古いルートだったので、この問題を無視して独自の理論を構築するのが最善です ;-)

コードには、標準が定義されていないという点で、多くの問題があります。最大の問題は、ノード構造体のリンクが c_Node* であることだと思いますが、安全でないコードは c_Node について何も知らないため、(ポインター演算を介して) void* としてそれらにアクセスします。

修正の 1 つは、アンセーフ コードが getter および setter 関数ポインターを介してすべての読み取りと書き込みを行い、すべてのポインター演算を回避し、c_Node インスタンスへのすべてのアクセスが c_Node* ポインターを介して行われるようにすることです。さらに良いことに、インターフェイスは getter/setter メソッドなどを持つクラスになります。完全なバイナリ ツリー ライブラリでは、これを行う別のポリシー クラスがあります。 「ジャンク」フォルダーは、私がめったに使用しないことに基づいており、おそらくブースト侵入リストを使用する必要があります。

ただし、これにより、他のはるかに複雑で頻繁に使用されるコンテナー ライブラリが残り、なくなることはありません。offsetof とポインター演算を取り除くために、非常に骨の折れるリファクタリングを行う必要があると思いますが、...

C++ の規則とは正確には何ですか? また、上記のバイナリ ツリー コードを書き直して、ポインタ演算を引き続き使用し、ライブラリの内部と外部の両方でノードにアクセス/変更できるようにし、さらにこの最適化の問題を回避できるようにすることはできますか?

4

2 に答える 2

3

警告をオフにしましたか？これはまさに (void**) Ptr_Add(...

コンパイラーは、異なる型へのポインターが (いくつかの例外を除いて) エイリアスしないと自由に想定し、ポインターのターゲットをレジスターにキャッシュする最適化されたコードを生成します。これを回避するには、ユニオンを使用して異なるポインター型を変換する必要があります。http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Optionsからの引用:

特に、あるタイプのオブジェクトは、タイプがほとんど同じでない限り、別のタイプのオブジェクトと同じアドレスに存在することは決してないと見なされます。たとえば、unsigned int は int にエイリアスできますが、void* または double にはエイリアスできません。文字型は、他のどの型にも別名を付けることができます。

次のようなコードには特に注意してください。

     union a_union {
        int i;
        double d;
      };

     int f() {
        union a_union t;
        t.d = 3.0;
        return t.i;
      }

最後に書き込まれたものとは異なるユニオン メンバーから読み取る (「タイプ パニング」と呼ばれる) 慣行は一般的です。-fstrict-aliasing を使用しても、union 型を介してメモリにアクセスする場合は、型パニングが許可されます。したがって、上記のコードは期待どおりに機能します。構造体共用体列挙とビットフィールドの実装を参照してください。ただし、このコードでは次のことができない場合があります。

     int f() {
        union a_union t;
        int* ip;
        t.d = 3.0;
        ip = &t.i;
        return *ip;
      }

同様に、アドレスを取得し、結果のポインターをキャストし、結果を逆参照することによるアクセスには、キャストがユニオン型を使用している場合でも、未定義の動作があります。

     int f() {
        double d = 3.0;
        return ((union a_union *) &d)->i;
      }

-fstrict-aliasing オプションは、レベル -O2、-O3、-Os で有効になります。

あなたの場合、次のようなものを使用できます

union {
    void** ret_ptr;
    ptrdiff_t in_ptr;
}

しかし、ptr_add のコードはひどく見えます ;-)

または、「fno-strict-aliasing」でこの特定の最適化を無効にします。ただし、コードを修正することをお勧めします;-)

于 2010-09-09T08:35:37.370 に答える
0

テンプレートを不注意に使用すると、肥大化する可能性があります。しかし、あなたはここで要点を完全に見逃しています。

  • テンプレートは、慎重にではなく不用意に使用すると肥大化します。
  • テンプレートによって回避される実行時エラーの量は膨大です。
  • テンプレート化されたコードの速度は、テンプレート化されていないコードよりもはるかに高速です。
  • 組み込みシステムで実行しない限り、実行可能ファイルのサイズはごくわずかです。
  • STL は、使用するためのマップ コンテナー (二分探索ツリー) を提供します。

あなたはこれをまったく適切に考えていません。テンプレートが提供する利点は、実行可能サイズが数 kb であることをはるかに上回ります。

コードが Visual Studio 2010 で期待どおりに機能することも注目に値します。

于 2010-09-09T08:35:08.010 に答える