Hi all,
in GC (in src/main/memory.c), FORWARD_CHILDREN() (called by PROCESS_NODES())
treats STRSXPs just like VECSXPs, i.e. it calls FORWARD_NODE() for all its
children. I claim that this is unnecessarily inefficient since the children of
a STRSXP can legitimately only be (atomic) CHARSXPs and could hence be marked
directly in the call of FORWARD_CHILDREN() on the STRSXP.
Attached patch (atomic_CHARSXP.diff) implements this and gives the following
performance improvements on my system compared to R devel (revision 81008):
Elapsed time for two full gc in a session after
x <- as.character(runif(5e7))[]
19sec -> 15sec.
This is the best-case scenario for the patch: very many unique/unmarked CHARSXP
in the STRSXP. For already marked CHARSXP there is no performance gain since
FORWARD_NODE() is a no-op for them.
The relative performance gain is even bigger if iterating through the STRSXP
produces many cache misses, as e.g. after
x <- as.character(runif(5e7))[]
x <- sample(x, length(x))
Elapsed time for two full gc here: 83sec -> 52sec. This is because we have less
cache misses per CHARSXP.
This patch additionally also assumes that the ATTRIBs of a CHARSXP are not to
be traced because they are just used for maintaining the CHARSXP hash chains.
The second attached patch (atomic_CHARSXP_safe_unlikely.diff) checks both
assumptions and calls gc_error() if they are violated and is still noticeably
faster than R devel: 19sec -> 17sec and 83sec -> 54sec, respectively.
Attached gc_test.R is the script I used to get the previously mentioned and
more gc timings.
Do you think that this is a reasonable change? It does make the code more
complex and I am not sure if there might be situations in which the assumptions
are violated, even though SET_STRING_ELT() and installAttrib() do enforce
them.
Best regards,
Andreas
Index: src/main/memory.c
===================================================================
--- src/main/memory.c (revision 81008)
+++ src/main/memory.c (working copy)
@@ -678,7 +678,7 @@
#define FREE_FORWARD_CASE
#endif
/*** assume for now all ALTREP nodes are based on CONS nodes */
-#define DO_CHILDREN(__n__,dc__action__,dc__extra__) do { \
+#define DO_CHILDREN4(__n__,dc__action__,dc__str__action__,dc__extra__) do { \
if (HAS_GENUINE_ATTRIB(__n__)) \
dc__action__(ATTRIB(__n__), dc__extra__); \
if (ALTREP(__n__)) { \
@@ -701,6 +701,12 @@
case S4SXP: \
break; \
case STRSXP: \
+ { \
+ R_xlen_t i; \
+ for (i = 0; i < XLENGTH(__n__); i++) \
+ dc__str__action__(VECTOR_ELT(__n__, i), dc__extra__); \
+ } \
+ break; \
case EXPRSXP: \
case VECSXP: \
{ \
@@ -740,6 +746,7 @@
} \
} while(0)
+#define DO_CHILDREN(__n__,dc__action__,dc__extra__) DO_CHILDREN4(__n__,dc__action__,dc__action__,dc__extra__)
/* Forwarding Nodes. These macros mark nodes or children of nodes and
place them on the forwarding list. The forwarding list is assumed
@@ -758,8 +765,22 @@
} while (0)
#define FC_FORWARD_NODE(__n__,__dummy__) FORWARD_NODE(__n__)
-#define FORWARD_CHILDREN(__n__) DO_CHILDREN(__n__,FC_FORWARD_NODE, 0)
+#define PROCESS_CHARSXP(s) do { \
+ SEXP fn__n__ = (s); \
+ if (fn__n__ && ! NODE_IS_MARKED(fn__n__)) { \
+ CHECK_FOR_FREE_NODE(fn__n__) \
+ MARK_NODE(fn__n__); \
+ UNSNAP_NODE(fn__n__); \
+ SNAP_NODE(fn__n__, R_GenHeap[NODE_CLASS(fn__n__)].Old[NODE_GENERATION(fn__n__)]); \
+ R_GenHeap[NODE_CLASS(fn__n__)].OldCount[NODE_GENERATION(fn__n__)]++; \
+ } \
+} while (0)
+
+#define FC_PROCESS_CHARSXP(__n__,__dummy__) PROCESS_CHARSXP(__n__)
+
+#define FORWARD_CHILDREN(__n__) DO_CHILDREN4(__n__,FC_FORWARD_NODE, FC_PROCESS_CHARSXP, 0)
+
/* This macro should help localize where a FREESXP node is encountered
in the GC */
#ifdef PROTECTCHECK
Index: src/main/memory.c
===================================================================
--- src/main/memory.c (revision 81008)
+++ src/main/memory.c (working copy)
@@ -678,7 +678,7 @@
#define FREE_FORWARD_CASE
#endif
/*** assume for now all ALTREP nodes are based on CONS nodes */
-#define DO_CHILDREN(__n__,dc__action__,dc__extra__) do { \
+#define DO_CHILDREN4(__n__,dc__action__,dc__str__action__,dc__extra__) do { \
if (HAS_GENUINE_ATTRIB(__n__)) \
dc__action__(ATTRIB(__n__), dc__extra__); \
if (ALTREP(__n__)) { \
@@ -701,6 +701,12 @@
case S4SXP: \
break; \
case STRSXP: \
+ { \
+ R_xlen_t i; \
+ for (i = 0; i < XLENGTH(__n__); i++) \
+ dc__str__action__(VECTOR_ELT(__n__, i), dc__extra__); \
+ } \
+ break; \
case EXPRSXP: \
case VECSXP: \
{ \
@@ -740,6 +746,7 @@
} \
} while(0)
+#define DO_CHILDREN(__n__,dc__action__,dc__extra__) DO_CHILDREN4(__n__,dc__action__,dc__action__,dc__extra__)
/* Forwarding Nodes. These macros mark nodes or children of nodes and
place them on the forwarding list. The forwarding list is assumed
@@ -758,8 +765,34 @@
} while (0)
#define FC_FORWARD_NODE(__n__,__dummy__) FORWARD_NODE(__n__)
-#define FORWARD_CHILDREN(__n__) DO_CHILDREN(__n__,FC_FORWARD_NODE, 0)
+#ifdef HAVE_BUILTIN_EXPECT
+#define likely(x) __builtin_expect((x), 1)
+#define unlikely(x) __builtin_expect((x), 0)
+#else
+#define likely(x) (x)
+#define unlikely(x) (x)
+#endif
+
+#define PROCESS_CHARSXP(s) do { \
+ SEXP fn__n__ = (s); \
+ if (fn__n__ && ! NODE_IS_MARKED(fn__n__)) { \
+ CHECK_FOR_FREE_NODE(fn__n__) \
+ if (unlikely(TYPEOF(fn__n__) != CHARSXP)) \
+ gc_error("gc encountered a STRSXP with non-CHARSXP child"); \
+ if (unlikely(ATTRIB(fn__n__) != R_NilValue && TYPEOF(ATTRIB(fn__n__)) != CHARSXP)) \
+ gc_error("gc encountered a CHARSXP with a non-CHARSXP attribute"); \
+ MARK_NODE(fn__n__); \
+ UNSNAP_NODE(fn__n__); \
+ SNAP_NODE(fn__n__, R_GenHeap[NODE_CLASS(fn__n__)].Old[NODE_GENERATION(fn__n__)]); \
+ R_GenHeap[NODE_CLASS(fn__n__)].OldCount[NODE_GENERATION(fn__n__)]++; \
+ } \
+} while (0)
+
+#define FC_PROCESS_CHARSXP(__n__,__dummy__) PROCESS_CHARSXP(__n__)
+
+#define FORWARD_CHILDREN(__n__) DO_CHILDREN4(__n__,FC_FORWARD_NODE, FC_PROCESS_CHARSXP, 0)
+
/* This macro should help localize where a FREESXP node is encountered
in the GC */
#ifdef PROTECTCHECK
______________________________________________
R-devel@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel
