[RFC] temporary Lisp_Strings

[RFC] temporary Lisp_Strings

[Dmitry Antipov]

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

I'm thinking about temporary Lisp_Strings on C stack (allocated with alloca).
Simple implementation (with no check whether it fits on stack) and a few use
cases attached.  Among others, the question is: is there a way to make sure
that an address returned by alloca fits in Lisp_Object?

Dmitry



[-- Attachment #2: alloca_string.patch --]
[-- Type: text/x-patch, Size: 2374 bytes --]

=== modified file 'src/fileio.c'
--- src/fileio.c	2014-09-02 11:41:22 +0000
+++ src/fileio.c	2014-09-02 11:47:45 +0000
@@ -1179,11 +1179,11 @@
 	      char newdir_utf8[MAX_UTF8_PATH];
 
 	      filename_from_ansi (newdir, newdir_utf8);
-	      tem = build_string (newdir_utf8);
+	      tem = alloca_string (newdir_utf8);
 	    }
 	  else
 #endif
-	    tem = build_string (newdir);
+	    tem = alloca_string (newdir);
 	  newdirlen = SBYTES (tem);
 	  if (multibyte && !STRING_MULTIBYTE (tem))
 	    {
@@ -1215,7 +1215,7 @@
 	      /* `getpwnam' may return a unibyte string, which will
 		 bite us since we expect the directory to be
 		 multibyte.  */
-	      tem = build_string (newdir);
+	      tem = alloca_string (newdir);
 	      newdirlen = SBYTES (tem);
 	      if (multibyte && !STRING_MULTIBYTE (tem))
 		{
@@ -1249,7 +1249,7 @@
 	    adir = NULL;
 	  else if (multibyte)
 	    {
-	      Lisp_Object tem = build_string (adir);
+	      Lisp_Object tem = alloca_string (adir);
 
 	      tem = DECODE_FILE (tem);
 	      newdirlen = SBYTES (tem);
@@ -1350,7 +1350,7 @@
 	    getcwd (adir, adir_size);
 	  if (multibyte)
 	    {
-	      Lisp_Object tem = build_string (adir);
+	      Lisp_Object tem = alloca_string (adir);
 
 	      tem = DECODE_FILE (tem);
 	      newdirlen = SBYTES (tem);

=== modified file 'src/lisp.h'
--- src/lisp.h	2014-09-02 06:49:40 +0000
+++ src/lisp.h	2014-09-02 12:31:01 +0000
@@ -4459,6 +4459,25 @@
   memcpy (alloca (SBYTES (string) + 1),		\
 	  SSDATA (string), SBYTES (string) + 1)
 
+/* Create temporary Lisp_String.  Use alloca and do not disturb GC.  */
+
+#define alloca_string(str)					\
+  ({ Lisp_Object string;					\
+     struct Lisp_String *s;					\
+     ptrdiff_t nchars, nbytes, size = strlen (str);		\
+     parse_str_as_multibyte ((const unsigned char *) str,	\
+			     size, &nchars, &nbytes);		\
+     s = alloca (sizeof *s + nbytes + 1);			\
+     s->data = (unsigned char *) s + sizeof (*s);		\
+     memcpy (s->data, str, nbytes);				\
+     s->data[size] = '\0';					\
+     s->intervals = NULL;					\
+     if (nbytes == nchars || nbytes != size)			\
+       s->size = size, s->size_byte = -1;			\
+     else							\
+       s->size = nchars, s->size_byte = nbytes;		\
+     XSETSTRING (string, s); string; })
+  
 /* Set up the name of the machine we're running on.  */
 extern void init_system_name (void);
 

[RFC] temporary Lisp_Strings

[Dmitry Antipov]

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

I'm thinking about temporary Lisp_Strings on C stack (allocated with alloca).
Simple implementation (with no check whether it fits on stack) and a few use
cases attached.  Among others, the question is: is there a way to make sure
that an address returned by alloca fits in Lisp_Object?

Dmitry



[-- Attachment #2: alloca_string.patch --]
[-- Type: text/x-patch, Size: 2374 bytes --]

=== modified file 'src/fileio.c'
--- src/fileio.c	2014-09-02 11:41:22 +0000
+++ src/fileio.c	2014-09-02 11:47:45 +0000
@@ -1179,11 +1179,11 @@
 	      char newdir_utf8[MAX_UTF8_PATH];
 
 	      filename_from_ansi (newdir, newdir_utf8);
-	      tem = build_string (newdir_utf8);
+	      tem = alloca_string (newdir_utf8);
 	    }
 	  else
 #endif
-	    tem = build_string (newdir);
+	    tem = alloca_string (newdir);
 	  newdirlen = SBYTES (tem);
 	  if (multibyte && !STRING_MULTIBYTE (tem))
 	    {
@@ -1215,7 +1215,7 @@
 	      /* `getpwnam' may return a unibyte string, which will
 		 bite us since we expect the directory to be
 		 multibyte.  */
-	      tem = build_string (newdir);
+	      tem = alloca_string (newdir);
 	      newdirlen = SBYTES (tem);
 	      if (multibyte && !STRING_MULTIBYTE (tem))
 		{
@@ -1249,7 +1249,7 @@
 	    adir = NULL;
 	  else if (multibyte)
 	    {
-	      Lisp_Object tem = build_string (adir);
+	      Lisp_Object tem = alloca_string (adir);
 
 	      tem = DECODE_FILE (tem);
 	      newdirlen = SBYTES (tem);
@@ -1350,7 +1350,7 @@
 	    getcwd (adir, adir_size);
 	  if (multibyte)
 	    {
-	      Lisp_Object tem = build_string (adir);
+	      Lisp_Object tem = alloca_string (adir);
 
 	      tem = DECODE_FILE (tem);
 	      newdirlen = SBYTES (tem);

=== modified file 'src/lisp.h'
--- src/lisp.h	2014-09-02 06:49:40 +0000
+++ src/lisp.h	2014-09-02 12:31:01 +0000
@@ -4459,6 +4459,25 @@
   memcpy (alloca (SBYTES (string) + 1),		\
 	  SSDATA (string), SBYTES (string) + 1)
 
+/* Create temporary Lisp_String.  Use alloca and do not disturb GC.  */
+
+#define alloca_string(str)					\
+  ({ Lisp_Object string;					\
+     struct Lisp_String *s;					\
+     ptrdiff_t nchars, nbytes, size = strlen (str);		\
+     parse_str_as_multibyte ((const unsigned char *) str,	\
+			     size, &nchars, &nbytes);		\
+     s = alloca (sizeof *s + nbytes + 1);			\
+     s->data = (unsigned char *) s + sizeof (*s);		\
+     memcpy (s->data, str, nbytes);				\
+     s->data[size] = '\0';					\
+     s->intervals = NULL;					\
+     if (nbytes == nchars || nbytes != size)			\
+       s->size = size, s->size_byte = -1;			\
+     else							\
+       s->size = nchars, s->size_byte = nbytes;		\
+     XSETSTRING (string, s); string; })
+  
 /* Set up the name of the machine we're running on.  */
 extern void init_system_name (void);
 

Re: [RFC] temporary Lisp_Strings

[Andreas Schwab]

Dmitry Antipov <dmantipov@yandex.ru> writes:

> I'm thinking about temporary Lisp_Strings on C stack (allocated with alloca).
> Simple implementation (with no check whether it fits on stack) and a few use
> cases attached.  Among others, the question is: is there a way to make sure
> that an address returned by alloca fits in Lisp_Object?

There is none.  The stack could be in a completely different address
region that may not be suitable in non-USE_LSB_TAG configurations.

> +#define alloca_string(str)					\
> +  ({ Lisp_Object string;					\
> +     struct Lisp_String *s;					\
> +     ptrdiff_t nchars, nbytes, size = strlen (str);		\
> +     parse_str_as_multibyte ((const unsigned char *) str,	\
> +			     size, &nchars, &nbytes);		\
> +     s = alloca (sizeof *s + nbytes + 1);			\
> +     s->data = (unsigned char *) s + sizeof (*s);		\
> +     memcpy (s->data, str, nbytes);				\
> +     s->data[size] = '\0';					\
> +     s->intervals = NULL;					\
> +     if (nbytes == nchars || nbytes != size)			\
> +       s->size = size, s->size_byte = -1;			\
> +     else							\
> +       s->size = nchars, s->size_byte = nbytes;		\
> +     XSETSTRING (string, s); string; })

This will eventually fail with USE_LSB_TAG, since you don't enforce
alignment.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [RFC] temporary Lisp_Strings

[Dmitry Antipov]

On 09/02/2014 05:21 PM, Andreas Schwab wrote:

> There is none.  The stack could be in a completely different address
> region that may not be suitable in non-USE_LSB_TAG configurations.

IIUC non-USE_LSB_TAG configurations are not widely used, so this is
a tier-2 problem.

>> +#define alloca_string(str)					\
>> +  ({ Lisp_Object string;					\
>> +     struct Lisp_String *s;					\
>> +     ptrdiff_t nchars, nbytes, size = strlen (str);		\
>> +     parse_str_as_multibyte ((const unsigned char *) str,	\
>> +			     size, &nchars, &nbytes);		\
>> +     s = alloca (sizeof *s + nbytes + 1);			\
>> +     s->data = (unsigned char *) s + sizeof (*s);		\
>> +     memcpy (s->data, str, nbytes);				\
>> +     s->data[size] = '\0';					\
>> +     s->intervals = NULL;					\
>> +     if (nbytes == nchars || nbytes != size)			\
>> +       s->size = size, s->size_byte = -1;			\
>> +     else							\
>> +       s->size = nchars, s->size_byte = nbytes;		\
>> +     XSETSTRING (string, s); string; })
>
> This will eventually fail with USE_LSB_TAG, since you don't enforce
> alignment.

What about alignment guaranteed by alloca?  IIUC compilers tends
to align it enough to US_LSB_TAG:

http://msdn.microsoft.com/en-us/library/x9sx5da1.aspx
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55945

Dmitry

Re: [RFC] temporary Lisp_Strings

[Stefan Monnier]

> I'm thinking about temporary Lisp_Strings on C stack (allocated with alloca).
> Simple implementation (with no check whether it fits on stack) and a few use
> cases attached.  Among others, the question is: is there a way to make sure
> that an address returned by alloca fits in Lisp_Object?

Have you made some preliminary measurements (on microbenchmarks) to try
and see how much speed up we might gain?  Given the cost of strlen and
parse_str_as_multibyte, I'd expect that the best-case benefit might turn
out to be rather small.


        Stefan

Re: [RFC] temporary Lisp_Strings

[Andreas Schwab]

Dmitry Antipov <dmantipov@yandex.ru> writes:

> What about alignment guaranteed by alloca?

You only get as much as the architecture requires.

> IIUC compilers tends to align it enough to US_LSB_TAG:

tends != guarantees.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [RFC] temporary Lisp_Strings

[Paul Eggert]

What would the GC do when it sees such a string?  Wouldn't this make the 
GC a bit less robust, as it couldn't diagnose bogus strings any more 
when GC_CHECK_MARKED_OBJECTS is defined?

Like Stefan, I wonder how much performance benefit you're really gaining 
here.  Presumably most of it is lack of pressure on the GC, and how do 
you measure that?

I assume you're thinking of eventually doing this for conses etc. too?

Dmitry Antipov wrote:
> is there a way to make sure that an address returned by alloca fits in Lisp_Object?

It should work on typical platforms, as alloca should return an address 
that is aligned well enough for Emacs, just as malloc does.  Perhaps we 
may run into an oddball platform where alloca isn't suitably aligned, 
but if so we can simply allocate a few more bytes than needed and then 
align the pointers ourselves.  For starters, though, I'd just assume 
that it's aligned.  An Emacs built with ENABLE_CHECKING should verify 
any alignment issues already, as make_lisp_ptr checks for this.

We don't need to worry about !USE_LSB_TAG on the trunk anymore, as 
support for abusing the high-order bits of pointers has been withdrawn 
on the trunk.

Re: [RFC] temporary Lisp_Strings

[Eli Zaretskii]

> Date: Tue, 02 Sep 2014 17:47:15 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> Cc: Emacs development discussions <emacs-devel@gnu.org>
> 
> What about alignment guaranteed by alloca?  IIUC compilers tends
> to align it enough to US_LSB_TAG:
> 
> http://msdn.microsoft.com/en-us/library/x9sx5da1.aspx

This is not relevant, it talks about the Microsoft compiler.

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55945

This is only about x64, AFAICT.

Re: [RFC] temporary Lisp_Strings

[Dmitry Antipov]

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

On 09/02/2014 06:00 PM, Stefan Monnier wrote:

> Have you made some preliminary measurements (on microbenchmarks) to try
> and see how much speed up we might gain?  Given the cost of strlen and
> parse_str_as_multibyte, I'd expect that the best-case benefit might turn
> out to be rather small.

For the moment, I don't have an idea how to benchmark parse_str_as_multibyte
in "near-to-real-use" conditions.  But I guess that we can have some gain
for "simple" (short, especially short unibyte) strings. That guess is based
on the following results (note ~3x speedup in strcpy/strcat workload):

$ gcc -Wall -O2 -o t-alloca t-alloca.c t-use.c
$
$ /usr/bin/time ./t-alloca 100 100
Use malloc for allocation and sprintf for workload
2.23user 0.00system 0:02.23elapsed 100%CPU (0avgtext+0avgdata 1440maxresident)k
0inputs+0outputs (0major+59minor)pagefaults 0swaps
$
$ /usr/bin/time ./t-alloca 100 100 x
Use alloca for allocation and sprintf for workload
1.85user 0.00system 0:01.85elapsed 99%CPU (0avgtext+0avgdata 1436maxresident)k
0inputs+0outputs (0major+59minor)pagefaults 0swaps
$
$ gcc -DFAST -Wall -O2 -o t-alloca t-alloca.c t-use.c
$
$ /usr/bin/time ./t-alloca 100 100
Use malloc for allocation and strcpy/strcat for workload
0.56user 0.00system 0:00.56elapsed 99%CPU (0avgtext+0avgdata 1440maxresident)k
0inputs+0outputs (0major+59minor)pagefaults 0swaps
$
$ /usr/bin/time ./t-alloca 100 100 x
Use alloca for allocation and strcpy/strcat for workload
0.20user 0.00system 0:00.20elapsed 100%CPU (0avgtext+0avgdata 1440maxresident)k
0inputs+0outputs (0major+60minor)pagefaults 0swaps

Dmitry


[-- Attachment #2: t-alloca.c --]
[-- Type: text/x-csrc, Size: 874 bytes --]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef FAST
#define FUNCNAME "strcpy/strcat"
#else
#define FUNCNAME "sprintf"
#endif

extern void use_with_malloc (char *, int, char *, int);
extern void use_with_alloca (char *, int, char *, int);

int
main (int argc, char *argv[])
{
  char *p1, *p2;
  int i, len1, len2;

  if (argc >= 3)
    {
      len1 = atoi (argv[1]);
      len2 = atoi (argv[2]);

      p1 = malloc (len1 + 1);
      memset (p1, 'a', len1);
      p1[len1] = '\0';

      p2 = malloc (len2 + 1);
      memset (p1, 'b', len2);
      p2[len2] = '\0';

      printf ("Use %s for allocation and %s for workload\n",
	      (argc == 3) ? "malloc" : "alloca", FUNCNAME);

      for (i = 0; i < 10000000; i++)
	{
	  if (argc == 3)
	    use_with_malloc (p1, len1, p2, len2);
	  else
	    use_with_alloca (p1, len1, p2, len2);
	}
    }
  return 0;
}

[-- Attachment #3: t-use.c --]
[-- Type: text/x-csrc, Size: 499 bytes --]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *ptr;

void
use_with_malloc (char *p, int plen, char *q, int qlen)
{
  ptr = malloc (plen + qlen + 1);
#ifdef FAST
  strcpy (ptr, p);
  strcat (ptr, q);
#else
  sprintf (ptr, "%s%s", p, q);
#endif
  (void) ptr;
  free (ptr);
}

void
use_with_alloca (char *p, int plen, char *q, int qlen)
{
  ptr = alloca (plen + qlen + 1);
#ifdef FAST
  strcpy (ptr, p);
  strcat (ptr, q);
#else
  sprintf (ptr, "%s%s", p, q);
#endif
  (void) ptr;
}

Re: [RFC] temporary Lisp_Strings

[Dmitry Antipov]

On 09/02/2014 06:37 PM, Paul Eggert wrote:

> What would the GC do when it sees such a string?

In theory, such a strings are out of GC's scope:
- If GC_MARK_STACK == GC_MAKE_GCPROS_NOOPS, such a string is never recorded
   in rb-tree and so GC should not recognize it as a collectable object;
- If GC_MARK_STACK == GC_USE_GCPROS_AS_BEFORE:
   - If you GCPRO such a string, this is fatal error;
   - Otherwise GC just silently ignores it.

> Wouldn't this make the GC a bit less robust, as it couldn't diagnose
> bogus strings any more when GC_CHECK_MARKED_OBJECTS is defined?

No ideas yet, this should be investigated.

Dmitry

Re: [RFC] temporary Lisp_Strings

[Dmitry Antipov]

On 09/02/2014 06:37 PM, Paul Eggert wrote:

> I assume you're thinking of eventually doing this for conses etc. too?

For the beginning, it may be even better because conses doesn't
need (over)complicated stuff like parse_str_as_multibyte.

Dmitry

Re: [RFC] temporary Lisp_Strings

[Stefan Monnier]

>> Have you made some preliminary measurements (on microbenchmarks) to try
>> and see how much speed up we might gain?  Given the cost of strlen and
>> parse_str_as_multibyte, I'd expect that the best-case benefit might turn
>> out to be rather small.
> For the moment, I don't have an idea how to benchmark parse_str_as_multibyte
> in "near-to-real-use" conditions.

I was thinking of benchmarking build_string against alloca_string.


        Stefan