From: Ben Pfaff <blp@gnu.org>
Date: Tue, 5 May 2009 12:51:54 +0000 (-0700)
Subject: sparse-array: Use __builtin_ctzl on GCC 4.0 or later, as an optimization.
X-Git-Tag: v0.7.3~97
X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pspp-builds.git;a=commitdiff_plain;h=ccead09ac2bc67bbaa40e67904f6c48f7cdf6700

sparse-array: Use __builtin_ctzl on GCC 4.0 or later, as an optimization.

This should be a worthwhile optimization in many cases, because
__builtin_ctzl compiles to a single machine instruction on x86, whereas
the generic implementation compiles to several.
---

diff --git a/src/libpspp/sparse-array.c b/src/libpspp/sparse-array.c
index 7af219bc..6471bbac 100644
--- a/src/libpspp/sparse-array.c
+++ b/src/libpspp/sparse-array.c
@@ -447,6 +447,9 @@ unset_in_use (struct leaf_node *leaf, unsigned int key)
 static inline int
 count_trailing_zeros (unsigned long int x)
 {
+#if __GNUC__ >= 4
+  return __builtin_ctzl (x);
+#else /* not GCC 4+ */
   /* This algorithm is from _Hacker's Delight_ section 5.4. */
   int n = 1;
 
@@ -469,6 +472,7 @@ count_trailing_zeros (unsigned long int x)
   COUNT_STEP (2);
 
   return n - (x & 1);
+#endif /* not GCC 4+ */
 }
 
 /* Returns the least index of the in-use element in LEAF greater