unofficial mirror of guile-devel@gnu.org 
 help / color / mirror / Atom feed
* Using branch prediction hints (or not)
@ 2007-12-04 20:35 Ludovic Courtès
  2007-12-04 22:36 ` Neil Jerram
  2007-12-05 22:39 ` Andy Wingo
  0 siblings, 2 replies; 4+ messages in thread
From: Ludovic Courtès @ 2007-12-04 20:35 UTC (permalink / raw)
  To: guile-devel

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

Hi,

A long time ago, Aubbrey Jaffer wrote this page about his experiments
with branch prediction in SCM:

  http://www-swiss.ai.mit.edu/~jaffer/CNS/interpreter-branch.html

I played with GCC's `__builtin_expect' (patch attached) to provide GCC
with branch prediction hints in the most obvious situations:
`SCM_ASSERT'-like macros, `scm_wrong_num_args ()' situations in the
evaluator, and a few others.

It provides a little improvement on my x86 machine, less than 5% for
this program:

  (let loop ((x 20000000))
    (and (> x 0)
         (loop (1- x))))

This made me wonder whether it's even worth it.  OTOH, it doesn't hurt.

So, should we apply it?

Thanks,
Ludovic.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: The patch --]
[-- Type: text/x-patch, Size: 12296 bytes --]

--- orig/libguile/__scm.h
+++ mod/libguile/__scm.h
@@ -3,7 +3,7 @@
 #ifndef SCM___SCM_H
 #define SCM___SCM_H
 
