由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - 为什么Cache LRU多用doubly linked list而不是single linked list来实现呢?
相关主题
Interview Question关于c++的效率再给个例子
stl iterator has "NULL" like const?RAII和GC对应的两条技术路线
请问java /c++ 双修的大牛,java和c++最主要的区别是什么?c++程序员转java您认为最需要补充的知识是什么C++ OO approach to use multi-dim array for HPC
没有data store的model有什么用吗?map shared memory to local process
HOW TO DELETE IN KEY-VALUE STORE问个C++编译器如何处理函数内的static 变量
[合集] 一个数据结构问题继续挖坑JAVA和C++
哪儿有经典的C++ programing 习题集嘛?Memory Usage问题
这次Go丢人有点大呀请教关于C++内存管理
相关话题的讨论汇总
话题: lru话题: linked话题: list话题: cache话题: single
进入Programming版参与讨论
1 (共1页)
h*****n
发帖数: 209
1
在Cache LRU实现的时候,为什么都是用doubly linked list而不是single linked
list呢?
请大牛赐教。
r*******e
发帖数: 971
2
Single LinkedList 的一大特点:要想删除一个节点,得找节点的上家,于是就得从头
找了。
h*****n
发帖数: 209
3
明白了,多谢。
f***8
发帖数: 510
4
如果我没有理解错的话,SINGLE LINKLIST要删除一个节点没必要从头啊。比如我在的
指针在节点D,我要删除它,下一个节点是E。我只要白E中的数据拷贝到D中,然后把E
删了,这相当于删了D。我一直这样认为的。

【在 r*******e 的大作中提到】
: Single LinkedList 的一大特点:要想删除一个节点,得找节点的上家,于是就得从头
: 找了。

a***n
发帖数: 538
5
最后一个节点怎么删啊。

E

【在 f***8 的大作中提到】
: 如果我没有理解错的话,SINGLE LINKLIST要删除一个节点没必要从头啊。比如我在的
: 指针在节点D,我要删除它,下一个节点是E。我只要白E中的数据拷贝到D中,然后把E
: 删了,这相当于删了D。我一直这样认为的。

f***8
发帖数: 510
6
最后一个特殊处理一下呗,这样总不至于别的节点也要每次从头找

【在 a***n 的大作中提到】
: 最后一个节点怎么删啊。
:
: E

S*A
发帖数: 7142
7
你的假定是没有其他的数据结构直接使用 E 和 D 的指针。
这个在 Kernel 里面几乎是不可能的。
在 Linux 里面,这个 link list next 指针是嵌套在一个大的 struct 里面的。
所以这个实际使用还是不行。

E

【在 f***8 的大作中提到】
: 如果我没有理解错的话,SINGLE LINKLIST要删除一个节点没必要从头啊。比如我在的
: 指针在节点D,我要删除它,下一个节点是E。我只要白E中的数据拷贝到D中,然后把E
: 删了,这相当于删了D。我一直这样认为的。

f***8
发帖数: 510
8
恩,我说的最最简单的情况,只是想说SINGLE LINKED LIST要删除一个节点也不是非要
从头找一遍。

【在 S*A 的大作中提到】
: 你的假定是没有其他的数据结构直接使用 E 和 D 的指针。
: 这个在 Kernel 里面几乎是不可能的。
: 在 Linux 里面,这个 link list next 指针是嵌套在一个大的 struct 里面的。
: 所以这个实际使用还是不行。
:
: E

h*****n
发帖数: 209
9
在Cache LRU实现的时候,为什么都是用doubly linked list而不是single linked
list呢?
请大牛赐教。
r*******e
发帖数: 971
10
Single LinkedList 的一大特点:要想删除一个节点,得找节点的上家,于是就得从头
找了。
相关主题
[合集] 一个数据结构问题关于c++的效率再给个例子
哪儿有经典的C++ programing 习题集嘛?RAII和GC对应的两条技术路线
这次Go丢人有点大呀C++ OO approach to use multi-dim array for HPC
进入Programming版参与讨论
h*****n
发帖数: 209
11
明白了,多谢。
f***8
发帖数: 510
12
如果我没有理解错的话,SINGLE LINKLIST要删除一个节点没必要从头啊。比如我在的
指针在节点D,我要删除它,下一个节点是E。我只要白E中的数据拷贝到D中,然后把E
删了,这相当于删了D。我一直这样认为的。

【在 r*******e 的大作中提到】
: Single LinkedList 的一大特点:要想删除一个节点,得找节点的上家,于是就得从头
: 找了。

a***n
发帖数: 538
13
最后一个节点怎么删啊。

E

【在 f***8 的大作中提到】
: 如果我没有理解错的话,SINGLE LINKLIST要删除一个节点没必要从头啊。比如我在的
: 指针在节点D,我要删除它,下一个节点是E。我只要白E中的数据拷贝到D中,然后把E
: 删了,这相当于删了D。我一直这样认为的。

f***8
发帖数: 510
14
最后一个特殊处理一下呗,这样总不至于别的节点也要每次从头找

