29  R internals

What, exactly, is a vector?

You have written thousands of them by now, filtered them, mapped functions over them, watched them copy themselves at surprising moments. But the object itself, the thing sitting in memory when you type x <- c(1, 2, 3), has remained invisible. This chapter opens it up. We are going to look at the C structs that R allocates on the heap, the pointer arithmetic that makes vectorized operations fast, the reference counter that decides when copies happen, and the garbage collector that reclaims everything you abandon. None of this is necessary for writing good R, but it turns copy-on-modify, lazy evaluation, and lexical scoping from rules into consequences of one design.

The vectorized operations come from S and the evaluation model from Scheme (Chapter 2 told that story). What holds the two together in the C source is a single data structure.

29.1 Stack and heap

When you write x <- c(1, 2, 3), R allocates a block of memory, fills it with your three numbers, and stores a pointer to that block in the binding for x. When x goes out of scope and nothing else references it, R’s garbage collector reclaims the block.

The block lives in the heap, the large region of memory where objects survive until something frees them: explicitly, in C, or when a garbage collector finds that nothing points to them any more, in R, Python, and Java. The other region is the stack: small, fast, and automatic. When you call a function, its bookkeeping (which function called which, where to return) goes on the stack and vanishes when the function returns. Every R object, without exception, lives on the heap; the stack holds only the record of who called whom.

29.2 Every object is a SEXP

R can show you the block. .Internal(inspect()) dumps the C-level representation of any object:

x <- c(1.5, 2.5, 3.5)
.Internal(inspect(x))
#> @0x0000020f0e218be8 14 REALSXP g0c3 [REF(2)] (len=3, tl=0) 1.5,2.5,3.5

Read the line left to right: a memory address, a type code (14) and its name (REALSXP), garbage-collector flags, a reference count (REF(1)), the length, and the three values. Every R object prints this way, because in R’s C source every object is a SEXP: a pointer to a SEXPREC struct. The name stands for “S expression,” inherited from Lisp.

The struct has two parts. The header is the same for every object: a type tag (the SEXPTYPE, an integer saying whether this is an integer vector, a closure, an environment, and so on), the flags the garbage collector uses to track whether the object is reachable, the reference count that copy-on-modify consults, and a pointer to a pairlist of attributes (names, class, dim). The payload varies by type. For a numeric vector it is a contiguous block of C double values; for a closure it is three pointers (formals, body, environment); for an environment it is a frame of bindings plus a pointer to the parent. Every R object, from a single integer to a nested list of data frames, wears the same header; only the payload differs.

Figure 29.1: The SEXPREC struct: a fixed-size header followed by a contiguous data array. x + y walks two arrays in lockstep with no pointer chasing.

You can see the type tag from R with typeof():

typeof(1:5)
#> [1] "integer"
typeof(c(1.0, 2.0))
#> [1] "double"
typeof("hello")
#> [1] "character"
typeof(list(1, 2))
#> [1] "list"
typeof(sum)
#> [1] "builtin"
typeof(mean)
#> [1] "closure"

typeof() returns the SEXPTYPE name as a string. The mapping between R concepts and SEXPTYPEs is direct:

R concept	SEXPTYPE	C constant
Integer vector	integer	INTSXP
Double vector	double	REALSXP
Character vector	character	STRSXP
Logical vector	logical	LGLSXP
List	list	VECSXP
Function (closure)	closure	CLOSXP
Built-in function	builtin	BUILTINSXP
Special function	special	SPECIALSXP
Environment	environment	ENVSXP
Promise	promise	PROMSXP
Language object	language	LANGSXP
Symbol (name)	symbol	SYMSXP

Some of these are familiar. CLOSXP is the closure, ENVSXP the environment, PROMSXP the promise. LANGSXP and SYMSXP are the calls and symbols you took apart in Chapter 26.

sum and mean have different types. sum is a builtin, implemented directly in C, evaluating all its arguments before being called. mean is a closure, a regular R function with formals, a body, and an environment. The distinction matters at the C level but rarely at the R level.

29.3 Inspecting objects

The lobstr package gives friendlier views of the same information:

