[TL][优化]如何设计一个高效的cache?

[Lucas Zhang]

我现在在做一个手机平台上的软件，现在的I/O瓶颈是一个用seek读取img文件的函数。在我的测试里，一共调用了这个函数7480325次，读取的bytes offset位置是从6800到130000，也就是说，平均一个位置的byte会被重复读到平均100次左右(实际情况是有的byte会被读到3到4次，有的会被读到1000次以上)。下面是一些统计数据：

bytes offset 6800 ~ 6900: 170884 times

bytes offset 6900 ~ 7000: 220944 times

bytes offset 7000 ~ 7100: 24216 times

bytes offset 7100 ~ 7200: 9576 times

bytes offset 7200 ~ 7300: 14813 times

bytes offset 7300 ~ 7400: 22109 times

bytes offset 7400 ~ 7500: 19748 times

bytes offset 7500 ~ 7600: 43110 times

bytes offset 7600 ~ 7700: 157976 times

...

bytes offset 121200 ~ 121300: 1514 times

bytes offset 121300 ~ 121400: 802 times

bytes offset 121400 ~ 121500: 606 times

bytes offset 121500 ~ 121600: 444 times

bytes offset 121600 ~ 121700: 398 times


max_bytes_offset 121703

min_bytes_offset 6848

于是我想到做一个cache来优化函数的性能。由于之前也没怎么接触过cache，仅限于课本上的一点知识，我在google了一番后，发现比较好的方法是用hash表和双向链表来实现LRU策略的cache.这里有个链接。如果要把所有位置的数据都搬到内存的话，大概是130KB左右。我想到一个简单的方法，用1300个桶来hash 130000个bytes offset位置，然后每个桶有个最大长度是10的双向链表来存查询的数据。这样的话可以13K搞定。这种方法比较好实现，维护起来也比较简单，但是离达到高效还有段距离，主要有以下问题：

1.在我的统计数据里，有些区段读取率很高，有些区段则读取率低一些，怎样让cache来适应这种结构呢？

2.在这种实现下，每次查询数据的时候，都在从双向链表的头开始往下遍历，平均要5次才能找到数据。有没有更好的结构来进行搜索呢？二叉树的话维护成本和复杂度又太大了。

3.不同的手机平台可以允许有不同的cache大小，怎么让cache根据手机平台来改变大小呢？除了变化桶的个数和双向链表的长度外。

组里应该有同学做过cache方面的东西，大家给点建议吧，介绍些相关的理论和paper也可以。Thx~

--
Zhang Qing (张卿)
@SJTU ShangHai

[chuang]

1.在我的统计数据里，有些区段读取率很高，有些区段则读取率低一些，怎样让cache来适应这种结构呢？

LRU就是这个目的,当空间有限的时候,读取率低的会被淘汰掉.

2.在这种实现下，每次查询数据的时候，都在从双向链表的头开始往下遍历，平均要5次才能找到数据。有没有更好的结构来进行搜索呢？二叉树的话维护成本和复杂度又太大了。

tokycabinet采用类平衡二叉树的机制在代码复杂度和查找速率之间进行了平衡,可以参见这里:

http://www.cppblog.com/converse/archive/2010/01/12/105500.html

当然,更省事的办法是增加hash桶的数量,看你空间大小了.

3.不同的手机平台可以允许有不同的cache大小，怎么让cache根据手机平台来改变大小呢？除了变化桶的个数和双向链表的长度外。

把cache模块作为可配置的?

我之前自己写过一个cache库,参见这里:

http://www.cppblog.com/converse/category/6498.html

LRU + hash-list或者hash-rbtree实现.

2010/7/7 Lucas Zhang <zhangq...@gmail.com>

[Milo Yip]

access pattern 是每次1個byte隨機讀取?

--
Milo Yip

Twitter @miloyip
http://www.cnblogs.com/miloyip/
http://miloyip.seezone.net/

[Lucas Zhang]

我每次读取一个装了4byte的32位int，然后再根据信息算出要读的bytes或者bits。 位置都是随机的。

2010/7/7 Milo Yip <mil...@gmail.com>

[Lucas Zhang]

回复的好快。先研究一下你们的方法~ 刚刚还有人建议我丢弃1300个桶+大小为10的双向链表的结构，用一个更大的hash table和双向链表来实现，好像效率会高很多，不过设计hash function又是一个问题。

2010/7/7 chuang <lichua...@gmail.com>

[wing fire]

在 2010年7月7日 下午5:15，Lucas Zhang <zhangq...@gmail.com>写道：

回复的好快。先研究一下你们的方法~ 刚刚还有人建议我丢弃1300个桶+大小为10的双向链表的结构，用一个更大的hash table和双向链表来实现，好像效率会高很多，不过设计hash function又是一个问题。

130k似乎不算很大啊，你直接开一个130k的数组，把数据都扔在里面，直接根据offset访问，不是最快？ 你分配内存的话，额外开销也是很昂贵的。

