Up until now, there were 4 cases of using sprintf to copy a string in the do_paste() routine. This can potentially be expensive, especially since we compile with the debugging flag (-g) and so may not gain from optimizations the compiler can infer. So we look here at 3 different ways of implementing this string copying: strcpy(), memcpy() and sprintf(). The following are the times taken to execute some S expressions involving paste(). They are not typical, but do exercise different parts of paste and are focus on the string copying.

Franz

The following are the times for a very simple paste. These results are from running on franz with the default installed version (today's snapshot) and my modified version that has code for all three approaches. The relative improvements are the same as on my machine.

New strcpy() version

> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 4.98 0.03 5.84 0.00 0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 4.80 0.06 5.66 0.00 0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 4.84 0.03 5.87 0.00 0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 4.83 0.03 5.87 0.00 0.00

Old-Style sprintf() version

> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1]  9.41  0.01 12.91  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1]  9.46  0.04 11.07  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1]  9.38  0.00 10.93  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1]  9.37  0.04 11.05  0.00  0.00

A longer computation

strcpy()

> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1]  9.41  0.02 11.00  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1]  9.40  0.02 10.98  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1]  9.44  0.02 11.02  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1]  9.37  0.01 10.93  0.00  0.00  

sprintf

> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 21.20  0.03 24.84  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 21.19  0.02 24.94  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 21.20  0.01 24.76  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 21.29  0.04 25.95  0.00  0.00

Computations involving collapse

Again on franz, we make comparison against the standard installed R (/usr/local/bin/R). This time, we use two vectors and collapse the result. This hopefully exercises all 4 cases of the string copying in do_paste(). The regular R gives
> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", collapse=" + ")})
[1] 29.72 0.08 34.95 0.00 0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", collapse=" + ")})
[1] 29.60 0.05 34.91 0.00 0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", collapse=" + ")})
[1] 29.66 0.03 35.06 0.00 0.00

With the new version, using strcpy:

> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", colla\pse=" + ")})
[1] 6.87 0.04 8.50 0.00 0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", colla\pse=" + ")})
[1] 6.78 0.03 7.95 0.00 0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", colla\pse=" + ")})
[1] 6.72 0.04 7.91 0.00 0.00

Duncan's Laptop

Regular R
> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", collapse=" + ")})
[1] 61.80  0.17 62.82  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", collapse=" + ")})
[1] 61.76  0.13 63.92  0.00  0.00

Version using strcpy.

> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", collapse=" + ")})
[1] 14.91  0.16 15.22  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), letters, sep="*", collapse=" + ")})
[1] 14.64  0.09 14.88  0.00  0.00

Duncan's Laptop

The following are comparisons of different three different approaches for handling the string copying. These are

Using memcpy

> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 11.82  0.18 20.18  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 11.17  0.10 11.38  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 11.05  0.08 11.24  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 10.98  0.09 11.18  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 11.16  0.14 11.42  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 11.13  0.17 11.74  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 10.93  0.11 11.15  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 10.96  0.10 11.17  0.00  0.00
memcpy with a larger vector.
system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 19.72  0.07 20.07  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 19.57  0.09 19.97  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 19.63  0.04 19.86  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 20.49  0.02 20.72  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 20.43  0.05 20.69  0.00  0.00

Using strcpy()

> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 10.37  0.07 10.54  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 10.08  0.13 10.31  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 10.20  0.06 10.41  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 19.76  0.12 21.02  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 19.24  0.15 19.58  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 19.47  0.18 19.85  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 19.30  0.09 19.60  0.00  0.00
> > system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 19.08  0.08 19.36  0.00  0.00
> 

Original sprintf

Using the original sprintf() mechanism. (Check these are the correct settings)
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 19.72  0.07 20.07  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 19.57  0.09 19.97  0.00  0.00
> system.time(for(i in 1:10000){paste(rep(letters, 20), sep="*")})
[1] 19.63  0.04 19.86  0.00  0.00
And the larger input vector.
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 42.62  0.16 45.68  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 42.37  0.09 42.89  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 41.95  0.08 42.65  0.00  0.00
> system.time(for(i in 1:1000){paste(rep(letters, 500), sep="*")})
[1] 41.59  0.07 42.45  0.00  0.00

Code

This is the code used to generate the second collection of timings comparing the different approaches: memcpy, strcpy and sprintf. Set USE_OLD to 1 to use the original sprintf approach. Set USE_MEMCPY to 1 to use memcpy. And set them both to 0 to use strcpy
#define USE_OLD 0
#define USE_MEMCPY 1