-/* Copyright (C) 1995,1996,1998,1999,2000,2001,2002,2003, 2006 Free Software Foundation, Inc.
+/* Copyright (C) 1995,1996,1998,1999,2000,2001,2002,2003, 2006, 2007 Free Software Foundation, Inc.
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -109,6 +109,20 @@
 #endif
 
 
+/* The SCM_EXPECT macros provide branch prediction hints to the compiler.  To
+ * use only in places where the result of the expression under "normal"
+ * circumstances is known.  */
+#if defined(__GNUC__) && (__GNUC__ >= 3)
+# define SCM_EXPECT    __builtin_expect
+#else
+# define SCM_EXPECT(_expr, _value) (_expr)
+#endif
+
+#define SCM_EXPECT_TRUE(_expr)  SCM_EXPECT ((_expr), 1)
+#define SCM_EXPECT_FALSE(_expr) SCM_EXPECT ((_expr), 0)
+
+
+\f
 /* {Supported Options}
  *
  * These may be defined or undefined.
@@ -500,14 +514,14 @@
 #define SCM_ASSERT_TYPE(_cond, _arg, _pos, _subr, _msg)
 #define SCM_ASRTGO(_cond, _label)
 #else
-#define SCM_ASSERT(_cond, _arg, _pos, _subr) \
-	do { if (!(_cond)) \
+#define SCM_ASSERT(_cond, _arg, _pos, _subr)			\
+        do { if (SCM_EXPECT_FALSE (!(_cond)))			\
           scm_wrong_type_arg (_subr, _pos, _arg); } while (0)
-#define SCM_ASSERT_TYPE(_cond, _arg, _pos, _subr, _msg) \
-	do { if (!(_cond)) \
+#define SCM_ASSERT_TYPE(_cond, _arg, _pos, _subr, _msg)			\
+        do { if (SCM_EXPECT_FALSE (!(_cond)))				\
           scm_wrong_type_arg_msg(_subr, _pos, _arg, _msg);  } while (0)
-#define SCM_ASRTGO(_cond, _label) \
-        do {  if (!(_cond)) \
+#define SCM_ASRTGO(_cond, _label)		\
+        do {  if (SCM_EXPECT_FALSE (!(_cond)))	\
           goto _label; } while (0)
 #endif
 
@@ -526,8 +540,9 @@
   return (SCM_UNPACK (gf)					\
 	  ? scm_call_generic_0 ((gf))				\
 	  : (scm_error_num_args_subr ((subr)), SCM_UNSPECIFIED))
-#define SCM_GASSERT0(cond, gf, subr) \
-  if (!(cond)) SCM_WTA_DISPATCH_0((gf), (subr))
+#define SCM_GASSERT0(cond, gf, subr)		\
+  if (SCM_EXPECT_FALSE(!(cond)))		\
+    SCM_WTA_DISPATCH_0((gf), (subr))
 
 SCM_API SCM scm_call_generic_1 (SCM gf, SCM a1);
 
@@ -535,8 +550,9 @@
   return (SCM_UNPACK (gf)					\
 	  ? scm_call_generic_1 ((gf), (a1))			\
 	  : (scm_wrong_type_arg ((subr), (pos), (a1)), SCM_UNSPECIFIED))
-#define SCM_GASSERT1(cond, gf, a1, pos, subr) \
-  if (!(cond)) SCM_WTA_DISPATCH_1((gf), (a1), (pos), (subr))
+#define SCM_GASSERT1(cond, gf, a1, pos, subr)		\
+  if (SCM_EXPECT_FALSE (!(cond)))			\
+    SCM_WTA_DISPATCH_1((gf), (a1), (pos), (subr))
 
 SCM_API SCM scm_call_generic_2 (SCM gf, SCM a1, SCM a2);
 
@@ -546,8 +562,9 @@
 	  : (scm_wrong_type_arg ((subr), (pos),				\
 				 (pos) == SCM_ARG1 ? (a1) : (a2)),	\
 	     SCM_UNSPECIFIED))
-#define SCM_GASSERT2(cond, gf, a1, a2, pos, subr) \
-  if (!(cond)) SCM_WTA_DISPATCH_2((gf), (a1), (a2), (pos), (subr))
+#define SCM_GASSERT2(cond, gf, a1, a2, pos, subr)	\
+  if (SCM_EXPECT_FALSE (!(cond)))			\
+    SCM_WTA_DISPATCH_2((gf), (a1), (a2), (pos), (subr))
 
 SCM_API SCM scm_apply_generic (SCM gf, SCM args);
 
@@ -558,8 +575,9 @@
 				 scm_list_ref ((args),			  \
 					       scm_from_int ((pos) - 1))), \
 	     SCM_UNSPECIFIED))
-#define SCM_GASSERTn(cond, gf, args, pos, subr) \
-  if (!(cond)) SCM_WTA_DISPATCH_n((gf), (args), (pos), (subr))
+#define SCM_GASSERTn(cond, gf, args, pos, subr)		\
+  if (SCM_EXPECT_FALSE (!(cond)))			\
+    SCM_WTA_DISPATCH_n((gf), (args), (pos), (subr))
 
 #ifndef SCM_MAGIC_SNARFER
 /* Let these macros pass through if


--- orig/libguile/eval.c
+++ mod/libguile/eval.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004,2005,2006
+/* Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004,2005,2006,2007
  * Free Software Foundation, Inc.
  * 
  * This library is free software; you can redistribute it and/or
@@ -299,10 +299,12 @@
 
 
 /* Shortcut macros to simplify syntax error handling. */
-#define ASSERT_SYNTAX(cond, message, form) \
-  { if (!(cond)) syntax_error (message, form, SCM_UNDEFINED); }
-#define ASSERT_SYNTAX_2(cond, message, form, expr) \
-  { if (!(cond)) syntax_error (message, form, expr); }
+#define ASSERT_SYNTAX(cond, message, form)		\
+  { if (SCM_EXPECT_FALSE (!(cond)))			\
+      syntax_error (message, form, SCM_UNDEFINED); }
+#define ASSERT_SYNTAX_2(cond, message, form, expr)	\
+  { if (SCM_EXPECT_FALSE (!(cond)))			\
+      syntax_error (message, form, expr); }
 
 \f
 


--- orig/libguile/eval.i.c
+++ mod/libguile/eval.i.c
@@ -681,7 +681,7 @@
 #ifdef DEVAL
               debug.info->a.args = arg1;
 #endif