[chuang]

hash function有现成高效还保证冲突率小的 请搜索"bob hash" 好像是当前可知最好的hash算法 linux 内核里面也有了他的代码

2010/7/7 Lucas Zhang <zhangq...@gmail.com>

[Milo Yip]

如果沒有locality，cache是無效的。最簡單辦法是把最常讀的部分讀入內存(應該是最前的部分?)。其他就用I/O吧。

[Lucas Zhang]

不算cache的话，这部分的程序总共占内存才50k左右~ 130k在PC上看起来不多，在移动平台上就不一样啦，有的手机总共内存才2M左右，130k就很大了

2010/7/7 wing fire <wing...@gmail.com>

[wing fire]

在 2010年7月7日 下午5:32，Lucas Zhang <zhangq...@gmail.com>写道：

不算cache的话，这部分的程序总共占内存才50k左右~ 130k在PC上看起来不多，在移动平台上就不一样啦，有的手机总共内存才2M左右，130k就很大了

 

嗯，我在嵌入式上玩过几天，但是没有遇到内存这么紧张的情况，想当然了。

我觉得，如果我遇到这个问题的话，我觉得有必要进一步分析访问的统计数据。得出访问的统计趋势。如果数据访问有局部性的话，可以采用数据预取的办法。我对链表的效率表示怀疑。

---------------------------------------
绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

[DaiZW]

同没有实际经验.
不过为什么不参考CPU cache的实现原理呢?
1. 使用固定大小的块, 比如1KB
2. 通过地址(offset)对cache块进行映射. 例如将bytes offset 121xxx 映射到 (121xxx / 1024
- 6) % 13. 有多种映射方法: 直接映射, 全相联映射, 组相联映射.
3. 用LRU对块的淘汰进行管理.

直接用数组就可以了, 不懂为什么需要用双向链表和hash表.

2010/7/7 Lucas Zhang <zhangq...@gmail.com>:

[Lucas Zhang]

刚刚理解错locality的意思了-_-。 应该还是有一定locality的，不过规律还不是很明显。有没有什么方法来分析locality呢？用excel画张表观察么？附上一部分数据，能帮我看一下么？那张图是google doc生成的，有点丑...

p.s. google的链接是http://spreadsheets.google.com/ccc?key=0AuvTUxa1-cCodEp2VHd3dWY2SmYtdDViX0Y3WDZIRFE&hl=en&authkey=CNyEhpEM

2010/7/7 Milo Yip <mil...@gmail.com>

[DaiZW]

呃...有一点需要更正, 直接映射不需要用LRU

2010/7/7 DaiZW <shinys...@gmail.com>:

[许峰峰]

1，可以考虑重新 排版 img 文件，让 局部性更强。

2，像 

DaiZW

  同学说的那样，文件offset 其实就像内存地址，用cpu的缓存方式就可以了。

[Milo Yip]

看來分佈非常集中。
建議類似做virtual memory，用page為單位去做LRU。page大小和平台(例如seek時間、read速率)及輸入數據有關，可以做實驗得出最優值。

[ilived.cn]

我怎么感觉是不是像MMU的实现

2010/7/7 DaiZW <shinys...@gmail.com>

[HaoPeiQiang]

我还是怀疑你的业务是什么，你这个貌似不是个通常的逻辑，你大致的描述下业务吧

2010/7/7 ilived.cn <ilived.cn@gmail.com>

--
Tinyfool的开发日记 http://www.tinydust.net/dev/
代码中国网 http://www.codechina.org
myTwitter: http://twitter.com/tinyfool

[wei...@gmail.com]

同意这种观点，主要是page的替换算法，这种做法还有个好处就是不同的手机平台可以允许有不同的cache大小，

On 7月7日, 下午7时27分, Milo Yip <milo...@gmail.com> wrote:
> 看來分佈非常集中。
> 建議類似做virtual memory，用page為單位去做LRU。page大小和平台(例如seek時間、read速率)及輸入數據有關，可以做實驗得出最優值。
>

> 在 2010年7月7日下午6:49，Lucas Zhang <zhangqing1...@gmail.com> 寫道：
>
>
>
>
>
> > 刚刚理解错locality的意思了-_-。

> > 应该还是有一定locality的，不过规律还不是很明显。有没有什么方法来分析locality呢？用excel画张表观察么？附上一部分数据，能帮我看一下 么？那张图是google
> > doc生成的，有点丑...
> > p.s.
> > google的链接是http://spreadsheets.google.com/ccc?key=0AuvTUxa1-cCodEp2VHd3dWY2SmYtd...
>
> > 2010/7/7 Milo Yip <milo...@gmail.com>
>
> >> 如果沒有locality，cache是無效的。最簡單辦法是把最常讀的部分讀入內存(應該是最前的部分?)。其他就用I/O吧。

