[PATCH 0/7] put struct symbol & friends on diet

[PATCH 0/7] put struct symbol & friends on diet

[Luc Van Oostenryck]

The goal of this series is to decrease sparse's memory consumption
by decreasing the size of some of the structure.

What can be win with these small changes is quite appreciable:
about 30% with some gain in speed too (but this are harder to
put numbers on it, 5% or a bit more seems quite common for
big files).

It should be noted that those gains come almost entirely from
the LIST_NODE_NR change which halves the size of struct ptrlist,
a very heavily used structure.


Luc Van Oostenryck (7):
  use long for all mem stats
  diet: use smaller LIST_NODE_NR (29 -> 13)
  diet: remove unused struct scope::token
  diet: remove unused struct symbol::arg_count
  diet: remove unused struct symbol::value
  diet: squeeze struct symbol's members
  diet: squeeze struct ctype's members

 allocate.c     |  2 +-
 allocate.h     |  3 ++-
 compile-i386.c | 12 ++++++------
 ptrlist.h      |  2 +-
 scope.h        |  1 -
 show-parse.c   |  8 ++++----
 symbol.h       | 12 ++++++------
 7 files changed, 20 insertions(+), 20 deletions(-)

-- 
2.13.0

[PATCH 1/7] use long for all mem stats

[Luc Van Oostenryck]

The 32bit 4G limit is not so easily reached but still
it's easy to flirt with 500M+, even with a moderatly big
program.

Avoid any possible overflow and use unsigned long as
they cost nothing here.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 allocate.c | 2 +-
 allocate.h | 3 ++-
 2 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/allocate.c b/allocate.c
