Optimizing ‘string=’

[ludo@gnu.org (Ludovic Courtès)]

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

Hello!

While profiling a Scheme program, I noticed that ‘string=?’ was
surprisingly high.  I ran OProfile on this Scheme program:

--8<---------------cut here---------------start------------->8---
(define s (make-string 123 #\a))
(let loop ()
  (string= s s)
  (loop))
--8<---------------cut here---------------end--------------->8---

The flat profile was like this:

--8<---------------cut here---------------start------------->8---
samples  %        symbol name
13683    24.6367  scm_i_string_ref
13447    24.2118  compare_strings
8652     15.5782  scm_i_string_chars
4801      8.6444  vm_debug_engine
4535      8.1654  scm_i_str2symbol
2123      3.8225  scm_ihashq
1338      2.4091  scm_fluid_ref
993       1.7879  scm_i_string_hash
750       1.3504  scm_hash_fn_get_handle
616       1.1091  scm_module_variable
445       0.8012  scm_from_locale_stringn
--8<---------------cut here---------------end--------------->8---

I came up with the following patch, which adds a shortcut for the most
common case:


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: text/x-patch, Size: 1259 bytes --]

diff --git a/libguile/srfi-13.c b/libguile/srfi-13.c
index c4e8571..4803830 100644
--- a/libguile/srfi-13.c
+++ b/libguile/srfi-13.c
@@ -1,6 +1,6 @@
 /* srfi-13.c --- SRFI-13 procedures for Guile
  *
- * Copyright (C) 2001, 2004, 2005, 2006, 2008, 2009 Free Software Foundation, Inc.
+ * Copyright (C) 2001, 2004, 2005, 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public License
@@ -1168,6 +1168,21 @@ SCM_DEFINE (scm_string_eq, "string=", 2, 4, 0,
 	    "value otherwise.")
 #define FUNC_NAME s_scm_string_eq
 {
+  if (SCM_LIKELY (scm_i_is_narrow_string (s1) == scm_i_is_narrow_string (s2)
+		  && SCM_UNBNDP (start1) && SCM_UNBNDP (end1)
+		  && SCM_UNBNDP (start2) && SCM_UNBNDP (end2)))
+    {
+      size_t len1, len2;
+
+      len1 = scm_i_string_length (s1);
+      len2 = scm_i_string_length (s2);
+
+      if (SCM_LIKELY (len1 == len2))
+	return scm_from_bool (memcmp (scm_i_string_chars (s1),
+				      scm_i_string_chars (s2),
+				      len1) == 0);
+    }
+
   return compare_strings (FUNC_NAME, 0, 
 			  s1, s2, start1, end1, start2, end2,
 			  SCM_BOOL_F, SCM_BOOL_F, SCM_BOOL_F, SCM_BOOL_F, SCM_BOOL_T);

[-- Attachment #3: Type: text/plain, Size: 932 bytes --]


It’s quite inelegant, but it leads to a more balanced profile:

--8<---------------cut here---------------start------------->8---
samples  %        symbol name
8079     23.3984  scm_string_eq
5649     16.3606  vm_debug_engine
5624     16.2882  scm_i_str2symbol
2840      8.2252  scm_ihashq
1755      5.0828  scm_i_string_hash
1637      4.7411  scm_fluid_ref
1027      2.9744  scm_i_string_ref
1011      2.9281  scm_hash_fn_get_handle
877       2.5400  scm_i_string_chars
793       2.2967  scm_module_variable
553       1.6016  scm_from_locale_stringn
471       1.3641  scm_from_stringn
426       1.2338  scm_sym2var
384       1.1121  scm_i_make_string
317       0.9181  scm_module_lookup
--8<---------------cut here---------------end--------------->8---

... and a 43% execution time improvement on a tight loop that does
‘string=’.

OK to commit?  Ideas for a better solution?

Thanks,
Ludo’.