dir_level explained?

dir_level explained?

[Marc Lehmann]

Hi!

In all my tests I intentionally didn't play with dir_level, to get an idea of
baseline performance. I also wasn't worried because my standard response to
slow random reads is dmcache, but now that I realised I can't use dmcache
with these drives, I got more interested in dir_level.

If I understand it correctly, higher values of dir_level potentially waste
more space but gain performance. However, I have no clue about what the
trade-off really is.

Could you explain what kind of extra space usage I can expect from higher
levels of dir_level, or what the values mean?

-- 
                The choice of a       Deliantra, the free code+content MORPG
      -----==-     _GNU_              http://www.deliantra.net
      ----==-- _       generation
      ---==---(_)__  __ ____  __      Marc Lehmann
      --==---/ / _ \/ // /\ \/ /      schmorp@schmorp.de
      -=====/_/_//_/\_,_/ /_/\_\

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

Re: dir_level explained?

[Jaegeuk Kim]

On Sun, Oct 04, 2015 at 11:56:47AM +0200, Marc Lehmann wrote:
> Hi!
> 
> In all my tests I intentionally didn't play with dir_level, to get an idea of
> baseline performance. I also wasn't worried because my standard response to
> slow random reads is dmcache, but now that I realised I can't use dmcache
> with these drives, I got more interested in dir_level.
> 
> If I understand it correctly, higher values of dir_level potentially waste
> more space but gain performance. However, I have no clue about what the
> trade-off really is.

The default directory structure consists of multi-level hash tables [1].
Each level represents a hash table, and when the level increases, f2fs
constructs a bigger hash table. Its height depends on the number of hash
collisions and there-in directory entries. So, normally, we expect lookup
overhead is O(logN).

However, if we assume a directory will have huge number of directory entries,
one big hash table would be perferable initially. In this case, you can increase
dir_level to obtain O(1).

So, dir_level indicates the base height when building a directory structure.
For example, if all the file names are less than 8 bytes long, you can set
dir_level as N to cover roughly 428*2^N entries in a big hash table.

[1] https://en.wikipedia.org/wiki/F2FS

> 
> Could you explain what kind of extra space usage I can expect from higher
> levels of dir_level, or what the values mean?
> 
> -- 
>                 The choice of a       Deliantra, the free code+content MORPG
>       -----==-     _GNU_              http://www.deliantra.net
>       ----==-- _       generation
>       ---==---(_)__  __ ____  __      Marc Lehmann
>       --==---/ / _ \/ // /\ \/ /      schmorp@schmorp.de
>       -=====/_/_//_/\_,_/ /_/\_\
> 
> ------------------------------------------------------------------------------
> _______________________________________________
> Linux-f2fs-devel mailing list
> Linux-f2fs-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

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