This is the mail archive of the fortran@gcc.gnu.org mailing list for the GNU Fortran 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, Fortran] Experimental LEN_TRIM and TRIM patch


Slightly improved patch and ChangeLog.

Daniel Kraft wrote:
Hi,

here's an experimental patch to tune the LEN_TRIM and TRIM intrinsics. In my own experience, I usually use TRIM (or LEN_TRIM) in combination with strings allocated too large (because no dynamic length is possible), so that there are usually lots of blanks at the end.

In this case (and for KIND=1 strings), instead of checking each and every character if it is a blank, we can check them in chunks of 4 (or 8) by comparing them as unsigned long integers. That's what the patch does, as well as add a test-case and re-use LEN_TRIM for TRIM instead of duplicating the code there.

For the attached (extreme) test-case, the patch really gives nearly 4x speed-up as expected for a best case; if the full string length is only marginally larger than the trimmed one (like one trailing blank), the patch slows down up to a factor of 2. But as soon as there are 4-5 trailing blanks, the new version is faster.

Comments welcome!

I guess there are configure-set macros telling me if unsigned long is 4 or 8 bytes on the machine, so we can make the blank_long initialization work on 64-bit, too...

Yours,
Daniel

PS: BTW, while gfortran does not complain about CHARACTER(LEN=0) (don't know if this is legal), for LEN=-1 one gets "Warning: CHARACTER variable has *zero* length" which sounds quite a little confusing.



--
Done:  Arc-Bar-Cav-Ran-Rog-Sam-Tou-Val-Wiz
To go: Hea-Kni-Mon-Pri
Index: libgfortran/intrinsics/string_intrinsics_inc.c
===================================================================
--- libgfortran/intrinsics/string_intrinsics_inc.c	(revision 144104)
+++ libgfortran/intrinsics/string_intrinsics_inc.c	(working copy)
@@ -165,15 +165,7 @@ void
 string_trim (gfc_charlen_type *len, CHARTYPE **dest, gfc_charlen_type slen,
 	     const CHARTYPE *src)
 {
-  gfc_charlen_type i;
-
-  /* Determine length of result string.  */
-  for (i = slen - 1; i >= 0; i--)
-    {
-      if (src[i] != ' ')
-        break;
-    }
-  *len = i + 1;
+  *len = string_len_trim (slen, src);
 
   if (*len == 0)
     *dest = &zero_length_string;
@@ -193,13 +185,52 @@ string_trim (gfc_charlen_type *len, CHAR
 gfc_charlen_type
 string_len_trim (gfc_charlen_type len, const CHARTYPE *s)
 {
+  const gfc_charlen_type long_len = (gfc_charlen_type) sizeof (unsigned long);
   gfc_charlen_type i;
 
-  for (i = len - 1; i >= 0; i--)
-    {
-      if (s[i] != ' ')
-        break;
+  i = len - 1;
+
+  /* If we've got the standard (KIND=1) character type, we scan the string in
+     long word chunks to speed it up (until a long word is hit that does not
+     consist of ' 's).  */
+  if (sizeof (CHARTYPE) == 1 && i >= long_len)
+    {
+      int starting;
+      unsigned long blank_longword;
+
+      /* Handle the first characters until we're aligned on a long word
+	 boundary.  Actually, s + i + 1 must be properly aligned, because
+	 s + i will be the last byte of a long word read.  */
+      starting = ((unsigned long) (s + i + 1)) % long_len;
+      i -= starting;
+      for (; starting > 0; --starting)
+	if (s[i + starting] != ' ')
+	  return i + starting + 1;
+
+      /* Handle the others in a batch until first non-blank long word is
+	 found.  Here again, s + i is the last byte of the current chunk,
+	 to it starts at s + i - sizeof (long) + 1.  */
+
+      /* XXX: Do this reliably, i.e. working for 64-bit systems, too.  */
+      blank_longword = 0x20202020L;
+
+      while (i >= long_len)
+	{
+	  i -= long_len;
+	  if (*((unsigned long*) (s + i + 1)) != blank_longword)
+	    {
+	      i += long_len;
+	      break;
+	    }
+	}
+
+      /* Now continue for the last characters with naive approach below.  */
+      assert (i >= 0);
     }
+
+  /* Simply look for the first non-blank character.  */
+  while (i >= 0 && s[i] == ' ')
+    --i;
   return i + 1;
 }
 
Index: libgfortran/intrinsics/string_intrinsics.c
===================================================================
--- libgfortran/intrinsics/string_intrinsics.c	(revision 144104)
+++ libgfortran/intrinsics/string_intrinsics.c	(working copy)
@@ -39,6 +39,7 @@ Boston, MA 02110-1301, USA.  */
 
 #include <stdlib.h>
 #include <string.h>
+#include <assert.h>
 
 
 /* Helper function to set parts of wide strings to a constant (usually
Index: gcc/testsuite/gfortran.dg/trim_1.f90
===================================================================
--- gcc/testsuite/gfortran.dg/trim_1.f90	(revision 0)
+++ gcc/testsuite/gfortran.dg/trim_1.f90	(revision 0)
@@ -0,0 +1,41 @@
+! { dg-do run }
+
+! Torture-test TRIM and LEN_TRIM for correctness.
+
+
+! Given a total string length and a trimmed length, construct an
+! appropriate string and check gfortran gets it right.
+
+SUBROUTINE check_trim (full_len, trimmed_len)
+  IMPLICIT NONE
+  INTEGER, INTENT(IN) :: full_len, trimmed_len
+  CHARACTER(LEN=full_len) :: string
+
+  string = ""
+  IF (trimmed_len > 0) THEN
+    string(trimmed_len:trimmed_len) = "x"
+  END IF
+
+  IF (LEN (string) /= full_len &
+      .OR. LEN_TRIM (string) /= trimmed_len &
+      .OR. LEN (TRIM (string)) /= trimmed_len &
+      .OR. TRIM (string) /= string (1:trimmed_len)) THEN
+    PRINT *, full_len, trimmed_len
+    PRINT *, LEN (string), LEN_TRIM (string)
+    CALL abort ()
+  END IF
+END SUBROUTINE check_trim
+
+
+! The main program, check with various combinations.
+
+PROGRAM main
+  IMPLICIT NONE
+  INTEGER :: i, j
+
+  DO i = 0, 20
+    DO j = 0, i
+      CALL check_trim (i, j)
+    END DO
+  END DO
+END PROGRAM main
2009-02-12  Daniel Kraft  <d@domob.eu>

	* intrinsics/string_intrinsics.c: #include <assert.h>
	* intrinsics/string_intrinsics_inc.c (string_trim): Use string_len_trim
	instead of calculating the length directly.
	(string_len_trim): For KIND=1, speed search up.

2009-02-12  Daniel Kraft  <d@domob.eu>

	* gfortran.dg/trim_1.f90: New test.

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