library(lobstr)

obj_addr(x)
#> [1] "0x20f0e218be8"
obj_size(x)
#> 80 B

obj_addr() returns the memory address as a string. obj_size() reports total memory including the header: for three doubles you get 80 bytes, 48 of header and 32 for the data, because R hands out small vectors in fixed size classes and 24 bytes rounds up to 32.

ref() shows whether two names point to the same underlying object:

y <- x
ref(x, y)
#> [1:0x20f0e218be8] <dbl> 
#>  
#> [1:0x20f0e218be8]

Both x and y point to the same memory address. No copy has been made. This is the copy-on-modify mechanism you saw in Section 9.4, now visible at the pointer level.

y[1] <- 99
ref(x, y)
#> [1:0x20f0e218be8] <dbl> 
#>  
#> [2:0x20f0e524b98] <dbl>

After modification, y points to a different address. R copied the vector when y was modified, because x still needed the original. The copy decision depends on how many names point to the same data, which raises the obvious question: how does R keep track?

Exercises

1. Use typeof() to check the type of: TRUE, 1L, 1.0, 1+2i, raw(1), quote(x + 1), as.name("x"). Which ones surprise you?

2. Run .Internal(inspect(list(1, "a", TRUE))). How many SEXPs do you see? Why more than one?

3. Create a <- 1:1e6 and b <- a. Check with lobstr::ref() that they share the same address. Now do b[1] <- 0L. Do they still share? What does lobstr::obj_size(a, b) report?

29.4 Memory layout of vectors

A numeric vector in R is stored as a SEXPREC header followed by a contiguous block of C double values, and “contiguous” is the word that matters here: the doubles sit next to each other in memory, with no gaps or pointers between them, exactly like a C array or a NumPy array.

/* Simplified layout of a REALSXP (not actual R source) */
struct SEXPREC {
    /* header: type, gc flags, refcount, attributes, ... */
    sxpinfo_struct sxpinfo;
    SEXP attrib;
    SEXP gengc_next_node;
    SEXP gengc_prev_node;
    /* payload for vectors: */
    R_xlen_t length;
    R_xlen_t truelength;
    double data[];  /* flexible array member: the actual numbers */
};

The contiguous layout is why vectorized operations are fast. When R computes x + y, the C code walks two arrays of doubles in lockstep, reading from sequential memory addresses; modern CPUs are optimized for exactly this access pattern, with hardware prefetchers loading the next cache line before you need it and SIMD instructions adding multiple doubles in a single clock cycle.

An integer vector (INTSXP) has the same layout but with int instead of double. A logical vector (LGLSXP) also uses int (not char), which is why logicals take 4 bytes per element, not 1.

Character vectors are a different beast entirely. A STRSXP is a vector of pointers to CHARSXP objects, where each CHARSXP holds an immutable C string. R interns (deduplicates) these strings globally, so two identical strings share the same CHARSXP:

a <- "hello"
b <- "hello"
.Internal(inspect(a))
#> @0x0000020f0e6ba660 16 STRSXP g0c1 [REF(5)] (len=1, tl=0)
#>   @0x0000020f0ff60e38 09 CHARSXP g0c1 [MARK,REF(7),gp=0x60] [ASCII] [cached] "hello"
.Internal(inspect(b))
#> @0x0000020f0e709dc8 16 STRSXP g0c1 [REF(5)] (len=1, tl=0)
#>   @0x0000020f0ff60e38 09 CHARSXP g0c1 [MARK,REF(7),gp=0x60] [ASCII] [cached] "hello"

The outer STRSXP addresses differ (they are separate character vectors), but the inner CHARSXP they point to is the same object. This interning saves memory when the same strings appear repeatedly, as in a factor or a character column with many repeated levels.

A list (VECSXP) is a vector of SEXP pointers. Each element can point to any R object of any type, which is why lists are heterogeneous: the list itself is an array of pointers, and the pointed-to objects can be anything. This pointer-based layout has consequences for tabular data. A data frame is a list of column vectors, each a contiguous array. Operations that scan down a column (summing, filtering, grouping) touch sequential memory and benefit from prefetching; operations that walk across a row jump between columns, touching addresses far apart. That is one reason column-wise operations in R are faster than row-wise ones.

