| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 836 人关注过本帖
标题:Unrolled linked list
只看楼主 加入收藏
mjh_abc
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2007-7-7
收藏
 问题点数:0 回复次数:0 
Unrolled linked list

Unrolled linked list
From Wikipedia, the free encyclopedia

In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references. It is related to the skip list and the B-tree.

Overview
A typical unrolled linked list node looks like this:

record node {
node next // reference to next node in list
int numElements // number of elements in this node, up to maxElements
array elements // an array of numElements elements, with space allocated for maxElements elements
}

Each node holds up to a certain maximum number of elements, typically just large enough so that the node fills a single cache line or a small multiple thereof. A position in the list is indicated by both a reference to the node and a position in the elements array. It's also possible to include a previous pointer for an unrolled doubly-linked linked list.

To insert a new element, we simply find the node the element should be in and insert the element into the elements array, incrementing numElements. If the array is already full, we first insert a new node either preceding or following the current one and move half of the elements in the current node into it.

To remove an element, similarly, we simply find the node it is in and delete it from the elements array, decrementing numElements. If numElements falls below maxElements ÷ 2 then we pull elements from adjacent nodes to fill it back up to this level. If both adjacent nodes are too low, we combine it with one adjacent node and then move some values into the other. This is necessary to avoid wasting space.

Performance

One of the primary benefits of unrolled linked lists is decreased storage requirements. All nodes (except at most one) are at least half-full. If many random inserts and deletes are done, the average node will be about three-quarters full, and if inserts and deletes are only done at the beginning and end, almost all nodes will be full.

Another advantage of unrolled linked lists is that they perform a number of operations, typically associated with arrays, much more quickly than ordinary linked lists. For example, when indexing into unrolled linked list, we can progress a node at a time rather than an element at a time, reducing the indexing time to O(n/m) instead of O(n).

Unrolled linked lists also perform sequential traversal much more rapidly, due to their cache behavior: iterating through an ordinary linked list of n elements triggers n cache misses in the worst case, and about 2nv/m in the best case, assuming v and s are about the same size. Iterating through an unrolled linked list of n elements triggers only 2n/m cache misses in the worst case and n/m in the best. Even arrays can do little better than this best case, with about n/(m+v/s) misses. When v is about s, linked lists have twice as many cache misses as unrolled linked lists in the best case, and m/2 times as many in the worst case, which in practice can speed up list traversal by as much as 10 times or more.

搜索更多相关主题的帖子: list linked STRONG Unrolled unrolled 
2007-08-10 08:10
快速回复:Unrolled linked list
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019630 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved