Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1523931
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | [PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 |
| Date | 2016-11-16 23:40 +0100 |
| Message-ID | <sEh22-uC-27@gated-at.bofh.it> (permalink) |
| References | <sEgSl-rg-1@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
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
Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
[PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
Re: [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Konstantin Khlebnikov <koct9i@gmail.com> - 2016-11-18 13:00 +0100
RE: [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-18 17:50 +0100
[PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
Re: [PATCH 23/29] idr: Add ida_is_empty Konstantin Khlebnikov <koct9i@gmail.com> - 2016-11-18 13:00 +0100
[PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
Re: [PATCH 20/29] radix tree: Improve multiorder iterators Konstantin Khlebnikov <koct9i@gmail.com> - 2016-11-18 12:50 +0100
RE: [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-18 17:40 +0100
Re: [PATCH 20/29] radix tree: Improve multiorder iterators Konstantin Khlebnikov <koct9i@gmail.com> - 2016-11-18 19:00 +0100
RE: [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-18 22:00 +0100
[PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 13/29] radix-tree: Fix typo Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 03/29] radix tree test suite: Track preempt_count Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
RE: [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-17 21:00 +0100
Re: [PATCH 00/29] Improve radix tree for 4.10 Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-11-17 23:20 +0100
RE: [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-18 05:40 +0100
[PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
csiph-web