[心得] 預分配記憶體的差異

[celestialgod (攸藍)]

其實一直想討論這個議題，只是遲遲沒有去寫這個

這次就想說來分享一下preallocated memory這件事

很多人會寫這樣的code:

A_list = list()
for (i in 1:N){
    A_list[[i]] = # give something
}

會直接給一個空的list然後開始塞東西

R裡面的list其實是一群pointer組成的向量

如果你沒有聽過pointer

你可當做"指示物"去引導到你要的東西

舉例來說：

List_1 <- list(a = 1:5, b = 2:4)

List_1就含有兩個pointer，指向a跟b的儲存位置

我們可以從tracemem來看到這點

tracemem回傳一個物件儲存在記憶體的位置

你可以透過這個去看物件有在記憶中被複製或被搬移等動作

我們來print out List_1的memory位置

cat(tracemem(List_1), '\n')
## <0000000015083EA8>

cat(tracemem(List_1[[1]]), '\n')
## <00000000060E97F0>

cat(tracemem(List_1[[2]]), '\n')
## <0000000015083EE0>

這樣可以看出tracemem(List_1)跟tracemem(List_1[[1]])的位置不同

如果list是沿著物件的大小去儲存

那麼我們應該看到List_1的位置跟List_1[[1]]的位置是重疊的

但是這裡顯示並非如此，因此，我們可以合理推斷

list是一群pointer組成的向量

以上如果你學過C++，應該對這個部分比較熟悉

如果不太熟悉，記得這個結果：list是一群pointer的向量


接著我們看如果我們給一個空的list

去做擴充list的動作會發生什麼事情

s1 = list()
cat(tracemem(s1), '\n')
## <000000001523AB70> 
for (i in 1:3)
{
  s1[[i]] = rnorm(i)
  cat(tracemem(s1), '\n')
}
## <00000000061DAC48> 
## <00000000067A55C8> 
## <000000000AC68AE8> 

這裡我們可以看到s1的位置不斷的被改變

代表說s1其實不斷搬移到不同位置上

那我們看看如果我們先設定好list大小的結果

s2 = vector('list', 3)
cat(tracemem(s2), '\n')
<000000000AD48B58> 
for (i in 1:3)
{
  s2[[i]] = rnorm(i)
  cat(tracemem(s2), '\n')
  cat(tracemem(s2[[i]]), '\n')
}
## <000000000AD48B58> 
## <000000000AD48B58> 
## <000000000AD48B58> 

我們可以看到完全沒有改變s2的位置，而s2沒有被搬移過

那麼沒有搬移告訴我們什麼事情？

沒有搬移就告訴我們不需要把位置上的東西做複製

不用做複製，那麼我們的操作就不會因為複製而變慢


我提供一個簡單的測試去測試有無preallocated memory的迴圈速度差異

f_without_preallocated <- function(){
  a <- list()
  for (i in 1:1e6){ a[[i]] <- rnorm(10) }
}

f_with_preallocated <- function(){
  a <- vector('list', 1e6)
  for (i in 1:1e6){ a[[i]] <- rnorm(10) }
}
library(rbenchmark)
benchmark(f_without_preallocated(), f_with_preallocated(),
  columns = c("test", "replications", "elapsed", "relative"),
  order = "relative", replications = 20)
##                       test replications elapsed relative
## 2    f_with_preallocated()           20    5.92    1.000
## 1 f_without_preallocated()           20  360.90   60.963

可以看到差到快60倍的速度，因此，建議preallocate memory!!

我的環境：windows 7 64bit, RRO-3.2.0 (2015-04-16), [email protected]


list只是其中一個例子

我只是挑大家最常用到的case去做

還有一些案例像是：