-              if (scm_badargsp (formals, arg1))
+              if (SCM_EXPECT_FALSE (scm_badargsp (formals, arg1)))
                 scm_wrong_num_args (proc);
               ENTER_APPLY;
               /* Copy argument list */
@@ -1143,7 +1143,7 @@
       case scm_tcs_closures:
         {
           const SCM formals = SCM_CLOSURE_FORMALS (proc);
-          if (scm_is_pair (formals))
+          if (SCM_EXPECT_FALSE (scm_is_pair (formals)))
             goto wrongnumargs;
           x = SCM_CLOSURE_BODY (proc);
           env = SCM_EXTEND_ENV (formals, SCM_EOL, SCM_ENV (proc));
@@ -1187,7 +1187,7 @@
 
   /* must handle macros by here */
   x = SCM_CDR (x);
-  if (scm_is_pair (x))
+  if (SCM_EXPECT_TRUE (scm_is_pair (x)))
     arg1 = EVALCAR (x, env);
   else
     scm_wrong_num_args (proc);
@@ -1316,7 +1316,7 @@
 	    goto badfun;
 	  }
       }
-    if (scm_is_pair (x))
+    if (SCM_EXPECT_TRUE (scm_is_pair (x)))
       arg2 = EVALCAR (x, env);
     else
       scm_wrong_num_args (proc);
@@ -1440,7 +1440,7 @@
             }
 	  }
       }
-      if (!scm_is_pair (x))
+      if (SCM_EXPECT_FALSE (!scm_is_pair (x)))
 	scm_wrong_num_args (proc);
 #ifdef DEVAL
       debug.info->a.args = scm_cons2 (arg1, arg2,
@@ -1518,7 +1518,7 @@
           }
 #else /* DEVAL */
 	case scm_tc7_subr_3:
-	  if (!scm_is_null (SCM_CDR (x)))
+	  if (SCM_EXPECT_FALSE (!scm_is_null (SCM_CDR (x))))
 	    scm_wrong_num_args (proc);
 	  else
 	    RETURN (SCM_SUBRF (proc) (arg1, arg2, EVALCAR (x, env)));