>
> >> 在 2010年7月7日下午5:10，Lucas Zhang <zhangqing1...@gmail.com> 寫道：
> >> > 我每次读取一个装了4byte的32位int，然后再根据信息算出要读的bytes或者bits。 位置都是随机的。
>

> >> > 2010/7/7 Milo Yip <milo...@gmail.com>

[Lucas Zhang]

img 文件里装的是一个复杂的trie和各种table，重新排版估计很难
明天再试试cpu的缓存方式，不过看完球不知道能不能撑住-_-

2010/7/7 许峰峰 <yanwu...@gmail.com>

[Lucas Zhang]

用数组的话 LRU怎么对块的淘汰进行管理呢？不需要遍历么？ 双向链表的优点是每次淘汰的都是尾指针指向的元素，每次加入的元素都在最前面，每次读取的元素次数加一后，可以很方便的移动到有序的位置。数组的话这些开销就很大了吧。

2010/7/7 DaiZW <shinys...@gmail.com>

[Lucas Zhang]

这个可以试一试

2010/7/7 Milo Yip <mil...@gmail.com>

[DaiZW]

LRU的确需要遍历.

你说的这种方法似乎应该叫做"时钟页面替换算法"? 是"第二次机会页面置换算法"的一种变形, 不是基于时间计数而是基于访问计数的.
这种方法的效率应该还不错.

总之淘汰策略有很多啦, 重要的是选择合适的算法和合适的数据结构.

2010/7/7 Lucas Zhang <zhangq...@gmail.com>:

[Milo Yip]

我之前建議用page，所有pages放進一個連續buffer裡。
另外做一個雙向鏈表做LRU。不用O(n)遍歷可以取得least recently used page。
怕寫錯可先用數組遍歷也可以，page數量不多。

--

[chuang]

不明白为什么需要O(N)遍历呢?如果一个链表上存放的是被访问的数据,假如访问过一次的数据每次往前走一步,那么最少被访问到的在链表尾了,不需要遍历即可得到.

2010/7/7 Milo Yip <mil...@gmail.com>

[Milo Yip]

我是說用雙向鏈表不用O(N)遍歷啊，用數組存timestamp才需要。

在 2010年7月8日上午1:49，chuang <lichua...@gmail.com> 寫道：
> 不明白为什么需要O(N)遍历呢?如果一个链表上存放的是被访问的数据,假如访问过一次的数据每次往前走一步,那么最少被访问到的在链表尾了,不需要遍历即可得到.
>
> 2010/7/7 Milo Yip <mil...@gmail.com>
>>
>> 我之前建議用page，所有pages放進一個連續buffer裡。
>> 另外做一個雙向鏈表做LRU。不用O(n)遍歷可以取得least recently used page。
>> 怕寫錯可先用數組遍歷也可以，page數量不多。
>>
>> 在 2010年7月7日下午10:31，Lucas Zhang <zhangq...@gmail.com> 寫道：
>> > 用数组的话 LRU怎么对块的淘汰进行管理呢？不需要遍历么？
>> >
>> > 双向链表的优点是每次淘汰的都是尾指针指向的元素，每次加入的元素都在最前面，每次读取的元素次数加一后，可以很方便的移动到有序的位置。数组的话这些开销就很大了吧。

--

[wing fire]

之前约了人吃饭，没仔细估算。我估算了一下你的方案内存用量：

》用1300个桶来hash 130000个bytes offset位置，然后每个桶有个最大长度是10的双向链表来存查询的数据。这样的话可以13K搞定

1300个桶，key+一个到链表的指针，就是8字节，这部分就要8*1.3k=10.4k. 双向链表的一个节点包括前后指针，数据，就是12个字节，内存消耗峰值时，链表平均长度为最大长度的一半5 ，一半已经过于乐观了。如此，链表内存将有1.3k*12*5=78k.这最少就要88.4k内存了。而不是你估计的13k。

为了实现LRU，在没有硬件支持的情况下，你至少要设个时间戳吧？假设时间戳为32位，如果粒度放到桶上，又增加5.2k，但是很可能效果不佳。放到节点上，需要1.3k*4*5=26k.

如果LRU只针对桶内数据，利用链表取出-->放到队尾的办法，可以不增加数据，但是：1.效果不佳 2.变慢，或需要额外数据记录队尾。

如果要针对所有数据进行LRU，额外空间不可避免。

所以，我的看法是，你的cache设想和malloc一个130k的数组相比，节省的内存有限，而速度大大下降。

---------------------------------------
绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

[chuang]

看错,乌龙了:)

2010/7/8 Milo Yip <mil...@gmail.com>

[Lucas Zhang]

