R in Java

FastR: an implementation of the R language

Petr Tomas Jan Floréal Helena

Maj Kalibera Vitek Morandat Kotthaus Java cup

Purdue University & Oracle Labs

[Link]
 10 Morandat et al.
Java cup
substitute. As the object system is built on those, we will only hint at its defini-
tion. The syntax of Core R, shown in Fig. 1, consists of expressions, denoted by e,
ranging over numeric literals, string literals, symbols, array accesses, blocks, function
declarations, function calls, variable assignments, variable super-assignments, array

What we do…
assignments, array super-assignments, and attribute extraction and assignment. Expres-
sions also include values, u, and partially reduced function calls, ⌫(a), which are not
used in the surface syntax of the language but are needed during evaluation. The pa-
rameters of a function declaration, denoted by f, can be either variables or variables
with a default value, an expression e. Symmetrical arguments of calls, denoted a, are
expressions which may be named by a symbol. We use the notation a to denote the

• TimeR — an instrumentation-based profiler for GNU-R

possibly empty sequence a1 . . . an . Programs compute over a heap, denoted H, and a

H::= ; | H[◆/F ]
stack, S, as shown in Fig. 2. For simplicity, the heap dif-
ferentiates between three kinds of addresses: frames, ◆,
| H[ /e ] | H[ /⌫] promises, , and data objects, ⌫. The notation H[◆/F ]

• TracR — a trace analysis framework for GNU-R

| H[⌫/↵ ] denotes the heap H extended with a mapping from ◆
↵::= ⌫? ⌫? u ::= | ⌫ to F . The metavariable ⌫? denotes ⌫ extended with the
::= num[n] | str[s] distinguished reference ? which is used for missing val-
| gen[⌫] | f.e, ues. Metavariable ↵ ranges over pairs of possibly missing

• CoreR — a formal semantics for a fragment of R

F ::= [] | F [x/u] addresses, ⌫? ⌫? . The metavariable u ranges over both
0

::= [] | ◆ ⇤ promises and data references. Data objects, ↵ , consist

S::= [] | e ⇤ S of a primitive value  and attributes ↵. Primitive val-
ues can be either an array of numerics, num[n1 . . . nn ],

• TestR — a testing framework for the R language

Fig. 2. Data an array of strings, str[s1 . . . sn ], an array of references
gen[⌫1 . . . ⌫n ], or a function, f.e, , where is the func-
tion’s environment. A frame, F , is a mapping from a symbol to a promise or data
12 Morandat et al.
reference. An environment, , is a sequence of frame references. Finally, a stack, S,

• FastR — a new R virtual machine written in Java

The ! relation has fourteen rules dealing with expressions, shown in Fig. 5, along
is a sequence of pairs, e , such that e is the current expression and is the current with some auxiliary definitions given in Fig. 18 (where s and g denote functions that
convert the type of their argument to a string and vector respectively). The first two

environment. Evaluating the Design of R 11

rules deal with numeric and string literals. They simply allocate a vector of length one
of the corresponding type with the specified value in it. By default, attributes for these
values are empty. A function declaration, [F UN], allocates a closure in the heap and

[N UM ] [S TR ] [F UN ]
⌫ fresh ↵ = ? ? ⌫ fresh ↵ = ? ? ⌫ fresh ↵ = ? ?
[E XP ] [F ORCE P] H 0 = H[⌫/num[n]↵ ] H 0 = H[⌫/str[s]↵ ] H 0 = H[⌫/ f.e, ↵ ]
0 0 0 n ; H ! ⌫; H 0 s ; H ! ⌫; H 0 function(f) e ; H ! ⌫; H 0
e ;H ! e ;H H( ) = e [F IND ] [G ET P]

⇤ S; H = C[e0 ] ⇤ S; H 0 ⇤ S; H = e 0 ⇤ C[ ]
(H, x) = u H( ) = ⌫
C[e] C[ ] ⇤ S; H x ; H ! u; H ; H ! ⌫; H 0
[A SS ]
0 0 0
cpy(H, ⌫) = H , ⌫ =◆⇤ H(◆) = F F = F [x/⌫ 0 ] 0
H 00 = H 0 [◆/F 0 ]
[F ORCE F] [G ET F] x < ⌫ ; H ! ⌫; H 00
getfun(H, , x) = getfun(H, , x) = ⌫ cpy(H, ⌫) = H 0 , ⌫ 0 = ◆ ⇤ 0 assign(x, ⌫ 0 , 0
[DA SS ]
, H 0 ) = H 00
x << ⌫ ; H ! ⌫; H 00
C[x(a)] ⇤ S; H = ⇤ C[x(a)] ⇤ S; H C[x(a)] ⇤ S; H = C[⌫(a)] ⇤ S; H [G ET ]
(H, x) = ⌫ 0 readn(⌫, H) = m get(⌫ 0 , m, H) = ⌫ 00 , H 0
[I NV F] x[[⌫]] ; H ! ⌫ 00 ; H 0