Exercises

1. Use lobstr::obj_size() to compare the size of integer(1000) and double(1000). Is the ratio exactly 1:2? Why or why not?

2. Create two character vectors: x <- rep("abcdef", 1000) and y <- paste0("abcdef", seq_len(1000)). Compare their sizes with obj_size(). Why is x much smaller?

3. Why does object.size(data.frame(a = 1:1e6)) report less memory than object.size(data.frame(a = as.double(1:1e6)))?

29.5 Reference counting and copy-on-modify

In Section 9.4, you learned that R copies objects only when they are modified and shared. But how does R decide?

Every SEXPREC header contains a reference count: the number of names (bindings) currently pointing to this object. When you assign y <- x, R increments the reference count on the underlying object instead of copying it. When you modify y, R checks the count: if it is 1 (only y points to the object), R can modify in place; if it is greater than 1, R must copy first.

x <- c(1, 2, 3)
.Internal(inspect(x))
#> @0x0000020f1031b958 14 REALSXP g0c3 [REF(2)] (len=3, tl=0) 1,2,3

REF(...) in the inspect output is the reference count.

y <- x
.Internal(inspect(x))
#> @0x0000020f1031b958 14 REALSXP g0c3 [REF(5)] (len=3, tl=0) 1,2,3

After y <- x, the count goes up but the address stays the same. Both names share the same data.

NoteBefore reference counting

Until R 4.0.0 (2020) the header carried a field called NAMED with three states: 0 for no references, 1 for one, and 2 for “more than one, or we have lost count”. NAMED could never decrease, so once an object reached 2, R copied it on every modification for the rest of its life, even after the extra reference was gone. Luke Tierney’s reference counter, which replaced it, tracks actual counts and lowers them when bindings disappear, which removed a whole class of unnecessary copies.

You can observe the practical effect. Modifying a vector inside a function that receives it as an argument triggers a copy, because the caller’s binding and the function’s parameter both point to the object (reference count of at least 2):

f <- function(v) {
  v[1] <- 0
  v
}

x <- c(1, 2, 3)
y <- f(x)
ref(x, y)
#> [1:0x20f109057c8] <dbl> 
#>  
#> [2:0x20f10904e18] <dbl>

x and y are different objects. The copy happened inside f when v[1] <- 0 was executed, because v shared its data with x.

TipOpinion

Reference counting is why you should not worry too much about “R copies everything.” R copies only when it must: when an object is shared and you modify it. Patterns that look wasteful, like passing large data frames into functions, are often free, because the function receives a pointer, not a copy. The copy happens only if the function modifies the data, which idiomatic functional code rarely does.

Exercises

1. Predict whether a copy occurs in each case, then verify with lobstr::ref():

   a <- 1:1e6
   b <- a           # copy?
   b[1] <- 0L       # copy?
   c <- a            # copy?
   rm(a)
   c[1] <- 0L       # copy now?

2. Write a function that takes a vector, does not modify it, and returns its obj_addr(). Call it with a large vector. Is the address the same inside and outside the function?

29.6 Garbage collection

Objects get created; reference counts rise and fall; eventually some objects have no references at all. What happens to them?

R uses a tracing garbage collector with a mark-and-sweep algorithm. When R runs low on memory, the collector pauses execution, traces all reachable objects by following pointers from the known roots (the global environment, the call stack, the symbol table), marks them, and sweeps away everything unmarked. If a SEXP has no path back to any root, it ceases to exist.

The collector is generational, dividing objects into three generations based on how long they have survived. New objects are generation 0; objects that survive one collection get promoted to generation 1, then to generation 2. The bet behind this design is that most objects die young (temporary vectors in a loop, intermediate results in a pipeline), so collecting generation 0 often and generation 2 rarely is efficient. Java’s and .NET’s collectors make the same bet.

You can trigger collection manually and see the results:

gc()
#>           used (Mb) gc trigger (Mb) max used (Mb)
#> Ncells  696293 37.2    1428252 76.3  1428252 76.3
#> Vcells 1272773  9.8    8388608 64.0  1938031 14.8

