[PATCH] avoid initialization overhead in strcoll

[PATCH] avoid initialization overhead in strcoll

[Leonhard Holz]

This patch removes some initialization overhead in the hot path of strcoll. It
improves the file listing benchmark by 20% on x86.

filelist#C			- 2.51%
filelist#en_US.UTF-8		-20.41%
lorem_ipsum#vi_VN.UTF-8		-29.86%
lorem_ipsum#en_US.UTF-8		-17.47%
lorem_ipsum#ar_SA.UTF-8		-15.81%
lorem_ipsum#zh_CN.UTF-8		- 5.03%
lorem_ipsum#cs_CZ.UTF-8		-13.44%
lorem_ipsum#en_GB.UTF-8		-14.51%
lorem_ipsum#da_DK.UTF-8		-18.99%
lorem_ipsum#pl_PL.UTF-8		-17.07%
lorem_ipsum#fr_FR.UTF-8		-16.64%
lorem_ipsum#pt_PT.UTF-8		-16.51%
lorem_ipsum#el_GR.UTF-8		-11.78%
lorem_ipsum#ru_RU.UTF-8		-14.07%
lorem_ipsum#iw_IL.UTF-8		- 9.20%
lorem_ipsum#es_ES.UTF-8		-22.05%
lorem_ipsum#hi_IN.UTF-8		  2.50%
lorem_ipsum#sv_SE.UTF-8		-18.63%
lorem_ipsum#hu_HU.UTF-8		-13.16%
lorem_ipsum#tr_TR.UTF-8		-16.54%
lorem_ipsum#is_IS.UTF-8		-17.30%
lorem_ipsum#it_IT.UTF-8		-17.82%
lorem_ipsum#sr_RS.UTF-8		-22.83%
lorem_ipsum#ja_JP.UTF-8		  4.99%


	* string/strcoll_l.c (STRCOLL): Removed unneeded initialization overhead.


diff --git a/string/strcoll_l.c b/string/strcoll_l.c
index 0fa005f..14bfb8b 100644
--- a/string/strcoll_l.c
+++ b/string/strcoll_l.c
@@ -62,7 +62,6 @@ typedef struct
   int len;			/* Length of the current sequence.  */
   size_t val;			/* Position of the sequence relative to the
 				   previous non-ignored sequence.  */
-  size_t idxnow;		/* Current index in sequences.  */
   size_t idxmax;		/* Maximum index in sequences.  */
   size_t idxcnt;		/* Current count of indices.  */
   size_t backw;			/* Current Backward sequence index.  */
@@ -313,20 +312,22 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2,
__locale_t l)
   assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
   assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);

-  int result = 0, rule = 0;
-
+  int result = 0;
   coll_seq seq1, seq2;
-  memset (&seq1, 0, sizeof (seq1));
-  seq2 = seq1;
+  seq1.len = 0;
+  seq1.idxmax = 0;
+  seq1.rule = 0;
+  seq2.len = 0;
+  seq2.idxmax = 0;

   for (int pass = 0; pass < nrules; ++pass)
     {
       seq1.idxcnt = 0;
+      seq2.idxcnt = 0;
       seq1.idx = 0;
       seq2.idx = 0;
       seq1.backw_stop = ~0ul;
       seq1.backw = ~0ul;
-      seq2.idxcnt = 0;
       seq2.backw_stop = ~0ul;
       seq2.backw = ~0ul;

@@ -338,8 +339,7 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2,
__locale_t l)
       /* We assume that if a rule has defined `position' in one section
 	 this is true for all of them.  Please note that the localedef programs
 	 makes sure that `position' is not used at the first level.  */
-
-      int position = rulesets[rule * nrules + pass] & sort_position;
+      int position = rulesets[seq1.rule * nrules + pass] & sort_position;

       while (1)
 	{
@@ -372,8 +372,6 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2,
__locale_t l)
 	  if (result != 0)
 	    return result;
 	}
-
-      rule = seq1.rule;
     }

   return result;

Re: [PATCH] avoid initialization overhead in strcoll

[Siddhesh Poyarekar]

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

On Thu, May 28, 2015 at 05:39:01PM +0200, Leonhard Holz wrote:
> This patch removes some initialization overhead in the hot path of strcoll. It
> improves the file listing benchmark by 20% on x86.

You've removed a memset call which seems to be the reason for the 20%
overhead; I can't see anything else that could have done this, but I
haven't looked hard enough.

This change however should be split up to only include the useful
stuff.

