mm/sparse: Optimize section number calculations using bit shifts
PATCH 1/1 mm/sparse: Optimize section number calculations using bit shifts
Add SECTIONS_PER_ROOT_SHIFT = ilog2(SECTIONS_PER_ROOT) with correctness guaranteed by BUILD_BUG_ON in sparse_init(). Convert SECTION_NR_TO_ROOT to use right shift instead of division for better performance. Add SECTION_NR_IN_ROOT() macro to improve code readability.
This improves code efficiency in hot paths where __nr_to_section() is frequently called, such as sparse_init() and memory section management operations.
Performance verification in sparse_init() on ARM (8GB RAM, 4 NUMA nodes):
sparse_init()
|
+----> memblocks_present()
|
+----> section initialization (sparse_init_nid loop)Time measurement points:
[T1] sparse_init start
|
v
[T2] memblocks_present() complete
|
v
[T3] sparse_init_nid() loop complete / sparse_init end
Measurement values:
memblocks_present_cycles = T2 - T1
section_initialization_cycles = T3 - T2
total_cycles = T3 - T1
Before (division):
[ 0.000000] sparse_init: total 7538 cycles [ 0.000000] memblocks_present: 4232 cycles [ 0.000000] section initialization: 3261 cycles
After (bit shift):
[ 0.000000] sparse_init: total 5641 cycles [ 0.000000] memblocks_present: 3562 cycles [ 0.000000] section initialization: 2057 cycles
Performance improvement:
Total: (7538-5641)/7538 = 25.2% faster
memblocks_present: (4232-3562)/4232 = 15.8% faster section initialization: (3261-2057)/3261 = 36.9% faster
--- include/linux/mmzone.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)
include/linux/mmzone.h +5 -2
@@ -2035,11 +2035,14 @@ struct mem_section {#ifdef CONFIG_SPARSEMEM_EXTREME #define SECTIONS_PER_ROOT (PAGE_SIZE / sizeof (struct mem_section)) +#define SECTIONS_PER_ROOT_SHIFT ilog2(SECTIONS_PER_ROOT)#else #define SECTIONS_PER_ROOT 1 +#define SECTIONS_PER_ROOT_SHIFT 0#endif -#define SECTION_NR_TO_ROOT (sec) ((sec) / SECTIONS_PER_ROOT) +#define SECTION_NR_TO_ROOT (sec) ((sec) >> SECTIONS_PER_ROOT_SHIFT) +#define SECTION_NR_IN_ROOT (sec) ((sec) & SECTION_ROOT_MASK)#define NR_SECTION_ROOTS DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)#define SECTION_ROOT_MASK (SECTIONS_PER_ROOT - 1)
@@ -2065,7 +2068,7 @@ static inline struct mem_section *__nr_to_section(unsigned long nr)if (!mem_section || !mem_section[root])return NULL ;#endif -return &mem_section[root][nr &SECTION_ROOT_MASK ]; +return &mem_section[root][SECTION_NR_IN_ROOT (nr)]; }extern size_t mem_section_usage_size (void );
Signature · 1 line
2.20.1
Mike Rapoport
reviewerHi,
Quoted 38 lines · Zhen Ni
Add
SECTIONS_PER_ROOT_SHIFT=ilog2(SECTIONS_PER_ROOT)with correctness guaranteed byBUILD_BUG_ONinsparse_init(). ConvertSECTION_NR_TO_ROOTto use right shift instead of division for better performance. AddSECTION_NR_IN_ROOT()macro to improve code readability.This improves code efficiency in hot paths where
__nr_to_section()is frequently called, such assparse_init()and memory section management operations.Performance verification in
sparse_init()on ARM (8GB RAM, 4 NUMA nodes):sparse_init() | +----> memblocks_present() | +----> section initialization (sparse_init_nid loop)Time measurement points:
[T1]
sparse_initstart
|
v
[T2]memblocks_present()complete
|
v
[T3]sparse_init_nid()loop complete /sparse_initendMeasurement values:
memblocks_present_cycles= T2 - T1
section_initialization_cycles= T3 - T2
total_cycles= T3 - T1Before (division):
[ 0.000000] sparse_init: total 7538 cycles [ 0.000000] memblocks_present: 4232 cycles [ 0.000000] section initialization: 3261 cyclesAfter (bit shift):
Quoted 8 lines
[ 0.000000] sparse_init: total 5641 cycles [ 0.000000] memblocks_present: 3562 cycles [ 0.000000] section initialization: 2057 cyclesPerformance improvement:
Total: (7538-5641)/7538 = 25.2% faster
memblocks_present: (4232-3562)/4232 = 15.8% faster section initialization: (3261-2057)/3261 = 36.9% faster
This is a nice improvement, but it's not the hot path. I believe you can derive improvement to __nr_to_section() from these measurements.
Quoted 26 lines
Signed-off-by Zhen Ni <[email protected]>--- include/linux/mmzone.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)include/linux/mmzone.h +4
-1@@ -2035,11 +2035,14 @@ struct mem_section {#ifdef CONFIG_SPARSEMEM_EXTREME #define SECTIONS_PER_ROOT (PAGE_SIZE / sizeof (struct mem_section)) +#define SECTIONS_PER_ROOT_SHIFT ilog2(SECTIONS_PER_ROOT)#else #define SECTIONS_PER_ROOT 1 +#define SECTIONS_PER_ROOT_SHIFT 0#endif -#define SECTION_NR_TO_ROOT (sec) ((sec) / SECTIONS_PER_ROOT) +#define SECTION_NR_TO_ROOT (sec) ((sec) >> SECTIONS_PER_ROOT_SHIFT) +#define SECTION_NR_IN_ROOT (sec) ((sec) & SECTION_ROOT_MASK)#define NR_SECTION_ROOTS DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)#define SECTION_ROOT_MASK (SECTIONS_PER_ROOT - 1)
include/linux/mmzone.h static inline struct mem_section *__nr_to_section(unsigned long nr) · line 2071
Quoted 5 lines
include/linux/mmzone.h +1
-1@@ -2065,7 +2068,7 @@ static inline struct mem_section *__nr_to_section(unsigned long nr)if (!mem_section || !mem_section[root])return NULL ;#endif -return &mem_section[root][nr &SECTION_ROOT_MASK ]; +return &mem_section[root][SECTION_NR_IN_ROOT (nr)];
The explicit masking is clearer IMO.
include/linux/mmzone.h static inline struct mem_section *__nr_to_section(unsigned long nr) · line 2073
Quoted 2 lines
include/linux/mmzone.h +0
-0}extern size_t mem_section_usage_size (void );
Hmm, I don't see BUILD_BUG_ON() you mention in the changelog.
Quoted 3 lines
Signature · 1 line
2.20.1
Signature · 2 lines
Sincerely yours, Mike.
Quoted 45 lines · Mike Rapoport
Hi,
Quoted 42 lines · Zhen Ni
Add
SECTIONS_PER_ROOT_SHIFT=ilog2(SECTIONS_PER_ROOT)with correctness guaranteed byBUILD_BUG_ONinsparse_init(). ConvertSECTION_NR_TO_ROOTto use right shift instead of division for better performance. AddSECTION_NR_IN_ROOT()macro to improve code readability.This improves code efficiency in hot paths where
__nr_to_section()is frequently called, such assparse_init()and memory section management operations.Performance verification in
sparse_init()on ARM (8GB RAM, 4 NUMA nodes):sparse_init() | +----> memblocks_present() | +----> section initialization (sparse_init_nid loop)Time measurement points:
[T1]
sparse_initstart
|
v
[T2]memblocks_present()complete
|
v
[T3]sparse_init_nid()loop complete /sparse_initendMeasurement values:
memblocks_present_cycles= T2 - T1
section_initialization_cycles= T3 - T2
total_cycles= T3 - T1Before (division):
[ 0.000000] sparse_init: total 7538 cycles [ 0.000000] memblocks_present: 4232 cycles [ 0.000000] section initialization: 3261 cyclesAfter (bit shift):
[ 0.000000] sparse_init: total 5641 cycles [ 0.000000] memblocks_present: 3562 cycles [ 0.000000] section initialization: 2057 cycles
Quoted 7 lines
Quoted 4 lines
Performance improvement:
Total: (7538-5641)/7538 = 25.2% faster memblocks_present: (4232-3562)/4232 = 15.8% faster section initialization: (3261-2057)/3261 = 36.9% fasterThis is a nice improvement, but it's not the hot path. I believe you can derive improvement to
__nr_to_section()from these measurements.
sparse_init() is not a hot path, but it invokes __nr_to_section() in a tight loop, making it a good measurement point to demonstrate the performance improvement.
Quoted 35 lines
Quoted 27 lines
Signed-off-by Zhen Ni <[email protected]>--- include/linux/mmzone.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)include/linux/mmzone.h +4
-1@@ -2035,11 +2035,14 @@ struct mem_section {#ifdef CONFIG_SPARSEMEM_EXTREME #define SECTIONS_PER_ROOT (PAGE_SIZE / sizeof (struct mem_section)) +#define SECTIONS_PER_ROOT_SHIFT ilog2(SECTIONS_PER_ROOT)#else #define SECTIONS_PER_ROOT 1 +#define SECTIONS_PER_ROOT_SHIFT 0#endif -#define SECTION_NR_TO_ROOT (sec) ((sec) / SECTIONS_PER_ROOT) +#define SECTION_NR_TO_ROOT (sec) ((sec) >> SECTIONS_PER_ROOT_SHIFT) +#define SECTION_NR_IN_ROOT (sec) ((sec) & SECTION_ROOT_MASK)#define NR_SECTION_ROOTS DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)#define SECTION_ROOT_MASK (SECTIONS_PER_ROOT - 1)include/linux/mmzone.h static inline struct mem_section *__nr_to_section(unsigned long nr) · line 2071
Quoted 5 lines
include/linux/mmzone.h +1
-1@@ -2065,7 +2068,7 @@ static inline struct mem_section *__nr_to_section(unsigned long nr)if (!mem_section || !mem_section[root])return NULL ;#endif -return &mem_section[root][nr &SECTION_ROOT_MASK ]; +return &mem_section[root][SECTION_NR_IN_ROOT (nr)];The explicit masking is clearer IMO.
Quoted 9 lines
include/linux/mmzone.h static inline struct mem_section *__nr_to_section(unsigned long nr) · line 2073
Quoted 2 lines
include/linux/mmzone.h +0
-0}extern size_t mem_section_usage_size (void );Hmm, I don't see
BUILD_BUG_ON()you mention in the changelog.Quoted 3 lines
Signature · 1 line
2.20.1
Regarding the BUILD_BUG_ON, it is in sparse_init() at line 419:
void __init sparse_init(void)
{
...
/* see include/linux/mmzone.h 'struct mem_section' definition */
BUILD_BUG_ON(!is_power_of_2(sizeof(struct mem_section)));
...
}This guarantees that sizeof(struct mem_section) is a power of 2, and since SECTIONS_PER_ROOT = PAGE_SIZE / sizeof(struct mem_section) and PAGE_SIZE is always a power of 2, SECTIONS_PER_ROOT is guaranteed to be a power of 2 as well, validating the use of bit shifts.
Thanks,
Zhen
Mike Rapoport
reviewerQuoted 8 lines · zhen.ni
Quoted 7 lines · Mike Rapoport
Quoted 5 lines · Zhen Ni
Performance improvement:
Total: (7538-5641)/7538 = 25.2% faster memblocks_present: (4232-3562)/4232 = 15.8% faster section initialization: (3261-2057)/3261 = 36.9% faster
Quoted 6 lines
Quoted 2 lines
This is a nice improvement, but it's not the hot path. I believe you can derive improvement to
__nr_to_section()from these measurements.
sparse_init()is not a hot path, but it invokes__nr_to_section()in a tight loop, making it a good measurement point to demonstrate the performance improvement.
Right, and explanation along these lines should be in the changelog.
Quoted 50 lines
Quoted 31 lines
Quoted 23 lines
Signed-off-by Zhen Ni <[email protected]>--- include/linux/mmzone.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)include/linux/mmzone.h +4
-1@@ -2035,11 +2035,14 @@ struct mem_section {#ifdef CONFIG_SPARSEMEM_EXTREME #define SECTIONS_PER_ROOT (PAGE_SIZE / sizeof (struct mem_section)) +#define SECTIONS_PER_ROOT_SHIFT ilog2(SECTIONS_PER_ROOT)#else #define SECTIONS_PER_ROOT 1 +#define SECTIONS_PER_ROOT_SHIFT 0#endif -#define SECTION_NR_TO_ROOT (sec) ((sec) / SECTIONS_PER_ROOT) +#define SECTION_NR_TO_ROOT (sec) ((sec) >> SECTIONS_PER_ROOT_SHIFT) +#define SECTION_NR_IN_ROOT (sec) ((sec) & SECTION_ROOT_MASK)#define NR_SECTION_ROOTS DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)#define SECTION_ROOT_MASK (SECTIONS_PER_ROOT - 1)include/linux/mmzone.h static inline struct mem_section *__nr_to_section(unsigned long nr) · line 2071
Quoted 5 lines
include/linux/mmzone.h +1
-1@@ -2065,7 +2068,7 @@ static inline struct mem_section *__nr_to_section(unsigned long nr)if (!mem_section || !mem_section[root])return NULL ;#endif -return &mem_section[root][nr &SECTION_ROOT_MASK ]; +return &mem_section[root][SECTION_NR_IN_ROOT (nr)];The explicit masking is clearer IMO.
Quoted 8 lines
include/linux/mmzone.h static inline struct mem_section *__nr_to_section(unsigned long nr) · line 2073
Quoted 2 lines
include/linux/mmzone.h +0
-0}extern size_t mem_section_usage_size (void );Hmm, I don't see
BUILD_BUG_ON()you mention in the changelog.Quoted 3 lines
Signature · 1 line
2.20.1Regarding the
BUILD_BUG_ON, it is insparse_init()at line 419:void
__initsparse_init(void){ ... /* see include/linux/mmzone.h 'struct mem_section' definition */ BUILD_BUG_ON(!is_power_of_2(sizeof(struct mem_section))); ... }
Quoted 4 lines
This guarantees that
sizeof(struct mem_section)is a power of 2, and sinceSECTIONS_PER_ROOT=PAGE_SIZE/sizeof(struct mem_section)andPAGE_SIZEis always a power of 2,SECTIONS_PER_ROOTis guaranteed to be a power of 2 as well, validating the use of bit shifts.
This was not clear from reading the changelog.
Quoted 2 lines
Thanks,
Zhen
Signature · 2 lines
Sincerely yours, Mike.
David Hildenbrand (Arm)
maintainerQuoted 62 lines · Zhen Ni
Add
SECTIONS_PER_ROOT_SHIFT=ilog2(SECTIONS_PER_ROOT)with correctness guaranteed byBUILD_BUG_ONinsparse_init(). ConvertSECTION_NR_TO_ROOTto use right shift instead of division for better performance. AddSECTION_NR_IN_ROOT()macro to improve code readability.This improves code efficiency in hot paths where
__nr_to_section()is frequently called, such assparse_init()and memory section management operations.Performance verification in
sparse_init()on ARM (8GB RAM, 4 NUMA nodes):sparse_init() | +----> memblocks_present() | +----> section initialization (sparse_init_nid loop)Time measurement points:
[T1]
sparse_initstart
|
v
[T2]memblocks_present()complete
|
v
[T3]sparse_init_nid()loop complete /sparse_initendMeasurement values:
memblocks_present_cycles= T2 - T1
section_initialization_cycles= T3 - T2
total_cycles= T3 - T1Before (division):
[ 0.000000] sparse_init: total 7538 cycles [ 0.000000] memblocks_present: 4232 cycles [ 0.000000] section initialization: 3261 cyclesAfter (bit shift):
[ 0.000000] sparse_init: total 5641 cycles [ 0.000000] memblocks_present: 3562 cycles [ 0.000000] section initialization: 2057 cyclesPerformance improvement:
Total: (7538-5641)/7538 = 25.2% faster
memblocks_present: (4232-3562)/4232 = 15.8% faster section initialization: (3261-2057)/3261 = 36.9% fasterSigned-off-by Zhen Ni <[email protected]>--- include/linux/mmzone.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)include/linux/mmzone.h +1
-0@@ -2035,11 +2035,14 @@ struct mem_section {#ifdef CONFIG_SPARSEMEM_EXTREME #define SECTIONS_PER_ROOT (PAGE_SIZE / sizeof (struct mem_section)) +#define SECTIONS_PER_ROOT_SHIFT ilog2(SECTIONS_PER_ROOT)#else
include/linux/mmzone.h struct mem_section { · line 2048
Quoted 10 lines
include/linux/mmzone.h +3
-1#define SECTIONS_PER_ROOT 1 +#define SECTIONS_PER_ROOT_SHIFT 0#endif -#define SECTION_NR_TO_ROOT (sec) ((sec) / SECTIONS_PER_ROOT) +#define SECTION_NR_TO_ROOT (sec) ((sec) >> SECTIONS_PER_ROOT_SHIFT) +#define SECTION_NR_IN_ROOT (sec) ((sec) & SECTION_ROOT_MASK)#define NR_SECTION_ROOTS DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)#define SECTION_ROOT_MASK (SECTIONS_PER_ROOT - 1)
From a compiler POV, "/ SECTIONS_PER_ROOT" is exactly the same as >> ilog2(SECTIONS_PER_ROOT) *as long as* the variable we are processing is "unsigned long".
The compiler should be smart enough to figure out that out with SECTIONS_PER_ROOT being known at compiletime.
Can you compare the generated code __nr_to_section() to see if and why the compiler fails to optimize that?
Signature · 3 lines
Cheers, David