This is the mail archive of the libc-alpha@sources.redhat.com mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] i386 strtok.S optimization


Hi,

Ulrich Drepper writes:

   > Shorter isn't necessarily faster.  I haven't tested the code yet
   > due to time constraints.  Please run some tests and time them.

I have put the results and times of some tests in the following URL:

http://home.t-online.de/home/jhair_tocancipa/t1.htm

   > And then provide a patch without any changes to the white spaces
   > and without dropping the opcode extensions like b,w,l.  Doing so
   > only makes reading the patch more difficult.

This new patch should not have those problems.

Thanks and regards,

-- 
--Jhair

2002-08-28  Jhair Tocancipa  <jhair_tocancipa@gmx.net>

	* sysdeps/i386/strtok.S: Don't use a new loop to terminate
	tokens.

--- strtok.S	6 Jul 2001 04:55:52
+++ strtok.S	28 Aug 2002 00:11:08
@@ -3,6 +3,7 @@
    Copyright (C) 1996, 1997, 1998, 2000, 2001 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1996.
+   New optimization by Jhair Tocancipa<jhair_tocancipa@gmx.net>, 2002.	
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -189,128 +190,92 @@
 	pushl $0
 	pushl $0
 
-/* For understanding the following code remember that %ecx == 0 now.
-   Although all the following instruction only modify %cl we always
-   have a correct zero-extended 32-bit value in %ecx.  */
-
-L(2):	movb (%eax), %cl	/* get byte from stopset */
-	testb %cl, %cl		/* is NUL char? */
-	jz L(1_1)		/* yes => start compare loop */
-	movb %cl, (%esp,%ecx)	/* set corresponding byte in stopset table */
+L(2):
+	movb (%eax), %cl	/* get byte from stopset */		
+	testb %cl, %cl		/* is NUL char? */	
+	jz L(3)			/* yes => look for delimiters in the string */
+	movb %cl, (%esp, %ecx)	/* no => put the byte in our flags table */
 
 	movb 1(%eax), %cl	/* get byte from stopset */
-	testb $0xff, %cl	/* is NUL char? */
-	jz L(1_2)		/* yes => start compare loop */
-	movb %cl, (%esp,%ecx)	/* set corresponding byte in stopset table */
+	testb $0xff, %cl	/* is NUL char? */		
+	jz L(3)			/* yes => look for delimiters in the string */	
+	movb %cl, (%esp, %ecx)	/* no => put the byte in our flags table */
 
 	movb 2(%eax), %cl	/* get byte from stopset */
 	testb $0xff, %cl	/* is NUL char? */
-	jz L(1_3)		/* yes => start compare loop */
-	movb %cl, (%esp,%ecx)	/* set corresponding byte in stopset table */
+	jz L(3)			/* yes => look for delimiters in the string */	
+	movb %cl, (%esp, %ecx)	/* no => put the byte in our flags table */	
 
-	movb 3(%eax), %cl	/* get byte from stopset */
-	addl $4, %eax		/* increment stopset pointer */
-	movb %cl, (%esp,%ecx)	/* set corresponding byte in stopset table */
+	movb 3(%eax), %cl	/* get byte from stopset */		
 	testb $0xff, %cl	/* is NUL char? */
-	jnz L(2)		/* no => process next dword from stopset */
-
-#if __BOUNDED_POINTERS__
-	jmp L(1_0)		/* pointer is correct for bounds check */
-L(1_3):	incl %eax		/* adjust pointer for bounds check */
-L(1_2):	incl %eax		/* ditto */
-L(1_1):	incl %eax		/* ditto */
-L(1_0):	CHECK_BOUNDS_HIGH (%eax, DELIM(%esp), jbe)
-#else
-L(1_3):; L(1_2):; L(1_1):	/* fall through */
-#endif
-	leal -4(%edx), %eax	/* prepare loop */
-
-	/* We use a neat trick for the following loop.  Normally we would
-	   have to test for two termination conditions
-	   1. a character in the stopset was found
-	   and
-	   2. the end of the string was found
-	   As a sign that the character is in the stopset we store its
-	   value in the table.  The value of NUL is NUL so the loop
-	   terminates for NUL in every case.  */
-
-L(3):	addl $4, %eax		/* adjust pointer for full loop round */
-
-	movb (%eax), %cl	/* get byte from string */
-	testb %cl, (%esp,%ecx)	/* is it contained in stopset? */
-	jz L(4)			/* no => start of token */
-
-	movb 1(%eax), %cl	/* get byte from string */
-	testb %cl, (%esp,%ecx)	/* is it contained in stopset? */
-	jz L(5)			/* no => start of token */
-
-	movb 2(%eax), %cl	/* get byte from string */
-	testb %cl, (%esp,%ecx)	/* is it contained in stopset? */
-	jz L(6)			/* no => start of token */
-
-	movb 3(%eax), %cl	/* get byte from string */
-	testb %cl, (%esp,%ecx)	/* is it contained in stopset? */
-	jnz L(3)		/* yes => start of loop */
-
-	incl %eax		/* adjust pointer */
-L(6):	incl %eax
-L(5):	incl %eax
-
-	/* Now we have to terminate the string.  */
-
-L(4):	leal -4(%eax), %edx	/* We use %EDX for the next run.  */
-
-L(7):	addl $4, %edx		/* adjust pointer for full loop round */
-
+	jz L(3)			/* yes => look for delimiters in the string */
+	movb %cl, (%esp, %ecx)	/* no => put the byte in our flags table */
+	addl $0x4, %eax		/* increment stopset pointer */
+	jmp L(2)	
+
+L(3):
+	movl %edx, %eax		/* save the begin of string */
+	xorl %ecx, %ecx
+L(3_5):	
 	movb (%edx), %cl	/* get byte from string */
