通缉：C中非常快速的链接列表

I am trying to implement a singly linked list in C. A common implementation that you see floating around the internet is something like

我试图在C中实现一个单独的链接列表。你看到在互联网上浮动的常见实现是类似的

typedef struct {
  int head;
  Node *tail;
} Node;

with methods like

用像这样的方法

Node cons(int head, Node tail) {
  Node y;
  y.head = head;
  y.tail = malloc(sizeof(Node));
  *y.tail = tail;
}

Performance is very important. Is there any way to implement a linked list in C that will be faster than this? For example, getting rid of the memory allocation (y.tail = malloc(sizeof(Node))) should provide a significant speed increase.

表现非常重要。有没有办法在C中实现比这更快的链表?例如,摆脱内存分配(y.tail = malloc(sizeof(Node)))应该会显着提高速度。

8 个解决方案

#1

Yes there is... This is called as a memory pool. Similar to a thread pool. Basically you allocate an area of memory at the beginning of the program of type Node. Pointers to this area are stored in an array. In your cons function all you do is get the pointers from the array. This does not improve the overall speed, but if you have frequent memory allocations this will increase the responsiveness of the program at the cost of some space for the array

是的有...这被称为内存池。类似于线程池。基本上,您在Node类型的程序开头分配一个内存区域。指向此区域的指针存储在一个数组中。在你的cons函数中,你所做的就是从数组中获取指针。这并没有提高整体速度,但如果你经常进行内存分配,这会增加程序的响应速度,代价是阵列的某些空间

#2

Very fast appending to a linked list? A rope (not limited to strings with small modifications) would allow you to batch allocate memory (improving perfomance) while not penalizing appending to the end of the list.

非常快速地附加到链表?绳索(不限于经过少量修改的字符串)将允许您批量分配内存(提高性能),同时不会在附加到列表末尾的情况下进行惩罚。

#3

What operation shall be fast: insertion, retrieval, all ? There is always a trade-off. Does your solution need to be scalable ? Linked list are not.

什么操作应该快:插入,检索,所有?总是需要权衡。您的解决方案是否需要可扩展?链接列表不是。

Should you want/need to stick to a linked list, you could store it into an array of structs having a field indicating the index of the next entry in the linked list. Insertion will be very fast, without any allocation, the downside being you have to know the number of elements in advance - or to reallocate the table when it's getting full.

如果您希望/需要坚持链接列表,您可以将其存储到结构数组中,该结构数组具有指示链接列表中下一个条目的索引的字段。插入将非常快,没有任何分配,缺点是您必须提前知道元素的数量 - 或者在表格满了时重新分配表格。

Refer to the "Linked lists using arrays of nodes" subsection of the Wikipedia page on linked list.

请参阅链接列表上Wikipedia页面的“使用节点数组的链接列表”子部分。

#4

Memory concerns aside, some thoughts on making single link lists faster.

除了内存问题,一些关于使单个链接列表更快的想法。

I think there is a bit of confusion in your code. At it's very core a linked list is:

我认为您的代码中存在一些混淆。在它的核心链接列表是:

typdef struct _node {
     ...
     struct _node *next;
} NODE;

Most implementations would have a void * in there to hang the payload on. That is not particularly important for now.

大多数实现都会有一个void *来挂起有效负载。这对现在来说并不是特别重要。

List inserts must connect the pointers. For simply adding the node (and ignoring the adding the payload) there 1 assignment if the node is going at the head or tail of a list, and 2 if it is going in the middle. There isn't much that can be done to get around that.

列表插入必须连接指针。对于简单地添加节点(并忽略添加有效载荷),如果节点位于列表的头部或尾部,则进行1次分配;如果节点位于中间,则进行2次分配。没有太多办法可以解决这个问题。

Occasionally simple lists only use node structures, so tail inserting requires traversal. This is costly. Having a special head structure with knowledge of the first and last node removes that cost.

有时,简单列表仅使用节点结构,因此尾部插入需要遍历。这很昂贵。拥有一个具有第一个和最后一个节点知识的特殊头部结构可以消除这种成本。

Traversals can be made faster by implementing this as a skip-list (http://en.wikipedia.org/wiki/Skip_list). Though some care needs to be taken during node insertion to optimize (and you get more pointer assignments during insertion).

通过将其作为跳过列表(http://en.wikipedia.org/wiki/Skip_list)实现,可以更快地实现遍历。虽然在节点插入期间需要注意优化(并且在插入期间会获得更多指针分配)。

#5

If you are concerned with malloc fragmentation, you could request a large multiple number of size Node and keep incrementing a pointer by sizeof(Node) every time you copy Node values.

如果您关注malloc碎片,则可以请求大量多个大小的Node,并在每次复制Node值时通过sizeof(Node)继续递增指针。

#6

I would suggest you to use the linux kernel list implementation:

我建议你使用linux内核列表实现:

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=include/linux/list.h

(no additional memory allocation)

(没有额外的内存分配)

#7

Check the speed of this singly linked list implementation as well:

检查这个单链表实现的速度:

http://web.archive.org/web/20071103112712/http://stsdas.stsci.edu/bps/linked_list.html

#8

If the only operations you need is pushing, popping and iterating then instead of linked list you could put elements into an array. Pushing and popping element is just to modify one number (index of the first or the last element). Front and back of the array can be cyclically connected so elements can be freely pushed without a problem that the array ends.

如果您需要的唯一操作是推送,弹出和迭代,那么您可以将元素放入数组中而不是链接列表。推送和弹出元素只是修改一个数字(第一个或最后一个元素的索引)。阵列的正面和背面可以循环连接,因此可以*推动元件,而不会出现阵列结束的问题。

#1

#2