inline build_string performance

inline build_string performance

[Paul Eggert]

Trunk bzr 108742 changed build_string from a standard
extern function to a static inline function:

static inline Lisp_Object
build_string (const char *str)
{
  return make_string (str, strlen (str));
}

This is not an unalloyed win, since it bloats the
size of the Emacs executable, as callers to build_string
often now have two function calls (strlen + make_string),
not one (just build_string).  In my environment
(Fedora 15 x86-64, GCC 4.7.1) this patch adds 5704 bytes (0.25%)
to the size of the Emacs text.  Presumably this puts
a bit more pressure on the text cache.

Has a performance analysis been done on this change
showing that the code bloat is worth it?

While we're on the subject, I suspect that
we'll get more of a performance win by having a
function 'build_unibyte_string' in the common case
where build_string is invoked on text that is known
to be unibyte, as that avoids a separate pass through
the string.  I haven't had time to investigate this,
though.

Re: inline build_string performance

[Andreas Schwab]

Paul Eggert <eggert@cs.ucla.edu> writes:

> Trunk bzr 108742 changed build_string from a standard
> extern function to a static inline function:
>
> static inline Lisp_Object
> build_string (const char *str)
> {
>   return make_string (str, strlen (str));
> }
>
> This is not an unalloyed win, since it bloats the
> size of the Emacs executable, as callers to build_string
> often now have two function calls (strlen + make_string),
> not one (just build_string).

On the plus side the argument of build_string is often a constant which
causes the strlen call to be optimized out completely.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: inline build_string performance

[Dmitry Antipov]

On 06/26/2012 06:53 PM, Paul Eggert wrote:

> This is not an unalloyed win, since it bloats the
> size of the Emacs executable, as callers to build_string
> often now have two function calls (strlen + make_string),
> not one (just build_string).

The core idea of this stuff is to eliminate calls to strlen when an
argument of build_string is a compile-time constant - the compiler
should just replace call to strlen with constant integer.

As of r108741, my binary image has 336 calls to build_string and
26 calls to make_string; r108742 has 34 and 328, respectively, and
~130 calls of make_string are performed with constant 2nd argument
(i.e. strlen was totally optimized away).

> In my environment
> (Fedora 15 x86-64, GCC 4.7.1) this patch adds 5704 bytes (0.25%)
> to the size of the Emacs text.  Presumably this puts
> a bit more pressure on the text cache.

I have just 3664 bytes (GCC 4.7.1 with -O3, stripped):

[dima@notebook src]$ readelf -S emacs.r108741  | grep -A1 .text
   [14] .text             PROGBITS         000000000040bf20  0000bf20
        0000000000217dc4  0000000000000000  AX       0     0     16
[dima@notebook src]$ readelf -S emacs.r108742  | grep -A1 .text
   [14] .text             PROGBITS         000000000040bf20  0000bf20
        0000000000218c14  0000000000000000  AX       0     0     16

(Note that I'm always using minimalistic configuration without DBus,
sound support, GTK, and so).

> Has a performance analysis been done on this change
> showing that the code bloat is worth it?

Although I can't say how much of 130 micro-optimizations described above
are on critical paths, I've got promising results - ~2% speedup both for
(indent-region) for xdisp.c buffer and (byte-force-recompile [all Lisp sources]).

Dmitry

Re: inline build_string performance

[Paul Eggert]

On 06/26/2012 09:29 AM, Dmitry Antipov wrote:
> 
> The core idea of this stuff is to eliminate calls to strlen when an
> argument of build_string is a compile-time constant

That sounds worthwhile for critical paths.

How about reverting the build_string change, and defining a new
inline function build_literal intended for when the argument is a
string literal and for when speed is more important than conserving
code space?  That would give us speed where speed matters and where
we know it'll be faster, while avoiding code bloat otherwise.
build_string and  build_literal would have identical semantics,
but different performance properties.

Re: inline build_string performance

[Dmitry Antipov]

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

On 06/26/2012 08:42 PM, Paul Eggert wrote:

> That sounds worthwhile for critical paths.
>
> How about reverting the build_string change, and defining a new
> inline function build_literal intended for when the argument is a
> string literal and for when speed is more important than conserving
> code space?  That would give us speed where speed matters and where
> we know it'll be faster, while avoiding code bloat otherwise.
> build_string and  build_literal would have identical semantics,
> but different performance properties.

