rcu skiplists v2
Subsystems (4)
cover rcu skiplists v2
Hi everyone,
This is another iteration of my skiplists patch, with some bugs fixed and a few missing parts of the API done. The biggest change is in the insertion code, where I now link from the bottom up once I find the proper insertion point. This makes it possible to write custom insertion routines that allow duplicate keys.
It also means insertion doesn't have to lock and track all the nodes from the top as it searches. In the likely event that we're able to insert into a free spot in an existing leaf, it only needs to take one lock.
The IOMMU part of the patch is updated slightly, but still not using all the new bits in the API. This is mostly because the IOMMU part is going to change later on and I'm really only using it for testing now.
For benchmarking, the IOMMU numbers are slightly higher than last time, but not more than 5% or so. This is because the bottleneck is still skiplist_insert_hole(), which I haven't really changed in this round.
Most of my benchmarking now is with the skiplist_test module, which has expanded to a few new cases. For random operations, my performance is slightly slower than rbtree when single threaded.
Random lookups on 10 million items: (inserts are similar)
rbtree random lookup time 4 s 327 ms
skiplist-rcu random lookup time 5 s 175 ms
The new API makes it easier to do sequential operations. Here is a walk through the 10 million item list:
skiplist-rcu check time 0 s 79 ms
rbtree check time 0 s 295 ms
And sequential insert:
kiplist-rcu fill time 1 s 599 ms
rbtree fill time 1 s 875 ms
The benchmark does random lookup/deletion/insertion rounds. Most of the operations done are either deletion or insertion, so I'm not skewing the results with the easy rcu lookup operation.
Single threaded rbtree does consistently win across all sizes of lists:
skiplist-rcu thread 0 time 0 s 287 ms
rbtree thread 0 time 0 s 215 ms
But once we go up to two threads, skiplists win:
skiplist-rcu thread 1 time 0 s 299 ms
rbtree thread 1 time 0 s 499 ms
At 8 threads, the skiplists don't get linear scaling, but it's really pretty good. Since I'm doing random operations on a wide key space, the locking skiplist variant is also fast:
skiplist-rcu thread 7 time 0 s 379 ms
skiplist-locking thread 7 time 0 s 425 ms
rbtree thread 7 time 3 s 711 ms
My test machine is 8 cores, so at 16 threads we're into HT:
skiplist-rcu thread 15 time 0 s 583 ms
skiplist-locking thread 15 time 0 s 559 ms
rbtree thread 15 time 7 s 423 ms
It's not all sunshine though. If I shrink the keyspace down to 1000 keys or less, there is more contention on the node locks and we're tied (or slightly worse) than rbtree. In that kind of workload it makes sense to add a big fat lock around the skiplist, or just stick with rbtrees.
The skiplists do have locking and rcu variants of lookup operations. The locking ones are built on top of the rcu ones, and you can use them both at the same time.
Patches follow.
-chris
RFC PATCH 1/2 Skiplist: rcu range index
--- include/linux/skiplist.h | 235 ++++++ init/main.c | 5 + lib/Kconfig | 14 + lib/Makefile | 3 + lib/skiplist.c | 2106 ++++++++++++++++++++++++++++++++++++++++++++++ lib/skiplist_test.c | 882 +++++++++++++++++++ 6 files changed, 3245 insertions(+) create mode 100644 include/linux/skiplist.h create mode 100644 lib/skiplist.c create mode 100644 lib/skiplist_test.c
include/linux/skiplist.h new file +235 -0
@@ -0,0 +1,235 @@ +/* +* (C) 2011 Liu Bo <[email protected]> +* (C) 2013 Fusion-io +* +* This program is free software; you can redistribute it and/or modify it under +* the terms of the GNU General Public License as published by the Free Software +* Foundation; version 2 of the License. +* +* This program is distributed in the hope that it will be useful, but WITHOUT +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +* FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +* details. +* +* You should have received a copy of the GNU General Public License along with +* this program; if not, write to the Free Software Foundation, Inc., 59 Temple +* Place, Suite 330, Boston, MA 02111-1307 USA +*/ +#ifndef _SKIPLIST_H +#define _SKIPLIST_H + +#include <linux/spinlock.h> + +/* +* This includes a basic skiplist implementation and builds a more +* cache friendly variant on top meant to index ranges of keys. +* +* our random generation function has P at 0.5, so a rough metric +* of good performance happens for lists up to 2^MAXLEVEL in size. +* Since we have an array of keys, you can do 2^MAXLEVEL * SKIP_KEYS_PER_NODE +*/ +#define SKIP_MAXLEVEL 32/* skiplist_get_new_level requires <= 32 */ + +struct sl_node_ptr { +struct sl_node *prev; +struct sl_node *next; +}; + +/* possible values for sl_node->pending */ +#define SKIPLIST_LIVE 0/* normal operations */ +#define SKIPLIST_PENDING_DEAD 1/* active unlink in progress */ +#define SKIPLIST_PENDING_INSERT 2/* active link in progress */ + +/* +* sl_node must be last in the leaf data struct. Allocate enough +* ram for a given size using either the sl_ptrs_size or sl_node_size +* helpers. +*/ +struct sl_node { +/* level tells us how big the ptrs array is. It cannot change */ +unsigned long level; + +/* pending is used to indicate a delete or link in progress */ +unsigned long pending; + +spinlock_t lock; + +/* +* ptrs must be at the bottom because it is variably sized +* based on the level +*/ +struct sl_node_ptr ptrs[]; +}; + +/* +* The head list structure. The head node has no data, +* but it does have the full array of pointers for all the levels. +*/ +struct sl_list { +/* +* in the head pointer, we use head->prev to point to +* the highest item in the list. But, the last item does +* not point back to the head. The head->prev items +* are protected the by node lock on the last item +*/ +struct sl_node *head; +unsigned int level; +}; + +/* +* If you are indexing extents, embed sl_slots into your structure and use +* sl_slot_entry to pull out your real struct. The key and size must not +* change if you're using rcu. +*/ +struct sl_slot { +/* +* when rcu is on, we use this key to verify the pointer we pull +* out of the array. It must not change once the object is +* inserted +*/ +unsigned long key; + +/* +* the range searching functions follow pointers into this slot +* struct and use this size field to find out how big the +* range is. +*/ +unsigned long size; + +/* +* a ref is taken when the slot is inserted, or +* during non-rcu lookup. It's +* the caller's job to drop the refs on deletion +* and rcu lookup. +*/ +atomic_t refs; +}; + +/* +* Larger values here make us faster when single threaded. Lower values +* increase cache misses but give more chances for concurrency. +*/ +#define SKIP_KEYS_PER_NODE 32 + +/* +* For indexing extents, this is a leaf in our skip list tree. +* Each leaf has a number of pointers and the max field +* is used to figure out the key space covered. +*/ +struct sl_leaf { +/* number of valid keys/ptrs in this leaf */ +int nr; + +/* reference count for this leaf */ +atomic_t refs; + +/* +* max value of the range covered by this leaf. This +* includes the size field of the very last extent, +* so max = keys[last_index] + ptrs[last_index]->size +*/ +unsigned long max; + +/* +* sorted, all the keys +*/ +unsigned long keys[SKIP_KEYS_PER_NODE ]; + +/* +* data pointers corresponding to the keys +*/ +struct sl_slot *ptrs[SKIP_KEYS_PER_NODE ]; + +/* for freeing our objects after the grace period */ +struct rcu_head rcu_head; + +/* this needs to be at the end. The size changes based on the level */ +struct sl_node node; +}; + +/* +* for a given level, how much memory we need for an array of +* all the pointers +*/ +static inline int sl_ptrs_size (int level) +{ +return sizeof (struct sl_node_ptr ) * (level +1 ); +} + +/* +* for a given level, how much memory we need for the +* array of pointers and the sl_node struct +*/ +static inline int sl_node_size (int level) +{ +return sizeof (struct sl_node ) +sl_ptrs_size (level); +} + +static inline int sl_leaf_size (int level) +{ +return sizeof (struct sl_leaf ) +sl_ptrs_size (level); +} + +#define sl_entry (ptr) container_of((ptr), struct sl_leaf, node) +#define sl_slot_entry (ptr, type, member) container_of(ptr, type, member) + +static inline int sl_empty (const struct sl_node *head) +{ +return head->ptrs[0 ].next ==NULL ; +} + +static inline int sl_node_dead (struct sl_node *node) +{ +return node->pending ==SKIPLIST_PENDING_DEAD ; +} + +static inline int sl_node_inserting (struct sl_node *node) +{ +return node->pending ==SKIPLIST_PENDING_INSERT ; +} + +int skiplist_preload (struct sl_list *list,gfp_t gfp_mask); +int skiplist_get_new_level (struct sl_list *list,int max_level); +int skiplist_insert (struct sl_list *list,struct sl_slot *slot, +int preload_token,struct sl_leaf **cache); +int sl_init_list (struct sl_list *list,gfp_t mask); +struct sl_slot *skiplist_lookup (struct sl_list *list,unsigned long key,unsigned long size); +struct sl_slot *skiplist_lookup_rcu (struct sl_list *list,unsigned long key,unsigned long size); +struct sl_slot *skiplist_delete (struct sl_list *list,unsigned long key,unsigned long size); +int skiplist_insert_hole (struct sl_list *list,unsigned long hint, +unsigned long limit, +unsigned long size,unsigned long align, +struct sl_slot *slot, +gfp_t gfp_mask); +void sl_lock_node (struct sl_node *n); +void sl_unlock_node (struct sl_node *n); +unsigned long sl_highest_key (struct sl_list *list); +int skiplist_search_leaf (struct sl_leaf *leaf,unsigned long key, +unsigned long size,int *slot); +struct sl_leaf *skiplist_lookup_leaf (struct sl_list *list, +unsigned long key, +unsigned long size); +struct sl_leaf *skiplist_lookup_first_leaf (struct sl_list *list, +unsigned long key, +unsigned long size); +struct sl_leaf *skiplist_lookup_leaf_rcu (struct sl_list *list, +unsigned long key, +unsigned long size); +struct sl_leaf *skiplist_lookup_first_leaf_rcu (struct sl_list *list, +unsigned long key, +unsigned long size); +void skiplist_unlock_leaf (struct sl_leaf *leaf); +void skiplist_lock_leaf (struct sl_leaf *leaf); +void skiplist_delete_leaf (struct sl_list *list,struct sl_leaf *leaf, +struct sl_leaf **cache_next); +struct sl_leaf *skiplist_next_leaf (struct sl_list *list, +struct sl_leaf *leaf); +struct sl_leaf *skiplist_next_leaf_rcu (struct sl_list *list, +struct sl_leaf *leaf); +struct sl_leaf *skiplist_first_leaf (struct sl_list *list); +struct sl_leaf *skiplist_first_leaf_rcu (struct sl_list *list); +void skiplist_get_leaf (struct sl_leaf *leaf); +int skiplist_get_leaf_not_zero (struct sl_leaf *leaf); +void skiplist_put_leaf (struct sl_leaf *leaf); +void skiplist_wait_pending_insert (struct sl_node *node); +#endif /* _SKIPLIST_H */
init/main.c +5 -0
@@ -90,6 +90,7 @@ extern void fork_init(unsigned long);extern void mca_init (void );extern void sbus_init (void );extern void radix_tree_init (void ); +extern void skiplist_init (void );#ifndef CONFIG_DEBUG_RODATA static inline void mark_rodata_ro (void ) { }#endif
@@ -566,6 +567,10 @@ asmlinkage void __init start_kernel(void)kmem_cache_init_late (); +#ifdef CONFIG_SKIPLIST +skiplist_init (); +#endif +/* * HACK ALERT! This is early. We're enabling the console before * we've done PCI setups etc, and console_init() must be aware of
lib/Kconfig +14 -0
@@ -393,6 +393,20 @@ config SIGNATURE Digital signature verification. Currently only RSA is supported. Implementation is done using GnuPG MPI library +config SKIPLIST + bool "Concurrent Skiplists" + default n + help + Concurrent skiplist indexing trees. Just say N + +config SKIPLIST_TEST + tristate "Skiplist testing module" + default n + select SKIPLIST + help + Testing module for the skiplist implementation + +# # # libfdt files, only selected if needed. #
lib/Makefile +3 -0
@@ -108,6 +108,9 @@ obj-$(CONFIG_NLATTR) += nlattr.o obj-$(CONFIG_LRU_CACHE) += lru_cache.o +obj-$(CONFIG_SKIPLIST) += skiplist.o +obj-$(CONFIG_SKIPLIST_TEST) += skiplist_test.o + obj-$(CONFIG_DMA_API_DEBUG) += dma-debug.o obj-$(CONFIG_GENERIC_CSUM) += checksum.o
lib/skiplist.c new file +2106 -0
2,106 lines not on this page · raw message
lib/skiplist_test.c new file +882 -0
613 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
1.8.2
Part of the diff is not shown here. View the raw message.
Re: [PATCH RFC 1/2] Skiplist: rcu range index
Quoted 13 lines · Chris Mason
Signed-off-by Chris Mason <[email protected]>--- include/linux/skiplist.h | 235 ++++++ init/main.c | 5 + lib/Kconfig | 14 + lib/Makefile | 3 + lib/skiplist.c | 2106 ++++++++++++++++++++++++++++++++++++++++++++++ lib/skiplist_test.c | 882 +++++++++++++++++++ 6 files changed, 3245 insertions(+)create mode 100644
include/linux/skiplist.h
create mode 100644lib/skiplist.c
create mode 100644lib/skiplist_test.c
...
lib/skiplist_test.c line 680
Quoted 8 lines
lib/skiplist_test.c new file +8
-0+ +static void pretty_time (struct timespec *ts,unsigned long long *seconds,unsigned long long *ms) +{ +unsigned long long m; + + *seconds = ts->tv_sec; + + m = ts->tv_nsec /1000000ULL ;
Linux: centos 6.4 32bit 3.10
Gcc version: gcc (GCC) 4.4.7 20120313 (Red Hat 4.4.7-3)
compiler error:
CC [M] lib/skiplist_test.o
Building modules, stage 2.
MODPOST 12 modules
ERROR: "__udivdi3" [lib/skiplist_test.ko] undefined!
Quoted 3 lines
lib/skiplist_test.c new file +3
-0+ *ms = m; +} +
...
RFC PATCH 2/2 Switch the IOMMU over to the skiplists
In reply to Chris MasonThis is for testing only and should never be used
--- drivers/iommu/intel-iommu.c | 4 - drivers/iommu/iova.c | 466 ++++++++++++++++++++------------------------ include/linux/iova.h | 8 +- 3 files changed, 210 insertions(+), 268 deletions(-)
drivers/iommu/intel-iommu.c +0 -4
@@ -1403,7 +1403,6 @@ static void iommu_detach_domain(struct dmar_domain *domain, }static struct iova_domain reserved_iova_list; -static struct lock_class_key reserved_rbtree_key;static int dmar_init_reserved_ranges (void ) {
@@ -1413,9 +1412,6 @@ static int dmar_init_reserved_ranges(void)init_iova_domain (&reserved_iova_list,DMA_32BIT_PFN ); -lockdep_set_class (&reserved_iova_list.iova_rbtree_lock, - &reserved_rbtree_key); -/* IOAPIC ranges shouldn't be accessed by DMA */ iova =reserve_iova (&reserved_iova_list,IOVA_PFN (IOAPIC_RANGE_START ),IOVA_PFN (IOAPIC_RANGE_END ));
drivers/iommu/iova.c +207 -259
556 lines not on this page · raw message
include/linux/iova.h +3 -5
@@ -13,7 +13,7 @@#include <linux/types.h> #include <linux/kernel.h> -#include <linux/rbtree.h> +#include <linux/skiplist.h> #include <linux/dma-mapping.h> /* IO virtual address start page frame number */
@@ -21,16 +21,14 @@/* iova structure */ struct iova { -struct rb_node node; +struct sl_slot slot;unsigned long pfn_hi;/* IOMMU dish out addr hi */ unsigned long pfn_lo;/* IOMMU dish out addr lo */ };/* holds all the iova translations for a domain */ struct iova_domain { -spinlock_t iova_rbtree_lock;/* Lock to protect update of rbtree */ -struct rb_root rbroot;/* iova domain rbtree root */ -struct rb_node *cached32_node;/* Save last alloced node */ +struct sl_list skiplist;/* iova domain skiplist */ unsigned long dma_32bit_pfn; };
Signature · 1 line
1.8.2
Hi Chris,
Quoted 8 lines · * Chris Mason ([email protected]) wrote:
Hi everyone,
This is another iteration of my skiplists patch, with some bugs fixed and a few missing parts of the API done. The biggest change is in the insertion code, where I now link from the bottom up once I find the proper insertion point. This makes it possible to write custom insertion routines that allow duplicate keys.
Quoted 4 lines
It also means insertion doesn't have to lock and track all the nodes from the top as it searches. In the likely event that we're able to insert into a free spot in an existing leaf, it only needs to take one lock.
nice, I did pretty much the same for RCU Judy arrays. I made insertion and deletion take only the localized locks required, nesting from bottom to top.
Quoted 8 lines
The IOMMU part of the patch is updated slightly, but still not using all the new bits in the API. This is mostly because the IOMMU part is going to change later on and I'm really only using it for testing now.
For benchmarking, the IOMMU numbers are slightly higher than last time, but not more than 5% or so. This is because the bottleneck is still
skiplist_insert_hole(), which I haven't really changed in this round.
Quoted 8 lines
Most of my benchmarking now is with the
skiplist_testmodule, which has expanded to a few new cases. For random operations, my performance is slightly slower than rbtree when single threaded.Random lookups on 10 million items: (inserts are similar)
rbtree random lookup time 4 s 327 ms
skiplist-rcu random lookup time 5 s 175 ms
These benchmarks are only considering averages.
I'm worried that the skiplist approach has chances to create long chains (probabilistically non-zero). Clearly, the lack of bound is something the RT guys might frown upon. I'd be curious to see how long the worse chains encountered can be on, say, 1000 machines stress-testing this for a week.
FWIW, my benchmark of RCU Judy array with ranges in similar conditions:
- Using 32-bit key length
- I first populated 10M ranges of len = 1, sequentially.
- Then, I run a reader threads for 10s, which perform random lookups (all successful) in keys from 0 to 10M.
The average lookup time is (on a per-core basis):
- single-thread: 522 ns / lookup ( 19122393 lookups in 10s)
- 2 threads: 553 ns / lookup ( ~36134994 lookups in 10s on 2 cores)
- 8 threads: 696 ns / lookup (~114854104 lookups in 10s on 8 cores)
We get an efficiency of 0.79 when going from 2 to 8 threads (efficiency of 1 being linear scalability).
Performed on this HW:
8-core
model name : Intel(R) Xeon(R) CPU E5405 @ 2.00GHz
What I gather from your skiplist-rcu numbers, it seems to take 517ns/lookup (avg), and for rbtree: 432ns/lookup. I'd be curious to test all these alternatives in the same test bench.
Quoted 7 lines
The new API makes it easier to do sequential operations. Here is a walk through the 10 million item list:
skiplist-rcu check time 0 s 79 ms
rbtree check time 0 s 295 ms
Quoted 8 lines
And sequential insert:
kiplist-rcu fill time 1 s 599 ms
rbtree fill time 1 s 875 msThe benchmark does random lookup/deletion/insertion rounds. Most of the operations done are either deletion or insertion, so I'm not skewing the results with the easy rcu lookup operation.
We could do helpers for sequential traversal of ranges, they are not implemented in RCU Judy array yet though.
Quoted 5 lines
Single threaded rbtree does consistently win across all sizes of lists:
skiplist-rcu thread 0 time 0 s 287 ms
rbtree thread 0 time 0 s 215 ms
Are the 287ms and 215ms numbers you get for skiplist-rcu and rbtree the total for 10M add/delete, or is it per operation, or is it a different number of operations altogether ? Also, how many items are present in the data structures in average ?
Quoted 5 lines
But once we go up to two threads, skiplists win:
skiplist-rcu thread 1 time 0 s 299 ms
rbtree thread 1 time 0 s 499 ms
Quoted 7 lines
At 8 threads, the skiplists don't get linear scaling, but it's really pretty good. Since I'm doing random operations on a wide key space, the locking skiplist variant is also fast:
skiplist-rcu thread 7 time 0 s 379 ms
skiplist-locking thread 7 time 0 s 425 ms
rbtree thread 7 time 3 s 711 ms
Hopefully I'm having a setup not too different from yours. Here is my benchmark of the RCU Judy Array insert operations. Please note that I have not focused on optimizing the update-side, I've made design choices aimed towards making lookups as fast as possible, sometimes at the expense of update overhead.
I used a keyspace of 400M, just so the number of inserts that end up being a simple rcu lookup are non significant. I'm still using a 32-bit key length. I'm adding ranges of length 1.
Here is the average time taken per insertion (on a per-core basis):
- single-thread: 15000 ns/insert ( 645474 inserts in 10s)
- 2 threads: 17000 ns/insert (~1188232 inserts in 10s on 2 cores)
- 8 threads: 25000 ns/insert (~3161024 inserts in 10s on 8 cores)
We get an efficiency of 0.66 when going from 2 to 8 threads (efficiency of 1 being linear scalability).
Quoted 6 lines
My test machine is 8 cores, so at 16 threads we're into HT:
skiplist-rcu thread 15 time 0 s 583 ms
skiplist-locking thread 15 time 0 s 559 ms
rbtree thread 15 time 7 s 423 ms
Skipping this test, since my test machine does not have hyperthreading.
Quoted 6 lines
It's not all sunshine though. If I shrink the keyspace down to 1000 keys or less, there is more contention on the node locks and we're tied (or slightly worse) than rbtree. In that kind of workload it makes sense to add a big fat lock around the skiplist, or just stick with rbtrees.
I'd expect a similar behavior with RCU judy arrays with respect to small keyspace (single lock around updates might perform better that locks distributed within the data). However, even with a small keyspace (and few nodes), I expect that RCU Judy Array and skiplist-rcu will win over non-RCU rbtree for lookup speed when we have concurrent updates and lookups from many cores.
Feedback is welcome,
Thanks!
Mathieu
Quoted 9 lines
The skiplists do have locking and rcu variants of lookup operations. The locking ones are built on top of the rcu ones, and you can use them both at the same time.
Patches follow.
-chris
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoting Mathieu Desnoyers (2013-06-26 19:02:18)
Quoted 17 lines
Quoted 8 lines
The IOMMU part of the patch is updated slightly, but still not using all the new bits in the API. This is mostly because the IOMMU part is going to change later on and I'm really only using it for testing now.
For benchmarking, the IOMMU numbers are slightly higher than last time, but not more than 5% or so. This is because the bottleneck is still
skiplist_insert_hole(), which I haven't really changed in this round.Quoted 8 lines
Most of my benchmarking now is with the
skiplist_testmodule, which has expanded to a few new cases. For random operations, my performance is slightly slower than rbtree when single threaded.Random lookups on 10 million items: (inserts are similar)
rbtree random lookup time 4 s 327 ms
skiplist-rcu random lookup time 5 s 175 ms
Quoted 7 lines
These benchmarks are only considering averages.
I'm worried that the skiplist approach has chances to create long chains (probabilistically non-zero). Clearly, the lack of bound is something the RT guys might frown upon. I'd be curious to see how long the worse chains encountered can be on, say, 1000 machines stress-testing this for a week.
Correct, the probability part may run into problems for RT. I haven't put in instrumentation for worst case. I think my retries (goto again) for concurrent update are a bigger RT problem, but they can be cut down significantly.
Quoted 7 lines
FWIW, my benchmark of RCU Judy array with ranges in similar conditions:
- Using 32-bit key length
- I first populated 10M ranges of len = 1, sequentially.
- Then, I run a reader threads for 10s, which perform random lookups (all successful) in keys from 0 to 10M.
Similar, I had 64 bit keys and the lookups were totally random (not all successful). I doubt it matters too much for these numbers.
Also, my benchmarks were not just inserting keys but keys pointing to things. So a lookup walked the tree and found an object and then returned the object. radix can just return a key/value without dereferencing the value, but that wasn't the case in my runs.
Quoted 9 lines
Quoted 4 lines
Single threaded rbtree does consistently win across all sizes of lists:
skiplist-rcu thread 0 time 0 s 287 ms
rbtree thread 0 time 0 s 215 msAre the 287ms and 215ms numbers you get for skiplist-rcu and rbtree the total for 10M add/delete, or is it per operation, or is it a different number of operations altogether ? Also, how many items are present in the data structures in average ?
The 287 and 215ms were total run time for the mixed bag of operations. It had lookups, single delete then re-insert and bulk (128 keys) delete then re-insert. There were always the same number of items present (10M).
It looks like you have some strong numbers here, especially considering that my test was all in kernel vs userland rcu.
-chris
Quoted 26 lines · * Chris Mason ([email protected]) wrote:
Quoting Mathieu Desnoyers (2013-06-26 19:02:18)
Quoted 17 lines
Quoted 8 lines
The IOMMU part of the patch is updated slightly, but still not using all the new bits in the API. This is mostly because the IOMMU part is going to change later on and I'm really only using it for testing now.
For benchmarking, the IOMMU numbers are slightly higher than last time, but not more than 5% or so. This is because the bottleneck is still
skiplist_insert_hole(), which I haven't really changed in this round.Quoted 8 lines
Most of my benchmarking now is with the
skiplist_testmodule, which has expanded to a few new cases. For random operations, my performance is slightly slower than rbtree when single threaded.Random lookups on 10 million items: (inserts are similar)
rbtree random lookup time 4 s 327 ms
skiplist-rcu random lookup time 5 s 175 msQuoted 7 lines
These benchmarks are only considering averages.
I'm worried that the skiplist approach has chances to create long chains (probabilistically non-zero). Clearly, the lack of bound is something the RT guys might frown upon. I'd be curious to see how long the worse chains encountered can be on, say, 1000 machines stress-testing this for a week.
Quoted 4 lines
Correct, the probability part may run into problems for RT. I haven't put in instrumentation for worst case. I think my retries (goto again) for concurrent update are a bigger RT problem, but they can be cut down significantly.
My RCU Judy array implementation uses a similar retry trick: e.g., for a delete operation, I first do a RCU lookup of the node I need to delete, and then take the mutexes needed to protect each internal node that needs to be modified. Once each mutex is taken, I do a validation that the nodes that were just locked did not change between lookup and mutex acquisition. If any of those has been updated concurrently, every lock is unlocked, and we retry the entire operation. Indeed, this would be bad for RT. One approach RT could take is to just grab a global mutex around the entire insert/delete operations on the data structure. It would improve RT behavior at the expense of update scalability.
The problem with long chains (skip list) is that they hurt RCU lookups too, and I don't see any workaround to fix this, given it's built into the skip list design.
Quoted 11 lines
Quoted 8 lines
FWIW, my benchmark of RCU Judy array with ranges in similar conditions:
- Using 32-bit key length
- I first populated 10M ranges of len = 1, sequentially.
- Then, I run a reader threads for 10s, which perform random lookups (all successful) in keys from 0 to 10M.Similar, I had 64 bit keys and the lookups were totally random (not all successful). I doubt it matters too much for these numbers.
I'd have to try with 64-bit keys, since it matters for RCU Judy. It means a successful lookup will need to read twice as many cache lines as for 32-bit keys. For my range implementation (on top of Judy), every lookup ends up succeeding, because it either finds an "empty" range or a populated range, so having match or non-match does not matter much for range lookups.
Quoted 5 lines
Also, my benchmarks were not just inserting keys but keys pointing to things. So a lookup walked the tree and found an object and then returned the object. radix can just return a key/value without dereferencing the value, but that wasn't the case in my runs.
In the specific test I ran, I'm looking up the "range" object, which is the dereferenced "value" pointer in terms of Judy lookup. My Judy array implementation represents items as a linked list of structures matching a given key. This linked list is embedded within the structures, similarly to the linux/list.h API. Then, if the lookup succeeds, I take a mutex on the range, and check if it has been concurrently removed.
The only thing I'm not currently doing is to dereference the "private data" pointer I have in the range. Eventually, I could even embed the range structure within another structure to use inheritance to save a pointer indirection. But I wanted to get the basic things to work first before going too far into optimisation land.
Quoted 11 lines
Quoted 10 lines
Quoted 5 lines
Single threaded rbtree does consistently win across all sizes of lists:
skiplist-rcu thread 0 time 0 s 287 ms
rbtree thread 0 time 0 s 215 msAre the 287ms and 215ms numbers you get for skiplist-rcu and rbtree the total for 10M add/delete, or is it per operation, or is it a different number of operations altogether ? Also, how many items are present in the data structures in average ?
Quoted 4 lines
The 287 and 215ms were total run time for the mixed bag of operations. It had lookups, single delete then re-insert and bulk (128 keys) delete then re-insert. There were always the same number of items present (10M).
When I find time, I'll try to have a closer look at this sequence of operations, and see if I can reproduce it.
Quoted 3 lines
It looks like you have some strong numbers here, especially considering that my test was all in kernel vs userland rcu.
I'm glad to see that Userspace RCU seems to closely match the kernel RCU performance (well, at least up to 8 cores) ;-) I'm pretty sure we'll eventually run into the same scalability issues that led to the design of the Linux kernel Tree RCU implementation some day though.
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoting Mathieu Desnoyers (2013-06-26 22:29:36)
Quoted 33 lines
Quoted 5 lines
Quoted 5 lines
FWIW, my benchmark of RCU Judy array with ranges in similar conditions:
Quoted 7 lines
Quoted 4 lines
- Using 32-bit key length
- I first populated 10M ranges of len = 1, sequentially.
- Then, I run a reader threads for 10s, which perform random lookups (all successful) in keys from 0 to 10M.Similar, I had 64 bit keys and the lookups were totally random (not all successful). I doubt it matters too much for these numbers.
I'd have to try with 64-bit keys, since it matters for RCU Judy. It means a successful lookup will need to read twice as many cache lines as for 32-bit keys. For my range implementation (on top of Judy), every lookup ends up succeeding, because it either finds an "empty" range or a populated range, so having match or non-match does not matter much for range lookups.
Quoted 5 lines
Also, my benchmarks were not just inserting keys but keys pointing to things. So a lookup walked the tree and found an object and then returned the object. radix can just return a key/value without dereferencing the value, but that wasn't the case in my runs.
In the specific test I ran, I'm looking up the "range" object, which is the dereferenced "value" pointer in terms of Judy lookup. My Judy array implementation represents items as a linked list of structures matching a given key. This linked list is embedded within the structures, similarly to the
linux/list.hAPI. Then, if the lookup succeeds, I take a mutex on the range, and check if it has been concurrently removed.
Quoted 5 lines
The only thing I'm not currently doing is to dereference the "private data" pointer I have in the range. Eventually, I could even embed the range structure within another structure to use inheritance to save a pointer indirection. But I wanted to get the basic things to work first before going too far into optimisation land.
Hmmm, in my tests for both rbtree and skiplists, the private data object also has the range length. So both are doing at least one dereference when they check against the length. It sounds like this corresponds to the Judy value pointer?
Quoted 12 lines
Quoted 12 lines
Quoted 11 lines
Quoted 6 lines
Single threaded rbtree does consistently win across all sizes of lists:
skiplist-rcu thread 0 time 0 s 287 ms
rbtree thread 0 time 0 s 215 msAre the 287ms and 215ms numbers you get for skiplist-rcu and rbtree the total for 10M add/delete, or is it per operation, or is it a different number of operations altogether ? Also, how many items are present in the data structures in average ?
Quoted 7 lines
Quoted 4 lines
The 287 and 215ms were total run time for the mixed bag of operations. It had lookups, single delete then re-insert and bulk (128 keys) delete then re-insert. There were always the same number of items present (10M).
When I find time, I'll try to have a closer look at this sequence of operations, and see if I can reproduce it.
It's fine to benchmark against pure lookup/insertion/deletion. Or said a different way, my assortment of operations isn't really matching any workload, so there's on reason to emulate it ;)
Batch lookup and deletion are probably important though.
-chris
Quoted 40 lines · * Chris Mason ([email protected]) wrote:
Quoting Mathieu Desnoyers (2013-06-26 22:29:36)
Quoted 33 lines
Quoted 5 lines
Quoted 5 lines
FWIW, my benchmark of RCU Judy array with ranges in similar conditions:
Quoted 7 lines
Quoted 4 lines
- Using 32-bit key length
- I first populated 10M ranges of len = 1, sequentially.
- Then, I run a reader threads for 10s, which perform random lookups (all successful) in keys from 0 to 10M.Similar, I had 64 bit keys and the lookups were totally random (not all successful). I doubt it matters too much for these numbers.
I'd have to try with 64-bit keys, since it matters for RCU Judy. It means a successful lookup will need to read twice as many cache lines as for 32-bit keys. For my range implementation (on top of Judy), every lookup ends up succeeding, because it either finds an "empty" range or a populated range, so having match or non-match does not matter much for range lookups.
Quoted 5 lines
Also, my benchmarks were not just inserting keys but keys pointing to things. So a lookup walked the tree and found an object and then returned the object. radix can just return a key/value without dereferencing the value, but that wasn't the case in my runs.
In the specific test I ran, I'm looking up the "range" object, which is the dereferenced "value" pointer in terms of Judy lookup. My Judy array implementation represents items as a linked list of structures matching a given key. This linked list is embedded within the structures, similarly to the
linux/list.hAPI. Then, if the lookup succeeds, I take a mutex on the range, and check if it has been concurrently removed.Quoted 5 lines
The only thing I'm not currently doing is to dereference the "private data" pointer I have in the range. Eventually, I could even embed the range structure within another structure to use inheritance to save a pointer indirection. But I wanted to get the basic things to work first before going too far into optimisation land.
Quoted 4 lines
Hmmm, in my tests for both rbtree and skiplists, the private data object also has the range length. So both are doing at least one dereference when they check against the length. It sounds like this corresponds to the Judy value pointer?
Yes, this is correct.
Quoted 18 lines
Quoted 18 lines
Quoted 17 lines
Quoted 5 lines
Quoted 5 lines
Single threaded rbtree does consistently win across all sizes of lists:
Quoted 7 lines
Quoted 2 lines
skiplist-rcu thread 0 time 0 s 287 ms
rbtree thread 0 time 0 s 215 msAre the 287ms and 215ms numbers you get for skiplist-rcu and rbtree the total for 10M add/delete, or is it per operation, or is it a different number of operations altogether ? Also, how many items are present in the data structures in average ?
The 287 and 215ms were total run time for the mixed bag of operations. It had lookups, single delete then re-insert and bulk (128 keys) delete then re-insert. There were always the same number of items present (10M).
Quoted 8 lines
Quoted 2 lines
When I find time, I'll try to have a closer look at this sequence of operations, and see if I can reproduce it.
It's fine to benchmark against pure lookup/insertion/deletion. Or said a different way, my assortment of operations isn't really matching any workload, so there's on reason to emulate it ;)
Batch lookup and deletion are probably important though.
Noted, thanks!
Mathieu
Quoted 2 lines
-chris
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 12 lines · Mathieu Desnoyers
Quoted 10 lines · * Chris Mason ([email protected]) wrote:
Quoting Mathieu Desnoyers (2013-06-26 19:02:18)
Quoted 6 lines
FWIW, my benchmark of RCU Judy array with ranges in similar conditions:
- Using 32-bit key length
- I first populated 10M ranges of len = 1, sequentially.
- Then, I run a reader threads for 10s, which perform random lookups (all successful) in keys from 0 to 10M.Similar, I had 64 bit keys and the lookups were totally random (not all successful). I doubt it matters too much for these numbers.
Quoted 6 lines
I'd have to try with 64-bit keys, since it matters for RCU Judy. It means a successful lookup will need to read twice as many cache lines as for 32-bit keys. For my range implementation (on top of Judy), every lookup ends up succeeding, because it either finds an "empty" range or a populated range, so having match or non-match does not matter much for range lookups.
Yeah, I only care about performance with 64 bit keys, sparse keyspace population and random extent lengths. Random lookup performance is more important than insert and delete, though I do have cases where bulk sequential insert and removal are important, too.
Quoted 11 lines
Quoted 4 lines
Also, my benchmarks were not just inserting keys but keys pointing to things. So a lookup walked the tree and found an object and then returned the object. radix can just return a key/value without dereferencing the value, but that wasn't the case in my runs.
In the specific test I ran, I'm looking up the "range" object, which is the dereferenced "value" pointer in terms of Judy lookup. My Judy array implementation represents items as a linked list of structures matching a given key. This linked list is embedded within the structures, similarly to the
linux/list.hAPI. Then, if the lookup succeeds, I take a mutex on the range, and check if it has been concurrently removed.
Does that mean that each "extent" that is indexed has a list head embedded in it? That blows the size of the index out when all I might want to store in the tree is a 64 bit value for a block mapping...
FWIW, when a bunch of scalability work was done on xfs_repair years ago, judy arrays were benchmarked for storing extent lists that tracked free/used space. We ended up using a btree, because while it was slower than the original bitmap code, it was actually faster than the highly optimised judy array library and at the scale we needed there was no memory usage advantage to using a judy array, either...
So I'm really starting to wonder if it'd be simpler for me just to resurrect the old RCU friendly btree code Peter Z wrote years ago
(http://programming.kicks-ass.net/kernel-patches/vma_lookup/) and customise it for the couple of uses I have in XFS....
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoting Dave Chinner (2013-06-27 01:19:18)
Quoted 13 lines · Mathieu Desnoyers
Quoted 11 lines
Quoted 4 lines
Also, my benchmarks were not just inserting keys but keys pointing to things. So a lookup walked the tree and found an object and then returned the object. radix can just return a key/value without dereferencing the value, but that wasn't the case in my runs.
In the specific test I ran, I'm looking up the "range" object, which is the dereferenced "value" pointer in terms of Judy lookup. My Judy array implementation represents items as a linked list of structures matching a given key. This linked list is embedded within the structures, similarly to the
linux/list.hAPI. Then, if the lookup succeeds, I take a mutex on the range, and check if it has been concurrently removed.
Quoted 4 lines
Does that mean that each "extent" that is indexed has a list head embedded in it? That blows the size of the index out when all I might want to store in the tree is a 64 bit value for a block mapping...
For the skiplists, it might make sense to take the optimizations a little farther and put the start/len/value triplet directly in the leaf.
Right now I push the len/value part into the user object. For btrfs this is always bigger than a single block mapping (some kind of flags etc).
Quoted 9 lines
FWIW, when a bunch of scalability work was done on
xfs_repairyears ago, judy arrays were benchmarked for storing extent lists that tracked free/used space. We ended up using a btree, because while it was slower than the original bitmap code, it was actually faster than the highly optimised judy array library and at the scale we needed there was no memory usage advantage to using a judy array, either...
Quoted 4 lines
So I'm really starting to wonder if it'd be simpler for me just to resurrect the old RCU friendly btree code Peter Z wrote years ago
(http://programming.kicks-ass.net/kernel-patches/vma_lookup/) and customise it for the couple of uses I have in XFS....
I did start with his rcu btree, but the problem for me was concurrent updates.
For xfs, the skiplists need two things:
i_size_read() style usage of u64 for keys instead of unsigned long. Helper to allow duplicate keys.
Both are pretty easy, but I'm trying things out in btrfs first to make sure I've worked out any problems.
-chris
Quoted 20 lines · * Dave Chinner ([email protected]) wrote:
Quoted 12 lines · Mathieu Desnoyers
Quoted 10 lines · * Chris Mason ([email protected]) wrote:
Quoting Mathieu Desnoyers (2013-06-26 19:02:18)
Quoted 6 lines
FWIW, my benchmark of RCU Judy array with ranges in similar conditions:
- Using 32-bit key length
- I first populated 10M ranges of len = 1, sequentially.
- Then, I run a reader threads for 10s, which perform random lookups (all successful) in keys from 0 to 10M.Similar, I had 64 bit keys and the lookups were totally random (not all successful). I doubt it matters too much for these numbers.
Quoted 6 lines
I'd have to try with 64-bit keys, since it matters for RCU Judy. It means a successful lookup will need to read twice as many cache lines as for 32-bit keys. For my range implementation (on top of Judy), every lookup ends up succeeding, because it either finds an "empty" range or a populated range, so having match or non-match does not matter much for range lookups.
Quoted 5 lines
Yeah, I only care about performance with 64 bit keys, sparse keyspace population and random extent lengths. Random lookup performance is more important than insert and delete, though I do have cases where bulk sequential insert and removal are important, too.
One thing I noticed about 64-bit keys in Judy though: let's say we only use part of the key space (e.g. lower 32-bits). Even with a 64-bit key lookup, we end up always touching the same cache-lines for the top level nodes, and therefore, the number of cache lines we need to bring from memory will be quite close to that of a Judy array with 32-bit keys. I'll have to confirm this with benchmarks though.
Quoted 13 lines
Quoted 6 lines
Quoted 5 lines
Also, my benchmarks were not just inserting keys but keys pointing to things. So a lookup walked the tree and found an object and then returned the object. radix can just return a key/value without dereferencing the value, but that wasn't the case in my runs.
Quoted 6 lines
In the specific test I ran, I'm looking up the "range" object, which is the dereferenced "value" pointer in terms of Judy lookup. My Judy array implementation represents items as a linked list of structures matching a given key. This linked list is embedded within the structures, similarly to the
linux/list.hAPI. Then, if the lookup succeeds, I take a mutex on the range, and check if it has been concurrently removed.
Quoted 4 lines
Does that mean that each "extent" that is indexed has a list head embedded in it? That blows the size of the index out when all I might want to store in the tree is a 64 bit value for a block mapping...
My implementation currently has chaining of duplicates for genericity. I'm keeping it simple (no special-cases) on purpose until we find out if the Judy approach is interesting at all. We could quite easily create a variant of the RCU Judy array augmented with range support that has this as node:
/* The 64-bit start of range value is implicit within the Judy Array */ struct {
uint64_t end; /* end of range */
spinlock_t lock; /* lock updates on range */
struct rcu_head head; /* if call_rcu() is required for reclaim */
unsigned int flags:2; /* range is free, allocated, or removed */};
Depending on what you are ready to let go in terms of scalability and RCU reclaim batching, the lock and rcu_head could be removed. This ends up being a trade-off between update scalability and memory footprint. So if you go all the way for low memory footprint with a single lock covering all updates, and use synchronize_rcu() to perform reclaim, you end up with:
/* The 64-bit start of range value is implicit within the Judy Array */ struct {
uint64_t end; /* end of range */
unsigned int flags:2; /* range is free, allocated, or removed */
};
We could probably encode the flags into unused low-order bits of the pointer to the range if needed.
Quoted 9 lines
FWIW, when a bunch of scalability work was done on
xfs_repairyears ago, judy arrays were benchmarked for storing extent lists that tracked free/used space. We ended up using a btree, because while it was slower than the original bitmap code, it was actually faster than the highly optimised judy array library and at the scale we needed there was no memory usage advantage to using a judy array, either...
Quoted 4 lines
So I'm really starting to wonder if it'd be simpler for me just to resurrect the old RCU friendly btree code Peter Z wrote years ago
(http://programming.kicks-ass.net/kernel-patches/vma_lookup/) and customise it for the couple of uses I have in XFS....
Balanced tree structures end up having contention near the root if you want to perform concurrent updates on them. The advantage of RCU skip lists and Judy arrays over trees is that no rebalancing is required, so updates can be performed concurrently when touching different areas of the key space.
Thanks,
Mathieu
Quoted 7 lines
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com