The output shows memory usage in Ncells (cons cells, used for pairlists and language objects) and Vcells (vector cells, used for vector data). The “used” column is current consumption; “max used” is the peak since the last gc(reset = TRUE).

gcinfo(TRUE) tells R to print a message every time the garbage collector runs, which is noisy but revealing when you want to understand how much allocation a piece of code is doing:

gcinfo(TRUE)
x <- lapply(1:1000, function(i) rnorm(1000))
gcinfo(FALSE)

The collector has one consequence for anyone who writes C code that creates R objects. It can run at any allocation, and if a SEXP you have just created is not reachable from any root, it will be swept away while you are still using it. The PROTECT() macro adds an object to a protection stack; UNPROTECT(n) removes the last n entries. Forgetting a PROTECT is the most common bug in R’s C extensions: a segfault that depends on the exact moment the collector happens to run, so it appears intermittently and rarely on the machine where the code was written.

/* Example: a C function callable from R via .Call() */
SEXP add_one(SEXP x) {
    SEXP result = PROTECT(allocVector(REALSXP, length(x)));
    double *px = REAL(x);
    double *pr = REAL(result);
    for (R_xlen_t i = 0; i < length(x); i++) {
        pr[i] = px[i] + 1.0;
    }
    UNPROTECT(1);
    return result;
}

The PROTECT(allocVector(...)) call allocates a new vector and protects it in a single line. The UNPROTECT(1) at the end removes it from the protection stack just before returning. Between those two points, the GC knows not to collect result. Get the count wrong, and you get either a segfault or a stack overflow, which is exactly why higher-level interfaces like Rcpp exist.

Exercises

1. Run gc() and note the “used” Vcells. Then create x <- rnorm(1e7), run gc() again, and note the change. Now rm(x) and gc() one more time. Did the Vcells return to roughly the original level?

2. What does gc(full = TRUE) do differently from gc()?

3. In the C function add_one above, what would happen if you removed the PROTECT() call? Would the bug appear every time, or only sometimes?

29.7 The evaluator

When you type an expression at the console, R parses it into a tree (a LANGSXP) and walks that tree in a C function called eval(), in the file eval.c. Since R 3.4.0 a just-in-time compiler translates closures into bytecode after their first couple of calls (compiler::enableJIT(-1) reports the current level, 3 by default), and a second interpreter in the same file runs that bytecode; the tree walk sketched below is what the console, the first calls of any function, and everything the compiler declines to handle go through.

The core of eval() is a large switch statement on the SEXPTYPE of the expression:

/* Simplified sketch of eval.c (not actual code) */
SEXP eval(SEXP e, SEXP rho) {
    switch (TYPEOF(e)) {
    case SYMSXP:    /* symbol: look up in environment */
        return findVar(e, rho);
    case LANGSXP:   /* function call: evaluate function and args, then apply */
        return applyClosure(e, rho);
    case PROMSXP:   /* promise: force it */
        return forcePromise(e);
    case REALSXP:
    case INTSXP:
    case STRSXP:    /* self-evaluating literals */
        return e;
    /* ... many more cases ... */
    }
}

When the expression is a symbol (SYMSXP), the evaluator looks it up in the environment rho by walking the chain of parent environments. When it is a function call (LANGSXP), the evaluator finds the function, evaluates the arguments (wrapping them in promises for closures), and calls it. When it is a literal (a number, a string), it returns the value unchanged.

This is why an R loop is slower than a compiled one: bytecode or not, every variable access is an environment lookup and every function call builds promises and matches arguments. Vectorized code avoids most of this by dropping into C for the inner loop, where none of these costs exist. The environments the evaluator searches through are data structures of their own: a frame of bindings (name-to-SEXP mappings) plus a pointer to a parent environment. Small frames, such as the execution environment of a function call, are plain lists; the global environment and package namespaces are hash tables (Section 9.3). Lookup walks the chain: check the current frame, then the parent’s, then the grandparent’s, up to the global environment and then the search path of attached packages.