MaxIter = 1e6
x = c()
i = 0
while (iter < MaxIter){
  i <- i + 1
  x <- c(x, i)
  if (## some condition)
    break
}

這種不斷增長vector x的方式也是十分的消耗記憶體複製的時間

這種不知道長度時最多人用的做法

但是其實可以換成下列這樣：

MaxIter = 1e6
x = rep(NA_real_, 10)
for (i in 1:MaxIter)
  x[i] <- i
  if (## some condition)
    break
}
x = x[!is.na(x)]

再給一個簡單的benchmark：

f_while_1 <- function(){
  MaxIter = 1e5
  x = c()
  i = 0
  while (iter < MaxIter){
    i <- i + 1
    x <- c(x, i)
    if (i > 5e4)
      break
  }
  x
}

f_while_2 <- function(){
  MaxIter = 1e5
  x = rep(NA_real_, MaxIter)  ## 註一
  for (i in 1:MaxIter)
    x[i] <- i
    if (i > 5e4)
      break
  }
  (x = x[!is.na(x)])
}
library(rbenchmark)
benchmark(f_while_1(), f_while_2(),
  columns = c("test", "replications", "elapsed", "relative"),
  order = "relative", replications = 20)
##          test replications elapsed relative
## 2 f_while_2()           20    1.00     1.00
## 1 f_while_1()           20   53.17    53.17

可以看出平均消耗的時間可以差到53倍。


這些測試希望可以帶給大家一些東西，謝謝觀看此篇文章。

裡面還有一些操作的議題，像是向量化運算(vectorise)等，有機會再來討論

有興趣可以先去讀讀看R in a Nutshell第24章有提到相關的事情