恩，我也算了一下，情况很不乐观:-(
所以更需要高效的设计了~

2010/7/8 wing fire <wing...@gmail.com>

[DaiZW]

或许lz不需要这么多个桶(页/块, whatever).

如果用链表/hash表这类数据结构, 光是指针的空间开销就不小.
所以还是建议使用长度较小的数组(例如<20), 即使O(N)遍历, 效率也不会差到哪里去.

2010/7/8 wing fire <wing...@gmail.com>

[Changsheng Jiang]

不懂手机平台, 想在PC上, 这种事情一般是交给内核做. 应用程序为降低系统调用次数, 一般是用 mmap 映射文件.

最大才 121703, 内存也存得下吧?

Hash表, 在 PC 上, 开放地址碰撞方案, 比链表方案要快, 减少指针跳跃, 也省指针内存. 只是要求哈稀函数不能太差.

                                                     Changsheng Jiang

2010/7/8 DaiZW <shinys...@gmail.com>

[Mikster.Z]

我觉得在数据结构上调优的效果受到紧张的空间和高效的制约，无论如何也没有完美的方案，cache的结构越简单越好，bucket/Array已经足够好了。根据数据的特性设计一个好的hash，这个上面获得的提升才会大。

[Christian]

是校友啊。
我觉得可以采用类似OS的page调度的机制。从图上看调用的地址集中在0-20000和20000-40000这个区间。可以先将130K的文件切割成13个10K的page存储在外存，系统初始化时可以将这两个区间的page都装入(40K)，系统维护一张简单表存储各page的读取次数。当出现调用地址不在内存page中时，再从外存读取，同时更新存储page读取次数的表，当某外部page读取大于内部page时swap，或者也可以用LRU对page进行调度。一般来说，连续数据读取是有相关性的。

--
因为无知而傲慢，因为有知而谦逊

[wing fire]

在考虑cache之前，我觉得你有许多值得再考虑的地方。

我觉得，你这个问题里面，"7480325次"函数调用是很可疑的。如果你的130K就是图像文件大小的话，你的每个像素平均至少访问了57次。我实在很难想象什么样的算法需要如此反复地访问同一个数据，我怀疑其算法的合理性。这都快赶上Ray tracing的计算量了。

我认为第一步是要评估和测量，那个外部调用者的算法复杂度和性能。

假设外面的算法确实是合理的，你现在的测量数据还是不够。需要测量数据访问的局部性。如果局部性较好的话，一个buffer就能解决问题了。局部性差一点，就开大一点的buffer，或者双buffer等等。如何选择依赖于数据访问的特征。

万一数据访问真的是随机分布的（个人认为不太可能），在你这个问题上，cache仍然是个中庸，但是效果不佳的方案。还不如对图像先做预处理，生成辅助数据结构，然后再做访问，而不是看上去很动态的LRU。

---------------------------------------

绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

[HaoPeiQiang]

我的看法类同，我觉得多半是你业务逻辑有什么问题……

2010/7/8 wing fire <wing...@gmail.com>

[qiaojie]

他说了“img 文件里装的是一个复杂的trie和各种table，重新排版估计很难”

估计是个字典或者输入法之类的软件。解决方案除了重新设计数据结构之外

用cache也不是不能解决。但是cache结构的设计很重要，用什么链表Hash表

之类都是不可取的，应该采用类似CPU常用的关联式cache，关联式cache只

需要额外1/16的内存存放tag，LRU之类的信息。

2010/7/8 wing fire <wing...@gmail.com>

[wing fire]

在 2010年7月8日 上午10:18，Mikster.Z <china...@gmail.com>写道：

我觉得在数据结构上调优的效果受到紧张的空间和高效的制约，无论如何也没有完美的方案，cache的结构越简单越好，bucket/Array已经足够好了。根据数据的特性设计一个好的hash，这个上面获得的提升才会大。

在 2010年7月8日 上午10:04，Changsheng Jiang <jiang...@gmail.com>写道：

不懂手机平台, 想在PC上, 这种事情一般是交给内核做. 应用程序为降低系统调用次数, 一般是用 mmap 映射文件.

最大才 121703, 内存也存得下吧?

不知道楼主的平台是什么。我玩的基本上和PC没啥区别，mmap也有，用来取代file io可以大幅度提高性能。

 

Hash表, 在 PC 上, 开放地址碰撞方案, 比链表方案要快, 减少指针跳跃, 也省指针内存. 只是要求哈稀函数不能太差.

                                                     Changsheng Jiang

2010/7/8 DaiZW <shinys...@gmail.com>

或许lz不需要这么多个桶(页/块, whatever).

如果用链表/hash表这类数据结构, 光是指针的空间开销就不小.
所以还是建议使用长度较小的数组(例如<20), 即使O(N)遍历, 效率也不会差到哪里去.

如果访问大体上是随机的，且，大部分数据至少被访问一次，桶少了根本没用，被反复命中的概率仍然太低。

如果访问不是完全随机的，为什么要用LRU呢？

[Lucas Zhang]

那个函数的算法的确挺复杂的，是个字典里面的八叉树搜索，读写磁盘文件相当频繁，所以才想到做一个cache。
手机平台主要是WM和Android吧，不过有些机型内存很吃紧。
之前没做过cache方面的东西，发现还有很多地方要学习。
再请教一下，怎样测量数据访问的局部性呢？search了一下没找到很有用的帮助... thx

2010/7/8 wing fire <wing...@gmail.com>

[wing fire]

去除无价值的访问是关键。

无论img里面的数据是什么格式，我们都可以根据上层应用的需要，重新组织数据结构，然后把这个结构的数据写到一个额外的文件中，以帮助应用层访问数据。且不说是不是适合这里的情况，但肯定是能做到的。

虽然CPU cache很重要。但是，很遗憾，这需要硬件支持。没有硬件，一不小心就引入一个O(lgN)/O(N)的算法复杂度来，这并不少见。至于直接利用硬件，在我的职业生涯中，我从未在项目中见过有人利用这一点来做哪怕是页面的交换，信号系统貌似还好点，可以重试，SEH就不是一般的麻烦了。

对楼主的问题，我的猜测，对block，而不是每个值做cache就足够好了。 将数据分成若干block，比如130个1k的块。然后弄个bitmap，17个字节，标记对应块是否在内存。然后根据系统限制或配置，new一大块内存（n*1k)，差不多就够用了。