29.8 Promises at C level

In Chapter 23 you learned that function arguments arrive as promises. Try to look at one:

f <- function(x) {
  cat("typeof x:", typeof(x), "\n")
  x
}
f(1 + 1)
#> typeof x: double
#> [1] 2

typeof(x) reports "double", never "promise", because asking for the type of x uses x, and using a promise forces it. Any inspection from R evaluates the promise first, which is why substitute() exists as a separate door: it reads the stored expression without touching it.

At the C level the promise (PROMSXP) is a struct with three fields: the expression (PRCODE), stored as a LANGSXP or SYMSXP; the environment to evaluate it in (PRENV); and the value (PRVALUE), initially the sentinel R_UnboundValue. When the evaluator meets a PROMSXP it checks PRVALUE. If it is still unbound, it evaluates PRCODE in PRENV, stores the result, and sets PRENV to R_NilValue so the environment can be collected. If a value is already there, it returns it. Evaluate once, cache forever.

The three fields explain behaviour from earlier chapters. A default argument can refer to another argument because PRENV is the function’s execution environment, where the earlier parameters are already bound. substitute() can hand back the unevaluated expression because it reads PRCODE directly. And the lazy evaluation trap in function factories (Section 20.2) happens because the promise stores the expression and the environment at call time and evaluates them later, after the environment has changed. Closures, the other abstraction those chapters relied on, have their own three-field struct.

29.9 Closures at C level

Take a closure apart from R:

adder <- function(n) function(x) x + n

add5 <- adder(5)

formals(add5)
#> $x
body(add5)
#> x + n
environment(add5)
#> <environment: 0x0000020f106b8548>

formals(), body(), and environment() read the three pointers of a CLOSXP: FORMALS, a pairlist of argument names and defaults; BODY, the parsed function body as a LANGSXP; and CLOENV, the environment the function was defined in. The environment of add5 is the execution environment created when adder(5) was called, and it contains the binding n = 5. This is lexical scoping made concrete: the closure carries a pointer to the environment where it was born, and that environment stays alive as long as the closure exists, because the GC traces the pointer and keeps the environment reachable.

Every user-defined function in R is a CLOSXP. Even a bare function(x) x + 1 carries all three fields. The distinction between “function” and “closure” that some languages make does not exist in R’s implementation. But not all callable things in R are closures, and the mechanisms for reaching compiled code differ in important ways.

Exercises

1. Use environment(), formals(), and body() to inspect stats::lm. What environment does it carry?

2. Create a function factory make_power(exp) that returns function(x) x^exp. Create square <- make_power(2) and cube <- make_power(3). Use ls(environment(square)) and ls(environment(cube)) to confirm each closure has its own environment.

29.10 Three roads to C

R provides three mechanisms for calling compiled code. They differ in age, safety, and flexibility.