H(⌫) = f.e, 0 args(f, a, , 0 , H) = F, 00 , H 0

[S ET L]
cpy(H, ⌫ 0 ) = H 0 , ⌫ 00 = ◆ ⇤ 0 ◆(H 0 , x) = ⌫ 000
readn(⌫, H 0 ) = m set(⌫ 000 , m, ⌫ 00 , H 0 ) = H 00
C[⌫(a)] ⇤ S; H = e 00 ⇤ C[⌫(a)] ⇤ S; H 0 x[[⌫]] < ⌫ 0 ; H ! ⌫ 0 ; H 00
[S ET G]
[R ET P] [R ET F] cpy(H, ⌫ 0 ) = H 0 , ⌫ 00 = ◆ ⇤ 0 H 0 (◆) = F 0
x 62 F (H 0 , x) = ⌫ 000
cpy(H 0 , ⌫ 000 ) = H 00 , ⌫ 0000 F 0 = F [x/⌫ 0000 ] H 000 = H 00 [◆/F 0 ]
H 0 = H[ /⌫] readn(⌫, H) = m set(⌫ 0000 , m, ⌫ 00 , H 000 ) = H 0000
x[[⌫]] < ⌫ 0 ; H ! ⌫ 0 ; H 0000
0
0
R[⌫] ⇤ C[ ] ⇤ S; H = C[ ] ⇤ S; H 0 R[⌫] ⇤ C[⌫ 0 (a)] ⇤ S; H = C[⌫] ⇤ S; H 0 H(⌫) = ↵ 0
↵ = ⌫? ⌫? index(⌫ 0 , ⌫?
0
, H) = n get(⌫? , n, H) = ⌫ 00
[G ETA]

26 Morandat et al. attr(⌫, ⌫ 0 ) ; H ! ⌫ 00 ; H

[R EPL A]
0
H(⌫) = ↵ index(⌫ 0 , ⌫?
0
, H) = n set(⌫, n, ⌫ 00 , H) = H 0
Evaluation Contexts: ↵ = ⌫? ⌫?
attr(⌫, ⌫ 0 ) < ⌫ 00 ; H ! ⌫ 00 ; H 0
[S ETA]
0

C ::= [] | x < C | x[[C]] | x[[e]] < C | x[[C]] < ⌫ | {C; e} | {⌫; C} cpy(H, ⌫ 00 ) = H 0 , ⌫ 000 H 0 (⌫) = ⌫? ⌫? index(⌫ 0 , ⌫?
0
, H 0 ) = ? reads(⌫ 0 , H 0 ) = s
0 0
H 0 (⌫? ) = gen[⌫]↵ H 0 (⌫? 0
) = str[s]↵ H 00 = H 0 [⌫? /gen[⌫⌫ 000 ]↵ ][⌫?
0
/str[ss]↵ ]

| attr(C, e) | attr(⌫, C) | attr(e, e) < C | attr(C, e) < ⌫ | attr(⌫, C) < ⌫ attr(⌫, ⌫ 0 ) < ⌫ 00 ; H ! ⌫ 00 ; H 00
[S ET B]
cpy(H, ⌫ 00 ) = H 0 , ⌫ 3 H 0 (⌫) = ? ? ⌫ 4 , ⌫ 5 fresh reads(⌫ 0 , H 0 ) = s
R ::= [] | {⌫; R} H 00 = H 0 [⌫ 4 /gen[⌫ 3 ]? ? ][⌫ 5 /str[s]? ? ]
attr(⌫, ⌫ 0 ) < ⌫ 00 ; H ! ⌫ 00 ; H 00

Fig. 5. Reduction relation ! .

