Re: string vs list processing

[Harvey J. Stein]

Sascha Ziemann <address@hidden> writes:

 > Sascha Ziemann <address@hidden> writes:
 > 
 > | The following example compares string-ref directly with list-ref:
 > | 
 > | (let* ((str (string-append (list->string (make-list 1000 #\A))))
 > |        (lst (string->list str))
 > |        (len (1- (length lst)))
 > |        (len/2 (quotient len 2)))
 > |   (compare-run-time 100000
 > |     (string-ref str 0)
 > |     (list-ref lst 0)
 > |     (string-ref str len/2)
 > |     (list-ref lst len/2)
 > |     (string-ref str len)
 > |     (list-ref lst len)))
 > | ;;   1.21 seconds for 100000 times (string-ref str 0)
 > | ;;   1.24 seconds for 100000 times (list-ref lst 0)
 > | ;;   1.24 seconds for 100000 times (string-ref str len/2)
 > | ;;   1.88 seconds for 100000 times (list-ref lst len/2)
 > | ;;   1.22 seconds for 100000 times (string-ref str len)
 > | ;;   2.58 seconds for 100000 times (list-ref lst len)
 > 
 > The calculation was not fair.  I removed the time spend for the
 > iterations and now the result looks different:
 > 
 > ;;   0.35 seconds for 100000 times (string-ref str 0)
 > ;;   0.34 seconds for 100000 times (list-ref lst 0)
 > ;;   0.37 seconds for 100000 times (string-ref str len/2)
 > ;;   1.03 seconds for 100000 times (list-ref lst len/2)
 > ;;   0.36 seconds for 100000 times (string-ref str len)
 > ;;   1.74 seconds for 100000 times (list-ref lst len)
 > 
 > But I think avoiding string functions is still a good idea.

That (string-ref str 0) takes about the same time as (list-ref lst 0)
is good.  The string ref is checking arguments, indexing into the
array & returning a char.  The list-ref is checking arguments &
dereferencing car of lst.  Actually, I'm a little surprised that
(string-ref ...) isn't slower.  Doesn't the string-ref have to malloc
to create the character that it's returning, whereas the list-ref
doesn't?  Or are all the char objects built in & (string-ref...) is
just returning a ptr to one of them?

The fact that (list-ref lst 10000) takes about 5x longer than (list-ref
lst 0) indicates that most of the .34 seconds for (list-ref lst 0) is
in interpreter overhead.  I wouldn't be surprised if more benchmarking
were to discover the general rule of thumb that the code that makes
the least fcn calls is the fastest.  That is - count the # of times
each primitive (coded in C) fcn is called when executing some piece of
code & you'll have a good estimator for the time the fcn takes.  When
this is violated, it indicates the existence of a primitive which is
extremely slow (like possibly the regexp stuff, which I've benchmarked
before).

-- 
Harvey Stein
Bloomberg LP
address@hidden