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方法进行比较时，我注意到我的函数需要大约两倍的时间。为什么？我怎样才能提高我的功能的性能？谢谢。

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字段，尝试仅触摸新分配的项目一次。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包含.c 应该可以很好地工作。truefalsestdbool.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 个堆操作（分配）。

从性能的角度来看，对节点 + 数据进行单一分配更为可取。此外，如果您的整体性能受到堆的显着影响，您可以（并且应该）使用替代堆。这样做可以将性能提高 100 倍甚至更多，这并不是一个高估。

于 2012-06-03T08:02:10.247 回答