Fig. 3. Reduction relation =) .
Fig. 3. Reduction relation =) .
Morandat, Hill, Osvald, Vitek. Evaluating the Design of the R Language. ECOOP’12
=◆⇤ 0
◆(H, x) = ⌫ H(⌫) = f.e,
[G ET F1]
00
= ◆ ⇤ 0 ◆(H, x) = ⌫ H(⌫) 6= f.e,
[G ET F2]
00

getfun(H, , x) = ⌫ getfun(H, , x) = getfun(H, 0 , x)

[G ET F3] [G ET F4]
0 00 0 00
=◆⇤ ◆(H, x) = H( ) = ⌫ H(⌫) = f.e, =◆⇤ ◆(H, x) = H( ) = e
getfun(H, , x) = ⌫ getfun(H, , x) =
[G ET F5]
0 00
=◆⇤ ◆(H, x) = H( ) = ⌫ H(⌫) 6= f.e,
 Why?
… language for data analysis and graphics
… used in statistics, biology, finance …
… books, conferences, user groups
… 4,338 packages
… 3 millions users
Scripting data
read data into variables
make plots
compute summaries
more intricate modeling
develop simple functions
to automate analysis
…
 R history
John Chambers @ Bell Labs, then S-Plus
• 1976 S (closed-source owned by Tibco)
Ross Ihaka and Robert Gentleman,
• 1993 R started R as new language at the
University of Auckland, NZ
• Today, The R project
Core team ~ 20 people, released under
GPL license. Continued development of
language & libraries: namespaces (‘11),
[Link] bytecode (‘11), indexing beyond 2GB (‘13)
[Link]
 What R is… What R isn’t…
• vectorized • fast
• functional • low-footprint
• object-oriented • concurrent
• lazy • distributed
• portable • formally specified
• interactive • standardized
 Intel X5460. 3.16GHz, Linux 2.6.34. R 2.12.1, GCC v4.4.5
The programming language shootout
C / Python / R
1 5 10 50 500

S−1

S−2

S−3

S−4

S−5

S−6

S−7

Fig. 6. Slowdown of Performance

S−8

S−9

S−10

S−11
Python

S−12
R

Avg
Python and R, normalized to C
 e created by pairlist().
ntioned above, they are C R User data R internal

used by the R VM. In

so consumes significant amounts of memory. Unlike C
Intel X5460. 3.16GHz, Linux 2.6.34. R 2.12.1, GCC v4.4.5
e standard library only
significant
ted, alltouser amounts
data in R must
MB of memory. Unlike Cand garbage
be heap allocated

10000
ee calls pairlist , the The programming language shootout
data
CRAN in code
pamounts
memory R must onlybe
usage heap
eight,
in C allocated
(calls to and garbage
malloc) and data allocated
of memory. Unlike C
sage
R in
oconductor C
allocation (calls
none.
is to
The
splitmalloc)
R
between and data allocated
vectors (which are typically
esstthem
be heap allocated
to represent code and garbage

1000
is mostly
e split between
used by vectors
the (which are
interpreter for,typically
e.g., arguments to
alls
passtoandmalloc)
processand func-data allocated
edhows
ll by that
the R
arguments. interpreter
allocates
It is inter- for, e.g.,
orders of argumentsmore
magnitude to data than
ween vectors (which are typically
allocates
o note that
cases,
terpreterthe orders
the
internal
for,
of
time spent
e.g.,
magnitude
data required
arguments
more
is
to moredata than
than the user data.
100
C/R

cating lists
ernal data isrequired
greater than is more than the user data.
mplemented
ders of by
magnitude a copy-on-write
more data (COW)
than mechanism. Thus,
e spent on vectors. Cons
y a copy-on-write
are
e 56shared
quired byte andand
islong,
more only
than (COW) usermechanism.
duplicated
takethe if there isThus,
data. actually a need
des only duplicated if there is actually a needalgorithm is
10

GB memory
-write on(COW)
average footprint.
in the
mechanism. Even Thus,
though the COW
ootprint.
ut37% Even is
ofif arguments
benchmarks.
icated there though are the
actually aCOW
[Link] algorithm is
other reason
uments are for the large
copied.
t() .
enisthough the COW data algorithm is
1

nt that all numeric

re boxed into a vector.C
opied.
S−1

S−2

S−3

S−4

S−5

S−6

S−7

S−8

S−9

S−10

S−11

S−12
R User data R internal
be
Inof vectors
% C allocated in R User data R internal
Heap Allocated Memory
ly
conductor vignettes
R User data con- Fig.
R internal 8. Heap allocated memory (MB log scale). C vs. R.
y a single numeric value.
0000

he
 where the

1.0
urn to more

0.9
grams. Fig. 7
n of execu-
ioconductor 0.8
th ProfileR.
0.7
mm
Builtin mm
mm
mm
mm
mm
alloc.c
a Biocon- [Link]
[Link]
[Link]
[Link]
[Link]
alloc.l
0.6

[Link]
[Link]
[Link]
[Link]
[Link]
key obser- External [Link]
[Link]
[Link]
[Link]
[Link] alloc.v
duplicate
duplicate
duplicate
duplicate
duplicate duplic
ry manage-
0.5

lookup
lookup
lookup
lookup
lookup lookup
n average of match
match
match
match
match match
Lookup external
external
external
external
external extern
0.4

me. Memory builtin

builtin
builtin
builtin
builtin builtin
was further Duplicate arith
arith
arith
arith
arith arith
0.3

special
special
special
special
special specia
me spent in Allocate vector
18.7%), al-
0.2

Allocate cons
3.6%), vec-
0.1