---------------------------------------
绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

[wing fire]

关于八叉树搜索。我不清楚你具体怎么搜索的，还有整个树是否平衡。假设每一次搜索，是自顶向下，逐步访问的话，那么，可能满足 顶部访问就很密集，叶节点稀疏的特点，这就有数据局部性了。

如果是测量的话，先得到一个所有访问的序列(第几次，偏移），然后以访问序号为横坐标，偏移量为纵坐标，每次访问作为一个点，得到一张点阵图。颜色深的横线（是虚线），就是访问次数多的偏移，这种地方，可以做全局性的缓存。颜色深的云团，就是时间方向上，局部性好的区域，可以做buffer。画图直观，不画图，也是能够计算出来的，你那个统计，相当于是横线。

每次读文件四个字节是极其低效的，这个应该避免。很多平台上，读一个字节和读多个字节的开销是一样的，你需要找到所在平台上最合适的大小（setvbuf?)，或者用mmap。

另外，感觉你这个算法和ray tracing还是有不少相似的地方，应该还是有改进的余地。从ray tracing的经验来看，1.改善空间划分的方法（平衡/快速排除有利）2.改进搜索过程，我们往往注重叶节点访问复杂度控制，忽视中间节点的访问开销，实际上中间节点的开销能增加到成为主要开销的程度，此时，快速排除无用的搜索就很重要。算法改进应该是收益最大的。

最后，如果只是字典的话，八叉树真的合适吗？这个等专业人士回答。 :P

---------------------------------------
绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

[qiaojie]

谁说关联式cache的复杂度是O(lgN)/O(N)的？硬件cache虽然快，但也不能降算法低复杂度的，最多也就是通过流水线来提高吞吐量，总的计算量是降不下来的。否则的话，我们大可以用硬件电路构造一个密码破解机，现在的密码算法岂不是都要失效？

 

2010/7/8 wing fire <wing...@gmail.com>

[wing fire]

我没研究过关联式Cache的工作原理，所以我没有对其作出一个字的评价。

我说"一不小心就引入"O(lgN)/O(N)的复杂度.1.我的"/"是或者的意思，除不是这个写法 2.我的不小心是指实现的时候容易犯的错，"这并不少见"。我不至于说“一个算法一不小心就变成了O(XXX)”这么脑残的话。

我见过用时间戳来淘汰页面的，可是为了找出淘汰时间戳，我见过用优先队列管理的,O(lgn)引入。

我也见过用链表管理的，淘汰是O(1)了，定位变成了O(n)，或者O(lgn).因为以前的标准C++中没有hash,所以，我确实没在项目里见到有人做成O(1)的，虽然道理大家都懂。

我没说这两种做法都对，但是，但是...我经历的项目中，几乎没见到两者都做到O(1)的样板，可悲。我所说只是我经历的项目代码，没说我看过的代码。

至于说 "硬件cache虽然快，但也不能降算法低复杂度",这个不知道。没什么看法，不评论。

但是得不出“否则的话，我们大可以用硬件电路构造一个密码破解机，现在的密码算法岂不是都要失效”。

硬件确实可以改变算法复杂度，这个道理很简单, INT i,j; i * j,可以是O1的复杂度,也可能是O(size(i)*size(j))的复杂度，就是看你硬件支持不支持，值域够不够大。这个观点，没记错的话，TAOCP里面能找到。

硬件破解密码的机器，也有----当然，我不会脑残到说所有密码体系都有。你似乎忘了密码体系是个大家族。所以，即使有密码破解机，"现在的密码算法岂不是都要失效"是不成立的。

---------------------------------------
绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

[qiaojie]