【在 a***n 的大作中提到】
: 最后一个节点怎么删啊。
:
: E

S*A
发帖数: 7142
15
你的假定是没有其他的数据结构直接使用 E 和 D 的指针。
这个在 Kernel 里面几乎是不可能的。
在 Linux 里面,这个 link list next 指针是嵌套在一个大的 struct 里面的。
所以这个实际使用还是不行。

E

【在 f***8 的大作中提到】
: 如果我没有理解错的话,SINGLE LINKLIST要删除一个节点没必要从头啊。比如我在的
: 指针在节点D,我要删除它,下一个节点是E。我只要白E中的数据拷贝到D中,然后把E
: 删了,这相当于删了D。我一直这样认为的。

f***8
发帖数: 510
16
恩,我说的最最简单的情况,只是想说SINGLE LINKED LIST要删除一个节点也不是非要
从头找一遍。

【在 S*A 的大作中提到】
: 你的假定是没有其他的数据结构直接使用 E 和 D 的指针。
: 这个在 Kernel 里面几乎是不可能的。
: 在 Linux 里面,这个 link list next 指针是嵌套在一个大的 struct 里面的。
: 所以这个实际使用还是不行。
:
: E

h*****n
发帖数: 209
17
还想问一下,这个cache LRU是不是用一个简单的circular buffer也可以实现啊?
为啥大家要弄doubley linked list呢?
g*****g
发帖数: 34805
18
circular buffer只是 double linked list的一种。

【在 h*****n 的大作中提到】
: 还想问一下,这个cache LRU是不是用一个简单的circular buffer也可以实现啊?
: 为啥大家要弄doubley linked list呢?

h*****n
发帖数: 209
19
Thanks.
circular buffer可以用数组实现啊,为什么好虫认为它是doubley linked list的一种
呢?
h*****n
发帖数: 209
20
Thanks.
circular buffer可以用数组实现啊,为什么好虫认为它是doubley linked list的一种
呢?
相关主题
map shared memory to local processMemory Usage问题
问个C++编译器如何处理函数内的static 变量请教关于C++内存管理
继续挖坑JAVA和C++c++ linking problem
进入Programming版参与讨论
L***s
发帖数: 1148
21
你的理解是对的。circular doubly linked list
是 circular buffer 这种 ADT 的一种具体实现方式。

【在 h*****n 的大作中提到】
: Thanks.
: circular buffer可以用数组实现啊,为什么好虫认为它是doubley linked list的一种
: 呢?

S*A
发帖数: 7142
22
用数组实现 LRU 有效率问题。
LRU 经常做的一件事是 update 里面的一个 entry。
如果entry 在 list 里面,拿出来,然后放到最前面。
用数组实现的话,添加在头容易,在头指针添加就可以了。
但是如果拿出来的话,原来的位置就会留下一个空洞。
空洞如果不清理,你的数组就会不断长大。如果每次清理,
就要把这个空洞填上,数组前面的元素后移动来填。
这个操作就比较昂贵,因为要移动最坏情况 N 个元素。

【在 h*****n 的大作中提到】
: Thanks.
: circular buffer可以用数组实现啊,为什么好虫认为它是doubley linked list的一种
: 呢?

g*****g
发帖数: 34805
23
double linked list存储加hashtable索引是常见做法。circular buffer是不增加
buffer size的,用数组存储性能问题很严重。

【在 S*A 的大作中提到】
: 用数组实现 LRU 有效率问题。
: LRU 经常做的一件事是 update 里面的一个 entry。
: 如果entry 在 list 里面,拿出来,然后放到最前面。
: 用数组实现的话,添加在头容易,在头指针添加就可以了。
: 但是如果拿出来的话,原来的位置就会留下一个空洞。
: 空洞如果不清理,你的数组就会不断长大。如果每次清理,
: 就要把这个空洞填上,数组前面的元素后移动来填。
: 这个操作就比较昂贵,因为要移动最坏情况 N 个元素。

S*A
发帖数: 7142
24
不是很清楚你说的 double linked list + hashtable 来实现
circular buffer 是不是很常见。
Wikipedia 和 Boost里的 C 和 C++ 实现就是一个 buffer
加 head, tail 指针。当然这个 buffer size 需要的话可以调整。
http://en.wikipedia.org/wiki/Circular_buffer
http://www.boost.org/doc/libs/1_39_0/libs/circular_buffer/doc/c

【在 g*****g 的大作中提到】
: double linked list存储加hashtable索引是常见做法。circular buffer是不增加
: buffer size的,用数组存储性能问题很严重。

g*****g
发帖数: 34805
25
我说的是 LRU, LRU O1的访问时间是必须的。

【在 S*A 的大作中提到】
: 不是很清楚你说的 double linked list + hashtable 来实现
: circular buffer 是不是很常见。
: Wikipedia 和 Boost里的 C 和 C++ 实现就是一个 buffer
: 加 head, tail 指针。当然这个 buffer size 需要的话可以调整。
: http://en.wikipedia.org/wiki/Circular_buffer
: http://www.boost.org/doc/libs/1_39_0/libs/circular_buffer/doc/c