duplications
Garbage collection
lue seman-
0.0

nt in built-
d where the

1.0
Intel X5460. 3.16GHz, Linux 2.6.34. R 2.12.1, GCC v4.4.5
turn to more

0.9
ograms. Fig. 7
wn of execu-
0.8
Bioconductor
Bioconductor vignettes

with ProfileR.
0.7

mm
[Link]
ts a Biocon- [Link]
0.6

he key obser- [Link]

duplicate
mory manage-
0.5

lookup
an average of match
external
0.4

ime. Memory builtin

arith
was further
0.3

special
time spent in
(18.7%), al-
0.2

(3.6%), vec-
0.1

duplications
value seman-
0.0

ent in built- Time breakdown

sents the true Fig. 7. Time breakdown of Bioconductor vignettes.
How is R used?
•Extract core semantics by testing
- R has no official semantics
- A single reference implementation
•Observational study based on a large corpus
- Many open source programs come with “vignettes”
- Dynamic analysis gives under-approximated behaviors
- Static analysis gives over-approximation
 POPULATION
ast group is the base library that is bundled with
se datasets.
e
Name Bioc. Shoot. Misc. CRAN Base
-
t # Package 630 11 7 1238 27
# Vignettes 100 11 4 – –
e R LOC 1.4M 973 1.3K 2.3M 91K
- C LOC 2M 0 0 2.9M 50K
0
- Fig. 5. Purdue R Corpus.
o
e as it makes them harder to analyze. We retained
Vectors
x <- c(2,7,9,NA,5)

c(1,2,3) + x[1:3]
with(fd,carb*den) [Link]
x[[Link](x)] <- 0 <-function(data,exp,...)
eval(substitute(exp),
data,
[Link])))
Functions
q<-function(x=5)x*x*x
q()
q(2)
with(fd,carb*den) [Link]
q(x=4) <-function(data,exp,...)
eval(substitute(exp),
data,
p<-function(x=5,...,y=x+1) [Link])))
d an existing data structure to operate on, thus they are always side effecting.
ey account for 22% of all side effects and 12% of all assignments.

R symbol lookup is 1G
ensitive. This feature, Position
Keyword
either Lisp nor Scheme
s exercised in less than 1M
Variadic
f(1, 2)
unction name lookups.
even though this num-
1K
, the number of sym-
lly checked is 3.6 on
The only symbols for 1
s feature actually mat- 1G
f(x=1,y=2)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20−39
the Bioconductor vi-
c and file, both pop- 1M f(y=1,x=2)
bles names and built-in

1K
f(2,x=1)
rs. The R function
n syntax is expressive
expressivity is widely 1 f(x=1,2)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20−39
99% of the calls, at
1G

rguments are passed,

percentage of calls 1M
7 arguments is 99.74%
12). Functions that are c(1,2,3,4)
is average are typically 1K
h positional arguments.
mber of parameters in-
sers are more likely to 1
200−201
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20−39
40−59
60−79
80−99
100−119
120−139
140−159
171−196

255+

nction parameters by
milarly, variadic param-
to be called with large Fig. 12. Histogram of the number of function arguments
in Bioconductor. (Log scale)
Promises
assert<-function(C,P)
if (C) print(P)

