Benchmarking and Profiling

class: center, middle, inverse, title-slide

# Benchmarking and Profiling
### Niels Richard Hansen
### September 10, 2020

---

## Benchmarking density estimation

```r
source("kernel.R")  
```

[Source R code](kernel.R)

---
## Function profiling

The code profiler in the utils package samples at regular intervals the call 
stack when code is executed. It gives information about the execution time 
spent "within" each function.

```r
x <- rnorm(2^15)
profFile <- "prof.Rprof"
Rprof(profFile)
kern_dens(x, 0.2)
Rprof(NULL)
```

```r
summaryRprof("prof.Rprof")
```

---
## Function profiling

```
## $by.self
##             self.time self.pct total.time total.pct
## "kern_dens"      0.02      100       0.02       100
## 
## $by.total
##             total.time total.pct self.time self.pct
## "kern_dens"       0.02       100      0.02      100
## 
## $sample.interval
## [1] 0.02
## 
## $sampling.time
## [1] 0.02
```

Not very informative ....

---
## Recall the code of `kern_dens`

```r
kern_dens
```

```
## function (x, h, m = 512) 
## {
##     rg <- range(x)
##     xx <- seq(rg[1] - 3 * h, rg[2] + 3 * h, length.out = m)
##     y <- numeric(m)
##     for (i in seq_along(xx)) {
##         for (j in seq_along(x)) {
##             y[i] <- y[i] + exp(-(xx[i] - x[j])^2/(2 * h^2))
##         }
##     }
##     y <- y/(sqrt(2 * pi) * h * length(x))
##     list(x = xx, y = y)
## }
## <bytecode: 0x7fbbc533ae18>
```

---
## Line profiling

The `profvis` package can summarize profiling information 
by line in the source code. The following code will open a 
profiling display when evaluated in RStudio.

```r
library("profvis")
profvis(kern_dens(x, 0.2))
```

The [result](kern_dens_prof.html) is an interactive HTML page, which can be saved and viewed 
in a browser.

In this case the line profiler is not super informative either.

---
## Line profiling

The one-liner in the loop did too many things. The `kern_dens_detail()` spells out
the steps in this condensed expression.

```
## function (x, h, m = 512) 
## {
##     rg <- range(x)
##     xx <- seq(rg[1] - 3 * h, rg[2] + 3 * h, length.out = m)
##     y <- numeric(m)
##     for (i in seq_along(xx)) {
##         for (j in seq_along(x)) {
##             z <- xx[i] - x[j]
##             z <- z^2
##             z <- z/(2 * h^2)
##             z <- exp(-z)
##             y[i] <- y[i] + z
##         }
##     }
##     y <- y/(sqrt(2 * pi) * h * length(x))
##     list(x = xx, y = y)
## }
```

---
## Line profiling

```r
profvis(kern_dens_detail(x, 0.2))
```

The [result](kern_dens_detail_prof.html) of profiling the code for this function call 
is more informative.

You should compare the profiling result above with the 
[result from the initial `kern_dens`](kern_dens_prof.html) implementation.

---
## Conclusions from profiling

The line profiler revealed that most time is spent on the 
kernel evaluation.

A trick to reduce the `$nm$` kernel evaluations to a smaller number is
*binning*.

(On the slides and in my implementations, `$m$` denotes the number of grid points 
for the evaluation of the estimate and `$n$` the length of the data vector.)

If `$n < m$` binning may not be beneficial.

---
## Binning

```r
kern_bin
```

```
## function (x, lo, hi, m) 
## {
##     w <- numeric(m)
##     delta <- (hi - lo)/(m - 1)
##     for (j in seq_along(x)) {
##         i <- floor((x[j] - lo)/delta + 0.5) + 1
##         w[i] <- w[i] + 1
##     }
##     w/sum(w)
## }
```

The `kern_bin()` function is a loop along the data vector, and 
arithmetic is used to determine which bin center is closest to a 
data point.

The `kern_dens_bin()` function (see [source](kernel.R)) computes bin weights 
using `kern_bin()` with grid points as bin centers.

---
## Benchmarking

```r
p + geom_point(data = resKern3, size = 4, aes(color = "kern3"))
```

The computations become faster for long sequences when binning is used.

---
## Testing

```r
plot(kern_dens(x, 0.2), type = "l", lwd = 4)
lines(kern_dens_bin(x, 0.2), col = "red", lwd = 2)
```

---
## Testing

The absolute errors due to binning are small but increasing with 
decreasing length of data sequence. Here `$n = 8192$` is black, `$n = 1024$` 
is red and `$n = 128$` is blue.

---
## Line profiling

The `kern_dens_bin()` function is so much faster for long sequences that to get good 
profiling results we use a 512 times longer data sequence.

```r
x <- rnorm(2^22)
profvis(kern_dens_bin(x, 0.2))
```

The [result](kern_dens_bin_prof.html) shows that now the largest fraction of time was spent 
in the binning algorithm.

---
## Benchmarking

When `density()` or `kern_dens_bin()` are used on longer data vectors, we see how they scale
with the length of the vector.