On Fri, Jan 22, 2016 at 3:11 AM, Nemo Yu <mzer0...@gmail.com> wrote: > Thank you for replying. > > 1) Where may I find the commit 449dd6984d0e47643c04c807f609dd56d48d5bcc ?
In linux git. See torvalds/linux.git at http://git.kernel.org I think you should read this too http://kernelnewbies.org/ > 2) After a simple calculating, I think both "path" and "count" variable in > radix_tree_node structure can be unsigned short type against unsigned int > now, if you have the binary logarithm. This migh have performance impact, not all achitectures have 16-bit operations. And very unlinkely will save any memory. > 3) There is another question that, radix_tree should not consider height == > 0 because we can make assumption height > 1, or force height > 1, then some > unnecessary branches(if-else statement) can be removed. > > On Fri, Jan 22, 2016 at 3:15 AM, Konstantin Khlebnikov <koc...@gmail.com> > wrote: >> >> On Thu, Jan 21, 2016 at 12:10 PM, Nemo Yu <mzer0...@gmail.com> wrote: >> > I am sorry bothering you. It was the name in the header file >> >> >> >> Copyright (C) 2012 Konstantin Khlebnikov >> > >> > made me sending this email to you. >> >> I've added iterator routine here. That's all. >> >> > >> > On Thu, Jan 21, 2016 at 4:37 PM, Konstantin Khlebnikov >> > <koc...@gmail.com> >> > wrote: >> >> >> >> On Thu, Jan 21, 2016 at 11:20 AM, Nemo Yu <mzer0...@gmail.com> wrote: >> >> > Hello Khlebnikov, I am Nemo. >> >> > >> >> > I found a very little mistake in your radix-tree.h of linux kernel >> >> > 4.3(I >> >> > don't know how is it going in kernel 4.4), here is the code: >> >> > >> >> >> 80 #define RADIX_TREE_HEIGHT_SHIFT (RADIX_TREE_MAX_PATH + 1) >> >> > >> >> > >> >> > I think it should be: >> >> > >> >> >> 80 #define RADIX_TREE_HEIGHT_SHIFT (log2(RADIX_TREE_MAX_PATH) + 1) >> >> > >> >> > >> >> > where log2 is the binary logarithm. >> >> > >> >> > (read the kernel 4.3 online: >> >> > http://lxr.free-electrons.com/source/include/linux/radix-tree.h) >> >> > >> >> > And, rename RADIX_TREE_MAX_PATH to RADIX_TREE_MAX_HEIGHT will be >> >> > better >> >> > to >> >> > understand(just suggestions). I can do a patch if you agree. >> >> Yep RADIX_TREE_HEIGHT_SHIFT -> count bits required for keeping height but >> bigger value is ok. It's used only once for splitting 32-bit node->path >> into >> two numbers offset in parent node in higher bits and subtree height in >> lower. >> >> This is relatively new code by Johannes Weiner, >> see commit 449dd6984d0e47643c04c807f609dd56d48d5bcc >> >> Probably it's easier to swap these parts - bit width of offset in node >> already here >> RADIX_TREE_MAP_SHIFT >> >> All currenly used combinations are fine 32/64bit CONFIG_BASE_SMALL=y/n >> and even debug mode RADIX_TREE_MAP_SHIFT=3 are fine. >> >> But 64-bit with 2-bit per node will not work: max-path is 32 in this >> case. >> >> >> >> >> This isn't my code, but I'll check this later. >> >> It would be better to add linux-kernel@vger.kernel.org into CC. >> >> Maybe somebody who has more free time will answer you sooner. >> > >> > >> >> send plain text mail, LKML forbids html. > >
