This is the mail archive of the
libc-alpha@sources.redhat.com
mailing list for the glibc project.
Re: [PATCH] i386 strtok.S optimization
- From: Jhair Tocancipa Triana <jhair_tocancipa at gmx dot net>
- To: Ulrich Drepper <drepper at redhat dot com>
- Cc: Glibc Alpha <libc-alpha at sources dot redhat dot com>
- Date: 28 Aug 2002 00:25:26 +0000
- Subject: Re: [PATCH] i386 strtok.S optimization
- References: <m3adnvaqju.fsf@mandala.local> <3D6703B4.4050703@redhat.com>
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