The oldest road, .Primitive(), is also the most restrictive. Primitive functions are built into the R interpreter itself; you cannot write new ones, because they are defined in a table in names.c in the R source. Examples include +, [, if, for, c(), and sum(). Primitives skip normal argument matching (some evaluate arguments before the call, some do not), which is why they are fast but also why their behavior sometimes surprises you.

sum
#> function (..., na.rm = FALSE)  .Primitive("sum")
`+`
#> function (e1, e2)  .Primitive("+")

The .Primitive("...") form shows that these functions are entry points into the C code of the interpreter itself.

The second road, .Internal(), calls C functions that are registered in R’s internal table but not exposed as primitives. They go through normal argument matching first, so many base R functions are thin R wrappers around .Internal() calls:

body(paste)
#> .Internal(paste(list(...), sep, collapse, recycle0))

The R-level function handles argument matching, default values, and error messages. The .Internal() call does the actual work in C.

The third road, .Call(), is the modern interface for extensions. It passes R objects (SEXPs) directly to a C or C++ function in a shared library (a .so or .dll file), where the C function receives SEXPs, manipulates them using R’s C API, and returns a SEXP. This is what data.table, Rcpp-based packages, and the tidyverse use for performance-critical code. Section 31.1 covers it with complete working examples.

/* A .Call function signature */
SEXP my_function(SEXP x, SEXP y) {
    /* work with x and y using R's C API */
    return result;
}

From R, you call it as .Call("my_function", x, y) or, more commonly, through a wrapper function generated by Rcpp or the package’s registration mechanism.

There is also .C() and .Fortran(), older interfaces that pass raw C arrays (not SEXPs). They are still used in some legacy packages, but .Call() is preferred for new code because it avoids unnecessary copying and gives full access to R object metadata.

Exercises

1. Check typeof(sum) and typeof(mean). One is "builtin", the other is "closure". What does this tell you about how each is implemented?

2. Look at the source of base::nchar (just type nchar at the console). Can you find the .Internal() call?

3. Why can’t you write a new .Primitive() function in a package?

29.11 Reading R’s source code

R’s source code is available at https://svn.r-project.org/R/ and mirrored on GitHub at https://github.com/wch/r-source. The interpreter lives in src/main/: eval.c is the evaluator, memory.c handles allocation and garbage collection, envir.c the environment operations, names.c the table of primitive and internal functions, and arithmetic.c the vectorized arithmetic. The parser grammar, in yacc format, is src/main/gram.y; the public C API, with every SEXP macro, type constant, and accessor, is src/include/Rinternals.h; and the R-level code for base functions is under src/library/base/R/.

To find where something is implemented, search names.c for the function name. That file maps R names to C function pointers, so searching for "cumsum" shows you it is implemented by do_cum in cum.c. The type of a function tells you which table to look in:

typeof(`if`)
#> [1] "special"
typeof(`+`)
#> [1] "builtin"
typeof(mean)
#> [1] "closure"

The distinction between builtin and special is about argument evaluation. Builtins evaluate all arguments before calling the C function (like normal function calls). Specials handle argument evaluation themselves, which is how if can avoid evaluating the branch not taken and && can short-circuit.

29.12 Putting it together

When you type x <- c(1, 2, 3) at the console, here is everything that happens:

1. The parser (gram.y) converts the text into a LANGSXP: a tree with <- at the root, x (a SYMSXP) on the left, and a call to c (another LANGSXP) on the right.

2. The evaluator (eval.c) processes the LANGSXP. It sees <- (a SPECIALSXP), evaluates the right-hand side first. The call to c is a BUILTINSXP, so all arguments are evaluated (they are literals, so they evaluate to themselves), and the C function do_c builds a REALSXP: a SEXPREC with a header and three contiguous doubles.

3. The evaluator binds the name x to the new SEXP in the current environment’s frame. The reference count is set to 1.

4. Later, if you write y <- x, the evaluator adds a new binding in the frame pointing to the same SEXP and increments the reference count to 2. No copy.

5. If you then write y[1] <- 99, the evaluator sees that the reference count is 2, so it copies the REALSXP, modifies the copy, and points y at the copy. x still points at the original. Reference count on the original drops to 1; reference count on the copy is 1.

6. If x goes out of scope or is removed with rm(), its reference count drops to 0. The next time the garbage collector runs (triggered when R needs more memory), it finds the original SEXP unreachable and reclaims its memory.

This is the full lifecycle: allocation, binding, sharing, copying when needed, and collection. Every R program is many of these cycles interleaved, and copy-on-modify, lexical scoping, and lazy evaluation are what the cycles look like from above. The next chapter goes the other way: instead of the C underneath function(), what function() alone can build.

Exercises

1. Trace the lifecycle of f <- function(x) x + 1 using the concepts from this chapter. What SEXPTYPE is created? What are its three fields? Where is it stored?

2. Consider df <- data.frame(a = 1:3, b = c("x", "y", "z")). How many SEXPs are involved? (Think about the data frame itself, each column, each string, the names attribute.)

3. Look at the R source for a base function you use frequently (e.g., rev, which, paste). Find the .Internal() or .Primitive() call. Then search names.c in the R source mirror to find the corresponding C function name.

4. Ross Ihaka’s 2010 paper “R: Lessons Learned, Directions for the Future” discusses design decisions he would change. Find it online and identify one regret related to the topics in this chapter.