assert( x==42, [Link]

with(fd,carb*den) print(“Oops”))
<-function(data,exp,...)
eval(substitute(exp),
data,
[Link])))
 12
f(1, 2)

10
8
f(x=1,y=2)
f(y=1,x=2)
6

f(2,x=1)
4

f(x=1,2)
2

c(1,2,3,4)
0

80 85 90 95 100

% of promises evaluated / vignette

(a) Promises evaluated (in %) (b
Forcing promises
x <- F

x[12] <- F

F ; e

{e ; F}
Scoping

Lexical scoping with context sensitive name resolution

c <- 42 c <- 42
d <- c
c(1,2,3) d(1,2,3)
less than 0.05% context sensitive
function name lookups

only symbols that rely on it are c

and file
Referential transparency
assert(y[[1]]==5)

f(y)
with(fd,carb*den) [Link]
assert(y[[1]]==5) <-function(data,exp,...)
eval(substitute(exp),
data,
f<-function(b){b[[1]]<-0} [Link])))
 [F IND ] [G ET P]
(H, x) = u H( ) = ⌫
Assignment
x ; H ! u; H ; H ! ⌫; H 0
[A SS ]
= H 0, ⌫0 = ◆ ⇤ 0 H(◆) = F F 0 = F [x/⌫ 0 ] H 00 = H 0 [◆/F 0 ]
x < ⌫ ; H ! ⌫; H 00
[DA SS ]
x [ 42
py(H, ⌫) = H 0 , ⌫ 0 = ◆ ⇤ ] assign(x,
<- ⌫ y, 0 0 0
, H 0 ) = H 00
x << ⌫ ; H ! ⌫; H 00
[G ET ]
(H, x) = ⌫ 0 readn(⌫, H) = m get(⌫ 0 , m, H) = ⌫ 00 , H 0
x[[⌫]] ; H ! ⌫ 00 ; H 0
[S ET L]
cpy(H, ⌫ 0 ) = H 0 , ⌫ 00 = ◆ ⇤ 0 ◆(H 0 , x) = ⌫ 000
readn(⌫, H 0 ) = m set(⌫ 000 , m, ⌫ 00 , H 0 ) = H 00
x[[⌫]] < ⌫ 0 ; H ! ⌫ 0 ; H 00
[S ET G]
⌫ 0 ) = H 0 , ⌫ 00 =◆⇤ 0
H 0 (◆) = F x 62 F 0
(H 0 , x) = ⌫ 000
py(H 0 , ⌫ 000 ) = H 00 , ⌫ 0000 F 0 = F [x/⌫ 0000 ] H 000 = H 00 [◆/F 0 ]
readn(⌫, H) = m set(⌫ 0000 , m, ⌫ 00 , H 000 ) = H 0000
 [F IND ] [G ET P]
(H, x) = u H( ) = ⌫