关联式cache的复杂度既不是O(lgN)也不是O(N)而是O(1)，原理跟hash表非常相似，定位是O(1)，淘汰也是O(1)，这么说够清楚了吧？

至于你举的这个例子：“这个道理很简单, INT i,j; i * j,可以是O1的复杂度,也可能是O(size(i)*size(j))的复杂度，就是看你硬件支持不支持，值域够不够大....”，我认为是不正确的，因为讨论BigO的时候，我们是以N趋向于无穷取极限来算BigO的，硬件虽然可以制造支持很多位的乘法器，但不可能制造出无穷多位的乘法器，所以如果以位数N来算BigO的话，那么不管什么硬件都是O(N*N)的，否则就会搞出什么O(7)，O(32)这样的笑话出来了。

 

2010/7/8 wing fire <wing...@gmail.com>

[wing fire]

在 2010年7月8日 下午1:48，qiaojie <qia...@gmail.com>写道：

关联式cache的复杂度既不是O(lgN)也不是O(N)而是O(1)，原理跟hash表非常相似，定位是O(1)，淘汰也是O(1)，这么说够清楚了吧？

我理解你的结论，但是仍然未理解“关联式cache”,抱歉。

 

至于你举的这个例子：“这个道理很简单, INT i,j; i * j,可以是O1的复杂度,也可能是O(size(i)*size(j))的复杂度，就是看你硬件支持不支持，值域够不够大....”，我认为是不正确的，因为讨论BigO的时候，我们是以N趋向于无穷取极限来算BigO的，硬件虽然可以制造支持很多位的乘法器，但不可能制造出无穷多位的乘法器，所以如果以位数N来算BigO的话，那么不管什么硬件都是O(N*N)的，否则就会搞出什么O(7)，O(32)这样的笑话出来了。

你可能理解错了我这里的INT，不仅仅是C++语言里的int，而是抽象的int。我用了size而不是sizeof。或许用length/bits/bytes会更准确点？一个事实是，我们平时在算复杂度时，一个整数乘法是看作O(1)的。我们并未讲清楚这个整数是怎么表示的，例如，是否必须是定长的,值域是有限的，补码表示等等限定，甚至，在TAOCP那个机器里面还搞了个10进制的表示。无所谓，不影响复杂度分析，是吧？但是，实际上我们是有个隐含前提的，那就是i*j一定能在常数时间内完成。然而这一假设不总是正确的。考虑一下，无限精度（或者，现实一点，超大尺度）的整数乘法呢？你还能认为i*j操作就是常数？不是我杜撰，有大整数运算库吧？

不知道你是否还觉得这是个笑话。

[Mikster.Z]

不懂啥叫关联式cache

[wing fire]

你说的“关联式cache”是不是这个里面的

• 2-way set associative cache
• 2-way skewed associative cache – "the best tradeoff for .... caches whose sizes are in the range 4K-8K bytes" – André Seznec^[1]
• 4-way set associative cache
• fully associative cache – the best (lowest) miss rates; only suitable for "small" caches

和Pseudo-associative cache

http://en.wikipedia.org/wiki/CPU_cache

如果是的话，我真的不懂，在没有硬件支持的情况下，怎么做到O(1)?特别是那个fully   associative   cache？你给讲解一下？

---------------------------------------
绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

在 2010年7月8日 下午1:48，qiaojie <qia...@gmail.com>写道：

[qiaojie]

2010/7/8 wing fire <wing...@gmail.com>

在 2010年7月8日 下午1:48，qiaojie <qia...@gmail.com>写道：

关联式cache的复杂度既不是O(lgN)也不是O(N)而是O(1)，原理跟hash表非常相似，定位是O(1)，淘汰也是O(1)，这么说够清楚了吧？

我理解你的结论，但是仍然未理解“关联式cache”,抱歉。

 

http://en.wikipedia.org/wiki/CPU_cache#Associativity

 

 

至于你举的这个例子：“这个道理很简单, INT i,j; i * j,可以是O1的复杂度,也可能是O(size(i)*size(j))的复杂度，就是看你硬件支持不支持，值域够不够大....”，我认为是不正确的，因为讨论BigO的时候，我们是以N趋向于无穷取极限来算BigO的，硬件虽然可以制造支持很多位的乘法器，但不可能制造出无穷多位的乘法器，所以如果以位数N来算BigO的话，那么不管什么硬件都是O(N*N)的，否则就会搞出什么O(7)，O(32)这样的笑话出来了。

你可能理解错了我这里的INT，不仅仅是C++语言里的int，而是抽象的int。我用了size而不是sizeof。或许用length/bits/bytes会更准确点？一个事实是，我们平时在算复杂度时，一个整数乘法是看作O(1)的。我们并未讲清楚这个整数是怎么表示的，例如，是否必须是定长的,值域是有限的，补码表示等等限定，甚至，在TAOCP那个机器里面还搞了个10进制的表示。无所谓，不影响复杂度分析，是吧？但是，实际上我们是有个隐含前提的，那就是i*j一定能在常数时间内完成。然而这一假设不总是正确的。考虑一下，无限精度（或者，现实一点，超大尺度）的整数乘法呢？你还能认为i*j操作就是常数？不是我杜撰，有大整数运算库吧？

 

 