S*A
发帖数: 7142
26
哦,明白。我还以为你还在说那个 circular buffer.
kernel 里面的比较大的 LRU 就是 active page 的 LRU。
拿个就是 double link list。没有另外的 hash table。
当然 kernel 也不需要访问第几个 item 这样的操作。

【在 g*****g 的大作中提到】
: 我说的是 LRU, LRU O1的访问时间是必须的。
g*****g
发帖数: 34805
27
我说的是 LRU cache, 一般是 key value pair.

【在 S*A 的大作中提到】
: 哦,明白。我还以为你还在说那个 circular buffer.
: kernel 里面的比较大的 LRU 就是 active page 的 LRU。
: 拿个就是 double link list。没有另外的 hash table。
: 当然 kernel 也不需要访问第几个 item 这样的操作。

y**********u
发帖数: 6366
28
Not exactly
If you take a look at how linux kernel implement lru_cache, the lc_element
is not only a double linklist node, but also a hlist node
http://lxr.free-electrons.com/source/include/linux/lru_cache.h?
look up lc_element is based on lc_find which uses classic hashmap lookup

【在 S*A 的大作中提到】
: 不是很清楚你说的 double linked list + hashtable 来实现
: circular buffer 是不是很常见。
: Wikipedia 和 Boost里的 C 和 C++ 实现就是一个 buffer
: 加 head, tail 指针。当然这个 buffer size 需要的话可以调整。
: http://en.wikipedia.org/wiki/Circular_buffer
: http://www.boost.org/doc/libs/1_39_0/libs/circular_buffer/doc/c

S*A
发帖数: 7142
29
你说的这个是另外的实现,kernel paging 没有用这个 lc_cache.
这个 lc_cache 找了一下 reference 大概就是 block driver 里面
某个驱动用了,比较明显的用户只有这一个。和我说的 MMU paging
的 LRU 不是一个东西。这个 LC 看上每个 entry 占内存挺多的。
应该不会用在 page 上面。
LRU 本身并不需要 hashmap。那个是 cache lookup 的时候用的。
这两个是相对独立的东西。说得不对欢迎指正啊。

【在 y**********u 的大作中提到】
: Not exactly
: If you take a look at how linux kernel implement lru_cache, the lc_element
: is not only a double linklist node, but also a hlist node
: http://lxr.free-electrons.com/source/include/linux/lru_cache.h?
: look up lc_element is based on lc_find which uses classic hashmap lookup

y**********u
发帖数: 6366
30
kernel paging is another story because linux has page table which everybody
knows
Do kernel paging needs a table?

element

【在 S*A 的大作中提到】
: 你说的这个是另外的实现,kernel paging 没有用这个 lc_cache.
: 这个 lc_cache 找了一下 reference 大概就是 block driver 里面
: 某个驱动用了,比较明显的用户只有这一个。和我说的 MMU paging
: 的 LRU 不是一个东西。这个 LC 看上每个 entry 占内存挺多的。
: 应该不会用在 page 上面。
: LRU 本身并不需要 hashmap。那个是 cache lookup 的时候用的。
: 这两个是相对独立的东西。说得不对欢迎指正啊。

相关主题
请教一个MS Linked List的问题stl iterator has "NULL" like const?
exe file compild by C++ cannot be run by another computer请问java /c++ 双修的大牛,java和c++最主要的区别是什么?c++程序员转java您认为最需要补充的知识是什么
Interview Question没有data store的model有什么用吗?
进入Programming版参与讨论
S*A
发帖数: 7142
31

everybody
但是你说的那个 Cache LRU 基本上没有被其他的 kernel 服务
用。仅仅是某个驱动自己带进来的。kernel 的 用到 cache 的模块
和代码很多。
你要是感兴趣,那个 struct page 的定义在这里,那个 double link list
的 lru 变量在 96行。
http://lxr.free-electrons.com/source/include/linux/mm_types.h?v
不知道你想问的是那个 table。 kernel MMU 有很多类似 table 的东西。
但是估计不是你想要的那种 lookup table。就我知道 MMU 里和 paging
LRU 绑一起的没有。要是你知道有欢迎指出来。

【在 y**********u 的大作中提到】
: kernel paging is another story because linux has page table which everybody
: knows
: Do kernel paging needs a table?
:
: element

1 (共1页)
进入Programming版参与讨论
相关主题
请教关于C++内存管理HOW TO DELETE IN KEY-VALUE STORE
c++ linking problem[合集] 一个数据结构问题
请教一个MS Linked List的问题哪儿有经典的C++ programing 习题集嘛?
exe file compild by C++ cannot be run by another computer这次Go丢人有点大呀
Interview Question关于c++的效率再给个例子
stl iterator has "NULL" like const?RAII和GC对应的两条技术路线
请问java /c++ 双修的大牛,java和c++最主要的区别是什么?c++程序员转java您认为最需要补充的知识是什么C++ OO approach to use multi-dim array for HPC
没有data store的model有什么用吗?map shared memory to local process
相关话题的讨论汇总
话题: lru话题: linked话题: list话题: cache话题: single