-	cmpb %cl, (%esp,%ecx)	/* is it contained in skipset? */
-	je L(8)			/* yes => return */
+	cmpb %cl, (%esp, %ecx)	/* is it contained in stopset? */
+	je L(3_1)		/* a (possibly NULL) token was found */
 
 	movb 1(%edx), %cl	/* get byte from string */
-	cmpb %cl, (%esp,%ecx)	/* is it contained in skipset? */
-	je L(9)			/* yes => return */
-
-	movb 2(%edx), %cl	/* get byte from string */
-	cmpb %cl, (%esp,%ecx)	/* is it contained in skipset? */
-	je L(10)		/* yes => return */
-
-	movb 3(%edx), %cl	/* get byte from string */
-	cmpb %cl, (%esp,%ecx)	/* is it contained in skipset? */
-	jne L(7)		/* no => start loop again */
-
-	incl %edx		/* adjust pointer */
-L(10):	incl %edx
-L(9):	incl %edx
-
-L(8):	/* Remove the stopset table.  */
-	addl $256, %esp
-
-	cmpl %eax, %edx
-	je L(returnNULL)	/* There was no token anymore.  */
-
-	movb $0, (%edx)		/* Terminate string.  */
-
-	/* Are we at end of string?  */
-	cmpb $0, %cl
-	je L(11)
+	cmpb %cl, (%esp, %ecx)	/* is it contained in stopset? */	
+	je L(3_2)		/* a (possibly NULL) token was found */
 
-	incl %edx
-L(11):
+	movb 2(%edx), %cl	/* get byte from string */		
+	cmpb %cl, (%esp, %ecx)	/* is it contained in stopset? */	
+	je L(3_3)		/* a (possibly NULL) token was found */
+
+	movb 3(%edx), %cl	/* get byte from string */		
+	cmpb %cl, (%esp, %ecx)	/* is it contained in stopset? */	
+	je L(3_4)		/* a (possibly NULL) token was found */
+	addl $0x4, %edx		/* increment string pointer */
+	jmp L(3_5)
+
+L(3_4):	
+	incl %edx		/* adjust string pointer */
+L(3_3):	
+	incl %edx		/* adjust string pointer */
+L(3_2):	
+	incl %edx		/* adjust string pointer */
+L(3_1):
+	cmpb $0x0, 0(%edx)	/* is the end of string? */
+	je L(4)
 
-	/* Store the pointer to the next character.  */
+	leal 1(%edx), %edx
 #ifdef USE_AS_STRTOK_R
-	movl SAVE(%esp), %ecx
+	/* +0x100 since we haven't flushed the flags table yet */	
+	movl SAVE+0x100(%esp), %ecx 
 #endif
 	movl %edx, SAVE_PTR
 	CHECK_BOUNDS_HIGH (%edx, SAVE_PTR, jb)
 	RETURN_BOUNDED_POINTER (SAVE_PTR)
 
+	leal -1(%edx), %ecx	/* we point to the last 'delimiter' found */
+	cmpl %ecx, %eax		/* is a NULL token? */
+	je L(3)			/* look forth for tokens */
+	movb $0x0, -1(%edx)	/* terminate the valid token found */
+
 L(epilogue):
+	addl $0x100, %esp	/* free the flags table */
 #if !defined USE_AS_STRTOK_R && defined PIC
 	popl %ebx
 #endif
 	LEAVE
 	RET_PTR
+
+L(4):	
+#ifdef USE_AS_STRTOK_R
+	movl SAVE+0x100(%esp), %ecx	
+#endif
+	movl %edx, SAVE_PTR	/* store the pointer to the next character */	
+	CHECK_BOUNDS_HIGH (%edx, SAVE_PTR, jb)
+	RETURN_BOUNDED_POINTER (SAVE_PTR)
+	cmpl %edx, %eax		/* is the last token? */
+	jne L(epilogue)		/* return the last token */
 
 L(returnNULL):
 	xorl %eax, %eax


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]