This may be implemented without reverting previous stuff. It will also gives
other (non-GCC) compilers a chance to demonstrate their optimization skills.

Dmitry




[-- Attachment #2: literal.patch --]
[-- Type: text/plain, Size: 1556 bytes --]

=== modified file 'src/alloc.c'
--- src/alloc.c	2012-06-26 14:41:01 +0000
+++ src/alloc.c	2012-06-26 17:26:02 +0000
@@ -2533,6 +2533,25 @@
   return string;
 }
 
+/* Fast version used when both STR and NBYTES are compile-time
+   constants, and all characters from STR are ASCII.  */
+
+Lisp_Object
+build_literal (const char *str, ptrdiff_t nbytes)
+{
+  Lisp_Object string;
+  struct Lisp_String *s;
+
+  eassert (nbytes > 0);
+
+  s = allocate_string ();
+  allocate_string_data (s, nbytes, nbytes);
+  memcpy (s->data, str, nbytes);
+  string_chars_consed += nbytes;
+
+  XSETSTRING (string, s);
+  return string;
+}
 
 \f
 /***********************************************************************

=== modified file 'src/lisp.h'
--- src/lisp.h	2012-06-26 05:00:30 +0000
+++ src/lisp.h	2012-06-26 17:24:48 +0000
@@ -2716,12 +2716,28 @@
 /* Make a string from the data at STR, treating it as multibyte if the
    data warrants.  */
 
+#ifdef __GNUC__
+
+extern Lisp_Object build_literal (const char *str, ptrdiff_t nbytes);
+
+#define build_string(str)				\
+  ({ Lisp_Object __val;					\
+    if (__builtin_constant_p (str) && strlen (str) > 0)	\
+      __val = build_literal (str, strlen (str));	\
+    else						\
+      __val = make_string (str, strlen (str));		\
+    __val; })
+
+#else
+
 static inline Lisp_Object
 build_string (const char *str)
 {
   return make_string (str, strlen (str));
 }
 
+#endif
+
 extern Lisp_Object pure_cons (Lisp_Object, Lisp_Object);
 EXFUN (Fgarbage_collect, 0);
 extern void make_byte_code (struct Lisp_Vector *);

Re: inline build_string performance

[Paul Eggert]

On 06/26/2012 10:33 AM, Dmitry Antipov wrote:
> This may be implemented without reverting previous stuff.

Sure, but if we we use build_literal for literals, and
build_string for non-literals, there's a performance
downside for having build_string be inline (namely,
it bloats the code), but no performance upside.

Perhaps I'm not quite following your idea, as
I thought the signature would be build_literal ("foo"),
whereas your build_literal also wants the string length.

Re: inline build_string performance

[Dmitry Antipov]

On 06/26/2012 09:37 PM, Paul Eggert wrote:

> Sure, but if we we use build_literal for literals, and
> build_string for non-literals, there's a performance
> downside for having build_string be inline (namely,
> it bloats the code), but no performance upside.

I don't understand this - build_string is a macro which expands to
build_literal (S, strlen (S)) if S is a compile-time constant,
and to make_string (S, strlen (S)) otherwise.  Note that it's possible
to have a nasty bug if someone calls build_literal with non-ASCII
string constant - it's definitely impossible to determine whether
a string constant is non-ASCII at compile time.

> Perhaps I'm not quite following your idea, as
> I thought the signature would be build_literal ("foo"),
> whereas your build_literal also wants the string length.

This assumes something like:

#define build_literal(str) __build_literal (str, strlen (str))

and clever compiler which can optimize away calls to strlen
if STR is a compile-time constant.

Another approach is to refactor all code like:

x = build_string ("test");

to:

x = build_literal ("test", 4);

This tends to be more error-prone in cases of size mismatch. But
it should be easy to implement a debugging version to use with
--enable-checking configure option; and there will be no dependency
from the compiler.

Dmitry

Re: inline build_string performance

[Paul Eggert]

On 06/26/2012 10:58 AM, Dmitry Antipov wrote:
> build_string is a macro which expands to
> build_literal (S, strlen (S)) if S is a compile-time constant,
> and to make_string (S, strlen (S)) otherwise.

Yes, but in the latter case there is code bloat
but no compensating performance benefit.

