all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* inline build_string performance
@ 2012-06-26 14:53 Paul Eggert
  2012-06-26 15:17 ` Andreas Schwab
                   ` (2 more replies)
  0 siblings, 3 replies; 12+ messages in thread
From: Paul Eggert @ 2012-06-26 14:53 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: Emacs Development

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.



^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 14:53 inline build_string performance Paul Eggert
@ 2012-06-26 15:17 ` Andreas Schwab
  2012-06-26 16:29 ` Dmitry Antipov
  2012-06-27  0:39 ` Stefan Monnier
  2 siblings, 0 replies; 12+ messages in thread
From: Andreas Schwab @ 2012-06-26 15:17 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Dmitry Antipov, Emacs Development

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."



^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 14:53 inline build_string performance Paul Eggert
  2012-06-26 15:17 ` Andreas Schwab
@ 2012-06-26 16:29 ` Dmitry Antipov
  2012-06-26 16:42   ` Paul Eggert
  2012-06-27  0:39 ` Stefan Monnier
  2 siblings, 1 reply; 12+ messages in thread
From: Dmitry Antipov @ 2012-06-26 16:29 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Emacs Development

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



^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 16:29 ` Dmitry Antipov
@ 2012-06-26 16:42   ` Paul Eggert
  2012-06-26 17:33     ` Dmitry Antipov
  0 siblings, 1 reply; 12+ messages in thread
From: Paul Eggert @ 2012-06-26 16:42 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: Emacs Development

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.



^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 16:42   ` Paul Eggert
@ 2012-06-26 17:33     ` Dmitry Antipov
  2012-06-26 17:37       ` Paul Eggert
  0 siblings, 1 reply; 12+ messages in thread
From: Dmitry Antipov @ 2012-06-26 17:33 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Emacs Development

[-- 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 *);


^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 17:33     ` Dmitry Antipov
@ 2012-06-26 17:37       ` Paul Eggert
  2012-06-26 17:58         ` Dmitry Antipov
  0 siblings, 1 reply; 12+ messages in thread
From: Paul Eggert @ 2012-06-26 17:37 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: Emacs Development

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.



^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 17:37       ` Paul Eggert
@ 2012-06-26 17:58         ` Dmitry Antipov
  2012-06-26 18:46           ` Paul Eggert
  2012-06-26 18:51           ` Thien-Thi Nguyen
  0 siblings, 2 replies; 12+ messages in thread
From: Dmitry Antipov @ 2012-06-26 17:58 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Emacs Development

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



^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 17:58         ` Dmitry Antipov
@ 2012-06-26 18:46           ` Paul Eggert
  2012-06-26 20:41             ` Eli Zaretskii
  2012-06-26 18:51           ` Thien-Thi Nguyen
  1 sibling, 1 reply; 12+ messages in thread
From: Paul Eggert @ 2012-06-26 18:46 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: Emacs Development

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);




^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 17:58         ` Dmitry Antipov
  2012-06-26 18:46           ` Paul Eggert
@ 2012-06-26 18:51           ` Thien-Thi Nguyen
  1 sibling, 0 replies; 12+ messages in thread
From: Thien-Thi Nguyen @ 2012-06-26 18:51 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: Paul Eggert, Emacs Development

() 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?



^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 18:46           ` Paul Eggert
@ 2012-06-26 20:41             ` Eli Zaretskii
  0 siblings, 0 replies; 12+ messages in thread
From: Eli Zaretskii @ 2012-06-26 20:41 UTC (permalink / raw)
  To: Paul Eggert; +Cc: dmantipov, Emacs-devel

> 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.



^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-26 14:53 inline build_string performance Paul Eggert
  2012-06-26 15:17 ` Andreas Schwab
  2012-06-26 16:29 ` Dmitry Antipov
@ 2012-06-27  0:39 ` Stefan Monnier
  2012-06-27  3:02   ` Eli Zaretskii
  2 siblings, 1 reply; 12+ messages in thread
From: Stefan Monnier @ 2012-06-27  0:39 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Dmitry Antipov, Emacs Development

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



^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: inline build_string performance
  2012-06-27  0:39 ` Stefan Monnier
@ 2012-06-27  3:02   ` Eli Zaretskii
  0 siblings, 0 replies; 12+ messages in thread
From: Eli Zaretskii @ 2012-06-27  3:02 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: eggert, dmantipov, Emacs-devel

> 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.



^ permalink raw reply	[flat|nested] 12+ messages in thread

end of thread, other threads:[~2012-06-27  3:02 UTC | newest]

Thread overview: 12+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2012-06-26 14:53 inline build_string performance Paul Eggert
2012-06-26 15:17 ` Andreas Schwab
2012-06-26 16:29 ` Dmitry Antipov
2012-06-26 16:42   ` Paul Eggert
2012-06-26 17:33     ` Dmitry Antipov
2012-06-26 17:37       ` Paul Eggert
2012-06-26 17:58         ` Dmitry Antipov
2012-06-26 18:46           ` Paul Eggert
2012-06-26 20:41             ` Eli Zaretskii
2012-06-26 18:51           ` Thien-Thi Nguyen
2012-06-27  0:39 ` Stefan Monnier
2012-06-27  3:02   ` Eli Zaretskii

Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.