@@ -1709,37 +1709,38 @@
   switch (SCM_TYP7 (proc))
     {
     case scm_tc7_subr_2o:
-      if (SCM_UNBNDP (arg1))
+      if (SCM_EXPECT_FALSE (SCM_UNBNDP (arg1)))
 	scm_wrong_num_args (proc);
       if (scm_is_null (args))
         args = SCM_UNDEFINED;
       else
         {
-          if (! scm_is_null (SCM_CDR (args)))
+          if (SCM_EXPECT_FALSE (! scm_is_null (SCM_CDR (args))))
             scm_wrong_num_args (proc);
           args = SCM_CAR (args);
         }
       RETURN (SCM_SUBRF (proc) (arg1, args));
     case scm_tc7_subr_2:
-      if (scm_is_null (args) || !scm_is_null (SCM_CDR (args)))
+      if (SCM_EXPECT_FALSE (scm_is_null (args) ||
+			    !scm_is_null (SCM_CDR (args))))
 	scm_wrong_num_args (proc);
       args = SCM_CAR (args);
       RETURN (SCM_SUBRF (proc) (arg1, args));
     case scm_tc7_subr_0:
-      if (!SCM_UNBNDP (arg1))
+      if (SCM_EXPECT_FALSE (!SCM_UNBNDP (arg1)))
 	scm_wrong_num_args (proc);
       else
 	RETURN (SCM_SUBRF (proc) ());
     case scm_tc7_subr_1:
-      if (SCM_UNBNDP (arg1))
+      if (SCM_EXPECT_FALSE (SCM_UNBNDP (arg1)))
 	scm_wrong_num_args (proc);
     case scm_tc7_subr_1o:
-      if (!scm_is_null (args))
+      if (SCM_EXPECT_FALSE (!scm_is_null (args)))
 	scm_wrong_num_args (proc);
       else
 	RETURN (SCM_SUBRF (proc) (arg1));
     case scm_tc7_dsubr:
-      if (SCM_UNBNDP (arg1) || !scm_is_null (args))
+      if (SCM_EXPECT_FALSE (SCM_UNBNDP (arg1) || !scm_is_null (args)))
 	scm_wrong_num_args (proc);
       if (SCM_I_INUMP (arg1))
         {
@@ -1760,13 +1761,13 @@
       SCM_WTA_DISPATCH_1 (*SCM_SUBR_GENERIC (proc), arg1,
                           SCM_ARG1, scm_i_symbol_chars (SCM_SNAME (proc)));
     case scm_tc7_cxr:
-      if (SCM_UNBNDP (arg1) || !scm_is_null (args))
+      if (SCM_EXPECT_FALSE (SCM_UNBNDP (arg1) || !scm_is_null (args)))
 	scm_wrong_num_args (proc);
       RETURN (scm_i_chase_pairs (arg1, (scm_t_bits) SCM_SUBRF (proc)));
     case scm_tc7_subr_3:
-      if (scm_is_null (args)
-	  || scm_is_null (SCM_CDR (args))
-	  || !scm_is_null (SCM_CDDR (args)))
+      if (SCM_EXPECT_FALSE (scm_is_null (args)
+			    || scm_is_null (SCM_CDR (args))
+			    || !scm_is_null (SCM_CDDR (args))))
 	scm_wrong_num_args (proc);
       else
 	RETURN (SCM_SUBRF (proc) (arg1, SCM_CAR (args), SCM_CADR (args)));
@@ -1777,7 +1778,7 @@
       RETURN (SCM_SUBRF (proc) (SCM_UNBNDP (arg1) ? SCM_EOL : scm_cons (arg1, args)));
 #endif
     case scm_tc7_lsubr_2:
-      if (!scm_is_pair (args))
+      if (SCM_EXPECT_FALSE (!scm_is_pair (args)))
 	scm_wrong_num_args (proc);
       else
 	RETURN (SCM_SUBRF (proc) (arg1, SCM_CAR (args), SCM_CDR (args)));
@@ -1809,7 +1810,7 @@
 #else
       arg1 = (SCM_UNBNDP (arg1) ? SCM_EOL : scm_cons (arg1, args));
 #endif
-      if (scm_badargsp (SCM_CLOSURE_FORMALS (proc), arg1))
+      if (SCM_EXPECT_FALSE (scm_badargsp (SCM_CLOSURE_FORMALS (proc), arg1)))
 	scm_wrong_num_args (proc);
       
       /* Copy argument list */


--- orig/libguile/numbers.c
+++ mod/libguile/numbers.c
@@ -3950,16 +3950,16 @@
 SCM
 scm_sum (SCM x, SCM y)
 {
-  if (SCM_UNBNDP (y))
+  if (SCM_EXPECT_FALSE (SCM_UNBNDP (y)))
     {
       if (SCM_NUMBERP (x)) return x;
       if (SCM_UNBNDP (x)) return SCM_INUM0;
       SCM_WTA_DISPATCH_1 (g_sum, x, SCM_ARG1, s_sum);
     }
 
-  if (SCM_I_INUMP (x))
+  if (SCM_EXPECT_TRUE (SCM_I_INUMP (x)))
     {
-      if (SCM_I_INUMP (y))
+      if (SCM_EXPECT_TRUE (SCM_I_INUMP (y)))
         {
           long xx = SCM_I_INUM (x);
           long yy = SCM_I_INUM (y);
@@ -4144,7 +4144,7 @@
 SCM
 scm_difference (SCM x, SCM y)
 {
-  if (SCM_UNBNDP (y))
+  if (SCM_EXPECT_FALSE (SCM_UNBNDP (y)))
     {
       if (SCM_UNBNDP (x))
         SCM_WTA_DISPATCH_0 (g_difference, s_difference);
@@ -4173,9 +4173,9 @@
           SCM_WTA_DISPATCH_1 (g_difference, x, SCM_ARG1, s_difference);
     }
   
-  if (SCM_I_INUMP (x))
+  if (SCM_EXPECT_TRUE (SCM_I_INUMP (x)))
     {
-      if (SCM_I_INUMP (y))
+      if (SCM_EXPECT_TRUE (SCM_I_INUMP (y)))
 	{
 	  long int xx = SCM_I_INUM (x);
 	  long int yy = SCM_I_INUM (y);
@@ -4388,7 +4388,7 @@
 SCM
 scm_product (SCM x, SCM y)
 {
-  if (SCM_UNBNDP (y))
+  if (SCM_EXPECT_FALSE (SCM_UNBNDP (y)))
     {
       if (SCM_UNBNDP (x))
 	return SCM_I_MAKINUM (1L);
@@ -4398,7 +4398,7 @@
 	SCM_WTA_DISPATCH_1 (g_product, x, SCM_ARG1, s_product);
     }
   
-  if (SCM_I_INUMP (x))
+  if (SCM_EXPECT_TRUE (SCM_I_INUMP (x)))
     {
       long xx;
 
@@ -4411,7 +4411,7 @@
         case 1: return y; break;
 	}
 
-      if (SCM_I_INUMP (y))
+      if (SCM_EXPECT_TRUE (SCM_I_INUMP (y)))
 	{
 	  long yy = SCM_I_INUM (y);
 	  long kk = xx * yy;
@@ -4611,7 +4611,7 @@
 {
   double a;
 
-  if (SCM_UNBNDP (y))
+  if (SCM_EXPECT_FALSE (SCM_UNBNDP (y)))
     {
       if (SCM_UNBNDP (x))
 	SCM_WTA_DISPATCH_0 (g_divide, s_divide);
@@ -4671,10 +4671,10 @@
 	SCM_WTA_DISPATCH_1 (g_divide, x, SCM_ARG1, s_divide);
     }
 
-  if (SCM_I_INUMP (x))
+  if (SCM_EXPECT_TRUE (SCM_I_INUMP (x)))
     {
       long xx = SCM_I_INUM (x);
-      if (SCM_I_INUMP (y))
+      if (SCM_EXPECT_TRUE (SCM_I_INUMP (y)))
 	{
 	  long yy = SCM_I_INUM (y);
 	  if (yy == 0)


--- orig/libguile/validate.h
+++ mod/libguile/validate.h
@@ -3,7 +3,7 @@
 #ifndef SCM_VALIDATE_H
 #define SCM_VALIDATE_H
 
-/* Copyright (C) 1999,2000,2001, 2002, 2004, 2006 Free Software Foundation, Inc.
+/* Copyright (C) 1999,2000,2001, 2002, 2004, 2006, 2007 Free Software Foundation, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -99,8 +99,10 @@
 #define SCM_OUT_OF_RANGE(pos, arg) \
   do { scm_out_of_range_pos (FUNC_NAME, arg, scm_from_int (pos)); } while (0)
 
-#define SCM_ASSERT_RANGE(pos, arg, f) \
-  do { if (!(f)) scm_out_of_range_pos (FUNC_NAME, arg, scm_from_int (pos)); } while (0)
+#define SCM_ASSERT_RANGE(pos, arg, f)					\
+  do { if (SCM_EXPECT_FALSE (!(f)))					\
+         scm_out_of_range_pos (FUNC_NAME, arg, scm_from_int (pos)); }	\
+  while (0)
 
 #define SCM_MUST_MALLOC_TYPE(type) \
   ((type *) scm_must_malloc (sizeof (type), FUNC_NAME))




[-- Attachment #3: Type: text/plain, Size: 143 bytes --]

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

^ permalink raw reply	[flat|nested] 4+ messages in thread
* Re: Using branch prediction hints (or not)
  2007-12-04 20:35 Using branch prediction hints (or not) Ludovic Courtès
@ 2007-12-04 22:36 ` Neil Jerram
  2007-12-05 22:39 ` Andy Wingo
  1 sibling, 0 replies; 4+ messages in thread
From: Neil Jerram @ 2007-12-04 22:36 UTC (permalink / raw)
  To: Ludovic Courtès; +Cc: guile-devel

ludo@gnu.org (Ludovic Courtès) writes:

> I played with GCC's `__builtin_expect' (patch attached) to provide GCC
> with branch prediction hints in the most obvious situations:
> `SCM_ASSERT'-like macros, `scm_wrong_num_args ()' situations in the
> evaluator, and a few others.
>
> It provides a little improvement on my x86 machine, less than 5% for
> this program:
>
>   (let loop ((x 20000000))
>     (and (> x 0)
>          (loop (1- x))))
>
> This made me wonder whether it's even worth it.  OTOH, it doesn't hurt.
>
> So, should we apply it?

Sounds like 5% worth having to me.

In terms of code readability (and so maintainability), I'd say the
SCM_EXPECT_XXX forms fit in quite easily, and don't make the code
noticeably more confusing or difficult.

So I'm in favour.

     Neil



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel


^ permalink raw reply	[flat|nested] 4+ messages in thread
* Re: Using branch prediction hints (or not)
  2007-12-04 20:35 Using branch prediction hints (or not) Ludovic Courtès
  2007-12-04 22:36 ` Neil Jerram
@ 2007-12-05 22:39 ` Andy Wingo
  2007-12-08 15:58   ` Ludovic Courtès
  1 sibling, 1 reply; 4+ messages in thread
From: Andy Wingo @ 2007-12-05 22:39 UTC (permalink / raw)
  To: Ludovic Courtès; +Cc: guile-devel

Hi Ludovic,

On Tue 04 Dec 2007 21:35, ludo@gnu.org (Ludovic Courtès) writes:

> I played with GCC's `__builtin_expect' (patch attached) to provide GCC
> with branch prediction hints in the most obvious situations:
> `SCM_ASSERT'-like macros, `scm_wrong_num_args ()' situations in the
> evaluator, and a few others.
>
> It provides a little improvement on my x86 machine, less than 5% for
> this program:

I think that more than 2% is reasonable for a performance-enhancing
patch.

> +/* Copyright (C) 1995,1996,1998,1999,2000,2001,2002,2003, 2006, 2007 Free Software Foundation, Inc.

Wasn't there something recently on gnu-prog-discuss about the X-Y year
form being acceptable?

> +#define SCM_EXPECT_TRUE(_expr)  SCM_EXPECT ((_expr), 1)
> +#define SCM_EXPECT_FALSE(_expr) SCM_EXPECT ((_expr), 0)

A bit of a mouthful. Perhaps we can follow GLib's example and call them
SCM_LIKELY and SCM_UNLIKELY.

Andy
-- 
http://wingolog.org/


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel


^ permalink raw reply	[flat|nested] 4+ messages in thread
* Re: Using branch prediction hints (or not)
  2007-12-05 22:39 ` Andy Wingo
@ 2007-12-08 15:58   ` Ludovic Courtès
  0 siblings, 0 replies; 4+ messages in thread
From: Ludovic Courtès @ 2007-12-08 15:58 UTC (permalink / raw)
  To: guile-devel

Hi,

Andy Wingo <wingo@pobox.com> writes:

> Wasn't there something recently on gnu-prog-discuss about the X-Y year
> form being acceptable?

I don't remember and I can't access the archive currently.

> A bit of a mouthful. Perhaps we can follow GLib's example and call them
> SCM_LIKELY and SCM_UNLIKELY.

Right, GMP (among others) does that too, so I changed the patch
accordingly and committed it.

Thanks,
Ludovic.



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel


^ permalink raw reply	[flat|nested] 4+ messages in thread
end of thread, other threads:[~2007-12-08 15:58 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2007-12-04 20:35 Using branch prediction hints (or not) Ludovic Courtès
2007-12-04 22:36 ` Neil Jerram
2007-12-05 22:39 ` Andy Wingo
2007-12-08 15:58   ` Ludovic Courtès

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).