h*****n
发帖数: 209 | 1 在Cache LRU实现的时候，为什么都是用doubly linked list而不是single linked
list呢？
请大牛赐教。 |
r*******e
发帖数: 971 | 2 Single LinkedList 的一大特点：要想删除一个节点，得找节点的上家，于是就得从头
找了。 |
h*****n
发帖数: 209 | |
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 的一大特点：要想删除一个节点，得找节点的上家，于是就得从头
找了。 |
|
|
h*****n
发帖数: 209 | |
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的一种
呢？ |
|
|
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 的时候用的。
: 这两个是相对独立的东西。说得不对欢迎指正啊。
|
|
|
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
|
