[RFC PATCH 1/2] mm/memblock: introduce for_each_mem_pfn_range_rev()

[RFC PATCH 1/2] mm/memblock: introduce for_each_mem_pfn_range_rev()

[Wei Yang]

This patch introduces the helper function for_each_mem_pfn_range_rev() for
later use.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 include/linux/memblock.h | 18 ++++++++++++++++++
 mm/memblock.c            | 39 ++++++++++++++++++++++++++++++++++++++-
 2 files changed, 56 insertions(+), 1 deletion(-)

diff --git a/include/linux/memblock.h b/include/linux/memblock.h
index 5b759c9acf97..87a0ebe18606 100644
--- a/include/linux/memblock.h
+++ b/include/linux/memblock.h
@@ -203,6 +203,8 @@ int memblock_search_pfn_nid(unsigned long pfn, unsigned long *start_pfn,
 			    unsigned long  *end_pfn);
 void __next_mem_pfn_range(int *idx, int nid, unsigned long *out_start_pfn,
 			  unsigned long *out_end_pfn, int *out_nid);
+void __next_mem_pfn_range_rev(int *idx, int nid, unsigned long *out_start_pfn,
+			  unsigned long *out_end_pfn, int *out_nid);
 
 /**
  * for_each_mem_pfn_range - early memory pfn range iterator
@@ -217,6 +219,22 @@ void __next_mem_pfn_range(int *idx, int nid, unsigned long *out_start_pfn,
 #define for_each_mem_pfn_range(i, nid, p_start, p_end, p_nid)		\
 	for (i = -1, __next_mem_pfn_range(&i, nid, p_start, p_end, p_nid); \
 	     i >= 0; __next_mem_pfn_range(&i, nid, p_start, p_end, p_nid))
+
+/**
+ * for_each_mem_pfn_range_rev - early memory pfn range rev-iterator
+ * @i: an integer used as loop variable
+ * @nid: node selector, %NUMA_NO_NODE for all nodes
+ * @p_start: ptr to ulong for start pfn of the range, can be %NULL
+ * @p_end: ptr to ulong for end pfn of the range, can be %NULL
+ * @p_nid: ptr to int for nid of the range, can be %NULL
+ *
+ * Walks over configured memory ranges in reverse order.
+ */
+#define for_each_mem_pfn_range_rev(i, nid, p_start, p_end, p_nid)	\
+	for (i = (int)INT_MAX,						\
+	      __next_mem_pfn_range_rev(&i, nid, p_start, p_end, p_nid); \
+	     i != (int)INT_MAX;						\
+	      __next_mem_pfn_range_rev(&i, nid, p_start, p_end, p_nid))
 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
 
 /**
diff --git a/mm/memblock.c b/mm/memblock.c
index 7608bc305936..79490005ecd6 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -1075,7 +1075,7 @@ void __init_memblock __next_mem_range_rev(u64 *idx, int nid, ulong flags,
 
 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
 /*
- * Common iterator interface used to define for_each_mem_range().
+ * Common iterator interface used to define for_each_mem_pfn_range().
  */
 void __init_memblock __next_mem_pfn_range(int *idx, int nid,
 				unsigned long *out_start_pfn,
@@ -1105,6 +1105,43 @@ void __init_memblock __next_mem_pfn_range(int *idx, int nid,
 		*out_nid = r->nid;
 }
 
+/*
+ * Common rev-iterator interface used to define for_each_mem_pfn_range_rev().
+ */
+void __init_memblock __next_mem_pfn_range_rev(int *idx, int nid,
+				unsigned long *out_start_pfn,
+				unsigned long *out_end_pfn, int *out_nid)
+{
+	struct memblock_type *type = &memblock.memory;
+	struct memblock_region *r;
+
+	if (WARN_ONCE(nid == MAX_NUMNODES, "Usage of MAX_NUMNODES is deprecated. Use NUMA_NO_NODE instead\n"))
+		nid = NUMA_NO_NODE;
+
+	if (*idx == (int)INT_MAX)
+		*idx = type->cnt;
+
+	while (--*idx >= 0) {
+		r = &type->regions[*idx];
+
+		if (PFN_UP(r->base) >= PFN_DOWN(r->base + r->size))
+			continue;
+		if (nid == NUMA_NO_NODE || nid == r->nid)
+			break;
+	}
+	if (*idx < 0) {
+		*idx = (int)INT_MAX;
+		return;
+	}
+
+	if (out_start_pfn)
+		*out_start_pfn = PFN_UP(r->base);
+	if (out_end_pfn)
+		*out_end_pfn = PFN_DOWN(r->base + r->size);
+	if (out_nid)
+		*out_nid = r->nid;
+}
+
 /**
  * memblock_set_node - set node ID on memblock regions
  * @base: base of area to set node ID for
-- 
2.11.0

[RFC PATCH 1/2] mm/memblock: introduce for_each_mem_pfn_range_rev()

[Wei Yang]

This patch introduces the helper function for_each_mem_pfn_range_rev() for
later use.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 include/linux/memblock.h | 18 ++++++++++++++++++
 mm/memblock.c            | 39 ++++++++++++++++++++++++++++++++++++++-
 2 files changed, 56 insertions(+), 1 deletion(-)

diff --git a/include/linux/memblock.h b/include/linux/memblock.h
index 5b759c9acf97..87a0ebe18606 100644
--- a/include/linux/memblock.h
+++ b/include/linux/memblock.h
@@ -203,6 +203,8 @@ int memblock_search_pfn_nid(unsigned long pfn, unsigned long *start_pfn,
 			    unsigned long  *end_pfn);
 void __next_mem_pfn_range(int *idx, int nid, unsigned long *out_start_pfn,
 			  unsigned long *out_end_pfn, int *out_nid);
+void __next_mem_pfn_range_rev(int *idx, int nid, unsigned long *out_start_pfn,
+			  unsigned long *out_end_pfn, int *out_nid);
 
 /**
  * for_each_mem_pfn_range - early memory pfn range iterator
@@ -217,6 +219,22 @@ void __next_mem_pfn_range(int *idx, int nid, unsigned long *out_start_pfn,
 #define for_each_mem_pfn_range(i, nid, p_start, p_end, p_nid)		\
 	for (i = -1, __next_mem_pfn_range(&i, nid, p_start, p_end, p_nid); \
 	     i >= 0; __next_mem_pfn_range(&i, nid, p_start, p_end, p_nid))
+
+/**
+ * for_each_mem_pfn_range_rev - early memory pfn range rev-iterator
+ * @i: an integer used as loop variable
+ * @nid: node selector, %NUMA_NO_NODE for all nodes
+ * @p_start: ptr to ulong for start pfn of the range, can be %NULL
+ * @p_end: ptr to ulong for end pfn of the range, can be %NULL
+ * @p_nid: ptr to int for nid of the range, can be %NULL
+ *
+ * Walks over configured memory ranges in reverse order.
+ */
+#define for_each_mem_pfn_range_rev(i, nid, p_start, p_end, p_nid)	\
+	for (i = (int)INT_MAX,						\
+	      __next_mem_pfn_range_rev(&i, nid, p_start, p_end, p_nid); \
+	     i != (int)INT_MAX;						\
+	      __next_mem_pfn_range_rev(&i, nid, p_start, p_end, p_nid))
 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
 
 /**
diff --git a/mm/memblock.c b/mm/memblock.c
index 7608bc305936..79490005ecd6 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -1075,7 +1075,7 @@ void __init_memblock __next_mem_range_rev(u64 *idx, int nid, ulong flags,
 
 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
 /*
- * Common iterator interface used to define for_each_mem_range().
+ * Common iterator interface used to define for_each_mem_pfn_range().
  */
 void __init_memblock __next_mem_pfn_range(int *idx, int nid,
 				unsigned long *out_start_pfn,
@@ -1105,6 +1105,43 @@ void __init_memblock __next_mem_pfn_range(int *idx, int nid,
 		*out_nid = r->nid;
 }
 
+/*
+ * Common rev-iterator interface used to define for_each_mem_pfn_range_rev().
+ */
+void __init_memblock __next_mem_pfn_range_rev(int *idx, int nid,
+				unsigned long *out_start_pfn,
+				unsigned long *out_end_pfn, int *out_nid)
+{
+	struct memblock_type *type = &memblock.memory;
+	struct memblock_region *r;
+
+	if (WARN_ONCE(nid == MAX_NUMNODES, "Usage of MAX_NUMNODES is deprecated. Use NUMA_NO_NODE instead\n"))
+		nid = NUMA_NO_NODE;
+
+	if (*idx == (int)INT_MAX)
+		*idx = type->cnt;
+
+	while (--*idx >= 0) {
+		r = &type->regions[*idx];
+
+		if (PFN_UP(r->base) >= PFN_DOWN(r->base + r->size))
+			continue;
+		if (nid == NUMA_NO_NODE || nid == r->nid)
+			break;
+	}
+	if (*idx < 0) {
+		*idx = (int)INT_MAX;
+		return;
+	}
+
+	if (out_start_pfn)
+		*out_start_pfn = PFN_UP(r->base);
+	if (out_end_pfn)
+		*out_end_pfn = PFN_DOWN(r->base + r->size);
+	if (out_nid)
+		*out_nid = r->nid;
+}
+
 /**
  * memblock_set_node - set node ID on memblock regions
  * @base: base of area to set node ID for
-- 
2.11.0

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Wei Yang]

During the sparse_init(), it iterate on each possible section. On x86_64,
it would always be (2^19) even there is not much memory. For example, on a
typical 4G machine, it has only (2^5) to (2^6) present sections. This
benefits more on a system with smaller memory.

This patch calculates the last section number from the highest pfn and use
this as the boundary of iteration.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 mm/sparse.c | 32 +++++++++++++++++++++-----------
 1 file changed, 21 insertions(+), 11 deletions(-)

diff --git a/mm/sparse.c b/mm/sparse.c
index 1e168bf2779a..d72f390d9e61 100644
--- a/mm/sparse.c
+++ b/mm/sparse.c
@@ -468,18 +468,20 @@ void __weak __meminit vmemmap_populate_print_last(void)
 
 /**
  *  alloc_usemap_and_memmap - memory alloction for pageblock flags and vmemmap
- *  @map: usemap_map for pageblock flags or mmap_map for vmemmap
+ *  @data: usemap_map for pageblock flags or mmap_map for vmemmap
  */
 static void __init alloc_usemap_and_memmap(void (*alloc_func)
 					(void *, unsigned long, unsigned long,
-					unsigned long, int), void *data)
+					unsigned long, int),
+					void *data,
+					unsigned long last_section_nr)
 {
 	unsigned long pnum;
 	unsigned long map_count;
 	int nodeid_begin = 0;
 	unsigned long pnum_begin = 0;
 
-	for (pnum = 0; pnum < NR_MEM_SECTIONS; pnum++) {
+	for (pnum = 0; pnum <= last_section_nr; pnum++) {
 		struct mem_section *ms;
 
 		if (!present_section_nr(pnum))
@@ -490,7 +492,7 @@ static void __init alloc_usemap_and_memmap(void (*alloc_func)
 		break;
 	}
 	map_count = 1;
-	for (pnum = pnum_begin + 1; pnum < NR_MEM_SECTIONS; pnum++) {
+	for (pnum = pnum_begin + 1; pnum <= last_section_nr; pnum++) {
 		struct mem_section *ms;
 		int nodeid;
 
@@ -503,16 +505,14 @@ static void __init alloc_usemap_and_memmap(void (*alloc_func)
 			continue;
 		}
 		/* ok, we need to take cake of from pnum_begin to pnum - 1*/
-		alloc_func(data, pnum_begin, pnum,
-						map_count, nodeid_begin);
+		alloc_func(data, pnum_begin, pnum, map_count, nodeid_begin);
 		/* new start, update count etc*/
 		nodeid_begin = nodeid;
 		pnum_begin = pnum;
 		map_count = 1;
 	}
 	/* ok, last chunk */
-	alloc_func(data, pnum_begin, NR_MEM_SECTIONS,
-						map_count, nodeid_begin);
+	alloc_func(data, pnum_begin, pnum, map_count, nodeid_begin);
 }
 
 /*
@@ -526,6 +526,9 @@ void __init sparse_init(void)
 	unsigned long *usemap;
 	unsigned long **usemap_map;
 	int size;
+	unsigned long last_section_nr;
+	int i;
+	unsigned long last_pfn = 0;
 #ifdef CONFIG_SPARSEMEM_ALLOC_MEM_MAP_TOGETHER
 	int size2;
 	struct page **map_map;
@@ -537,6 +540,11 @@ void __init sparse_init(void)
 	/* Setup pageblock_order for HUGETLB_PAGE_SIZE_VARIABLE */
 	set_pageblock_order();
 
+	for_each_mem_pfn_range_rev(i, NUMA_NO_NODE, NULL,
+				&last_pfn, NULL)
+		break;
+	last_section_nr = pfn_to_section_nr(last_pfn);
+
 	/*
 	 * map is using big page (aka 2M in x86 64 bit)
 	 * usemap is less one page (aka 24 bytes)
@@ -553,7 +561,8 @@ void __init sparse_init(void)
 	if (!usemap_map)
 		panic("can not allocate usemap_map\n");
 	alloc_usemap_and_memmap(sparse_early_usemaps_alloc_node,
-							(void *)usemap_map);
+				(void *)usemap_map,
+				last_section_nr);
 
 #ifdef CONFIG_SPARSEMEM_ALLOC_MEM_MAP_TOGETHER
 	size2 = sizeof(struct page *) * NR_MEM_SECTIONS;
@@ -561,10 +570,11 @@ void __init sparse_init(void)
 	if (!map_map)
 		panic("can not allocate map_map\n");
 	alloc_usemap_and_memmap(sparse_early_mem_maps_alloc_node,
-							(void *)map_map);
+				(void *)map_map,
+				last_section_nr);
 #endif
 
-	for (pnum = 0; pnum < NR_MEM_SECTIONS; pnum++) {
+	for (pnum = 0; pnum <= last_section_nr; pnum++) {
 		if (!present_section_nr(pnum))
 			continue;
 
-- 
2.11.0

[RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Wei Yang]

During the sparse_init(), it iterate on each possible section. On x86_64,
it would always be (2^19) even there is not much memory. For example, on a
typical 4G machine, it has only (2^5) to (2^6) present sections. This
benefits more on a system with smaller memory.

This patch calculates the last section number from the highest pfn and use
this as the boundary of iteration.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 mm/sparse.c | 32 +++++++++++++++++++++-----------
 1 file changed, 21 insertions(+), 11 deletions(-)

diff --git a/mm/sparse.c b/mm/sparse.c
index 1e168bf2779a..d72f390d9e61 100644
--- a/mm/sparse.c
+++ b/mm/sparse.c
@@ -468,18 +468,20 @@ void __weak __meminit vmemmap_populate_print_last(void)
 
 /**
  *  alloc_usemap_and_memmap - memory alloction for pageblock flags and vmemmap
- *  @map: usemap_map for pageblock flags or mmap_map for vmemmap
+ *  @data: usemap_map for pageblock flags or mmap_map for vmemmap
  */
 static void __init alloc_usemap_and_memmap(void (*alloc_func)
 					(void *, unsigned long, unsigned long,
-					unsigned long, int), void *data)
+					unsigned long, int),
+					void *data,
+					unsigned long last_section_nr)
 {
 	unsigned long pnum;
 	unsigned long map_count;
 	int nodeid_begin = 0;
 	unsigned long pnum_begin = 0;
 
-	for (pnum = 0; pnum < NR_MEM_SECTIONS; pnum++) {
+	for (pnum = 0; pnum <= last_section_nr; pnum++) {
 		struct mem_section *ms;
 
 		if (!present_section_nr(pnum))
@@ -490,7 +492,7 @@ static void __init alloc_usemap_and_memmap(void (*alloc_func)
 		break;
 	}
 	map_count = 1;
-	for (pnum = pnum_begin + 1; pnum < NR_MEM_SECTIONS; pnum++) {
+	for (pnum = pnum_begin + 1; pnum <= last_section_nr; pnum++) {
 		struct mem_section *ms;
 		int nodeid;
 
@@ -503,16 +505,14 @@ static void __init alloc_usemap_and_memmap(void (*alloc_func)
 			continue;
 		}
 		/* ok, we need to take cake of from pnum_begin to pnum - 1*/
-		alloc_func(data, pnum_begin, pnum,
-						map_count, nodeid_begin);
+		alloc_func(data, pnum_begin, pnum, map_count, nodeid_begin);
 		/* new start, update count etc*/
 		nodeid_begin = nodeid;
 		pnum_begin = pnum;
 		map_count = 1;
 	}
 	/* ok, last chunk */
-	alloc_func(data, pnum_begin, NR_MEM_SECTIONS,
-						map_count, nodeid_begin);
+	alloc_func(data, pnum_begin, pnum, map_count, nodeid_begin);
 }
 
 /*
@@ -526,6 +526,9 @@ void __init sparse_init(void)
 	unsigned long *usemap;
 	unsigned long **usemap_map;
 	int size;
+	unsigned long last_section_nr;
+	int i;
+	unsigned long last_pfn = 0;
 #ifdef CONFIG_SPARSEMEM_ALLOC_MEM_MAP_TOGETHER
 	int size2;
 	struct page **map_map;
@@ -537,6 +540,11 @@ void __init sparse_init(void)
 	/* Setup pageblock_order for HUGETLB_PAGE_SIZE_VARIABLE */
 	set_pageblock_order();
 
+	for_each_mem_pfn_range_rev(i, NUMA_NO_NODE, NULL,
+				&last_pfn, NULL)
+		break;
+	last_section_nr = pfn_to_section_nr(last_pfn);
+
 	/*
 	 * map is using big page (aka 2M in x86 64 bit)
 	 * usemap is less one page (aka 24 bytes)
@@ -553,7 +561,8 @@ void __init sparse_init(void)
 	if (!usemap_map)
 		panic("can not allocate usemap_map\n");
 	alloc_usemap_and_memmap(sparse_early_usemaps_alloc_node,
-							(void *)usemap_map);
+				(void *)usemap_map,
+				last_section_nr);
 
 #ifdef CONFIG_SPARSEMEM_ALLOC_MEM_MAP_TOGETHER
 	size2 = sizeof(struct page *) * NR_MEM_SECTIONS;
@@ -561,10 +570,11 @@ void __init sparse_init(void)
 	if (!map_map)
 		panic("can not allocate map_map\n");
 	alloc_usemap_and_memmap(sparse_early_mem_maps_alloc_node,
-							(void *)map_map);
+				(void *)map_map,
+				last_section_nr);
 #endif
 
-	for (pnum = 0; pnum < NR_MEM_SECTIONS; pnum++) {
+	for (pnum = 0; pnum <= last_section_nr; pnum++) {
 		if (!present_section_nr(pnum))
 			continue;
 
-- 
2.11.0

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Tejun Heo]

Hello,

On Sat, Feb 11, 2017 at 10:18:29AM +0800, Wei Yang wrote:
> During the sparse_init(), it iterate on each possible section. On x86_64,
> it would always be (2^19) even there is not much memory. For example, on a
> typical 4G machine, it has only (2^5) to (2^6) present sections. This
> benefits more on a system with smaller memory.
> 
> This patch calculates the last section number from the highest pfn and use
> this as the boundary of iteration.

* How much does this actually matter?  Can you measure the impact?

* Do we really need to add full reverse iterator to just get the
  highest section number?

Thanks.

-- 
tejun

Re: [RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Tejun Heo]

Hello,

On Sat, Feb 11, 2017 at 10:18:29AM +0800, Wei Yang wrote:
> During the sparse_init(), it iterate on each possible section. On x86_64,
> it would always be (2^19) even there is not much memory. For example, on a
> typical 4G machine, it has only (2^5) to (2^6) present sections. This
> benefits more on a system with smaller memory.
> 
> This patch calculates the last section number from the highest pfn and use
> this as the boundary of iteration.

* How much does this actually matter?  Can you measure the impact?

* Do we really need to add full reverse iterator to just get the
  highest section number?

Thanks.

-- 
tejun

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Wei Yang]

On Sat, Feb 11, 2017 at 10:24 AM, Tejun Heo <tj@kernel.org> wrote:
>
> Hello,
>

Hi, Tejun

Sorry for the delay, my gmail client seems to facing some problem.
I can't see latest mails. So I have to use the web client and reply.

> On Sat, Feb 11, 2017 at 10:18:29AM +0800, Wei Yang wrote:
> > During the sparse_init(), it iterate on each possible section. On x86_64,
> > it would always be (2^19) even there is not much memory. For example, on a
> > typical 4G machine, it has only (2^5) to (2^6) present sections. This
> > benefits more on a system with smaller memory.
> >
> > This patch calculates the last section number from the highest pfn and use
> > this as the boundary of iteration.
>
> * How much does this actually matter?  Can you measure the impact?
>

Hmm, I tried to print the "jiffies", while it is not ready at that moment. So
I mimic the behavior in user space.

I used following code for test.

#include <stdio.h>
#include <stdlib.h>

int array[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

int main()
{
unsigned long i;
int val;

    for (i = 0; i < (1UL << 5); i++)
        val += array[i%10];
    for (i = 0; i < (1UL << 5); i++)
        val += array[i%10];
    for (i = 0; i < (1UL << 5); i++)
        val += array[i%10];

    //printf("%lx %d\n", i, val);

    return 0;
}

And compare the ruling with the iteration for the loop to be (1UL <<
5) and (1UL << 19).
The runtime is 0.00s and 0.04s respectively. The absolute value is not much.

> * Do we really need to add full reverse iterator to just get the
>   highest section number?
>

You are right. After I sent out the mail, I realized just highest pfn
is necessary.

> Thanks.
>
> --
> tejun

Re: [RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Wei Yang]

On Sat, Feb 11, 2017 at 10:24 AM, Tejun Heo <tj@kernel.org> wrote:
>
> Hello,
>

Hi, Tejun

Sorry for the delay, my gmail client seems to facing some problem.
I can't see latest mails. So I have to use the web client and reply.

> On Sat, Feb 11, 2017 at 10:18:29AM +0800, Wei Yang wrote:
> > During the sparse_init(), it iterate on each possible section. On x86_64,
> > it would always be (2^19) even there is not much memory. For example, on a
> > typical 4G machine, it has only (2^5) to (2^6) present sections. This
> > benefits more on a system with smaller memory.
> >
> > This patch calculates the last section number from the highest pfn and use
> > this as the boundary of iteration.
>
> * How much does this actually matter?  Can you measure the impact?
>

Hmm, I tried to print the "jiffies", while it is not ready at that moment. So
I mimic the behavior in user space.

I used following code for test.

#include <stdio.h>
#include <stdlib.h>

int array[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

int main()
{
unsigned long i;
int val;

    for (i = 0; i < (1UL << 5); i++)
        val += array[i%10];
    for (i = 0; i < (1UL << 5); i++)
        val += array[i%10];
    for (i = 0; i < (1UL << 5); i++)
        val += array[i%10];

    //printf("%lx %d\n", i, val);

    return 0;
}

And compare the ruling with the iteration for the loop to be (1UL <<
5) and (1UL << 19).
The runtime is 0.00s and 0.04s respectively. The absolute value is not much.

> * Do we really need to add full reverse iterator to just get the
>   highest section number?
>

You are right. After I sent out the mail, I realized just highest pfn
is necessary.

> Thanks.
>
> --
> tejun

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Wei Yang]

On Mon, Feb 13, 2017 at 9:03 PM, Wei Yang <richard.weiyang@gmail.com> wrote:
> On Sat, Feb 11, 2017 at 10:24 AM, Tejun Heo <tj@kernel.org> wrote:
>>
>> Hello,
>>
>
> Hi, Tejun
>
> Sorry for the delay, my gmail client seems to facing some problem.
> I can't see latest mails. So I have to use the web client and reply.
>
>> On Sat, Feb 11, 2017 at 10:18:29AM +0800, Wei Yang wrote:
>> > During the sparse_init(), it iterate on each possible section. On x86_64,
>> > it would always be (2^19) even there is not much memory. For example, on a
>> > typical 4G machine, it has only (2^5) to (2^6) present sections. This
>> > benefits more on a system with smaller memory.
>> >
>> > This patch calculates the last section number from the highest pfn and use
>> > this as the boundary of iteration.
>>
>> * How much does this actually matter?  Can you measure the impact?
>>
>
> Hmm, I tried to print the "jiffies", while it is not ready at that moment. So
> I mimic the behavior in user space.
>
> I used following code for test.
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int array[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
>
> int main()
> {
> unsigned long i;
> int val;
>
>     for (i = 0; i < (1UL << 5); i++)
>         val += array[i%10];
>     for (i = 0; i < (1UL << 5); i++)
>         val += array[i%10];
>     for (i = 0; i < (1UL << 5); i++)
>         val += array[i%10];
>
>     //printf("%lx %d\n", i, val);
>
>     return 0;
> }
>
> And compare the ruling with the iteration for the loop to be (1UL <<
> 5) and (1UL << 19).
> The runtime is 0.00s and 0.04s respectively. The absolute value is not much.
>

Hi, Tejun

What's your opinion on this change?

>> * Do we really need to add full reverse iterator to just get the
>>   highest section number?
>>
>
> You are right. After I sent out the mail, I realized just highest pfn
> is necessary.
>
>> Thanks.
>>
>> --
>> tejun

Re: [RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Wei Yang]

On Mon, Feb 13, 2017 at 9:03 PM, Wei Yang <richard.weiyang@gmail.com> wrote:
> On Sat, Feb 11, 2017 at 10:24 AM, Tejun Heo <tj@kernel.org> wrote:
>>
>> Hello,
>>
>
> Hi, Tejun
>
> Sorry for the delay, my gmail client seems to facing some problem.
> I can't see latest mails. So I have to use the web client and reply.
>
>> On Sat, Feb 11, 2017 at 10:18:29AM +0800, Wei Yang wrote:
>> > During the sparse_init(), it iterate on each possible section. On x86_64,
>> > it would always be (2^19) even there is not much memory. For example, on a
>> > typical 4G machine, it has only (2^5) to (2^6) present sections. This
>> > benefits more on a system with smaller memory.
>> >
>> > This patch calculates the last section number from the highest pfn and use
>> > this as the boundary of iteration.
>>
>> * How much does this actually matter?  Can you measure the impact?
>>
>
> Hmm, I tried to print the "jiffies", while it is not ready at that moment. So
> I mimic the behavior in user space.
>
> I used following code for test.
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int array[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
>
> int main()
> {
> unsigned long i;
> int val;
>
>     for (i = 0; i < (1UL << 5); i++)
>         val += array[i%10];
>     for (i = 0; i < (1UL << 5); i++)
>         val += array[i%10];
>     for (i = 0; i < (1UL << 5); i++)
>         val += array[i%10];
>
>     //printf("%lx %d\n", i, val);
>
>     return 0;
> }
>
> And compare the ruling with the iteration for the loop to be (1UL <<
> 5) and (1UL << 19).
> The runtime is 0.00s and 0.04s respectively. The absolute value is not much.
>

Hi, Tejun

What's your opinion on this change?

>> * Do we really need to add full reverse iterator to just get the
>>   highest section number?
>>
>
> You are right. After I sent out the mail, I realized just highest pfn
> is necessary.
>
>> Thanks.
>>
>> --
>> tejun

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Tejun Heo]

Hello, Wei.

On Fri, Feb 17, 2017 at 10:12:31PM +0800, Wei Yang wrote:
> > And compare the ruling with the iteration for the loop to be (1UL <<
> > 5) and (1UL << 19).
> > The runtime is 0.00s and 0.04s respectively. The absolute value is not much.

systemd-analyze usually does a pretty good job of breaking down which
phase took how long.  It might be worthwhile to test whether the
improvement is actually visible during the boot.

> >> * Do we really need to add full reverse iterator to just get the
> >>   highest section number?
> >>
> >
> > You are right. After I sent out the mail, I realized just highest pfn
> > is necessary.

That said, getting efficient is always great as long as the added
complexity is justifiably small enough.  If you can make the change
simple enough, it'd be a lot easier to merge.

Thanks.

-- 
tejun

Re: [RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Tejun Heo]

Hello, Wei.

On Fri, Feb 17, 2017 at 10:12:31PM +0800, Wei Yang wrote:
> > And compare the ruling with the iteration for the loop to be (1UL <<
> > 5) and (1UL << 19).
> > The runtime is 0.00s and 0.04s respectively. The absolute value is not much.

systemd-analyze usually does a pretty good job of breaking down which
phase took how long.  It might be worthwhile to test whether the
improvement is actually visible during the boot.

> >> * Do we really need to add full reverse iterator to just get the
> >>   highest section number?
> >>
> >
> > You are right. After I sent out the mail, I realized just highest pfn
> > is necessary.

That said, getting efficient is always great as long as the added
complexity is justifiably small enough.  If you can make the change
simple enough, it'd be a lot easier to merge.

Thanks.

-- 
tejun

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC PATCH 2/2] mm/sparse: add last_section_nr in sparse_init() to reduce some iteration cycle

[Wei Yang]

[-- Attachment #1: Type: text/plain, Size: 2282 bytes --]

On Mon, Mar 06, 2017 at 02:42:25PM -0500, Tejun Heo wrote:
>Hello, Wei.
>
>On Fri, Feb 17, 2017 at 10:12:31PM +0800, Wei Yang wrote:
>> > And compare the ruling with the iteration for the loop to be (1UL <<
>> > 5) and (1UL << 19).
>> > The runtime is 0.00s and 0.04s respectively. The absolute value is not much.
>
>systemd-analyze usually does a pretty good job of breaking down which
>phase took how long.  It might be worthwhile to test whether the
>improvement is actually visible during the boot.
>

Hi, Tejun

Thanks for your suggestion. I have tried systemd-analyze to measure the
effect, while looks not good.

Result without patch
-------------------------
Startup finished in 7.243s (kernel) + 25.034s (userspace) = 32.277s
Startup finished in 7.254s (kernel) + 19.816s (userspace) = 27.071s
Startup finished in 7.272s (kernel) + 4.363s (userspace) = 11.636s
Startup finished in 7.258s (kernel) + 24.319s (userspace) = 31.577s
Startup finished in 7.262s (kernel) + 9.481s (userspace) = 16.743s
Startup finished in 7.266s (kernel) + 14.766s (userspace) = 22.032s

Avg = 7.259s

Result with patch
-------------------------
Startup finished in 7.262s (kernel) + 14.294s (userspace) = 21.557s
Startup finished in 7.264s (kernel) + 19.519s (userspace) = 26.783s
Startup finished in 7.266s (kernel) + 4.730s (userspace) = 11.997s
Startup finished in 7.258s (kernel) + 9.514s (userspace) = 16.773s
Startup finished in 7.258s (kernel) + 14.371s (userspace) = 21.629s
Startup finished in 7.258s (kernel) + 14.627s (userspace) = 21.885s

Avg = 7.261s

It looks the effect is not obvious. Maybe the improvement is not good
enough :(

>> >> * Do we really need to add full reverse iterator to just get the
>> >>   highest section number?
>> >>
>> >
>> > You are right. After I sent out the mail, I realized just highest pfn
>> > is necessary.
>
>That said, getting efficient is always great as long as the added
>complexity is justifiably small enough.  If you can make the change
>simple enough, it'd be a lot easier to merge.
>

Agree.

I have replaced the reverse iteration with a simple last pfn return. The test
result above is based on the new version.

>Thanks.
>
>-- 
>tejun

-- 
Wei Yang
Help you, Help me

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]