How about the following instead?

=== modified file 'src/alloc.c'
--- src/alloc.c	2012-06-26 14:41:01 +0000
+++ src/alloc.c	2012-06-26 18:43:25 +0000
@@ -2496,6 +2496,20 @@
 }
 
 
+/* Make a string from the data at STR, treating it as multibyte if the
+   data warrants.  */
+
+Lisp_Object
+build_string_1 (const char *str)
+{
+  return make_string (str, strlen (str));
+}
+
+/* Make the build_string macro visible to GDB.  */
+extern Lisp_Object (build_string) (const char *) EXTERNALLY_VISIBLE;
+Lisp_Object (build_string) (const char *s) { return build_string (s); }
+
+
 /* Return an unibyte Lisp_String set up to hold LENGTH characters
    occupying LENGTH bytes.  */
 
@@ -2533,6 +2547,27 @@
   return string;
 }
 
+#ifdef __GNUC__
+/* Fast version used when both STR and NBYTES are compile-time
+   constants, and all characters from STR are ASCII.  */
+
+Lisp_Object
+build_literal (const char *str, ptrdiff_t nbytes)
+{
+  Lisp_Object string;
+  struct Lisp_String *s;
+
+  eassert (nbytes > 0);
+
+  s = allocate_string ();
+  allocate_string_data (s, nbytes, nbytes);
+  memcpy (s->data, str, nbytes);
+  string_chars_consed += nbytes;
+
+  XSETSTRING (string, s);
+  return string;
+}
+#endif
 
 \f
 /***********************************************************************

=== modified file 'src/lisp.h'
--- src/lisp.h	2012-06-26 05:00:30 +0000
+++ src/lisp.h	2012-06-26 18:36:28 +0000
@@ -2715,12 +2715,19 @@
 
 /* Make a string from the data at STR, treating it as multibyte if the
    data warrants.  */
-
-static inline Lisp_Object
-build_string (const char *str)
-{
-  return make_string (str, strlen (str));
-}
+extern Lisp_Object build_string_1 (const char *);
+#ifdef __GNUC__
+extern Lisp_Object build_literal (const char *, ptrdiff_t);
+# define build_string(str)					\
+   ({ Lisp_Object __val;					\
+     if (__builtin_constant_p (str) && strlen (str) > 0)	\
+       __val = build_literal (str, strlen (str));		\
+     else							\
+       __val = build_string_1 (str);				\
+     __val; })
+#else
+# define build_string(str) build_string_1 (str)
+#endif
 
 extern Lisp_Object pure_cons (Lisp_Object, Lisp_Object);
 EXFUN (Fgarbage_collect, 0);

Re: inline build_string performance

[Thien-Thi Nguyen]

() Dmitry Antipov <dmantipov@yandex.ru>
() Tue, 26 Jun 2012 21:58:34 +0400

   This assumes something like:

   #define build_literal(str) __build_literal (str, strlen (str))

If the argument ‘str’ is a literal string, how about:

  /* -*- c -*- */
  #define build_literal(str)  make_string (str, sizeof (str) - 1)

Or is ‘sizeof’ somehow unsuitable for the job?

Re: inline build_string performance

[Eli Zaretskii]

> Date: Tue, 26 Jun 2012 11:46:34 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> Cc: Emacs Development <Emacs-devel@gnu.org>
> 
> How about the following instead?

Another change that sacrifices maintainability (and the sanity of the
maintainers) for 0.0003% of speedup.

Re: inline build_string performance

[Stefan Monnier]

Let's stop the madness.  This is all mostly irrelevant.  The only think
that's important here is code cleanliness.
So let's make things as simple and clear as possible, please.


        Stefan

Re: inline build_string performance

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Tue, 26 Jun 2012 20:39:58 -0400
> Cc: Dmitry Antipov <dmantipov@yandex.ru>,
> 	Emacs Development <Emacs-devel@gnu.org>
> 
> Let's stop the madness.  This is all mostly irrelevant.  The only think
> that's important here is code cleanliness.
> So let's make things as simple and clear as possible, please.

110% agreement.  Each change that spreads information about the
internals between several places adds to the obstacles one must
negotiate to make non-trivial changes in Emacs internals without
introducing bugs.  The bar is already too high.  If we want more
developers to come on board, we should make such changes only if they
give significant tangible wins.