missing REPLACE transforms for strings

[Nikodemus Siivola]

FOO2 is 20 times faster than either FOO1 or FOO2. I think it would be reasonable for even a plain STRING declaration be enough to bring a specialized -- if not inlined -- version in play.

(defun foo0 (s1 s2)
  (declare (simple-string s1 s2))
  (replace s1 s2))

(defun foo1 (s1 s2)
  (declare (type (and simple-string (not simple-base-string)) s1 s2))
  (replace s1 s2))

(defun foo2 (s1 s2)
  (declare (type (simple-array character (*)) s1 s2))
  (replace s1 s2))

[MrOrdinaire (mrordinaire)]

hi, I'd like to take on this bug. could you give me some pointers on how to get started?

[Stas Boukarev (stassats)]

In slime, press M-. on replace. You'll see lots of :DEFTRANSFORM, select one of them, and you'll see how they're generated.

So, to add support transforms for simple strings, try adding (define-one-transform simple-string simple-string) to the macrolet body (and other combinations, like simple-string <=> simple-base-string).
For non-inline version, a function which would do the copying needs to be defined and then a transform to that function, something like:

(deftransform replace ((string1 string2) (simple-string simple-string) simple-string)
  `(replace-simple-strings string1 string2))

A macro for defining for all the combinations of simple-string with simple-base-string and (simple-array character (*)) could be useful.

[Paul Khuong (pvk)]

Not quite. The problem is that simple-string is an union type: it could be a simple-base-string or a (simple-array character 1) (or a simple-array nil, but that's not that important). Without additional runtime type dispatch, DEFINE-ONE-TRANSFORM will have to call generic array accessors.

The best way is probably to have code that does something like

(typecase string1
  (simple-base-string
   (typecase string2
     (simple-base-string
      (replace ...))
     ((simple-array character 1)
      (replace ...))
     (t ; simple-array nil
      (error ...))))
  ((simple-array character 1)
   (typecase string2
     (simple-base-string
      (replace ...))
     ((simple-array character 1)
      (replace ...))
     (t
      (error ...))))
  (t
   (error ...)))

I'm pretty sure I would rather have this in an out of line function (let's call it %replace-simple-strings).

The problem is that a transform that substitutes a call to %replace-simple-strings instead of regular REPLACE might trigger when a more specific transform would. I see two and a half complementary measures:

1. transforms that are defined last are executed first, so we want to define the one that calls to %replace-simple-strings before the define-replace-transforms block;
2 a) more specific transforms might only trigger after constraint propagation has tightened derived types; DELAY-IR1-TRANSFORM/:CONSTRAINT can help there;
2 b) add some transforms to specialise calls to %replace-simple-strings like we currently do for calls to REPLACE.

Defining new out-of-line functions is a bit of work: you have to find a good spot to put the definition (in this case, src/code/seq.lisp would make sense), edit package definitions to export the symbol (see package-data-list.lisp-expr), and then create the transform. However, that's only needed for a fresh build. Nearly all the development can be done on a live image, including (re)defining new transforms [*] that expand into calls to CL-USER::%REPLACE-SIMPLE-STRINGS or whatever you want.

[*] For that to work well, you want to write a docstring. If the types and docstring match, the previous definition will be overwritten.

Now, particularly if one of the strings is more specifically typed (e.g. one is a simple-string but the other a simple-base-string), it might be worth it to inline the typecase. If you do that, the transform might trigger recursively. Simply adding a call to DELAY-IR1-TRANSFORM would work. A wordier and slightly less modular approach is to directly emit the code that would be inlined instead of the REPLACE forms. Factoring a chunk out of make-replace-transform will probably be necessary then. The advantage is that the transform won't slow down compilation as much and will work even if contraint propagation is eventually disabled.

I also noticed that these optimisations only happen for simple-arrays. There's probably a decent win to be had by handling potentially non-simple arrays via with-array-data, but that's completely a different project.

[Paul Khuong (pvk)]

One last note: stuff foo1 would be interesting to handle. There are only two cases, a simple array nil (we don't particularly care about doing nothing or signalling errors efficiently), and (simple-array character 1). So really, only one real case is left: a pair of (simple-array character 1).

[MrOrdinaire (mrordinaire)]

Wow, that is a lot of info to take in. I am sorry but I don't quite understand what you two said. Could you suggest some more reading materials or maybe point me to some other bugs that suits a newbie more?

[MrOrdinaire (mrordinaire)]

Is this patch going in the right direction?

[MrOrdinaire (mrordinaire)]

@pvk: adding (define-one-transform (simple-array character 1) (simple-array character 1)) to the progn body at line 871 seems to make the compiler go into infinite recursion

[Paul Khuong (pvk)]

I haven't had time to go in details to determine what's going on, but (simple-array character 1) -> (simple-array character 1) is already defined via (define-replace-transforms), which transforms for [type] -> [type] REPLACE, for each specialised array type.

Adding transforms for
  (define-one-transform simple-string {simple-base-string, (simple-array character 1)})
and vice versa is an easy fix, but far from the best we can do. Moreover, it doesn't address the common situation of simple-string -> simple-string.

SBCL mostly works via source-to-source transformations. I find it easiest to design such transforms by first trying to write the code I'd like the compiler to come up with. Once I have something that seems to work (and that results in better code), I figure out how to express it as a transform. You could try to write a function efficiently perform REPLACE on from one simple-string to another, when you'll only know at runtime which specific element type you'll get. I sketched what such a function could look like in my previous post.

[Douglas Katzman (dougk)]

string replace transforms for simple-base <-> simple-character were present as of https://sourceforge.net/p/sbcl/sbcl/ci/260a9146f023
so I'm not really sure what was being asked here- Maybe runtime determination of the best replace routine for compile-time-unknown element-type? I suspect we do that now.
And the initial comment is unclear - FOO2 is faster than FOO2 ???

At any rate, I found that for a string of about 100 mega-characters, all of FOO0, FOO1, and FOO2 perform roughly the same, certainly not 20x apart. And at that string length, memory cache behavior is the dominating factor. So I can't really say what we do for short strings because they're too small to measure and I didn't bother to check.