我认为我没有理解错。对于任意位大数乘法，不管用什么硬件，算法复杂度都为O(N*N)，N为乘数的位数。而你说可以构造某种硬件使复杂度可以降为O(1).

 

 

[Milo Yip]

http://en.wikipedia.org/wiki/Multiplication_algorithm

從 O(n^2) 到 2007年的 n log(n) 2^Θ(log*(n))

我覺得，應該是要決定問題中那些是變量，那些是常量，不然沒法談complexity。

例如只考慮32-bit加數，32可作為常量。那麼32-bit n個值的和是O(n)。若要計算n個m-bit值的和，就是O(nm)。

wing fire <wing...@gmail.com> 於 2010年7月8日下午3:28 寫道：

在 2010年7月8日 下午1:48，qiaojie <qia...@gmail.com>写道：

关联式cache的复杂度既不是O(lgN)也不是O(N)而是O(1)，原理跟hash表非常相似，定位是O(1)，淘汰也是O(1)，这么说够清楚了吧？

我理解你的结论，但是仍然未理解“关联式cache”,抱歉。

 

至于你举的这个例子：“这个道理很简单, INT i,j; i * j,可以是O1的复杂度,也可能是O(size(i)*size(j))的复杂度，就是看你硬件支持不支持，值域够不够大....”，我认为是不正确的，因为讨论BigO的时候，我们是以N趋向于无穷取极限来算BigO的，硬件虽然可以制造支持很多位的乘法器，但不可能制造出无穷多位的乘法器，所以如果以位数N来算BigO的话，那么不管什么硬件都是O(N*N)的，否则就会搞出什么O(7)，O(32)这样的笑话出来了。

你可能理解错了我这里的INT，不仅仅是C++语言里的int，而是抽象的int。我用了size而不是sizeof。或许用length/bits/bytes会更准确点？一个事实是，我们平时在算复杂度时，一个整数乘法是看作O(1)的。我们并未讲清楚这个整数是怎么表示的，例如，是否必须是定长的,值域是有限的，补码表示等等限定，甚至，在TAOCP那个机器里面还搞了个10进制的表示。无所谓，不影响复杂度分析，是吧？但是，实际上我们是有个隐含前提的，那就是i*j一定能在常数时间内完成。然而这一假设不总是正确的。考虑一下，无限精度（或者，现实一点，超大尺度）的整数乘法呢？你还能认为i*j操作就是常数？不是我杜撰，有大整数运算库吧？

不知道你是否还觉得这是个笑话。

[qiaojie]

没错，就是指这个。一般CPU都不会去实现fully associative cache，常见的为2-way/4-way，定位只是一次取模，然后检查2个或者4个cache项就可以了，你认为这个不是O(1)？

2010/7/8 wing fire <wing...@gmail.com>

[free.wang]

n log(n) 2^Θ(log*(n))

带问下这个怎么输入的？

2010/7/8 Milo Yip <mil...@gmail.com>

--
真正的杰出，不是妙用规则的错层，而是极致的偏执于信念.
The Crankiness of  Belief achieves Great , not the Trick of Regulation.

[wing fire]

---------------------------------------
绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

我无意纠正的你”我认为“，但是你不要曲解我的话。

我的意思是:我们平时都是把整数乘法当作常数，这实际上是有适用范围的。这很难理解吗？

我那句话有：”可以构造某种硬件使复杂度可以降为O(1)“的意思了？

 

 

 

[qiaojie]

2010/7/8 wing fire <wing...@gmail.com>

为了避免再次发生人身伤害事故，那么就请第三方来解释一下你这句话到底想表达什么意思吧。

 

“硬件确实可以改变算法复杂度，这个道理很简单, INT i,j; i * j,可以是O1的复杂度,也可能是O(size(i)*size(j))的复杂度，就是看你硬件支持不支持，值域够不够大。这个观点，没记错的话，TAOCP里面能找到。”

 

[wing fire]

在 2010年7月8日 下午3:54，Milo Yip <mil...@gmail.com>写道：

http://en.wikipedia.org/wiki/Multiplication_algorithm

從 O(n^2) 到 2007年的 n log(n) 2^Θ(log*(n))

多谢。我还停留在n^2年代。汗。。。

 

我覺得，應該是要決定問題中那些是變量，那些是常量，不然沒法談complexity。

例如只考慮32-bit加數，32可作為常量。那麼32-bit n個值的和是O(n)。若要計算n個m-bit值的和，就是O(nm)。

 

