Optimizing ‘string=’

Optimizing ‘string=’

[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’.

Re: Optimizing ‘string=’

[Ludovic Courtès]

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

Oops, there was a thinko in the patch, whereby wide strings would not be
entirely compared.  Here’s an updated one:


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

diff --git a/libguile/srfi-13.c b/libguile/srfi-13.c
index c4e8571..f29ceaa 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,26 @@ 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))
+	{
+	  if (!scm_i_is_narrow_string (s1))
+	    len1 *= 4;
+
+	  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: 12 bytes --]


Ludo’.

Re: Optimizing ‘string=’

[Andy Wingo]

Hi,

Nice profile-driven debugging :)

On Tue 22 Jun 2010 21:40, ludo@gnu.org (Ludovic Courtès) writes:

> @@ -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);
> +    }
> +

Nasty, but OK I guess if you need it. Why not also add a fast path for
scm_is_eq (s1, s2), or for comparing stringbufs, or something ?

> It’s quite inelegant, but it leads to a more balanced profile:
>
> samples  %        symbol name
> 8079     23.3984  scm_string_eq
> 5649     16.3606  vm_debug_engine
> 5624     16.2882  scm_i_str2symbol
                    ^ What is this doing here?

And for the matter, what are the rest about? Did you just do a really
short profile?

> 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

Andy
-- 
http://wingolog.org/

Re: Optimizing ‘string=’

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> writes:

> On Tue 22 Jun 2010 21:40, ludo@gnu.org (Ludovic Courtès) writes:
>
>> @@ -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);
>> +    }
>> +
>
> Nasty, but OK I guess if you need it. Why not also add a fast path for
> scm_is_eq (s1, s2), or for comparing stringbufs, or something ?

Hmm yes.  Though if there are too many fast paths the whole thing ends
up being slow.  ;-)

I don’t expect (eq? s1 s2) and (eq? (string-buf s1) (string-buf s2)) to
be common enough to warrant a more specific special case, though.

>> It’s quite inelegant, but it leads to a more balanced profile:
>>
>> samples  %        symbol name
>> 8079     23.3984  scm_string_eq
>> 5649     16.3606  vm_debug_engine
>> 5624     16.2882  scm_i_str2symbol
>                     ^ What is this doing here?

I comes from the ‘load-symbol’ instruction.

Indeed, the loop’s body goes like this:

--8<---------------cut here---------------start------------->8---
  36    (new-frame)                     
  37    (load-symbol "string=")         ;; string=
  48    (link-now)                      
  49    (variable-ref)                  
  50    (load-symbol "s")               ;; s
  55    (link-now)                      
  56    (variable-ref)                  
  57    (load-symbol "s")               ;; s
  62    (link-now)                      
  63    (variable-ref)                  
  64    (mv-call 2 :L39)                ;; MV -> 74
  69    (drop)                          
  70    (br :L40)                       ;; -> 77
  74    (truncate-values 0 0)           
  77    (br :L41)                       ;; -> 36
  81    (br :L41)                       ;; -> 36
--8<---------------cut here---------------end--------------->8---

Because it’s a top-level program, “string=” is looked up at each
iteration.

If we instead do:

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

(define (foo)
  (let loop ()
    (string= s s)
    (loop)))

(foo)
--8<---------------cut here---------------end--------------->8---

we get:

--8<---------------cut here---------------start------------->8---
   0    (assert-nargs-ee/locals 0)      
   2    (br :L38)                       ;; -> 30
   6    (new-frame)                     
   7    (toplevel-ref 1)                
   9    (toplevel-ref 2)                
  11    (toplevel-ref 2)                
  13    (mv-call 2 :L39)                ;; MV -> 23
  18    (drop)                          
  19    (br :L40)                       ;; -> 26
  23    (truncate-values 0 0)           
  26    (br :L41)                       ;; -> 6
  30    (br :L41)                       ;; -> 6
--8<---------------cut here---------------end--------------->8---

and thus presumably no ‘scm_i_str2symbol’.

> And for the matter, what are the rest about?

Lookups of ‘string=’.

> Did you just do a really short profile?

Yes.

Ludo’.

Re: Optimizing ‘string=’

[Andy Wingo]

Greets,

On Tue 22 Jun 2010 23:32, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> Nasty, but OK I guess if you need it. Why not also add a fast path for
>> scm_is_eq (s1, s2), or for comparing stringbufs, or something ?
>
> Hmm yes.  Though if there are too many fast paths the whole thing ends
> up being slow.  ;-)

> I don’t expect (eq? s1 s2) and (eq? (string-buf s1) (string-buf s2)) to
> be common enough to warrant a more specific special case, though.

Does it affect your original case at all?. In any event, it doesn't
involve a memory dereference, only a branch. It's a cheap check.

> Because it’s a top-level program, “string=” is looked up at each
> iteration.

Ah, right. Thanks for the explanation :)

Andy
-- 
http://wingolog.org/

Re: Optimizing ‘string=’

[Mike Gran]

> From: Ludovic Courtès ludo@gnu.org

> Oops, there was a thinko in the patch, whereby wide strings would not 
> be entirely compared.  Here’s an updated one:

Looks good to me.

Perhaps skip the memcmp if the string lengths are zero?  

At some point probably should replace all hardcoded '4'
in libguile with some #define.

-Mike

Re: Optimizing ‘string=’

[Ludovic Courtès]

Hello Andy!

Andy Wingo <wingo@pobox.com> writes:

> On Tue 22 Jun 2010 23:32, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Andy Wingo <wingo@pobox.com> writes:
>>
>>> Nasty, but OK I guess if you need it. Why not also add a fast path for
>>> scm_is_eq (s1, s2), or for comparing stringbufs, or something ?
>>
>> Hmm yes.  Though if there are too many fast paths the whole thing ends
>> up being slow.  ;-)
>
>> I don’t expect (eq? s1 s2) and (eq? (string-buf s1) (string-buf s2)) to
>> be common enough to warrant a more specific special case, though.
>
> Does it affect your original case at all?

No, I was just comparing strings not eq?.

> In any event, it doesn't involve a memory dereference, only a
> branch. It's a cheap check.

Even cheaper to not do it.  :-)

Thanks,
Ludo’.