flex_array: conditionally optimize out divides

RFC PATCH In review Dave Hansen 2 participants 3 messages Aug 17, 2009 – Aug 18, 2009 Library code

Share & tools

Dave Hansen

author

2009-08-17 20:43 UTC #0 lore raw

RFC PATCH 1/1 flex_array: conditionally optimize out divides

There are three flex_array operations that require divides:
1. figuring out into which "part" we should access
2. figuring out where into that part we fit
3. figuring out in how many elements fit into a part

Division can get expensive, and we may incur one or two divides for each put() or get() that is performed. If we rounded the elements to a power-of-two and stored shifts and masks, we could rid ourselves of the divides, but we would lose storage space with oddly-sized objects. We could code the implementation to handle divides and special- case the shifts when they can be used, but that would complicate the code.

This is an alternative. We introduce variants of flex_array_get() and flex_array_put() since they are the most common operations. We append an _es() to their names (for Element Size) and get flex_array_get_es() and flex_array_put_es(). The allocation and free functions remain unoptimized since they're not indended to be hot paths.

Passing the element size into each operation, and using it like this:

	flex_array_get(fa, nr, sizeof(struct my_struct));

lets the compiler turn the divides into shifts if 'my_struct' is a power-of-two in size.

It seems that only gcc 4.1 and up are smart enough to figure this out, though.

---

 linux-2.6.git-dave/include/linux/flex_array.h |   54 ++++++++++++++++++++++++++
 linux-2.6.git-dave/lib/flex_array.c           |   52 +++++++++++++------------
 2 files changed, 82 insertions(+), 24 deletions(-)

include/linux/flex_array.h renamed from include/linux/flex_array.h~precalc +54 -0

diff -puN include/linux/flex_array.h~precalc include/linux/flex_array.h
@@ -1,6 +1,7 @@
 #ifndef _FLEX_ARRAY_H
 #define _FLEX_ARRAY_H
 
+#include <linux/errno.h>
 #include <linux/types.h>
 #include <asm/page.h>

@@ -36,6 +37,59 @@ struct flex_array {
 	.total_nr_elements = (total),	\
 } } }
 
+/*
+ * The 'unsigned' here seems to make gcc more happy
+ * to optimize the divide.
+ */
+static inline unsigned int __elements_per_part(int element_size)
+{
+	return FLEX_ARRAY_PART_SIZE / element_size;
+}
+
+static inline int __fa_element_to_part_nr(int element_size, int element_nr)
+{
+	return element_nr / __elements_per_part(element_size);
+}
+
+static inline int __fa_index_inside_part(int element_size, int element_nr)
+{
+	return element_nr % __elements_per_part(element_size);
+}
+
+int flex_array_put_precalc(struct flex_array *fa, int part_nr,
+			   int index_inside_part, void *src, gfp_t flags);
+void *flex_array_get_precalc(struct flex_array *fa, int part_nr,
+			     int index_inside_part);
+
+/*
+ * Use the _es() variants when you want the compiler to
+ * be able to optimize the divides like when you have a
+ * power-of-two element_size.
+ */
+static inline void *flex_array_get_es(struct flex_array *fa,
+		int element_nr, int element_size)
+{
+	int part_nr = __fa_element_to_part_nr(element_size, element_nr);
+	int index_inside = __fa_index_inside_part(element_size, element_nr);
+
+	if (element_nr >= fa->total_nr_elements)
+		return NULL;
+
+	return flex_array_get_precalc(fa, part_nr, index_inside);
+}
+
+static inline int flex_array_put_es(struct flex_array *fa, int element_nr,
+		int element_size, void *src, gfp_t flags)
+{
+	int part_nr = __fa_element_to_part_nr(element_size, element_nr);
+	int index_inside = __fa_index_inside_part(element_size, element_nr);
+
+	if (element_nr >= fa->total_nr_elements)
+		return -ENOSPC;
+
+	return flex_array_put_precalc(fa, part_nr, index_inside, src, flags);
+}
+
 struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags);
 int flex_array_prealloc(struct flex_array *fa, int start, int end, gfp_t flags);
 void flex_array_free(struct flex_array *fa);

