Skip to contentSkip to conversation

mm: sparse: shift operation instead of division operation for root index

PATCH In review Guo Hui 2 participants 3 messages Aug 10, 2023 – Aug 12, 2023

Subsystems (3)
lore
Share & tools
lore

Guo Hui

author
#0 lore raw

PATCH 1/1 mm: sparse: shift operation instead of division operation for root index

In the function __nr_to_section,
Use shift operation instead of division operation in order to improve the performance of memory management. There are no functional changes.

Some performance data is as follows:
Machine configuration: Hygon 128 cores, 256M memory

Stream single core:

           with patch       without patch       promote
Copy       23376.7731       23907.1532          -1.27%
Scale      12580.2913       11679.7852          +7.71%
Add        11922.9562       11461.8669          +4.02%
Triad      12549.2735       11491.9798          +9.20%
---
 include/linux/mmzone.h | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
include/linux/mmzone.h +2 -1
index 5e50b78d58ea..8dde6fb56109 100644
@@ -1818,7 +1818,8 @@ struct mem_section {
 #define SECTIONS_PER_ROOT	1
 #endif
 
-#define SECTION_NR_TO_ROOT(sec)	((sec) / SECTIONS_PER_ROOT)
+#define SECTION_ROOT_SHIFT        (__builtin_popcount(SECTIONS_PER_ROOT - 1))
+#define SECTION_NR_TO_ROOT(sec)	((sec) >> SECTION_ROOT_SHIFT)
 #define NR_SECTION_ROOTS	DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)
 #define SECTION_ROOT_MASK	(SECTIONS_PER_ROOT - 1)
 
Signature · 1 line
2.20.1
#1 lore raw
Quoted 8 lines · Guo Hui

In the function __nr_to_section,
Use shift operation instead of division operation in order to improve the performance of memory management. There are no functional changes.

Some performance data is as follows:
Machine configuration: Hygon 128 cores, 256M memory

Quoted 6 lines

Stream single core:

           with patch       without patch       promote
Copy       23376.7731       23907.1532          -1.27%
Scale      12580.2913       11679.7852          +7.71%
Add        11922.9562       11461.8669          +4.02%
Triad      12549.2735       11491.9798          +9.20%

How stable are these numbers? Because this patch makes no sense to me.

#define SECTION_NR_TO_ROOT(sec) ((sec) / SECTIONS_PER_ROOT)

with:

#ifdef CONFIG_SPARSEMEM_EXTREME
#define SECTIONS_PER_ROOT (PAGE_SIZE / sizeof (struct mem_section))
#else
#define SECTIONS_PER_ROOT 1
#endif

sizeof(struct mem_section) is a constant power-of-two. So if this result is real, then GCC isn't able to turn a divide-by-a-constant-power-of-two into a shift. That seems _really_ unlikely to me. And if that is what's going on, then that needs to be fixed! Can you examine some before-and-after assembly dumps to see if that is what's going on?

Quoted 23 lines
---
 include/linux/mmzone.h | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
include/linux/mmzone.h +2 -1
index 5e50b78d58ea..8dde6fb56109 100644
@@ -1818,7 +1818,8 @@ struct mem_section {
 #define SECTIONS_PER_ROOT	1
 #endif
 
-#define SECTION_NR_TO_ROOT(sec)	((sec) / SECTIONS_PER_ROOT)
+#define SECTION_ROOT_SHIFT        (__builtin_popcount(SECTIONS_PER_ROOT - 1))
+#define SECTION_NR_TO_ROOT(sec)	((sec) >> SECTION_ROOT_SHIFT)
 #define NR_SECTION_ROOTS	DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)
 #define SECTION_ROOT_MASK	(SECTIONS_PER_ROOT - 1)
 
Signature · 1 line
2.20.1
author
#2 lore raw
Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Guo Hui

In the function __nr_to_section,
Use shift operation instead of division operation in order to improve the performance of memory management. There are no functional changes.

Some performance data is as follows:
Machine configuration: Hygon 128 cores, 256M memory

Quoted 7 lines
Quoted 6 lines

Stream single core:
with patch without patch promote

Copy       23376.7731       23907.1532          -1.27%
Scale      12580.2913       11679.7852          +7.71%
Add        11922.9562       11461.8669          +4.02%
Triad      12549.2735       11491.9798          +9.20%

How stable are these numbers? Because this patch makes no sense to me.

Thank you for your reply.

The increase is not stable, between 4% and 7%.

Quoted 11 lines

#define SECTION_NR_TO_ROOT(sec) ((sec) / SECTIONS_PER_ROOT)

with:

#ifdef CONFIG_SPARSEMEM_EXTREME
#define SECTIONS_PER_ROOT (PAGE_SIZE / sizeof (struct mem_section))
#else
#define SECTIONS_PER_ROOT 1
#endif

Quoted 6 lines

sizeof(struct mem_section) is a constant power-of-two. So if this result is real, then GCC isn't able to turn a divide-by-a-constant-power-of-two into a shift. That seems _really_ unlikely to me. And if that is what's going on, then that needs to be fixed! Can you examine some before-and-after assembly dumps to see if that is what's going on?

Thank you for your guide.

I have done an assembly code analysis on the use of __nr_to_section in the function online_mem_sections, as follows:

ffffffff81383580 <online_mem_sections>:
{
... ...
        return pfn >> PFN_SECTION_SHIFT;
ffffffff8138359d:       48 89 f8                mov    %rdi,%rax
        unsigned long root = SECTION_NR_TO_ROOT(nr);
ffffffff813835a0:       48 89 f9                mov    %rdi,%rcx
        return pfn >> PFN_SECTION_SHIFT;
ffffffff813835a3:       48 c1 e8 0f             shr    $0xf,%rax
        unsigned long root = SECTION_NR_TO_ROOT(nr);
ffffffff813835a7:       48 c1 e9 16             shr $0x16,%rcx               -----------------------------  A ffffffff813835ab:       e9 38 ea d5 01          jmpq ffffffff830e1fe8 <_einittext+0x2a78>

In code line A, the compiler can automatically convert the division into a shift operation. My patch has the same effect, so it is unnecessary to use my patch, so the improvement of Stream above may come from other reasons, and I will continue to go deeper analyze this improvement.

My intention is to use the function __builtin_popcount to calculate the number of 1s in (SECTIONS_PER_ROOT - 1) at compile time, which is the offset number of section_nr.

Quoted 24 lines
Quoted 24 lines
---
  include/linux/mmzone.h | 3 ++-
  1 file changed, 2 insertions(+), 1 deletion(-)
include/linux/mmzone.h +2 -1
index 5e50b78d58ea..8dde6fb56109 100644
@@ -1818,7 +1818,8 @@ struct mem_section {
  #define SECTIONS_PER_ROOT	1
  #endif
 
-#define SECTION_NR_TO_ROOT(sec)	((sec) / SECTIONS_PER_ROOT)
+#define SECTION_ROOT_SHIFT        (__builtin_popcount(SECTIONS_PER_ROOT - 1))
+#define SECTION_NR_TO_ROOT(sec)	((sec) >> SECTION_ROOT_SHIFT)
  #define NR_SECTION_ROOTS	DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)
  #define SECTION_ROOT_MASK	(SECTIONS_PER_ROOT - 1)
 
Signature · 1 line
2.20.1