| Message ID | 1377804111-15247-1-git-send-email-fdmanana@gmail.com (mailing list archive) |
|---|---|
| State | Superseded, archived |
| Headers | show |
On Thu, Aug 29, 2013 at 08:21:51PM +0100, Filipe David Borba Manana wrote: > Count: 5013 > Range: 25.000 - 497.000; Mean: 82.767; Median: 64.000; Stddev: 49.972 > Percentiles: 90th: 141.000; 95th: 182.000; 99th: 287.000 > 25.000 - 33.930: 211 ###### > 33.930 - 45.927: 277 ######## > 45.927 - 62.045: 1834 ##################################################### > 62.045 - 83.699: 1203 ################################### > 83.699 - 112.789: 609 ################## > 112.789 - 151.872: 450 ############# > 151.872 - 204.377: 246 ####### > 204.377 - 274.917: 124 #### > 274.917 - 369.684: 48 # > 369.684 - 497.000: 11 | > > Approach proposed by this patch: > > Count: 5013 > Range: 10.000 - 8303.000; Mean: 28.505; Median: 18.000; Stddev: 119.147 > Percentiles: 90th: 49.000; 95th: 74.000; 99th: 115.000 > 10.000 - 20.339: 3160 ##################################################### > 20.339 - 40.397: 1131 ################### > 40.397 - 79.308: 507 ######### > 79.308 - 154.794: 199 ### > 154.794 - 301.232: 14 | > 301.232 - 585.313: 1 | > 585.313 - 8303.000: 1 | The statistics do not change from patch to patch+1 but you're doing changes that may affect performance, can you please update them as well? thanks, david -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 30, 2013 at 3:14 PM, David Sterba <dsterba@suse.cz> wrote: > On Thu, Aug 29, 2013 at 08:21:51PM +0100, Filipe David Borba Manana wrote: >> Count: 5013 >> Range: 25.000 - 497.000; Mean: 82.767; Median: 64.000; Stddev: 49.972 >> Percentiles: 90th: 141.000; 95th: 182.000; 99th: 287.000 >> 25.000 - 33.930: 211 ###### >> 33.930 - 45.927: 277 ######## >> 45.927 - 62.045: 1834 ##################################################### >> 62.045 - 83.699: 1203 ################################### >> 83.699 - 112.789: 609 ################## >> 112.789 - 151.872: 450 ############# >> 151.872 - 204.377: 246 ####### >> 204.377 - 274.917: 124 #### >> 274.917 - 369.684: 48 # >> 369.684 - 497.000: 11 | >> >> Approach proposed by this patch: >> >> Count: 5013 >> Range: 10.000 - 8303.000; Mean: 28.505; Median: 18.000; Stddev: 119.147 >> Percentiles: 90th: 49.000; 95th: 74.000; 99th: 115.000 >> 10.000 - 20.339: 3160 ##################################################### >> 20.339 - 40.397: 1131 ################### >> 40.397 - 79.308: 507 ######### >> 79.308 - 154.794: 199 ### >> 154.794 - 301.232: 14 | >> 301.232 - 585.313: 1 | >> 585.313 - 8303.000: 1 | > > The statistics do not change from patch to patch+1 but you're doing > changes that may affect performance, can you please update them as well? Sure. They're actually better now :) Patch following with updated histograms. > > thanks, > david
On Fri, Aug 30, 2013 at 03:47:21PM +0100, Filipe David Manana wrote: > Sure. > They're actually better now :) Thanks. The numbers changed in both samples, but the relative difference is still 2x improvement in this particular test. david -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 30, 2013 at 3:59 PM, David Sterba <dsterba@suse.cz> wrote: > On Fri, Aug 30, 2013 at 03:47:21PM +0100, Filipe David Manana wrote: >> Sure. >> They're actually better now :) > > Thanks. The numbers changed in both samples, but the relative difference > is still 2x improvement in this particular test. I tend to favor the percentiles above everything else, and for these last comparison, they're all about 5x better. These times are for a single search node/leaf. The highest the level (where root is highest) an exact match first happens, the better it will be for the overall tree search operation, as more times this optimal code path will be executed. > > david
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c index 5fa521b..a48cbb2 100644 --- a/fs/btrfs/ctree.c +++ b/fs/btrfs/ctree.c @@ -2426,6 +2426,41 @@ done: return ret; } +static void key_search_validate(struct extent_buffer *b, + struct btrfs_key *key, + int level) +{ +#ifdef CONFIG_BTRFS_ASSERT + struct btrfs_disk_key disk_key; + + btrfs_cpu_key_to_disk(&disk_key, key); + + if (level == 0) + ASSERT(!memcmp_extent_buffer(b, &disk_key, + offsetof(struct btrfs_leaf, items[0].key), + sizeof(disk_key))); + else + ASSERT(!memcmp_extent_buffer(b, &disk_key, + offsetof(struct btrfs_node, ptrs[0].key), + sizeof(disk_key))); +#endif +} + +static int key_search(struct extent_buffer *b, struct btrfs_key *key, + int level, int *prev_cmp, int *slot) +{ + + if (*prev_cmp != 0) { + *prev_cmp = bin_search(b, key, level, slot); + return *prev_cmp; + } + + key_search_validate(b, key, level); + *slot = 0; + + return 0; +} + /* * look for key in the tree. path is filled in with nodes along the way * if key is found, we return zero and you can find the item in the leaf @@ -2454,6 +2489,7 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root int write_lock_level = 0; u8 lowest_level = 0; int min_write_lock_level; + int prev_cmp; lowest_level = p->lowest_level; WARN_ON(lowest_level && ins_len > 0); @@ -2484,6 +2520,7 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root min_write_lock_level = write_lock_level; again: + prev_cmp = -1; /* * we try very hard to do read locks on the root */ @@ -2584,7 +2621,7 @@ cow_done: if (!cow) btrfs_unlock_up_safe(p, level + 1); - ret = bin_search(b, key, level, &slot); + ret = key_search(b, key, level, &prev_cmp, &slot); if (level != 0) { int dec = 0; @@ -2719,6 +2756,7 @@ int btrfs_search_old_slot(struct btrfs_root *root, struct btrfs_key *key, int level; int lowest_unlock = 1; u8 lowest_level = 0; + int prev_cmp; lowest_level = p->lowest_level; WARN_ON(p->nodes[0] != NULL); @@ -2729,6 +2767,7 @@ int btrfs_search_old_slot(struct btrfs_root *root, struct btrfs_key *key, } again: + prev_cmp = -1; b = get_old_root(root, time_seq); level = btrfs_header_level(b); p->locks[level] = BTRFS_READ_LOCK; @@ -2746,7 +2785,7 @@ again: */ btrfs_unlock_up_safe(p, level + 1); - ret = bin_search(b, key, level, &slot); + ret = key_search(b, key, level, &prev_cmp, &slot); if (level != 0) { int dec = 0;
When the binary search returns 0 (exact match), the target key will necessarily be at slot 0 of all nodes below the current one, so in this case the binary search is not needed because it will always return 0, and we waste time doing it, holding node locks for longer than necessary, etc. Below follow histograms with the times spent on the current approach of doing a binary search when the previous binary search returned 0, and times for the new approach, which directly picks the first item/child node in the leaf/node. Current approach: Count: 5013 Range: 25.000 - 497.000; Mean: 82.767; Median: 64.000; Stddev: 49.972 Percentiles: 90th: 141.000; 95th: 182.000; 99th: 287.000 25.000 - 33.930: 211 ###### 33.930 - 45.927: 277 ######## 45.927 - 62.045: 1834 ##################################################### 62.045 - 83.699: 1203 ################################### 83.699 - 112.789: 609 ################## 112.789 - 151.872: 450 ############# 151.872 - 204.377: 246 ####### 204.377 - 274.917: 124 #### 274.917 - 369.684: 48 # 369.684 - 497.000: 11 | Approach proposed by this patch: Count: 5013 Range: 10.000 - 8303.000; Mean: 28.505; Median: 18.000; Stddev: 119.147 Percentiles: 90th: 49.000; 95th: 74.000; 99th: 115.000 10.000 - 20.339: 3160 ##################################################### 20.339 - 40.397: 1131 ################### 40.397 - 79.308: 507 ######### 79.308 - 154.794: 199 ### 154.794 - 301.232: 14 | 301.232 - 585.313: 1 | 585.313 - 8303.000: 1 | These samples were captured during a run of the btrfs tests 001, 002 and 004 in the xfstests, with a leaf/node size of 4Kb. Signed-off-by: Filipe David Borba Manana <fdmanana@gmail.com> --- V2: Simplified code, removed unnecessary code. V3: Replaced BUG_ON() with the new ASSERT() from Josef. V4: Addressed latest comments from Zach Brown and Josef Bacik. Surrounded all code that is used for the assertion with a #ifdef CONFIG_BTRFS_ASSERT ... #endif block. Also changed offset arguments to be more strictly correct. fs/btrfs/ctree.c | 43 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 41 insertions(+), 2 deletions(-)