redis函数dictScan设计的高位加法的一个理解和猜想

redis6.0.5之dict.c中的函数dictScan设计的高位加法的一个理解和猜想
-- ccy于2020.8.28
*******************************************************************************************
假设: v=3ul, m0=15ul
v |= ~m0; //fffffffffffffff3
/* Increment the reverse cursor */ 完成了高位向低位进位的加法,用两位举例 00->10->01->11
v = rev(v); //cfffffffffffffff 0011->1100所以3->c
v++; //d000000000000000 = cfffffffffffffff + 1 这一步加法最神奇,连进那么多位!
v = rev(v); //d->b 1101 -> 1011
*******************************************************************************************
下面我们用自己想到的正向加法来重新理解它
int count = 0;
while(t->sizemask >>=1)
count++;
int movebits = sizeof(v)*8-count; //这里的movebits就是无掩码的位数
同上述初始条件一致,t->sizemask=16,r2=3ul,那么movebits=60
上面是解释movebits如何得到,接下来我们看正向加法
r2 <<=movebits; r2=3 ,3<<60 => 3000000000000000 因为v是一个反值,所以我们先将无掩码位补齐
r2 = rev(r2); 3000000000000000 -> c 0011->1100 然后取反求正
r2++; c->d 1100 + 1 = 1101 再正向的+1
r2=rev(r2); d-> b000000000000000 1101->1011 然后求反
r2 >>=movebits; b000000000000000>>60 = b 再把无掩码位去掉
*******************************************************************************************
为什么要设计这么难以理解的算法,是为了遍历的时候遇到扩容尽量减少重复遍历数据!

如果用我们常用的10进制来看,那么原先为3位000, 现在高位扩容变成4位0000
如果已经遍历了001,002,003,004,005,006,007,008,009,010,011,012,注意现在是高位扩容,
我们访问过的001就会分散到0001(已访问过),1001,2001,3001,4001,5001,6001,7001,8001,9001中去,
。。。
同理012也会分散到0002(已访问过),1012,2012,3012,4012,5012,6012,7012,8012,9012中去,
如果我们现在从0013开始继续遍历, 这样我们就会重复访问这些数据。
这里的主要原因在于高位扩容,如果扩容的是低位,
那么001,就会分散到0010,0011,0012,0013,0014,0015,0016,0017,0018,0019
。。。
那么012,就会分散到0120,0121,0122,0123,0124,0125,0126,0127,0128,0129
如果再从0130开始访问,恰好不会重复访问之前访问过的数据,因为刚好接上了0129.

关于收缩会有部分重复访问数据,但是远少于高位扩容,所以我们猜测算法的作者看到了这种现象之后,
就考虑将高低位倒置进行处理,于是有了高位加法这个算法!

 

上一篇:An error occurred during the installation of assembly 'Microsoft.VC90.ATL or 'Microsoft.VC80.ATL'


下一篇:[COI2009] OTOCI - LCT