(詳細資訊：R in a Nutshell, Joseph Adler, O'Reilly)


註一：NA有四種類型NA_integer_, NA_real_, NA_complex_ and NA_character_

分別是整數、帶小數的數、複數跟字元的NA類別

不同NA類別會給vector不同類型的儲存大小、儲存類型

給一個適當的NA也是一個好方法

另外，一般的NA是NA_character_


PS：

有些人會提到sapply, lapply會比較有效率：

但是其實sapply跟lapply只是有preallocate memory的動作

(sapply, lapply可能有其他優化，如果有人知道再麻煩告知我)

會比沒有preallocate memory的for-loop快而已

在你要同時進行多個list或是向量操作

還是建議用迴圈比較簡單做操作，因為時間根本不會差太多

在一些情況下，sapply跟lapply會更慢 (註二)

給一個簡單的例子：

N = 5e4
st <- proc.time()
a11 <- c()
a21 <- list()
a31 <- c()
for (i in 1:N){
  a11[i] <- i
  a21[[i]] <- cumsum(1:i)
  a31[i] <- sum(1:i)
}
proc.time() - st
##   user  system elapsed 
##  12.70    0.02   12.75

st <- proc.time()
a12 <- sapply(1:N, function(i)i)
a22 <- lapply(1:N, function(i) cumsum(1:i))
a32 <- lapply(1:N, function(i) sum(1:i))
proc.time() - st
##   user  system elapsed 
##   7.57    0.02    9.93 

st <- proc.time()
a13 <- vector('numeric', N)
a23 <- vector('list', N)
a33 <- vector('numeric', N)
for (i in 1:N){
  a13[i] <- i
  a23[[i]] <- cumsum(1:i)
  a33[i] <- sum(1:i)
}
proc.time() - st
##   user  system elapsed 
##   7.76    0.00    8.20

這個結果顯示sapply最快，有preallocate memory的for-loop差不多

而沒有preallocate memory的for-loop最慢

但是這裡還有一件事要注意

就是sapply跟有preallocate memory的for-loop並非總是最快

有時候反而會比沒有preallocate memory的for-loop最慢

而且在記憶體相對少時

沒有preallocate memory的for-loop跑得出來結果

而sapply跟有preallocate memory的for-loop會跑不出來，因為記憶體不足

因此，在這方面需要去衡量你的運算是否需要消耗大量記憶體

如果是，那麼preallocate memory對你有弊無利

這方面需要經驗去判斷，但是我還是建議初學者多多使用preallocate memory



但是這裡有一個有趣的結果(完全超乎預期的結果)：

我把上面的程式碼做一點改變(下面我用紅色標註我做改變的地方)

N = 5e4
st <- proc.time()
a11 <- c()
a21 <- list()
a31 <- c()
for (i in 1:N){
  a11[i] <- i
  a21[[i]] <- rnorm(round(mean(a11)/10))
  a31[i] <- sum(a11)
}
proc.time() - st
##   user  system elapsed 
##  12.87    0.11   12.98 

st <- proc.time()
a12 <- sapply(1:N, function(i)i)
a22 <- lapply(1:N, function(i) rnorm(round(mean(a12[1:i])/10)))
a32 <- sapply(1:N, function(i) sum(a12[1:i]))
proc.time() - st
   user  system elapsed 
  17.41    0.08   17.49 

st <- proc.time()
a13 <- vector('numeric', N)
a23 <- vector('list', N)
a33 <- vector('numeric', N)
for (i in 1:N){
  a13[i] <- i
  a23[[i]] <- rnorm(round(mean(a13[1:i])/10))
  a33[i] <- sum(a13[1:i])
}
proc.time() - st
   user  system elapsed 
  18.75    0.16   18.90 

如果你透過了外來變數來計算你其他的值

而且你的外生變數不斷的變化大小下

先生成好外生變數，再進行取子集的動作反而會更慢

這個結果，讓我滿意外的，我還沒有想過這個要怎麼解釋

可能看有沒有人可以幫忙回答這個問題


註二：

我有遇過這種情況，不過目前還不清楚出現的條件為何，

我的猜測是運算的複雜程度，我給一個我手邊有的測試：

(我只跑了三四次，都是lapply比較慢，有空的人可以跑跑看rbenchmark)


N = 1e4
st <- proc.time()
a12 <- lapply(1:N, function(i) replicate(10, rnorm(1000)))
b <- rnorm(10)
a22 <- lapply(1:N, function(i) a12[[i]] %*% b + rnorm(1000))
a32 <- lapply(1:N, function(i) lm(a22[[i]] ~ a12[[i]]))
a42 <- lapply(1:N, function(i) fitted(a32[[i]]))
a52 <- lapply(1:N, function(i) resid(a32[[i]]))
proc.time() - st
##    user  system elapsed 
##   28.63    0.31   28.94

st <- proc.time()
a13 <- vector('list', N)
a23 <- vector('list', N)
a33 <- vector('list', N)
a43 <- vector('list', N)
a53 <- vector('list', N)
b <- rnorm(10)
for (i in 1:N){
  a13[[i]] <- replicate(10, rnorm(1000))
  a23[[i]] <- a12[[i]] %*% b + rnorm(1000)
  a33[[i]] <- lm(a22[[i]] ~ a12[[i]])
  a43[[i]] <- fitted(a32[[i]])
  a53[[i]] <- resid(a32[[i]])
}
proc.time() - st
##    user  system elapsed 
##    28.1     0.2    28.3 

[關鍵字]: preallocated memory


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.27.107
※ 文章網址: https://www.ptt.cc/bbs/R_Language/M.1437916508.A.C27.html
→ andrew43: 簡單說，就是很大的物件可以先規劃好它的記憶體大小。
→ andrew43: 這篇文給了一個明確的證明，指出這在R也是一樣有效。
→ andrew43: 是這樣嗎？
應該說儘量養成習慣先給大小。太大也是無法運行。
→ andrew43: 我在學其它語言也有類似的概念，但經驗不足的朋友可能沒
matlab滿常提醒這一點，如果有接觸的話，而且matlab還很強調vectorise。
→ andrew43: 聽過這件事情對效率和記憶體有很大的影響。值得了解。
推 Edster: 其實就是 numeric(1000)跟for(i in 1:1000)I=c(I,0)的差別
→ Edster: 一個是預先指定記憶體位置 跟 一個不斷成長的 vector.
→ Edster: 每次都指定記憶體位置是需要時間的.
是的。
→ andrew43: 我所懂的和Edster說的一模一樣，但在R中哪些情況可以避
→ andrew43: 免（即使我自以為已經避免了）就不甚清楚。這篇多少有幫
→ andrew43: 助到我，像是如何進行檢查。
如果有幫助，再好不過了。
→ andrew43: 我在學習matlab的時候也有學到向量化和記憶體預分配。
→ andrew43: 大概書是同一本吧！ :)
我沒有看過matlab的書，哈哈哈
都是網路上看到的tips for speeding up matlab
→ andrew43: C兄，你 "s1 = vector('list', 3)" 這行是不是寫錯了？
→ andrew43: 這樣寫不是和之後的s2 一樣嗎
→ andrew43: 我猜你要寫的會不會是 "s1 = vector('list')" ?
要寫s1=list() 當初忘記改程式
結果確是我要的，囧
※ 編輯: celestialgod (123.205.27.107), 07/27/2015 08:12:14
推 SeaSprite: love this post. almost god like~