2

Cリストがあり、push_back関数を実装しました：

bool_t push_back_clist(clist_ptr pList, void* item)
{
    if(pList)
    {
        node_ptr pNode = new_node(item, pList->sizeof_item);
        if(!pNode) return FALSE;

        if(!pList->head)
            pList->head = pList->tail = pNode;
        else
        {
            pList->tail->next = pNode;
            pNode->prev = pList->tail;
            pList->tail = pNode;
        }

        pList->size++;
        return TRUE;
    }

    return FALSE;
}

static node_ptr new_node(void* data, size_t sizeof_item)
{
    node_ptr pNode = (node_ptr) malloc(sizeof(node_t));
    if(!pNode) return NULL;

     pNode->data = malloc(sizeof_item);

     if(!pNode->data)
     {
         free(pNode);
         return NULL;
     }

     memcpy(pNode->data, data, sizeof_item);
     pNode->next = pNode->prev = NULL;
     return pNode;
}

push_back_clistそれは機能しますが、関数とメソッドを比較するとstd::list.push_back、関数には約 2 倍の時間が必要であることに気付きました。なんで？関数のパフォーマンスを改善するにはどうすればよいですか? ありがとう。

4

3 に答える 3

5

malloc呼び出し回数を節約するために、データとノードを一度に割り当てることができます。

char* mem = malloc(sizeof(node_t)+sizeof_item);
// Check alloc here...
node_ptr pNode = (node_ptr)mem;
pNode->data = mem+sizeof(node_t);
于 2012-06-02T23:57:14.147 に答える
2

これはインターフェースの暗黙の変更であり、さらに文書化するのが難しいため、dasblinkenlightによって提案された単一の割り当てを使用する必要はないと思います。そのように割り当てられたアイテムは、異なるデータを格納したり、それらで見つかったデータを削除します。

可能な最適化のために、あなたのバージョンでは、制御フローが複雑すぎて、いくつかの最適化を妨げる可能性があると思います。割り当て機能に直接prevandフィールドを指定して、新しく割り当てられたアイテムに1回だけ触れてみてください。next次に、その割り当て機能の制御フローを合理化します。

static node_ptr new_node(void* data, size_t sizeof_item, node_ptr prev, node_ptr next)
{
     void * cdata = malloc(sizeof_item);
     if(!cdata) return NULL;
     memcpy(cdata, data, sizeof_item);

     node_ptr pNode = malloc(sizeof *pNode);
     if(pNode)
       *pNode = (struct node){ .data = cdata, .prev = prev, .next = next, };
     return pNode;
}

これは、C99互換コンパイラを使用している場合にのみそのまま機能します。そうでない場合は、取得することを再検討するか、複合リテラルの使用を一連の割り当てに変更してください。

いくつかの落とし穴：

  • Cには、現在（13年以降）独自のブール型がありbool、trueをfalse含めるとうまく機能するはずですstdbool.h。
  • のリターンをキャストしないでくださいmalloc
  • typedefのポインタ型は、Cコミュニティの多くの人から悪いスタイルと見なされています

編集：別のバージョンで少し遊んでみると、自分の設定（x86_64、linux、gcc、またはclang）で最も優れたアセンブラーを生成するために次のことがわかりました。

node_ptr new_node1(void* data, size_t sizeof_item, node_ptr next, node_ptr prev)
{
  node_ptr ret = NULL;
  void * nData = malloc(sizeof_item);
  if (!nData) return ret;
  struct node const nNode = {
    /* memcpy is unavoidable since nothing is known about the type of
       the data. But we can save a register by using the return value
       of memcpy. */
    memcpy(nData, data, sizeof_item),
    next,
    prev
  };
  /* Allocate the return value last so it may stay in the same return
     register */
  ret = malloc(sizeof *ret);
  if (!ret) return ret;
  /* Assignment is better than memcpy since this can just use "ret" as
     target address with offsets. */
  *ret = nNode;
  return ret;
}
于 2012-06-03T07:30:47.253 に答える
0

人々がここで言ったように、挿入ごとに 2 つのヒープ操作 (割り当て) を実行するため、リストは 2 倍遅くなります。

パフォーマンスの観点からは、ノードとデータに対して単一の割り当てを行うことをお勧めします。また、全体的なパフォーマンスがヒープの影響を大きく受ける場合は、代替ヒープを使用することができます (使用する必要があります)。そうすることで、パフォーマンスが 100 倍以上向上する可能性がありますが、これは過大評価ではありません。

于 2012-06-03T08:02:10.247 に答える