CODEWITHSUNDEEP
rperformancematrixbenchmarkingmicrobenchmark
Euler_Salter
Euler_Salter

Reputation: 3561

is it faster to fill a matrix by row or to transpose a matrix filled by columns?

I was reading that R uses column-major storage in matrices, which means that elements in nearby columns are stored in contiguous blocks or something of that sort. This made me wonder: Is it faster to fill a matrix by row (using byrow=TRUE in the base R function matrix()) or is it faster to fill the matrix by column first (using the default byrow=FALSE) and then transpose it using t()?

I tried benchmarking it.

Filling a Matrix by Row

> microbenchmark(matrix(1, n, n, byrow=TRUE))
Unit: seconds
                          expr      min       lq     mean   median       uq      max neval
 matrix(1, n, n, byrow = TRUE) 1.047379 1.071353 1.105468 1.081795 1.112995 1.628675   100

Filling a Matrix by Column and then Transpose it

> microbenchmark(t(matrix(1, n, n)))
Unit: seconds
               expr     min       lq     mean  median       uq      max neval
 t(matrix(1, n, n)) 1.43931 1.536333 1.692572 1.61793 1.726244 3.070821   100

Conclusion

It seems that it's faster to fill the matrix by row! Am I missing something? I would have thought that R would just do some relabelling with t() but it's actually slower than filling in the matrix by row!

Is there an explanation for this? I'm quite baffled.

Observation

After ThomasIsCoding's answer and after benchmarking myself a few times it looks like it depends on the number of rows and number of columns.

Upvotes: 2

Views: 1113

Answers (2)

ThomasIsCoding
ThomasIsCoding

Reputation: 102241

I think it depends on the relation between numbers of columns and rows.

It should be noted that, in the method "Filling a Matrix by Column and then Transpose it", filling by row is faster, but transposition is the bottleneck for the speed.

  • number of rows > number of columns 
n <- 1e5
m <- 1e3
microbenchmark(matrix(1, n, m, byrow=TRUE),
               t(matrix(1, m, n)),
               check = "equal",
               unit = "relative",
               times = 10)

such that

Unit: relative
                          expr     min       lq     mean   median       uq      max neval
 matrix(1, n, m, byrow = TRUE) 1.00000 1.000000 1.000000 1.000000 1.000000 1.000000    10
            t(matrix(1, m, n)) 3.57835 3.556422 3.935004 3.583247 3.714243 4.820607    10

and 

> # fill by row
> system.time(x <- matrix(1, n, m, byrow=TRUE))
   user  system elapsed 
   0.48    0.08    0.61 
> # fill by column
> system.time(y <- matrix(1, m, n))
   user  system elapsed 
   0.03    0.14    0.17 
> # transpose
> system.time(t(y))
   user  system elapsed 
   1.59    0.08    1.71
  • number of rows < number of columns 
n <- 1e3
m <- 1e5
microbenchmark(matrix(1, n, m, byrow=TRUE),
               t(matrix(1, m, n)),
               check = "equal",
               unit = "relative",
               times = 10)

such that

Unit: relative
                          expr      min       lq     mean   median       uq      max neval
 matrix(1, n, m, byrow = TRUE) 1.885902 1.893168 1.717817 1.730453 1.744869 1.480463    10
            t(matrix(1, m, n)) 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000    10

and

> # fill by row
> system.time(x <- matrix(1, n, m, byrow=TRUE))
   user  system elapsed 
   0.92    0.39    1.33 

> # fill by column
> system.time(y <- matrix(1, m, n))
   user  system elapsed 
   0.13    0.08    0.20 

> # transpose
> system.time(t(y))
   user  system elapsed 
   0.47    0.10    0.58
  • number of rows = number of columns 
n <- 1e4
m <- 1e4
microbenchmark(matrix(1, n, m, byrow=TRUE),
               t(matrix(1, m, n)),
               check = "equal",
               unit = "relative",
               times = 10)

such that

Unit: relative
                          expr      min       lq     mean   median       uq      max neval
 matrix(1, n, m, byrow = TRUE) 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000    10
            t(matrix(1, m, n)) 1.163218 1.197249 1.279579 1.178185 1.354539 1.387548    10

and 

> # fill by row
> system.time(x <- matrix(1, n, m, byrow=TRUE))
   user  system elapsed 
   1.18    0.18    1.47 

> # fill by column
> system.time(y <- matrix(1, m, n))
   user  system elapsed 
   0.08    0.10    0.17 

> # transpose
> system.time(t(y))
   user  system elapsed 
   2.47    0.14    2.63

Upvotes: 5

BigFinger
BigFinger

Reputation: 1043

In R matrices are stored column-wise as vectors. Filling a matrix by columns is more efficient than filling it by rows. The transpose function makes a copy of the underlying vector with rearranged elements. As a result, the total time of filling by columns and doing a transpose is a combination of 2 opposing effects: filling the matrix more efficiently and adding the overhead of copying and rearranging.

Adding benchmarks similar to those of ThomasIsCoding to address the comments:

library(microbenchmark)

n <- 1e5
m <- 1e3
microbenchmark(matrix(1, n, m, byrow=TRUE),
               matrix(1, n, m),
               t(matrix(1, m, n)),
               check = "equal",
               unit = "relative",
               times = 10)
## Unit: relative
##                           expr      min       lq     mean   median       uq      max neval cld
##  matrix(1, n, m, byrow = TRUE) 1.842346 1.881930 1.628921 1.735783 1.294805 1.569826    10  b 
##                matrix(1, n, m) 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000    10 a  
##             t(matrix(1, m, n)) 6.205065 6.459522 5.371109 5.944001 4.492510 4.449736    10   c

n <- 1e3
m <- 1e5
microbenchmark(matrix(1, n, m, byrow=TRUE),
               matrix(1, n, m),
               t(matrix(1, m, n)),
               check = "equal",
               unit = "relative",
               times = 10)
## Unit: relative
##                           expr      min       lq     mean   median       uq      max neval cld
##  matrix(1, n, m, byrow = TRUE) 4.058060 4.002568 3.249719 3.203163 2.769305 2.719077    10   c
##                matrix(1, n, m) 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000    10 a  
##             t(matrix(1, m, n)) 2.956505 2.973743 2.508964 2.471689 2.218416 2.162319    10  b 

n <- 1e4
m <- 1e4
microbenchmark(matrix(1, n, m, byrow=TRUE),
               matrix(1, n, m),
               t(matrix(1, m, n)),
               check = "equal",
               unit = "relative",
               times = 10)
## Unit: relative
##                           expr      min       lq     mean   median       uq      max neval cld
##  matrix(1, n, m, byrow = TRUE) 4.378733 4.273794 3.721100 4.240410 2.902938 3.180665    10  b 
##                matrix(1, n, m) 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000    10 a  
##             t(matrix(1, m, n)) 5.659562 5.797812 5.062428 5.894572 4.195282 3.876377    10   c

Upvotes: 4

Related Questions