* [PATCH] flex_array: Avoid divisions when accessing elements.
@ 2011-04-26 20:41 Jesse Gross
2011-04-27 16:13 ` Dave Hansen
0 siblings, 1 reply; 6+ messages in thread
From: Jesse Gross @ 2011-04-26 20:41 UTC (permalink / raw)
To: Andrew Morton; +Cc: linux-kernel, Dave Hansen, David Rientjes
On most architectures division is an expensive operation and
accessing an element currently requires four of them. This
performance penalty effectively precludes flex arrays from
being used on any kind of fast path. However, two of these
divisions can be handled at creation time and the others can
be replaced by a reciprocal divide, completely avoiding real
divisions on access.
Signed-off-by: Jesse Gross <jesse@nicira.com>
CC: Dave Hansen <dave@linux.vnet.ibm.com>
CC: David Rientjes <rientjes@google.com>
---
include/linux/flex_array.h | 2 ++
lib/flex_array.c | 21 ++++++++++++---------
2 files changed, 14 insertions(+), 9 deletions(-)
diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h
index 70e4efa..9641a8f 100644
--- a/include/linux/flex_array.h
+++ b/include/linux/flex_array.h
@@ -21,6 +21,8 @@ struct flex_array {
struct {
int element_size;
int total_nr_elements;
+ int elems_per_part;
+ u32 reciprocal_elems;
struct flex_array_part *parts[];
};
/*
diff --git a/lib/flex_array.c b/lib/flex_array.c
index c0ea40b..17ed599 100644
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -24,6 +24,7 @@
#include <linux/slab.h>
#include <linux/stddef.h>
#include <linux/module.h>
+#include <linux/reciprocal_div.h>
struct flex_array_part {
char elements[FLEX_ARRAY_PART_SIZE];
@@ -88,8 +89,8 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total,
gfp_t flags)
{
struct flex_array *ret;
- int max_size = FLEX_ARRAY_NR_BASE_PTRS *
- FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
+ int elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
+ int max_size = FLEX_ARRAY_NR_BASE_PTRS * elems_per_part;
/* max_size will end up 0 if element_size > PAGE_SIZE */
if (total > max_size)
@@ -99,6 +100,8 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total,
return NULL;
ret->element_size = element_size;
ret->total_nr_elements = total;
+ ret->elems_per_part = elems_per_part;
+ ret->reciprocal_elems = reciprocal_value(elems_per_part);
if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
memset(&ret->parts[0], FLEX_ARRAY_FREE,
FLEX_ARRAY_BASE_BYTES_LEFT);
@@ -109,7 +112,7 @@ EXPORT_SYMBOL(flex_array_alloc);
static int fa_element_to_part_nr(struct flex_array *fa,
unsigned int element_nr)
{
- return element_nr / FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size);
+ return reciprocal_divide(element_nr, fa->reciprocal_elems);
}
/**
@@ -138,12 +141,12 @@ void flex_array_free(struct flex_array *fa)
EXPORT_SYMBOL(flex_array_free);
static unsigned int index_inside_part(struct flex_array *fa,
- unsigned int element_nr)
+ unsigned int element_nr,
+ unsigned int part_nr)
{
unsigned int part_offset;
- part_offset = element_nr %
- FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size);
+ part_offset = element_nr - part_nr * fa->elems_per_part;
return part_offset * fa->element_size;
}
@@ -196,7 +199,7 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
if (!part)
return -ENOMEM;
}
- dst = &part->elements[index_inside_part(fa, element_nr)];
+ dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
memcpy(dst, src, fa->element_size);
return 0;
}
@@ -224,7 +227,7 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
if (!part)
return -EINVAL;
}
- dst = &part->elements[index_inside_part(fa, element_nr)];
+ dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
memset(dst, FLEX_ARRAY_FREE, fa->element_size);
return 0;
}
@@ -293,7 +296,7 @@ void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
if (!part)
return NULL;
}
- return &part->elements[index_inside_part(fa, element_nr)];
+ return &part->elements[index_inside_part(fa, element_nr, part_nr)];
}
EXPORT_SYMBOL(flex_array_get);
--
1.7.1
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH] flex_array: Avoid divisions when accessing elements.
2011-04-26 20:41 [PATCH] flex_array: Avoid " Jesse Gross
@ 2011-04-27 16:13 ` Dave Hansen
2011-04-29 1:48 ` Jesse Gross
0 siblings, 1 reply; 6+ messages in thread
From: Dave Hansen @ 2011-04-27 16:13 UTC (permalink / raw)
To: Jesse Gross; +Cc: Andrew Morton, linux-kernel, David Rientjes
On Tue, 2011-04-26 at 13:41 -0700, Jesse Gross wrote:
> On most architectures division is an expensive operation and
> accessing an element currently requires four of them. This
> performance penalty effectively precludes flex arrays from
> being used on any kind of fast path. However, two of these
> divisions can be handled at creation time and the others can
> be replaced by a reciprocal divide, completely avoiding real
> divisions on access.
flex_array.c has a nice table for how many objects can be allocated:
* Element size | Objects | Objects |
* PAGE_SIZE=4k | 32-bit | 64-bit |
* ---------------------------------|
* 1 bytes | 4186112 | 2093056 |
* 2 bytes | 2093056 | 1046528 |
* 3 bytes | 1395030 | 697515 |
* 4 bytes | 1046528 | 523264 |
* 32 bytes | 130816 | 65408 |
* 33 bytes | 126728 | 63364 |
* 2048 bytes | 2044 | 1022 |
* 2049 bytes | 1022 | 511 |
* void * | 1046528 | 261632 |
This patch changes that a bit. Would you mind updating it?
-- Dave
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] flex_array: Avoid divisions when accessing elements.
2011-04-27 16:13 ` Dave Hansen
@ 2011-04-29 1:48 ` Jesse Gross
0 siblings, 0 replies; 6+ messages in thread
From: Jesse Gross @ 2011-04-29 1:48 UTC (permalink / raw)
To: Dave Hansen; +Cc: Andrew Morton, linux-kernel, David Rientjes
On Wed, Apr 27, 2011 at 9:13 AM, Dave Hansen <dave@linux.vnet.ibm.com> wrote:
> On Tue, 2011-04-26 at 13:41 -0700, Jesse Gross wrote:
>> On most architectures division is an expensive operation and
>> accessing an element currently requires four of them. This
>> performance penalty effectively precludes flex arrays from
>> being used on any kind of fast path. However, two of these
>> divisions can be handled at creation time and the others can
>> be replaced by a reciprocal divide, completely avoiding real
>> divisions on access.
>
> flex_array.c has a nice table for how many objects can be allocated:
>
> * Element size | Objects | Objects |
> * PAGE_SIZE=4k | 32-bit | 64-bit |
> * ---------------------------------|
> * 1 bytes | 4186112 | 2093056 |
> * 2 bytes | 2093056 | 1046528 |
> * 3 bytes | 1395030 | 697515 |
> * 4 bytes | 1046528 | 523264 |
> * 32 bytes | 130816 | 65408 |
> * 33 bytes | 126728 | 63364 |
> * 2048 bytes | 2044 | 1022 |
> * 2049 bytes | 1022 | 511 |
> * void * | 1046528 | 261632 |
>
> This patch changes that a bit. Would you mind updating it?
Sure, I'll send out an updated patch that does that tomorrow.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH] flex_array: avoid divisions when accessing elements
@ 2011-05-02 17:26 Eric Paris
2011-05-02 17:36 ` Dave Hansen
0 siblings, 1 reply; 6+ messages in thread
From: Eric Paris @ 2011-05-02 17:26 UTC (permalink / raw)
To: linux-kernel
Cc: Jesse Gross, Dave Hansen, David Rientjes, Eric Paris,
Andrew Morton
From: Jesse Gross <jesse@nicira.com>
On most architectures division is an expensive operation and accessing an
element currently requires four of them. This performance penalty
effectively precludes flex arrays from being used on any kind of fast
path. However, two of these divisions can be handled at creation time and
the others can be replaced by a reciprocal divide, completely avoiding
real divisions on access.
Signed-off-by: Jesse Gross <jesse@nicira.com>
Cc: Dave Hansen <dave@linux.vnet.ibm.com>
Cc: David Rientjes <rientjes@google.com>
Cc: Eric Paris <eparis@redhat.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
[rebase on top of changes to support 0 len elements: eparis]
[initialize part_nr when array fits entirely in base: eparis]
Signed-off-by: Eric Paris <eparis@redhat.com>
---
include/linux/flex_array.h | 2 +
lib/flex_array.c | 51 +++++++++++++++++++++++++-------------------
2 files changed, 31 insertions(+), 22 deletions(-)
diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h
index ebeb2f3..6843cf1 100644
--- a/include/linux/flex_array.h
+++ b/include/linux/flex_array.h
@@ -21,6 +21,8 @@ struct flex_array {
struct {
int element_size;
int total_nr_elements;
+ int elems_per_part;
+ u32 reciprocal_elems;
struct flex_array_part *parts[];
};
/*
diff --git a/lib/flex_array.c b/lib/flex_array.c
index cab7621..9b8b894 100644
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -24,6 +24,7 @@
#include <linux/slab.h>
#include <linux/stddef.h>
#include <linux/module.h>
+#include <linux/reciprocal_div.h>
struct flex_array_part {
char elements[FLEX_ARRAY_PART_SIZE];
@@ -70,15 +71,15 @@ static inline int elements_fit_in_base(struct flex_array *fa)
* Element size | Objects | Objects |
* PAGE_SIZE=4k | 32-bit | 64-bit |
* ---------------------------------|
- * 1 bytes | 4186112 | 2093056 |
- * 2 bytes | 2093056 | 1046528 |
- * 3 bytes | 1395030 | 697515 |
- * 4 bytes | 1046528 | 523264 |
- * 32 bytes | 130816 | 65408 |
- * 33 bytes | 126728 | 63364 |
- * 2048 bytes | 2044 | 1022 |
- * 2049 bytes | 1022 | 511 |
- * void * | 1046528 | 261632 |
+ * 1 bytes | 4177920 | 2088960 |
+ * 2 bytes | 2088960 | 1044480 |
+ * 3 bytes | 1392300 | 696150 |
+ * 4 bytes | 1044480 | 522240 |
+ * 32 bytes | 130560 | 65408 |
+ * 33 bytes | 126480 | 63240 |
+ * 2048 bytes | 2040 | 1020 |
+ * 2049 bytes | 1020 | 510 |
+ * void * | 1044480 | 261120 |
*
* Since 64-bit pointers are twice the size, we lose half the
* capacity in the base structure. Also note that no effort is made
@@ -88,11 +89,15 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total,
gfp_t flags)
{
struct flex_array *ret;
+ int elems_per_part = 0;
+ int reciprocal_elems = 0;
int max_size = 0;
- if (element_size)
- max_size = FLEX_ARRAY_NR_BASE_PTRS *
- FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
+ if (element_size) {
+ elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
+ reciprocal_elems = reciprocal_value(elems_per_part);
+ max_size = FLEX_ARRAY_NR_BASE_PTRS * elems_per_part;
+ }
/* max_size will end up 0 if element_size > PAGE_SIZE */
if (total > max_size)
@@ -102,6 +107,8 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total,
return NULL;
ret->element_size = element_size;
ret->total_nr_elements = total;
+ ret->elems_per_part = elems_per_part;
+ ret->reciprocal_elems = reciprocal_elems;
if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
memset(&ret->parts[0], FLEX_ARRAY_FREE,
FLEX_ARRAY_BASE_BYTES_LEFT);
@@ -112,7 +119,7 @@ EXPORT_SYMBOL(flex_array_alloc);
static int fa_element_to_part_nr(struct flex_array *fa,
unsigned int element_nr)
{
- return element_nr / FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size);
+ return reciprocal_divide(element_nr, fa->reciprocal_elems);
}
/**
@@ -141,12 +148,12 @@ void flex_array_free(struct flex_array *fa)
EXPORT_SYMBOL(flex_array_free);
static unsigned int index_inside_part(struct flex_array *fa,
- unsigned int element_nr)
+ unsigned int element_nr,
+ unsigned int part_nr)
{
unsigned int part_offset;
- part_offset = element_nr %
- FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size);
+ part_offset = element_nr - part_nr * fa->elems_per_part;
return part_offset * fa->element_size;
}
@@ -186,7 +193,7 @@ __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags)
int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
gfp_t flags)
{
- int part_nr;
+ int part_nr = 0;
struct flex_array_part *part;
void *dst;
@@ -202,7 +209,7 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
if (!part)
return -ENOMEM;
}
- dst = &part->elements[index_inside_part(fa, element_nr)];
+ dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
memcpy(dst, src, fa->element_size);
return 0;
}
@@ -217,7 +224,7 @@ EXPORT_SYMBOL(flex_array_put);
*/
int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
{
- int part_nr;
+ int part_nr = 0;
struct flex_array_part *part;
void *dst;
@@ -233,7 +240,7 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
if (!part)
return -EINVAL;
}
- dst = &part->elements[index_inside_part(fa, element_nr)];
+ dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
memset(dst, FLEX_ARRAY_FREE, fa->element_size);
return 0;
}
@@ -302,7 +309,7 @@ EXPORT_SYMBOL(flex_array_prealloc);
*/
void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
{
- int part_nr;
+ int part_nr = 0;
struct flex_array_part *part;
if (!fa->element_size)
@@ -317,7 +324,7 @@ void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
if (!part)
return NULL;
}
- return &part->elements[index_inside_part(fa, element_nr)];
+ return &part->elements[index_inside_part(fa, element_nr, part_nr)];
}
EXPORT_SYMBOL(flex_array_get);
--
1.7.1
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH] flex_array: avoid divisions when accessing elements
2011-05-02 17:26 [PATCH] flex_array: avoid divisions when accessing elements Eric Paris
@ 2011-05-02 17:36 ` Dave Hansen
2011-05-02 20:23 ` Jesse Gross
0 siblings, 1 reply; 6+ messages in thread
From: Dave Hansen @ 2011-05-02 17:36 UTC (permalink / raw)
To: Eric Paris; +Cc: linux-kernel, Jesse Gross, David Rientjes, Andrew Morton
On Mon, 2011-05-02 at 13:26 -0400, Eric Paris wrote:
> On most architectures division is an expensive operation and accessing an
> element currently requires four of them. This performance penalty
> effectively precludes flex arrays from being used on any kind of fast
> path. However, two of these divisions can be handled at creation time and
> the others can be replaced by a reciprocal divide, completely avoiding
> real divisions on access.
>
> Signed-off-by: Jesse Gross <jesse@nicira.com>
> Cc: David Rientjes <rientjes@google.com>
> Cc: Eric Paris <eparis@redhat.com>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> [rebase on top of changes to support 0 len elements: eparis]
> [initialize part_nr when array fits entirely in base: eparis]
> Signed-off-by: Eric Paris <eparis@redhat.com>
This seems sane to me, especially in the element access case.
Acked-by: Dave Hansen <dave@linux.vnet.ibm.com>
-- Dave
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] flex_array: avoid divisions when accessing elements
2011-05-02 17:36 ` Dave Hansen
@ 2011-05-02 20:23 ` Jesse Gross
0 siblings, 0 replies; 6+ messages in thread
From: Jesse Gross @ 2011-05-02 20:23 UTC (permalink / raw)
To: Dave Hansen; +Cc: Eric Paris, linux-kernel, David Rientjes, Andrew Morton
On Mon, May 2, 2011 at 10:36 AM, Dave Hansen <dave@linux.vnet.ibm.com> wrote:
> On Mon, 2011-05-02 at 13:26 -0400, Eric Paris wrote:
>> On most architectures division is an expensive operation and accessing an
>> element currently requires four of them. This performance penalty
>> effectively precludes flex arrays from being used on any kind of fast
>> path. However, two of these divisions can be handled at creation time and
>> the others can be replaced by a reciprocal divide, completely avoiding
>> real divisions on access.
>>
>> Signed-off-by: Jesse Gross <jesse@nicira.com>
>> Cc: David Rientjes <rientjes@google.com>
>> Cc: Eric Paris <eparis@redhat.com>
>> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
>> [rebase on top of changes to support 0 len elements: eparis]
>> [initialize part_nr when array fits entirely in base: eparis]
>> Signed-off-by: Eric Paris <eparis@redhat.com>
>
> This seems sane to me, especially in the element access case.
>
> Acked-by: Dave Hansen <dave@linux.vnet.ibm.com>
Thanks Eric!
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2011-05-02 20:23 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2011-05-02 17:26 [PATCH] flex_array: avoid divisions when accessing elements Eric Paris
2011-05-02 17:36 ` Dave Hansen
2011-05-02 20:23 ` Jesse Gross
-- strict thread matches above, loose matches on Subject: below --
2011-04-26 20:41 [PATCH] flex_array: Avoid " Jesse Gross
2011-04-27 16:13 ` Dave Hansen
2011-04-29 1:48 ` Jesse Gross
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox