lkml.org 
[lkml]   [2016]   [Nov]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH v3 31/33] idr: Reduce the number of bits per level from 8 to 6
    Date
    From: Matthew Wilcox <willy@linux.intel.com>

    In preparation for merging the IDR and radix tree, reduce the fanout at
    each level from 256 to 64. If this causes a performance problem then
    a bisect will point to this commit, and we'll have a better idea about
    what we might do to fix it.

    Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
    ---
    include/linux/idr.h | 9 ++++-----
    1 file changed, 4 insertions(+), 5 deletions(-)

    diff --git a/include/linux/idr.h b/include/linux/idr.h
    index 1eb755f..3c01b89 100644
    --- a/include/linux/idr.h
    +++ b/include/linux/idr.h
    @@ -18,12 +18,11 @@
    #include <linux/rcupdate.h>

    /*
    - * We want shallower trees and thus more bits covered at each layer. 8
    - * bits gives us large enough first layer for most use cases and maximum
    - * tree depth of 4. Each idr_layer is slightly larger than 2k on 64bit and
    - * 1k on 32bit.
    + * Using 6 bits at each layer allows us to allocate 7 layers out of each page.
    + * 8 bits only gave us 3 layers out of every pair of pages, which is less
    + * efficient except for trees with a largest element between 192-255 inclusive.
    */
    -#define IDR_BITS 8
    +#define IDR_BITS 6
    #define IDR_SIZE (1 << IDR_BITS)
    #define IDR_MASK ((1 << IDR_BITS)-1)

    --
    2.10.2
    \
     
     \ /
      Last update: 2016-11-28 21:00    [W:5.060 / U:0.044 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site