> diff --git a/string/strcoll_l.c b/string/strcoll_l.c
> index 0fa005f..14bfb8b 100644
> --- a/string/strcoll_l.c
> +++ b/string/strcoll_l.c
> @@ -62,7 +62,6 @@ typedef struct
>    int len;			/* Length of the current sequence.  */
>    size_t val;			/* Position of the sequence relative to the
>  				   previous non-ignored sequence.  */
> -  size_t idxnow;		/* Current index in sequences.  */

This should go in as a separate change since it is valid without any
performance justification.  idxnow is unused.  Please post this as a
separate patch.

>    size_t idxmax;		/* Maximum index in sequences.  */
>    size_t idxcnt;		/* Current count of indices.  */
>    size_t backw;			/* Current Backward sequence index.  */
> @@ -313,20 +312,22 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2,
> __locale_t l)
>    assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
>    assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
> 
> -  int result = 0, rule = 0;
> -
> +  int result = 0;
>    coll_seq seq1, seq2;
> -  memset (&seq1, 0, sizeof (seq1));
> -  seq2 = seq1;
> +  seq1.len = 0;
> +  seq1.idxmax = 0;
> +  seq1.rule = 0;
> +  seq2.len = 0;
> +  seq2.idxmax = 0;

I'm surprised that this actually makes a difference.  The memset
should have been optimized out and replaced with movs.  The change to
remove the RULE variable seems unrelated to me and should just be
avoided if it does not result in any interesting code change..

Can you please post a more detailed justification of what caused the
performance improvement?

Siddhesh

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

Re: [PATCH] avoid initialization overhead in strcoll

[Ondřej Bílka]

On Fri, Jun 05, 2015 at 12:08:37AM +0530, Siddhesh Poyarekar wrote:
> On Thu, May 28, 2015 at 05:39:01PM +0200, Leonhard Holz wrote:
> > This patch removes some initialization overhead in the hot path of strcoll. It
> > improves the file listing benchmark by 20% on x86.
> 
> You've removed a memset call which seems to be the reason for the 20%
> overhead; I can't see anything else that could have done this, but I
> haven't looked hard enough.
> 
> This change however should be split up to only include the useful
> stuff.
> 
> > diff --git a/string/strcoll_l.c b/string/strcoll_l.c
> > index 0fa005f..14bfb8b 100644
> > --- a/string/strcoll_l.c
> > +++ b/string/strcoll_l.c
> > @@ -62,7 +62,6 @@ typedef struct
> >    int len;			/* Length of the current sequence.  */
> >    size_t val;			/* Position of the sequence relative to the
> >  				   previous non-ignored sequence.  */
> > -  size_t idxnow;		/* Current index in sequences.  */
> 
> This should go in as a separate change since it is valid without any
> performance justification.  idxnow is unused.  Please post this as a
> separate patch.
> 
> >    size_t idxmax;		/* Maximum index in sequences.  */
> >    size_t idxcnt;		/* Current count of indices.  */
> >    size_t backw;			/* Current Backward sequence index.  */
> > @@ -313,20 +312,22 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2,
> > __locale_t l)
> >    assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
> >    assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
> > 
> > -  int result = 0, rule = 0;
> > -
> > +  int result = 0;
> >    coll_seq seq1, seq2;
> > -  memset (&seq1, 0, sizeof (seq1));
> > -  seq2 = seq1;
> > +  seq1.len = 0;
> > +  seq1.idxmax = 0;
> > +  seq1.rule = 0;
> > +  seq2.len = 0;
> > +  seq2.idxmax = 0;
> 
> I'm surprised that this actually makes a difference.  The memset
> should have been optimized out and replaced with movs.  The change to
> remove the RULE variable seems unrelated to me and should just be
> avoided if it does not result in any interesting code change..
> 
> Can you please post a more detailed justification of what caused the
> performance improvement?
> 
Main difference from assembly output is saving 64 bytes on stack space,
otherwise looks like random renaming of jumps.

Re: [PATCH] avoid initialization overhead in strcoll

[Leonhard Holz]

Hi Siddhesh,


Am 04.06.2015 um 20:38 schrieb Siddhesh Poyarekar:
> On Thu, May 28, 2015 at 05:39:01PM +0200, Leonhard Holz wrote:
>> This patch removes some initialization overhead in the hot path of strcoll.
>> It improves the file listing benchmark by 20% on x86.
> 
> You've removed a memset call which seems to be the reason for the 20% 
> overhead; I can't see anything else that could have done this, but I haven't
> looked hard enough.
> 

I think so too.

> This change however should be split up to only include the useful stuff.
> 
>> diff --git a/string/strcoll_l.c b/string/strcoll_l.c index 0fa005f..14bfb8b
>> 100644 --- a/string/strcoll_l.c +++ b/string/strcoll_l.c @@ -62,7 +62,6 @@
>> typedef struct int len;			/* Length of the current sequence.  */ size_t
>> val;			/* Position of the sequence relative to the previous non-ignored
>> sequence.  */ -  size_t idxnow;		/* Current index in sequences.  */
> 
> This should go in as a separate change since it is valid without any 
> performance justification.  idxnow is unused.  Please post this as a separate
> patch.