Assignment x ; H ! u; H ; H ! ⌫; H 0
[A SS ]
cpy(H, ⌫) = H 0 , ⌫ 0 = ◆ ⇤ 0 H(◆) = F F 0 = F [x/⌫ 0 ] H 00 = H 0 [◆/F 0 ]
x < ⌫ ; H ! ⌫; H 00
[DA SS ]
y <- c(…)
cpy(H, ⌫) = H 0 , ⌫ 0 = ◆ ⇤ 0 assign(x, ⌫ 0 , 0
, H 0 ) = H 00
x << ⌫ ; H ! ⌫; H 00
f <-
(H, x) = ⌫ 0
function() { 0
readn(⌫, H) = m get(⌫ , m, H) = ⌫ , H 00
[G ET ]
0

x x[[⌫]]
[ 42 ; H ! ⌫]; H <- 00 0
y [S ET L]
cpy(H, ⌫ 0 ) = H 0 , ⌫ 00 = ◆ ⇤ 0 ◆(H 0 , x) = ⌫ 000
readn(⌫, H 0 ) = m set(⌫ 000 , m, ⌫ 00 , H 0 ) = H 00
x[[⌫]] < ⌫ 0 ; H ! ⌫ 0 ; H 00
[S ET G]
0 0 00 0 0 0
cpy(H, ⌫ ) = H , ⌫ =◆⇤ H (◆) = F x 62 F (H , x) = ⌫ 000
0

cpy(H 0 , ⌫ 000 ) = H 00 , ⌫ 0000 F 0 = F [x/⌫ 0000 ] H 000 = H 00 [◆/F 0 ]

readn(⌫, H) = m set(⌫ 0000 , m, ⌫ 00 , H 000 ) = H 0000
x[[⌫]] < ⌫ 0 ; H ! ⌫ 0 ; H 0000
[G ETA]
0
H(⌫) = ↵ ↵ = ⌫? ⌫? index(⌫ 0 , ⌫?
0
, H) = n get(⌫? , n, H) = ⌫ 00
attr(⌫, ⌫ 0 ) ; H ! ⌫ 00 ; H
 [N UM ] [S TR ]
Assignment⌫ fresh
resh ↵ = ? ? ↵ = ?? ⌫ fresh ↵ = ? ?
= H[⌫/num[n]↵ ] H 0 = H[⌫/str[s]↵ ] H 0 = H[⌫/ f.e, ↵ ]
; H ! ⌫; H 0 s ; H ! ⌫; H 0 function(f) e ; H ! ⌫
[F IND ] [G ET P]
(H, x) = u H( ) = ⌫
x [ 42 ] <<-
x ; H ! u; H
y
; H ! ⌫; H 0

H, ⌫) = H 0 , ⌫ 0 = ◆ ⇤ 0 H(◆) = F F 0 = F [x/⌫ 0 ] H 00 = H 0 [◆
x < ⌫ ; H ! ⌫; H 00
[DA SS ]
cpy(H, ⌫) = H 0 , ⌫ 0 = ◆ ⇤ 0 assign(x, ⌫ 0 , 0
, H 0 ) = H 00
x << ⌫ ; H ! ⌫; H 00
[G ET ]
(H, x) = ⌫ 0 readn(⌫, H) = m get(⌫ 0 , m, H) = ⌫ 00 , H 0
x[[⌫]] ; H ! ⌫ 00 ; H 0
[S ET L]
cpy(H, ⌫ 0 ) = H 0 , ⌫ 00 =◆⇤ 0
◆(H 0 , x) = ⌫ 000
45% of assignments are definitions

only 2 out of 217 million

assignments are definitions in a
parent frame

99.9% of side effects are local

Objects
who <-function(x) UseMethod("who")

[Link] <-function(x) print("Ceasar!")

[Link] <-function(x)print("??")
with(fd,carb*den) [Link]
me <- 42; who(me)
<-function(data,exp,...)

class(me)<-‘man’; eval(substitute(exp),
who(me)
data,
[Link])))
 500
and, seem to S3 method redefinitions
al way. The
400
p (maximum
at either. The
300

surprisingly
, but reaches
uper-classes.
200

i.e., classes
are ignored.
100

f method re-
smaller than
t languages.
0

0
1
2
3
4
5
6
7
8
9
10
11−12
13−14
15−19
20−24
24−29
30−39
40−49
50−69
70−99
100−199
200−299
300−402
996
> 1000
the absence
class unions,
Fig. 16. S3 method redefinitions (on x axis).
Objects
setClass("P",representation(x="numeric",y="numeric"))
setClass("C",representation(color="character"))
setClass("CP",contains=c("P","C"))

r <- new("CP", x = 0, y = 0, color = "red")

r@color

setGeneric("add",
with(fd,carb*den)function(a, b) standardGeneric("add"))
[Link]
setMethod("add", signature("P","P"),
<-function(data,exp,...)
function(a, b) new("P", x=a@x+b @x, y=a@y+b@y))
eval(substitute(exp),
setMethod("add",signature("CP", "CP"),
function(a, b)new("CP",x=a@x+b@x,y=a@y+b @y,color=a@color)
data,
[Link])))
 Object usage
Evaluating the Design of R 23

arizes the use Bioc Misc CRAN Base Total