index daa4ac247..0cc556307 100644
--- a/allocate.c
+++ b/allocate.c
@@ -120,7 +120,7 @@ void *allocate(struct allocator_struct *desc, unsigned int size)
 
 void show_allocations(struct allocator_struct *x)
 {
-	fprintf(stderr, "%s: %d allocations, %d bytes (%d total bytes, "
+	fprintf(stderr, "%s: %d allocations, %lu bytes (%lu total bytes, "
 			"%6.2f%% usage, %6.2f average size)\n",
 		x->name, x->allocations, x->useful_bytes, x->total_bytes,
 		100 * (double) x->useful_bytes / x->total_bytes,
diff --git a/allocate.h b/allocate.h
index 64bb6dd64..cbddc2aa7 100644
--- a/allocate.h
+++ b/allocate.h
@@ -14,7 +14,8 @@ struct allocator_struct {
 	unsigned int chunking;
 	void *freelist;
 	/* statistics */
-	unsigned int allocations, total_bytes, useful_bytes;
+	unsigned int allocations;
+	unsigned long total_bytes, useful_bytes;
 };
 
 struct allocator_stats {
-- 
2.13.0

[PATCH 2/7] diet: use smaller LIST_NODE_NR (29 -> 13)

[Luc Van Oostenryck]

Currently the size of the array used for ptrlist is 29.
However, some inspection shows that the mean size of ptrlists
is much smaller: around 2.5 - 5 only. This means that most memory
allocated for ptrlists are never used.

Change this by changing the size to the conservative value of 13.
With this value, on some test programs, memory used for ptrlists
is only 43% - 48% smaller or 24% - 28% for the total memory.
This difference in memory consumption allow also to win some time:
5 - 7% in the conditions used for the test but YMMV.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ptrlist.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/ptrlist.h b/ptrlist.h
index d09be2f51..b605bb858 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -22,7 +22,7 @@
  */
 #define MKTYPE(head,expr)		({ (TYPEOF(head))(expr); })
 
-#define LIST_NODE_NR (29)
+#define LIST_NODE_NR (13)
 
 struct ptr_list {
 	int nr;
-- 
2.13.0

[PATCH 3/7] diet: remove unused struct scope::token

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 scope.h | 1 -
 1 file changed, 1 deletion(-)

diff --git a/scope.h b/scope.h
index 9bbb6757b..d9a14aa34 100644
--- a/scope.h
+++ b/scope.h
@@ -28,7 +28,6 @@
 struct symbol;
 
 struct scope {
-	struct token *token;		/* Scope start information */
 	struct symbol_list *symbols;	/* List of symbols in this scope */
 	struct scope *next;
 };
-- 
2.13.0

[PATCH 4/7] diet: remove unused struct symbol::arg_count

[Luc Van Oostenryck]

It's not used, it's never set and .. it seems has never been used.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 symbol.h | 1 -
 1 file changed, 1 deletion(-)

diff --git a/symbol.h b/symbol.h
index 327449611..ac3fd8bf0 100644
--- a/symbol.h
+++ b/symbol.h
@@ -164,7 +164,6 @@ struct symbol {
 			unsigned long	offset;
 			int		bit_size;
 			unsigned int	bit_offset:8,
-					arg_count:10,
 					variadic:1,
 					initialized:1,
 					examined:1,
-- 
2.13.0

[PATCH 5/7] diet: remove unused struct symbol::value

[Luc Van Oostenryck]

This member seemed to be used for:
- current value of an enum during parsing
- index into the virtual frame
but is currently not used and never set, it's only
displayed in compile-i386 & show_parse (as zero since never
initialized).

Remove it to make struct symbol a bit more light.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 compile-i386.c | 2 +-
 show-parse.c   | 2 +-
 symbol.h       | 1 -
 3 files changed, 2 insertions(+), 3 deletions(-)

diff --git a/compile-i386.c b/compile-i386.c
index 44b72ec39..633d9a476 100644
--- a/compile-i386.c
+++ b/compile-i386.c
@@ -2238,7 +2238,7 @@ static struct storage *x86_symbol_expr(struct symbol *sym)
 		return new;
 	}
 	if (sym->ctype.modifiers & MOD_ADDRESSABLE) {
-		printf("\taddi.%d\t\tv%d,vFP,$%lld\n", bits_in_pointer, new->pseudo, sym->value);
+		printf("\taddi.%d\t\tv%d,vFP,$%lld\n", bits_in_pointer, new->pseudo, 0ULL);
 		return new;
 	}
 	printf("\taddi.%d\t\tv%d,vFP,$offsetof(%s:%p)\n", bits_in_pointer, new->pseudo, show_ident(sym->ident), sym);
diff --git a/show-parse.c b/show-parse.c
index d365d737f..dd7e76fc4 100644
--- a/show-parse.c
+++ b/show-parse.c
@@ -927,7 +927,7 @@ static int show_symbol_expr(struct symbol *sym)
 		return new;
 	}
 	if (sym->ctype.modifiers & MOD_ADDRESSABLE) {
-		printf("\taddi.%d\t\tv%d,vFP,$%lld\n", bits_in_pointer, new, sym->value);
+		printf("\taddi.%d\t\tv%d,vFP,$%lld\n", bits_in_pointer, new, 0ULL);
 		return new;
 	}
 	printf("\taddi.%d\t\tv%d,vFP,$offsetof(%s:%p)\n", bits_in_pointer, new, show_ident(sym->ident), sym);
diff --git a/symbol.h b/symbol.h
index ac3fd8bf0..1bedc75c3 100644
--- a/symbol.h
+++ b/symbol.h
@@ -182,7 +182,6 @@ struct symbol {
 			struct symbol_list *inline_symbol_list;
 			struct expression *initializer;
 			struct entrypoint *ep;
-			long long value;		/* Initial value */
 			struct symbol *definition;
 		};
 	};
-- 
2.13.0

[PATCH 6/7] diet: squeeze struct symbol's members

[Luc Van Oostenryck]

struct symbol::arguments is only used for functions, while
struct symbol::initializer is never used for functions.

Put both of them in an union in order to make the structure
a bit more lightweight.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 symbol.h | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/symbol.h b/symbol.h
index 1bedc75c3..d8733e99f 100644
--- a/symbol.h
+++ b/symbol.h
@@ -175,12 +175,14 @@ struct symbol {
 					transparent_union:1;
 			struct expression *array_size;
 			struct ctype ctype;
-			struct symbol_list *arguments;
 			struct statement *stmt;
+			union {
+				struct symbol_list *arguments;
+				struct expression *initializer;
+			};
 			struct symbol_list *symbol_list;
 			struct statement *inline_stmt;
 			struct symbol_list *inline_symbol_list;
-			struct expression *initializer;
 			struct entrypoint *ep;
 			struct symbol *definition;
 		};
-- 
2.13.0

[PATCH 7/7] diet: squeeze struct ctype's members

[Luc Van Oostenryck]

Using 'int' instead of 'long' for alignment and shuffling
struct ctype's member around avoid any hole in the structure
(on a 64bit machine), making it and struct symbol smaller.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 compile-i386.c | 10 +++++-----
 show-parse.c   |  6 +++---
 symbol.h       |  4 ++--
 3 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/compile-i386.c b/compile-i386.c
index 633d9a476..24e408baa 100644
--- a/compile-i386.c
+++ b/compile-i386.c
@@ -899,13 +899,13 @@ static void emit_func_post(struct symbol *sym)
 
 /* emit object (a.k.a. variable, a.k.a. data) prologue */
 static void emit_object_pre(const char *name, unsigned long modifiers,
-			    unsigned long alignment, unsigned int byte_size)
+			    unsigned int alignment, unsigned int byte_size)
 {
 	if ((modifiers & MOD_STATIC) == 0)
 		printf(".globl %s\n", name);
 	emit_section(".data");
 	if (alignment)
-		printf("\t.align %lu\n", alignment);
+		printf("\t.align %u\n", alignment);
 	printf("\t.type\t%s, @object\n", name);
 	printf("\t.size\t%s, %d\n", name, byte_size);
 	printf("%s:\n", name);
@@ -940,7 +940,7 @@ static void emit_scalar(struct expression *expr, unsigned int bit_size)
 }
 
 static void emit_global_noinit(const char *name, unsigned long modifiers,
-			       unsigned long alignment, unsigned int byte_size)
+			       unsigned int alignment, unsigned int byte_size)
 {
 	char s[64];
 
@@ -949,7 +949,7 @@ static void emit_global_noinit(const char *name, unsigned long modifiers,
 		textbuf_push(&unit_post_text, s);
 	}
 	if (alignment)
-		sprintf(s, "\t.comm\t%s,%d,%lu\n", name, byte_size, alignment);
+		sprintf(s, "\t.comm\t%s,%d,%u\n", name, byte_size, alignment);
 	else
 		sprintf(s, "\t.comm\t%s,%d\n", name, byte_size);
 	textbuf_push(&unit_post_text, s);
@@ -1796,7 +1796,7 @@ static void emit_switch_statement(struct statement *stmt)
 
 static void x86_struct_member(struct symbol *sym)
 {
-	printf("\t%s:%d:%ld at offset %ld.%d", show_ident(sym->ident), sym->bit_size, sym->ctype.alignment, sym->offset, sym->bit_offset);
+	printf("\t%s:%d:%u at offset %ld.%d", show_ident(sym->ident), sym->bit_size, sym->ctype.alignment, sym->offset, sym->bit_offset);
 	printf("\n");
 }
 
diff --git a/show-parse.c b/show-parse.c
index dd7e76fc4..5e3e13165 100644
--- a/show-parse.c
+++ b/show-parse.c
@@ -72,7 +72,7 @@ static void do_debug_symbol(struct symbol *sym, int indent)
 
 	if (!sym)
 		return;
-	fprintf(stderr, "%.*s%s%3d:%lu %s %s (as: %d) %p (%s:%d:%d) %s\n",
+	fprintf(stderr, "%.*s%s%3d:%u %s %s (as: %d) %p (%s:%d:%d) %s\n",
 		indent, indent_string, typestr[sym->type],
 		sym->bit_size, sym->ctype.alignment,
 		modifier_string(sym->ctype.modifiers), show_ident(sym->ident), sym->ctype.as,
@@ -166,7 +166,7 @@ const char *modifier_string(unsigned long mod)
 
 static void show_struct_member(struct symbol *sym)
 {
-	printf("\t%s:%d:%ld at offset %ld.%d", show_ident(sym->ident), sym->bit_size, sym->ctype.alignment, sym->offset, sym->bit_offset);
+	printf("\t%s:%d:%u at offset %ld.%d", show_ident(sym->ident), sym->bit_size, sym->ctype.alignment, sym->offset, sym->bit_offset);
 	printf("\n");
 }
 
@@ -432,7 +432,7 @@ void show_symbol(struct symbol *sym)
 		return;
 
 	if (sym->ctype.alignment)
-		printf(".align %ld\n", sym->ctype.alignment);
+		printf(".align %u\n", sym->ctype.alignment);
 
 	show_type(sym);
 	type = sym->ctype.base_type;
diff --git a/symbol.h b/symbol.h
index d8733e99f..ab3124662 100644
--- a/symbol.h
+++ b/symbol.h
@@ -99,9 +99,9 @@ DECLARE_PTR_LIST(context_list, struct context);
 
 struct ctype {
 	unsigned long modifiers;
-	unsigned long alignment;
-	struct context_list *contexts;
+	unsigned int alignment;
 	unsigned int as;
+	struct context_list *contexts;
 	struct symbol *base_type;
 };
 
-- 
2.13.0

Re: [PATCH 0/7] put struct symbol & friends on diet

[Christopher Li]

On Wed, Jun 28, 2017 at 10:16 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The goal of this series is to decrease sparse's memory consumption
> by decreasing the size of some of the structure.

Do you have that in git repository some where?

Right now I have different review work flow for patches vs git.
Patches will be fetch from patchworks and git from git fetch.
If you are going to do a git pull later on, It would be nice to
provide a git url for the series as well.

Thanks

Chris

Re: [PATCH 0/7] put struct symbol & friends on diet

[Luc Van Oostenryck]

On Thu, Jun 29, 2017 at 03:04:16PM -0700, Christopher Li wrote:
> On Wed, Jun 28, 2017 at 10:16 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > The goal of this series is to decrease sparse's memory consumption
> > by decreasing the size of some of the structure.
> 
> Do you have that in git repository some where?
> 
> Right now I have different review work flow for patches vs git.
> Patches will be fetch from patchworks and git from git fetch.
> If you are going to do a git pull later on, It would be nice to
> provide a git url for the series as well.

Yes, I have.
But for the moment, I was more interested in feedback on conceptual
level. I'll need to consolidate things and then I'll resend things.

-- Luc

Re: [PATCH 0/7] put struct symbol & friends on diet

[Christopher Li]

On Sat, Jul 1, 2017 at 1:45 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Yes, I have.
> But for the moment, I was more interested in feedback on conceptual
> level. I'll need to consolidate things and then I'll resend things.

No problem. I get that you want those patch for review only.
I am only asking git branch because it can save me switch to the
patchwork setup. Some one else might want to try your patches
as well.

No a big deal, I will just fetch from patchworks then.

Chris

Re: [PATCH 0/7] put struct symbol & friends on diet

[Luc Van Oostenryck]

On Sat, Jul 01, 2017 at 12:14:10PM -0700, Christopher Li wrote:
> On Sat, Jul 1, 2017 at 1:45 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Yes, I have.
> > But for the moment, I was more interested in feedback on conceptual
> > level. I'll need to consolidate things and then I'll resend things.
> 
> No problem. I get that you want those patch for review only.
> I am only asking git branch because it can save me switch to the
> patchwork setup. Some one else might want to try your patches
> as well.
> 
> No a big deal, I will just fetch from patchworks then.

Sorry but this WE I hadn't access to my usual setup.

The patches can be found at:
	git://github.com/lucvoo/sparse.git diet-symbol
and
	git://github.com/lucvoo/sparse.git diet-for-stmt


-- Luc

Re: [PATCH 0/7] put struct symbol & friends on diet

[Christopher Li]

On Wed, Jun 28, 2017 at 10:16 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> What can be win with these small changes is quite appreciable:
> about 30% with some gain in speed too (but this are harder to
> put numbers on it, 5% or a bit more seems quite common for
> big files).

I am curious about the performance difference against the full kernel
source check with sparse.
I have some benchmark script build for that with linux "allmodconfig".

My test environment will only do sparse portion of the checking and
save the result
into files. The makefile is non-recursive so it is much faster than
running sparse
from the kernel build. A kernel no change incremental build take about 2m10s.
On my non-recursive makefile for sparse it is only 4 seconds. So  the overhead
of make itself is very light.

Any way, the two run of normal build of RC3:
$ time make -f $PWD/linux-checker.make -j12 -C ../linux name=master
real 2m31.778s
user 18m18.019s
sys 8m19.468s

real 2m29.668s
user 18m12.991s
sys 8m12.728s

two run with LIST_NODE_NR = 13 version of sparse

real 2m27.166s
user 18m3.866s
sys 7m51.140s

real 2m28.089s
user 18m5.966s
sys 7m49.956s

So it is barely able to register a real world difference, consider the
run to run variance is about 2 second as well.

The number for the pure sparse run is about 1.3% difference on
the full kernel allmodconfig build.

Chris

Re: [PATCH 0/7] put struct symbol & friends on diet

[Luc Van Oostenryck]

On Fri, Jun 30, 2017 at 01:13:37AM -0700, Christopher Li wrote:
> On Wed, Jun 28, 2017 at 10:16 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > What can be win with these small changes is quite appreciable:
> > about 30% with some gain in speed too (but this are harder to
> > put numbers on it, 5% or a bit more seems quite common for
> > big files).
> 
> I am curious about the performance difference against the full kernel
> source check with sparse.
> I have some benchmark script build for that with linux "allmodconfig".
> 
> My test environment will only do sparse portion of the checking and
> save the result
> into files. The makefile is non-recursive so it is much faster than
> running sparse
> from the kernel build. A kernel no change incremental build take about 2m10s.
> On my non-recursive makefile for sparse it is only 4 seconds. So  the overhead
> of make itself is very light.
> 
> Any way, the two run of normal build of RC3:
> $ time make -f $PWD/linux-checker.make -j12 -C ../linux name=master
> real 2m31.778s
> user 18m18.019s
> sys 8m19.468s
> 
> real 2m29.668s
> user 18m12.991s
> sys 8m12.728s
> 
> two run with LIST_NODE_NR = 13 version of sparse
> 
> real 2m27.166s
> user 18m3.866s
> sys 7m51.140s
> 
> real 2m28.089s
> user 18m5.966s
> sys 7m49.956s
> 
> So it is barely able to register a real world difference, consider the
> run to run variance is about 2 second as well.
> 
> The number for the pure sparse run is about 1.3% difference on
> the full kernel allmodconfig build.

For the moment, I have no access to the measurements I made. I'll see
what I can do. One of the problem I had with kernel 'build' was that
I wasn't able able to get number stable enough to my taste (typically,
I had a two groups of values, each with a small variance within the
group, but the difference between the groups was like 10%, like you
would heer have a few value around 2m30 and a few ones around 2m45.
Given this, I never bothered to calculate the variance).

Meanwhile, I just looked at your numbers. At first sight, they look
more or less as expected. I'm just surprised that the sys time is so
high: around 45% of the user time (IIRC, in my measurements it was
more like 10%, but I can be wrong).

Looking closer, calculating the mean value of each pair of measures
with the standard deviation in parenthesis, then calculating the
absolute and relative difference, I get:

	  NR = 29		   NR = 13		 delta
real	 150.723 (1.492)	 147.628 (0.653)	 3.096 = 2.1%
user	1095.505 (3.555)	1084.916 (1.485)	10.589 = 1.0%
sys	 496.098 (4.766)	 470.548 (0.837)	25.550 = 5.1%

This look largely non-surprising:
* there is a significative difference in the sys time (where the memory
  allocation cost is)
* a much smaller difference in user time (which I suppose we can credit
  to positive cache effect minus some extra work for lists which are
  bigger than 13).
* all in all, it gives a modest win of 2% in real time (but here the
  difference is only twice the stdvar, so caution with this).

So it would give here 2% for what I consider as 'normal sized files'
compared to the 5% or more I saw for 'big files'.

Of course, the speedup must largely be dependent on the amount of free
memory and how fragmented memory is, in others words: how hard it is
for the kernel to allocate more memory for your process.

-- Luc

Re: [PATCH 0/7] put struct symbol & friends on diet

[Christopher Li]

On Sat, Jul 1, 2017 at 1:39 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> For the moment, I have no access to the measurements I made. I'll see
> what I can do. One of the problem I had with kernel 'build' was that
> I wasn't able able to get number stable enough to my taste (typically,
> I had a two groups of values, each with a small variance within the
> group, but the difference between the groups was like 10%, like you
> would heer have a few value around 2m30 and a few ones around 2m45.
> Given this, I never bothered to calculate the variance).

That is exactly the reason I develop my own test makefile instead of using
kbuild directly.

A python script generate that makefile from the kbuild .*.cmd files.
The kbuild has a lot of extra cost. If I invoke kbuild with two make without
any file change, all file has been cached. The second make still takes a long
time to complete, in terms of minutes.

My sparse test makefile will complete the second null incremental make.
Total 4 seconds with one job. With my scripts, the variance run to run is in
terms of seconds as long as I keep the in cache. Very predictable.

I can share my scripts after I clean it up some how.

>
> Meanwhile, I just looked at your numbers. At first sight, they look
> more or less as expected. I'm just surprised that the sys time is so
> high: around 45% of the user time (IIRC, in my measurements it was
> more like 10%, but I can be wrong).

That is most likely cause by a high job count "-j12". My test machine
has 12 hyper-threaded core total. That is why I pick "-j12".

I can run with some lower job count and see how it goes.

>
> Looking closer, calculating the mean value of each pair of measures
> with the standard deviation in parenthesis, then calculating the
> absolute and relative difference, I get:
>
>           NR = 29                  NR = 13               delta
> real     150.723 (1.492)         147.628 (0.653)         3.096 = 2.1%
> user    1095.505 (3.555)        1084.916 (1.485)        10.589 = 1.0%
> sys      496.098 (4.766)         470.548 (0.837)        25.550 = 5.1%

I assume your test done with normal kernel kbuild.
How many run was that per setup?

>
> This look largely non-surprising:
> * there is a significative difference in the sys time (where the memory
>   allocation cost is)
> * a much smaller difference in user time (which I suppose we can credit
>   to positive cache effect minus some extra work for lists which are
>   bigger than 13).
> * all in all, it gives a modest win of 2% in real time (but here the
>   difference is only twice the stdvar, so caution with this).

Yes, that all make sense.

Keep in mind of the NR change for ptrlist. For any list that is longer than
29 items. The memory wasted by the ptr_node itself will increase.

With NR=29, for long list (list has more than 29 entries). the memory
use by ptr node is 3/32, about 9.4%. Which NR=13, 3/16= 18.8%.
So there is about 9% more memory usage for longer list.
That is some thing we need to keep in mind of.

> Of course, the speedup must largely be dependent on the amount of free
> memory and how fragmented memory is, in others words: how hard it is
> for the kernel to allocate more memory for your process.

More system call for mmap and more CPU cache missing.

Chris

Re: [PATCH 0/7] put struct symbol & friends on diet

[Luc Van Oostenryck]

On Sat, Jul 01, 2017 at 12:51:53PM -0700, Christopher Li wrote:
> On Sat, Jul 1, 2017 at 1:39 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > For the moment, I have no access to the measurements I made. I'll see
> > what I can do. One of the problem I had with kernel 'build' was that
> > I wasn't able able to get number stable enough to my taste (typically,
> > I had a two groups of values, each with a small variance within the
> > group, but the difference between the groups was like 10%, like you
> > would heer have a few value around 2m30 and a few ones around 2m45.
> > Given this, I never bothered to calculate the variance).
> 
> That is exactly the reason I develop my own test makefile instead of using
> kbuild directly.

Oh, I have no reason to believe that this variance had anything
to do with the build system. Sure kbuild have some overhead (not
much though) but it should be as deterministic as the rest.
I think it was just caused by some background tasks and I was busy
do to stuff while measuring.

I've run a batch of time measurement on another machine really unused,
it should give much more stable results. I'll give them when I'll have
access to them tomorrow.

> >
> > Meanwhile, I just looked at your numbers. At first sight, they look
> > more or less as expected. I'm just surprised that the sys time is so
> > high: around 45% of the user time (IIRC, in my measurements it was
> > more like 10%, but I can be wrong).
> 
> That is most likely cause by a high job count "-j12". My test machine
> has 12 hyper-threaded core total. That is why I pick "-j12".
> 
> I can run with some lower job count and see how it goes.

No, it's OK, -j12 is as good as -j4 or -j8. 
I still found very strange that your sys time is so high.
 
> >
> > Looking closer, calculating the mean value of each pair of measures
> > with the standard deviation in parenthesis, then calculating the
> > absolute and relative difference, I get:
> >
> >           NR = 29                  NR = 13               delta
> > real     150.723 (1.492)         147.628 (0.653)         3.096 = 2.1%
> > user    1095.505 (3.555)        1084.916 (1.485)        10.589 = 1.0%
> > sys      496.098 (4.766)         470.548 (0.837)        25.550 = 5.1%
> 
> I assume your test done with normal kernel kbuild.
> How many run was that per setup?

That's just your numbers.

> >
> > This look largely non-surprising:
> > * there is a significative difference in the sys time (where the memory
> >   allocation cost is)
> > * a much smaller difference in user time (which I suppose we can credit
> >   to positive cache effect minus some extra work for lists which are
> >   bigger than 13).
> > * all in all, it gives a modest win of 2% in real time (but here the
> >   difference is only twice the stdvar, so caution with this).
> 
> Yes, that all make sense.
> 
> Keep in mind of the NR change for ptrlist. For any list that is longer than
> 29 items. The memory wasted by the ptr_node itself will increase.
> 
> With NR=29, for long list (list has more than 29 entries). the memory
> use by ptr node is 3/32, about 9.4%. Which NR=13, 3/16= 18.8%.
> So there is about 9% more memory usage for longer list.
> That is some thing we need to keep in mind of.

I know, but the funny things is that even with a very short NR you win
memory and he speed is not slower, because the avarage list length is
so small. I'll give some numbers tomorrow.

> > Of course, the speedup must largely be dependent on the amount of free
> > memory and how fragmented memory is, in others words: how hard it is
> > for the kernel to allocate more memory for your process.
> 
> More system call for mmap and more CPU cache missing.

Yes, and more work for kernel's page allocation too and ... more time
to clear the pages before handing to user space (this is where most
time is spend) as nicely reported by perf. 

-- Luc

Re: [PATCH 0/7] put struct symbol & friends on diet

[Christopher Li]

On Sat, Jul 1, 2017 at 2:02 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Oh, I have no reason to believe that this variance had anything
> to do with the build system. Sure kbuild have some overhead (not
> much though) but it should be as deterministic as the rest.

I should correct that I don't know how consistent is kbuild.
For me kbuild has very noticeable overhead on incremental build
compare to my script:

One job:

$ time make
  CHK     include/config/kernel.release
  CHK     include/generated/uapi/linux/version.h
  CHK     include/generated/utsrelease.h
  CHK     include/generated/bounds.h
  CHK     include/generated/timeconst.h
  CHK     include/generated/asm-offsets.h
  CALL    scripts/checksyscalls.sh
  DESCEND  objtool
  CHK     scripts/mod/devicetable-offsets.h
  CHK     include/generated/compile.h
  CHK     kernel/config_data.h
  CHK     include/generated/uapi/linux/version.h
  DATAREL arch/x86/boot/compressed/vmlinux
Kernel: arch/x86/boot/bzImage is ready  (#15)
  Building modules, stage 2.
  MODPOST 6350 modules

real 2m22.493s
user 1m44.339s
sys 0m35.836s

Change that to 12 jobs:

$ time make -j12
  CHK     include/config/kernel.release
  CHK     include/generated/uapi/linux/version.h
  DESCEND  objtool
  CHK     include/generated/utsrelease.h
  CHK     scripts/mod/devicetable-offsets.h
  CHK     include/generated/timeconst.h
  CHK     include/generated/bounds.h
  CHK     include/generated/asm-offsets.h
  CALL    scripts/checksyscalls.sh
  CHK     include/generated/compile.h
  CHK     kernel/config_data.h
  CHK     include/generated/uapi/linux/version.h
  Building modules, stage 2.
  LD      arch/x86/boot/compressed/vmlinux
  ZOFFSET arch/x86/boot/zoffset.h
  OBJCOPY arch/x86/boot/vmlinux.bin
  AS      arch/x86/boot/header.o
  LD      arch/x86/boot/setup.elf
  OBJCOPY arch/x86/boot/setup.bin
  BUILD   arch/x86/boot/bzImage
Setup is 17084 bytes (padded to 17408 bytes).
System is 11508 kB
CRC 212b68e6
Kernel: arch/x86/boot/bzImage is ready  (#15)
  MODPOST 6350 modules

real 0m44.660s
user 2m10.570s
sys 0m45.502s


With my make script:

$ time make -f $PWD/linux-checker.make  -C ../linux name=master
make: Entering directory '/home/xxxx/git/kernel/linux'
make: Nothing to be done for 'all'.
make: Leaving directory '/home/xxxx/git/kernel/linux'

real 0m4.168s
user 0m4.008s
sys 0m0.143s

$ time make -j12 -f $PWD/linux-checker.make  -C ../linux name=master
make: Entering directory '/home/xxxx/git/kernel/linux'
make: Leaving directory '/home/xxxx/git/kernel/linux'

real 0m4.206s
user 0m4.106s
sys 0m0.181s


> I think it was just caused by some background tasks and I was busy
> do to stuff while measuring.

Of course back ground task will impact it.

>
> I've run a batch of time measurement on another machine really unused,
> it should give much more stable results. I'll give them when I'll have
> access to them tomorrow.

You don't have to do the test. I am fine with this change. I am just
curious with
the numbers myself.

>> I can run with some lower job count and see how it goes.
>
> No, it's OK, -j12 is as good as -j4 or -j8.
> I still found very strange that your sys time is so high.

See my other email. With lower job count, the system time
drop down a lot. If you are using kbuild, it is understandable
system time is lower, because in kbuild the make process is
doing a lot of work comparing compile parameters. That will
water down the total time required.


>> > Looking closer, calculating the mean value of each pair of measures
>> > with the standard deviation in parenthesis, then calculating the
>> > absolute and relative difference, I get:
>> >
>> >           NR = 29                  NR = 13               delta
>> > real     150.723 (1.492)         147.628 (0.653)         3.096 = 2.1%
>> > user    1095.505 (3.555)        1084.916 (1.485)        10.589 = 1.0%
>> > sys      496.098 (4.766)         470.548 (0.837)        25.550 = 5.1%
>>
>> I assume your test done with normal kernel kbuild.
>> How many run was that per setup?
>
> That's just your numbers.

Oh, Oh I see. I mis-understand that part.

Chris

Re: [PATCH 0/7] put struct symbol & friends on diet

[Luc Van Oostenryck]

On Sat, Jul 01, 2017 at 02:28:44PM -0700, Christopher Li wrote:
> On Sat, Jul 1, 2017 at 2:02 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > Oh, I have no reason to believe that this variance had anything
> > to do with the build system. Sure kbuild have some overhead (not
> > much though) but it should be as deterministic as the rest.
> 
> I should correct that I don't know how consistent is kbuild.
> For me kbuild has very noticeable overhead on incremental build
> compare to my script:
> 
> One job:
> $ time make
...
> real 2m22.493s
> user 1m44.339s
> sys 0m35.836s
> 
> Change that to 12 jobs:
> $ time make -j12
...
> real 0m44.660s
> user 2m10.570s
> sys 0m45.502s
> 
> 
> With my make script:
> $ time make -f $PWD/linux-checker.make  -C ../linux name=master
> real 0m4.168s
> user 0m4.008s
> sys 0m0.143s
> 
> $ time make -j12 -f $PWD/linux-checker.make  -C ../linux name=master
> real 0m4.206s
> user 0m4.106s
> sys 0m0.181s

Yes, I did some simple 'make vmlinux' on an allyesconfig kernel which
was already compiled and I was surprised by the time it took (all times
in seconds, followed between the parenthesis by standard deviation,
relative standard deviation and the standard error (of the mean):
	          nbr measures: 12
	real:	  71.90 (1.50 = 2.09% ~ 0.67)
	user:	  57.19 (1.19 = 2.08% ~ 0.53)
	sys:	  10.30 (0.36 = 3.52% ~ 0.16)
But the variance is not much, about the same as full compile or full
check by sparse (see here under).

> You don't have to do the test. I am fine with this change. I am just
> curious with
> the numbers myself.

I'm interested myself in some good numbers.
 
The result for an allyesconfig kernel without using kbuild:
	NR = 29, nbr measures: 12
	real:	1080.44 (2.62 = 0.24% ~ 0.76)
	user:	 818.06 (2.27 = 0.28% ~ 0.66)
	sys:	 227.18 (1.12 = 0.49% ~ 0.32)

	NR = 13, nbr measures: 20
	real:	1064.25 (1.65 = 0.15% ~ 0.37)
	user:	 816.35 (1.29 = 0.16% ~ 0.29)
	sys:	 213.33 (0.90 = 0.42% ~ 0.20)

	NR = 05, nbr measures: 11
	real:	1058.52 (2.57 = 0.24% ~ 0.78)
	user:	 817.17 (2.34 = 0.29% ~ 0.70)
	sys:	 207.12 (0.95 = 0.46% ~ 0.29)

For the speedup, this gives us:
1) using NR=13 instead of 29:
	real:  16.19 (1.50%)
	user:   1.71 (0.21%)
	sys:   13.85 (6.10%)

1) using NR=5 instead of 29:
	real:  21.92 (2.03%)
	user:   0.89 (0.11%)
	sys:   20.06 (8.83%)

So, the speedup on the whole kernel is real but modest:
* 1.5-2.0% on real time,
* the gain in user time is negligible and smaller than the std dev.
  -> cache effect is very small or inexisting or is compensated
  by some extra work due to the use of  more list blocks.
* the speedup in system time is appreciable though: 6-8%

I have done some others tests with NR = 7, 9, ... They are not much
interesting, giving times similar but a bit higher than for NR = 13
(but for NR = 9). The differences are anyway quite small.

-- Luc

Re: [PATCH 0/7] put struct symbol & friends on diet

[Christopher Li]

On Sat, Jul 1, 2017 at 1:39 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Meanwhile, I just looked at your numbers. At first sight, they look
> more or less as expected. I'm just surprised that the sys time is so
> high: around 45% of the user time (IIRC, in my measurements it was
> more like 10%, but I can be wrong).


For what is worth, I have rerun the test with less jobs:

Two run with -j6:

real 3m12.199s
user 12m47.617s
sys 5m30.896s

real 3m11.469s
user 12m44.292s
sys 5m29.944s

One run with one job:

real 14m21.460s
user 10m18.034s
sys 3m56.646s

As predicted, the system overhead come down dramatically with
less jobs. I think that sparse is the one with NR=29.

Chris