Skip to contentSkip to conversation

mm/sparse: Optimize section number calculations using bit shifts

PATCH In review Zhen Ni 3 participants 5 messages Jun 16

Subsystems (2)
lore
Share & tools
lore

Zhen Ni

author
#0 lore raw

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
index 9adb2ad21da5..5daf471f6823 100644
@@ -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
reviewer
#1 lore raw

Hi,

Quoted 38 lines · Zhen Ni

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):

Quoted 8 lines
[    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

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
---
 include/linux/mmzone.h | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
include/linux/mmzone.h +4 -1
index 9adb2ad21da5..5daf471f6823 100644
@@ -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.
author
#2 lore raw
Quoted 45 lines · Mike Rapoport

Hi,

Quoted 42 lines · Zhen Ni

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
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% 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.

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
---
  include/linux/mmzone.h | 7 +++++--
  1 file changed, 5 insertions(+), 2 deletions(-)
include/linux/mmzone.h +4 -1
index 9adb2ad21da5..5daf471f6823 100644
@@ -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

reviewer
#3 lore raw
Quoted 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
---
  include/linux/mmzone.h | 7 +++++--
  1 file changed, 5 insertions(+), 2 deletions(-)
include/linux/mmzone.h +4 -1
index 9adb2ad21da5..5daf471f6823 100644
@@ -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.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)));
    ...
}
Quoted 4 lines

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.

This was not clear from reading the changelog.

Quoted 2 lines

Thanks,
Zhen

Signature · 2 lines
Sincerely yours,
Mike.
#4 lore raw
In reply to Zhen Ni
Quoted 62 lines · Zhen Ni

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 +1 -0
index 9adb2ad21da5..5daf471f6823 100644
@@ -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