on in the cor- # classes 1 535 0 3 351 191 3 860
us, 1 055 S3 # methods 1 008 0 1 924 289 2 438
one fourth of S3 Avg. redef. 6.23 0 7.26 4.25 9.75
Method calls 13M 58M - - 76M
o methods de- Super calls 697K 1.2M - - 2M
1 107 classes, # classes 1 915 2 1 406 63 2 893
rint or plot # singleton 608 2 370 28 884
es the number # leaves 819 0 621 16 1 234
S3 methods. Hier. depth 9 1 8 4 9
finitions larger S4 Direct supers 1.09 0 1.13 0.83 1.07
# methods 4 136 22 2 151 24 5 557
ome polymor- Avg. redef. 3 1 3.9 2.96 3.26
gly, plot and Redef. depth 1.12 1 1.21 1.08 1.14
While impor- # new 668K 64 - - 668K
for these two Method calls 15M 266 - - 15M
stify an object Super calls 94K 0 - - 94K
already allow
 The trouble with R ?

•R is slow because it lacks a JIT

•R is a memory hog because it has large objects,
allocates profusely and a non-moving garbage collector

•R has tricky semantics rife with cobwebs and dark

corners

R is legacy software that must be maintained,

yet it must also evolve to meet new challenges
 R
in
Java
 Why Java ?

•Because JavaScript may not be fast enough

•Leverage a runtime system with zero-maintenance
•Get a good just-in-time compiler
•OpenJDK is an open source platform
 Why not Java ?

•The R community dislikes Java

•Interaction with C is cumbersome
•Complete break with GNU-R
R interpreter FastR Architecture
written in
Truffle
Java ANTLR
Specializing
parser Interpreter FastR Java
Runtime Libraries
47 KLOC Exec
OSR
Up to 20x
faster on Garbage
GRAAL Collector
shootout Hotspot JIT
Compiler Thread and
GPL license locks

Built on JNI
OpenJDK, Native libraries
Graal, Truffle (C, Fortran…)
FastR Throughput (w/o JIT)

[Link]

Java cup
 Interpretation

f(12, x+1, a=3)

gen_call
f f <- function(a,b,c){a+c}

exp exp exp

12 x+1 3
‘a’
 Specialization
guard

f == o

pos_call
gen_call f <- function(a,b,c){a+c}

exp exp exp

12 x+1 3
3 12 x+1
‘a’
 Runtime specialization
class If {
RNode condE, trueB, falseB;

Object execute(Frame f) {
try {
val = [Link](frame);
} catch (UnexpectedResult e) {
cast = [Link](condE, [Link]());
replaceChild(condE, cast);
return execute(frame);
}
if (val == TRUE) return [Link](f);
if (val == FALSE) return [Link](f);
throw unexpectedNA();
}
 Data types

• Data types are

specialized to optimize
memory usage and
speed

• Scalar are unboxed

when possible (soon)

• Memory footprint is
improved
 Views
Java cup

a <- b+c +
...
o <- a*2 *
2

• …delay construction of large data objects

• …are a data-flow representation of vectors
• …avoid unnecessary work if a subset of the data is required
• …avoid allocation of temporary objects
• …permit fusion of multiple data traversals into one
Experiments
 Inlining
spectralnorm-naive

A <- function(i, j) {
1 / ((i + j) * (i + j + 1) / 2 + i + 1) }

B <- function(u) { ...

for (j in 0:n1)
ret[[i]] <- ret[[i]] + u[[j + 1]]
* A(i - 1, j)
1.8x
• Inlining is a critical optimization in modern languages
• Replace a function call with it’s body
• Guarded inlining leaves a slow path in the code that performs
the normal function
 Relite
Delite is a compiler framework and runtime for parallel
embedded DSLs.
Delite provides:
• Built-in parallel execution patterns
• Optimizers for parallel code
• Code generators for Scala, C++ and CUDA
• A heterogeneous runtime for executing DSLs
Relite is a proof-of-concept R interface to Delite.
[Link]

Brown, e.a. A Heterogeneous Parallel Framework for Domain-Specific Languages PACT11

 Relite
sapply(1:50000, function(x){sum(1:x)})
4.1s GNU-R
1.5s FastR
Delite(sapply(1:50000,function(x) {sum(1:x)}))
0.4s Relite
sapply(1:50000,function(x) {sum((1:x)*0.1)})
9.0s GNU-R
2.2s FastR
0.5s Relite
sapply(1:50000,
function(x){ sum(sapply(1:x, function(y) y*0.1))})
2395s GNU-R
104s FastR
0.5s Relite
 Conclusions

• R is an amazingly successful systems with great mindshare

• The R implementation is hard to maintain and evolve
• The FastR project aims to rethink how to implement R
• We leverage well tested technologies to build a high
performance VM
• FastR can be a source of inspiration for GNU R