Re: Optimizing ‘string=’

[ludo@gnu.org (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’.