lib/flex_array.c renamed from lib/flex_array.c~precalc +28 ~~-24~~

111 lines not on this page · raw message

diff -L include/linux/flex_array.hcd -puN /dev/null /dev/null _

Dan Williams

2009-08-18 18:02 UTC #1 lore raw

Quoted 28 lines · Dave Hansen

There are three flex_array operations that require divides:
1. figuring out into which "part" we should access
2. figuring out where into that part we fit
3. figuring out in how many elements fit into a part
Division can get expensive, and we may incur one or two divides for each put() or get() that is performed. If we rounded the elements to a power-of-two and stored shifts and masks, we could rid ourselves of the divides, but we would lose storage space with oddly-sized objects. We could code the implementation to handle divides and special- case the shifts when they can be used, but that would complicate the code.
This is an alternative. We introduce variants of flex_array_get() and flex_array_put() since they are the most common operations. We append an _es() to their names (for Element Size) and get flex_array_get_es() and flex_array_put_es(). The allocation and free functions remain unoptimized since they're not indended to be hot paths.
Passing the element size into each operation, and using it like this:
flex_array_get(fa, nr, sizeof(struct my_struct));

Quoted 7 lines

lets the compiler turn the divides into shifts if 'my_struct' is a power-of-two in size.
It seems that only gcc 4.1 and up are smart enough to figure this out, though.
---

Hi Dave,

Thanks for this. I'll give it a shot hopefully in the next few days. One comment below...

include/linux/flex_array.h struct flex_array { · line 76

Quoted 13 lines

include/linux/flex_array.h renamed from include/linux/flex_array.h~precalc +13 -0

+/*
+ * Use the _es() variants when you want the compiler to
+ * be able to optimize the divides like when you have a
+ * power-of-two element_size.
+ */
+static inline void *flex_array_get_es(struct flex_array *fa,
+               int element_nr, int element_size)
+{
+       int part_nr = __fa_element_to_part_nr(element_size, element_nr);
+       int index_inside = __fa_index_inside_part(element_size, element_nr);
+
+       if (element_nr >= fa->total_nr_elements)
+               return NULL;

This if()...

include/linux/flex_array.h struct flex_array { · line 88

Quoted 12 lines

include/linux/flex_array.h renamed from include/linux/flex_array.h~precalc +12 -0

+
+       return flex_array_get_precalc(fa, part_nr, index_inside);
+}
+
+static inline int flex_array_put_es(struct flex_array *fa, int element_nr,
+               int element_size, void *src, gfp_t flags)
+{
+       int part_nr = __fa_element_to_part_nr(element_size, element_nr);
+       int index_inside = __fa_index_inside_part(element_size, element_nr);
+
+       if (element_nr >= fa->total_nr_elements)
+               return -ENOSPC;

...and this one look like good candidates for unlikely() as these additional branches may be a concern for the fast path.

Thanks,
Dan

Dave Hansen

author

2009-08-18 21:30 UTC #2 lore raw

Quoted 6 lines · Dan Williams

Quoted 6 lines

include/linux/flex_array.h renamed from include/linux/flex_array.h~precalc +6 -0

+       return flex_array_get_precalc(fa, part_nr, index_inside);
+}
+
+static inline int flex_array_put_es(struct flex_array *fa, int element_nr,
+               int element_size, void *src, gfp_t flags)
+{

Quoted 8 lines

include/linux/flex_array.h struct flex_array { · line 88
Quoted 5 lines
include/linux/flex_array.h renamed from include/linux/flex_array.h~precalc +5 -0
+       int part_nr = __fa_element_to_part_nr(element_size, element_nr);
+       int index_inside = __fa_index_inside_part(element_size, element_nr);
+
+       if (element_nr >= fa->total_nr_elements)
+               return -ENOSPC;
...and this one look like good candidates for unlikely() as these additional branches may be a concern for the fast path.

Personally, I think those macros are grossly overused. I'm loathe to use them unless there's actual profiling data showing that they make an appreciable performance improvement or that the generated code is unquestionably better.

-- Dave