SEXP do_paste(SEXP call, SEXP op, SEXP args, SEXP env)
{
    SEXP ans, collapse, sep, x, tmpchar;
    int i, j, k, maxlen, nx, pwidth, sepw;
    char *s, *buf;

    checkArity(op, args);

    /* We use formatting and so we */
    /* must initialize printing. */

    PrintDefaults(env);

    /* Check the arguments */

    x = CAR(args);
    if (!isVectorList(x))
	errorcall(call, "invalid first argument");

    sep = CADR(args);
    if (!isString(sep) || LENGTH(sep) <= 0)
	errorcall(call, "invalid separator");
    sep = STRING_ELT(sep, 0);
    sepw = LENGTH(sep);

    collapse = CADDR(args);
    if (!isNull(collapse))
	if(!isString(collapse) || LENGTH(collapse) <= 0)
	    errorcall(call, "invalid collapse argument");

    /* Maximum argument length and */
    /* check for arguments of list type */

    nx = length(x);
    maxlen = 0;
    for (j = 0; j < nx; j++) {
	if (!isString(VECTOR_ELT(x, j)))
	    error("non-string argument to Internal paste");
	if(length(VECTOR_ELT(x, j)) > maxlen)
	    maxlen = length(VECTOR_ELT(x, j));
    }
    if(maxlen == 0)
	return mkString("");

    PROTECT(ans = allocVector(STRSXP, maxlen));

    for (i = 0; i < maxlen; i++) {
	pwidth = 0;
	for (j = 0; j < nx; j++) {
	    k = length(VECTOR_ELT(x, j));
	    if (k > 0)
		pwidth += LENGTH(STRING_ELT(VECTOR_ELT(x, j), i % k));
	}
	pwidth += (nx - 1) * sepw;
	tmpchar = allocString(pwidth);
	buf = CHAR(tmpchar);
	for (j = 0; j < nx; j++) {
	    k = length(VECTOR_ELT(x, j));
	    if (k > 0) {
		s = CHAR(STRING_ELT(VECTOR_ELT(x, j), i % k));
#if USE_OLD
		sprintf(buf, "%s", s);
#else
#if USE_MEMCPY
		memcpy(buf, s, strlen(s));
		buf[strlen(s)] = '\0';
#else
                strcpy(buf,s);
#endif
#endif
		buf += LENGTH(STRING_ELT(VECTOR_ELT(x, j), i % k));
	    }
	    if (j != nx - 1 && sepw != 0) {
#if USE_OLD
  	        sprintf(buf, "%s", CHAR(sep)); 
#else
#if USE_MEMCPY
		memcpy(buf, CHAR(sep), LENGTH(sep));
		buf[LENGTH(sep)] = '\0';
#else
	        strcpy(buf, CHAR(sep));
#endif
#endif
		buf += sepw;
	    }
	}
	SET_STRING_ELT(ans, i, tmpchar);
    }

    /* Now collapse, if required. */

    if(collapse != R_NilValue && (nx=LENGTH(ans)) != 0) {
	sep = STRING_ELT(collapse, 0);
	sepw = LENGTH(sep);
	pwidth = 0;
	for (i = 0; i < nx; i++)
	    pwidth += LENGTH(STRING_ELT(ans, i));
	pwidth += (nx - 1) * sepw;
	tmpchar = allocString(pwidth);
	buf = CHAR(tmpchar);
	for (i = 0; i < nx; i++) {
	    if(i > 0) {
#if USE_OLD
	        sprintf(buf, "%s", CHAR(sep)); 
#else
#if USE_MEMCPY
	        memcpy(buf, CHAR(sep), LENGTH(sep));
	        buf[LENGTH(sep)] = '\0';
#else
	        strcpy(buf, CHAR(sep));
#endif
#endif
		buf += sepw;
	    }
	    s = CHAR(STRING_ELT(ans, i));
#if USE_OLD
	    sprintf(buf, "%s", s); 
	    while (*buf)
		buf++;
#else
#if USE_MEMCPY
	    { int n;
	    if((n = LENGTH(STRING_ELT(ans,i))) > 0) {
              memcpy(buf, s, n);
	    }
             
             buf[n] ='\0';
             buf += n;       
	    }
#else
            strcpy(buf, s);
	    while (*buf)
		buf++;
#endif
#endif
	}
	PROTECT(tmpchar);
	ans = allocVector(STRSXP, 1);
	UNPROTECT(1);
	SET_STRING_ELT(ans, 0, tmpchar);
    }
    UNPROTECT(1);
    return ans;
}

Duncan Temple Lang <duncan@research.bell-labs.com>
Last modified: Sat May 5 15:07:54 EDT 2001