Ok.

> 
>> size_t idxmax;		/* Maximum index in sequences.  */ size_t idxcnt;		/*
>> Current count of indices.  */ size_t backw;			/* Current Backward sequence
>> index.  */ @@ -313,20 +312,22 @@ STRCOLL (const STRING_TYPE *s1, const
>> STRING_TYPE *s2, __locale_t l) assert (((uintptr_t) extra) % __alignof__
>> (extra[0]) == 0); assert (((uintptr_t) indirect) % __alignof__
>> (indirect[0]) == 0);
>> 
>> -  int result = 0, rule = 0; - +  int result = 0; coll_seq seq1, seq2; -
>> memset (&seq1, 0, sizeof (seq1)); -  seq2 = seq1; +  seq1.len = 0; +
>> seq1.idxmax = 0; +  seq1.rule = 0; +  seq2.len = 0; +  seq2.idxmax = 0;
> 
> I'm surprised that this actually makes a difference.  The memset should have
> been optimized out and replaced with movs.  The change to remove the RULE
> variable seems unrelated to me and should just be avoided if it does not
> result in any interesting code change..

It is not merely a replacement of memset with assignments, after the patch only
the properties that need to be set to zero are set and the rest is left
uninitialized. They will be set by get_next_seq() anyway. Removing the RULE var
is included because it saves an initialization.

> 
> Can you please post a more detailed justification of what caused the 
> performance improvement?

Maybe it is platform dependent, but my (x86) assembly output shows a rep stos
that is removed due to the patch.

Before:

319	  memset (&seq1, 0, sizeof (seq1));
   0x000000ef <__strcoll_l+175>:	lea    0x90(%esp),%edx
   0x000000f6 <__strcoll_l+182>:	mov    %ebx,%eax
   0x000000f8 <__strcoll_l+184>:	mov    $0xc,%ecx
   0x000000fd <__strcoll_l+189>:	movl   $0x0,0x20(%esp)
   0x00000105 <__strcoll_l+197>:	movl   $0x0,0x74(%esp)
   0x0000010d <__strcoll_l+205>:	mov    %edx,%edi
   0x0000010f <__strcoll_l+207>:	movl   $0x0,0x7c(%esp)
   0x00000117 <__strcoll_l+215>:	movl   $0x0,0x3c(%esp)
   0x0000011f <__strcoll_l+223>:	rep stos %eax,%es:(%edi)
   0x00000121 <__strcoll_l+225>:	xor    %eax,%eax

After (bigger snippet because compiler moved code):

308	    current->values[_NL_ITEM_INDEX
(CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
309	
310	  assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
   0x000000c7 <__strcoll_l+135>:	and    $0x3,%esi
   0x000000d2 <__strcoll_l+146>:	jne    0x11f5 <__strcoll_l+4533>

311	  assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
312	  assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
313	  assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
   0x000000d8 <__strcoll_l+152>:	testb  $0x3,0x38(%esp)
   0x000000dd <__strcoll_l+157>:	jne    0x11dc <__strcoll_l+4508>
   0x000000e3 <__strcoll_l+163>:	movl   $0x0,0x4c(%esp)
   0x000000eb <__strcoll_l+171>:	movb   $0x0,0x9d(%esp)
   0x000000f3 <__strcoll_l+179>:	movl   $0x0,0x20(%esp)
   0x000000fb <__strcoll_l+187>:	movl   $0x0,0x3c(%esp)

314	
315	  int result = 0;
316	  coll_seq seq1, seq2;
317	  seq1.len = 0;
318	  seq1.idxmax = 0;
319	  seq1.rule = 0;
320	  seq2.len = 0;
321	  seq2.idxmax = 0;
322	
323	  for (int pass = 0; pass < nrules; ++pass)
324	    {
325	      seq1.idxcnt = 0;
   0x00000163 <__strcoll_l+291>:	movl   $0x0,0x60(%esp)

Leonhard

Re: [PATCH] avoid initialization overhead in strcoll

[Siddhesh Poyarekar]

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

On Fri, Jun 05, 2015 at 02:37:04PM +0200, Leonhard Holz wrote:
> Maybe it is platform dependent, but my (x86) assembly output shows a rep stos
> that is removed due to the patch.

OK great, this is what I wanted to know.  Can you now confirm if the
RULE local variable removal is necessary?  Please send two patches as
I said before and I'll check those in.

Siddhesh

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]