你说的没错。但是平时我们并不需要刻意地协商那些是常量，哪些是变量。在一个特定的问题中或环境中讨论时，一般来说，常量和变量都是不言而喻的，或者说是隐藏的的。当某些隐藏的边界可能被越过时，就需要拿出来分析一下。

我说int只是举个例子。在我不理解”关联式cache“的时候，我只是简单地怀疑O(1)的结论是忽略了某些边界的结果。

[wing fire]

好吧，我也列一下：

你的话：”可以构造某种硬件使复杂度可以降为O(1)“

我的话：“硬件确实可以改变算法复杂度”

---------------------------------------
绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

[wing fire]

我最初google你的“关联式cache”并没有得到结果，所以我说了，我不懂什么是“关联式cache”，不评价。其次，我更不知道你所谓的“关联式cache”特指“2-way/4-way”，自然无法判断。

所以，你不必给我“你认为这个不是O(1)？”的帽子。

---------------------------------------
绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

[Mikster.Z]

原来是这玩意儿。我认为这个“关联式cache”在这个问题里毫无益处。

[Lucas Zhang]

准备差不多就这么做了。
实际情况中函数读的是bits(不会超过20位)，不过是处理为读bytes的，这样的话还需要考虑读的bits不在同一个block里面。
准备做些实验来确定最优的block大小

2010/7/8 wing fire <wing...@gmail.com>

[Dubiwang]

楼主把问题复杂化了， 就这问题而言， 使用Page机制在内存的使用率上应该是最优的。在cashe大小一定的情况下，任何付加的内存使用本身都会降低cashe的作用的。跟据楼主的问题，每个page的大小可以设定在100到300之间。算法上，可以使用一额外的数组或链表，保持最近访问的页面在数组定部，或者仅在页面在数组的后半部时才移动到顶部。这样有效地减少数组移动的次数。每个数组元素用2个字节保存页面在文件里的offset,再用1个或2个字节保存页面的索引号。整个算法符合简单设计原则，每个页面只需要额外的4个字节。
发自我的 iPod

在 2010-7-8，13:48，qiaojie <qia...@gmail.com> 写到：

2010/7/8 wing fire <wing...@gmail.com>

 

2010/7/8 wing fire <wing...@gmail.com>

2010/7/8 wing fire <wing...@gmail.com>

绝圣弃知，大盗乃止；擿玉毁珠，小盗不起；

2010/7/8 wing fire <wing...@gmail.com>

 

2010/7/7 wing fire <wing...@gmail.com>

回复的好快<330.gif>。先研究一下你们的方法~ 刚刚还有人建议我丢弃1300个桶+大小为10的双向链表的结构，用一个更大的hash table和双向链表来实现，好像效率会高很多，不过设计hash function又是一个问题。

[yjw...@gmail.com]

不知道你的手机平台上有没有boost库，我现在一般用boost的multi_index做cache，很方便。

On Jul 7, 4:40 pm, Lucas Zhang <zhangqing1...@gmail.com> wrote:
> 我现在在做一个手机平台上的软件，现在的I/O瓶颈是一个用seek读取img文件的函数。在我的测试里，一共调用了这个函数7480325次，读取的bytes
> offset位置是从6800到130000，也就是说，平均一个位置的byte会被重复读到平均100次左右(实际情况是有的byte会被读到3到4次，有的会被读到1000次以上)。下面是一些统计数据：
>
> bytes offset 6800 ~ 6900: 170884 times
> bytes offset 6900 ~ 7000: 220944 times
> bytes offset 7000 ~ 7100: 24216 times
> bytes offset 7100 ~ 7200: 9576 times
> bytes offset 7200 ~ 7300: 14813 times
> bytes offset 7300 ~ 7400: 22109 times
> bytes offset 7400 ~ 7500: 19748 times
> bytes offset 7500 ~ 7600: 43110 times
> bytes offset 7600 ~ 7700: 157976 times
> ...
> bytes offset 121200 ~ 121300: 1514 times
> bytes offset 121300 ~ 121400: 802 times
> bytes offset 121400 ~ 121500: 606 times
> bytes offset 121500 ~ 121600: 444 times
> bytes offset 121600 ~ 121700: 398 times
>
> max_bytes_offset 121703
> min_bytes_offset 6848
>
> 于是我想到做一个cache来优化函数的性能。由于之前也没怎么接触过cache，仅限于课本上的一点知识，我在google了一番后，发现比较好的方法是用hash表和双向链表来实现LRU策略的cache.这里有个

> 链接 <http://stackoverflow.com/questions/3027484/lru-caches-in-c>。如果要把所有位置的数据都搬到内存的话，大概是130KB左右。我想到一个简单的方法，用1300个桶来hash

[Linker]

其实OS是自己有Cache的。
用mmap会比较快。

2010/7/12 yjw...@gmail.com <yjw...@gmail.com>

--
Regards,
Linker Lin
linker...@gmail.com