summaryrefslogtreecommitdiffstats
path: root/include/uapi
diff options
context:
space:
mode:
authorFilipe David Borba Manana <fdmanana@gmail.com>2013-08-30 15:46:43 +0100
committerChris Mason <chris.mason@fusionio.com>2013-09-01 08:16:42 -0400
commitd7396f07358a7c6e22c238d36d1d85f9d652a414 (patch)
treedf344c7621c7df62d8adc4bb162d8b15d6cb845a /include/uapi
parent45d5fd14d22304c9a40d5aae75ec610f5d1cbb53 (diff)
downloadop-kernel-dev-d7396f07358a7c6e22c238d36d1d85f9d652a414.zip
op-kernel-dev-d7396f07358a7c6e22c238d36d1d85f9d652a414.tar.gz
Btrfs: optimize key searches in btrfs_search_slot
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: 6682 Range: 35.000 - 8370.000; Mean: 85.837; Median: 75.000; Stddev: 106.429 Percentiles: 90th: 124.000; 95th: 145.000; 99th: 206.000 35.000 - 61.080: 1235 ################ 61.080 - 106.053: 4207 ##################################################### 106.053 - 183.606: 1122 ############## 183.606 - 317.341: 111 # 317.341 - 547.959: 6 | 547.959 - 8370.000: 1 | Approach proposed by this patch: Count: 6682 Range: 6.000 - 135.000; Mean: 16.690; Median: 16.000; Stddev: 7.160 Percentiles: 90th: 23.000; 95th: 27.000; 99th: 40.000 6.000 - 8.418: 58 # 8.418 - 11.670: 1149 ######################### 11.670 - 16.046: 2418 ##################################################### 16.046 - 21.934: 2098 ############################################## 21.934 - 29.854: 744 ################ 29.854 - 40.511: 154 ### 40.511 - 54.848: 41 # 54.848 - 74.136: 5 | 74.136 - 100.087: 9 | 100.087 - 135.000: 6 | 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> Signed-off-by: Josef Bacik <jbacik@fusionio.com> Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Diffstat (limited to 'include/uapi')
0 files changed, 0 insertions, 0 deletions
OpenPOWER on IntegriCloud