r - xlabel - tick size ggplot2



왜 샘플 행렬이 매우 느린가요? (1)

R의 함수 MatrixSubset (265 행) 에서 두 가지 가능성이 눈여겨 보입니다 .

이 둘 중 하나가 아닐 수도 있습니다. 그냥 추측 해.

1. 캐시에서 비효율적 인 방향으로 반복되는 것처럼 보입니다.

for (i = 0; i < nrs; i++) {    // rows
  ...
  for (j = 0; j < ncs; j++) {  // columns
    ...

귀하의 예는 많은 칼럼을 가지고 있습니다 (8,000). 내부 루프가 새로운 열을 가져올 때마다 RAM에서 해당 값을 캐시에 저장하는 RAM 페이지를 가져와야합니다 (L2 가능성이 높습니다). 다음 번 가져 오기는 다른 열이므로 이미 L2에있는 페이지를 재사용 할 가능성이 적습니다. matrix 은 내부적으로 하나의 커다란 연속 벡터입니다 : 모든 열 1 다음에 모든 열 2 등이 있습니다. 페이지 가져 오기는 비교적 비쌉니다. "잘못된"방향으로 들어가면 너무 많은 페이지를 가져옵니다. CPU 캐시에 대한 자세한 내용은 here .

좋은 컴파일러는 기본적으로 gcc -floop-interchange 와 같은 루프 교환을 자동으로 수행해야합니다. here 더. 이 최적화는 for 루프 내부의 복잡성으로 인해 발생하지 않을 수 있습니다. 이 경우에는 switch 문이 필요할 수 있습니다. 또는 OS에서 사용중인 R 버전이 해당 옵션이있는 컴파일러로 컴파일되지 않았거나 켜져 있지 않은 것일 수 있습니다.

2. 스위치 ()가 너무 깊습니다.

스위치 온 유형은 matrix 모든 항목에서 발생합니다. matrix 이 하나의 유형이지만! 그래서 이것은 낭비입니다. 점프 테이블사용 하여 스위치를 최적화하는 경우에도 매트릭스의 모든 항목에 대해 점프 테이블이 계속 발생하고 있습니다 (CPU가 스위치를 예측할 수 있기 때문에 '아마'). 귀하의 예제 matrix 가 61MB로 작기 때문에 잘못된 방향으로가는 것보다 범인이되는 방향으로 기울고 있습니다.

위의 두 가지 (제안 된)

// Check the row numbers once up front rather than 8,000 times.
// This is a contiguous sweep and therefore almost instant
// Declare variables i and ii locally for safety and maximum compiler optimizations
for (int i = 0; i < nrs; i++) {
  int ii = INTEGER(sr)[i];
  if (ii != NA_INTEGER && (ii < 1 || ii > nr))
    errorcall(call, R_MSG_subs_o_b);
}

// Check the column numbers up front once rather than 2,000 times
for (int j = 0; j < ncs; j++) {
  int jj = INTEGER(sc)[j];
  if (jj != NA_INTEGER && (jj < 1 || jj > nc))
    errorcall(call, R_MSG_subs_o_b);
}

// Now switch once on type rather than 8,000 * 2,000 times
// Loop column-by-column not row-by-row

int resi=0;  // contiguous write to result (for page efficiency)
int ii, jj;  // the current row and column, bounds checked above
switch (TYPEOF(x)) {
  case LGLSXP:  // the INTSXP will work for LGLSXP too, currently
  case INTSXP:
    for (int j=0; j<ncs; j++) {  // column-by-column
      jj = INTEGER(sc)[j];
      for (int i=0; i<nrs; i++) {  // within-this-column
        ii = INTEGER(sr)[i];
        INTEGER(result)[resi++] = (ii == NA_INTEGER || jj == NA_INTEGER) ? NA_INTEGER : INTEGER(x)[ii + jj * nr];
      }
    }
    break;
  case REALSXP:
    for (int j=0; j<ncs; j++) {
      jj = INTEGER(sc)[j];
      for (int i=0; i<nrs; i++) {
        ii = INTEGER(sr)[i];
        REAL(result)[resi++] = (ii == NA_INTEGER || jj == NA_INTEGER) ? NA_REAL : REAL(x)[ii + jj * nr];
      }
    }
    break;
  case ...

보시다시피 switch() case 내에서 반복적으로 for 루프 for 반복해야하기 때문에 이렇게 많은 코드가 있습니다. 코드 가독성과 견고성의 이유는 원래 코드가 원래의 방식 인 이유 일 수 있습니다. R의 구현에서 오타가 발생할 가능성이 적습니다. 그것은 LOGICAL을 위해 LGLSXP 케이스를 특별히 구현하지 않았기 때문에 이미 증명되었습니다. 나는 LOGICAL이 현재 기본 R에있는 INTEGER와 정확히 동일하다는 것을 알고있다. 그러나 미래에 변경 될 수도 있으므로 LOGICAL이 변경되면 내 게으름 (코드 부 풀림으로 인한)이 R에서 버그를 일으킬 수있다. RAM 효율성).

한 가지 가능한 옵션은 코드 팽창 문제를 해결하는 것입니다. 실제로 일어나는 모든 일은 메모리를 움직이는 것입니다. 따라서 모든 유형 (STRSXP, VECSXP 및 EXPRSXP 제외)은 유형의 크기를 갖는 memcpy 를 사용하는 단일 이중 for ループ로 수행 될 수 있습니다. SET_STRING_ELTSET_VECTOR_ELT 는 해당 개체의 참조 횟수를 유지 관리하는 데 계속 사용해야합니다. 그래서 그것은 루프를 유지 for double의 단지 3 번의 반복이어야합니다. 대안으로, 그 관용구는 R의 다른 부분에서 수행되는 #define 으로 래핑 될 수 있습니다.

마지막으로, 전달 된 행 또는 열에 NA가 있는지 여부 (NA '번째 행 또는 NA'번째 열을 요청하지 않는 매우 일반적인 경우)가 첫 번째 경계 검사 루프에서 감지 될 수 있습니다. NAs가 없으면 가장 (ii == NA_INTEGER || jj == NA_INTEGER) ? : 삼항 ( (ii == NA_INTEGER || jj == NA_INTEGER) ? : (해당 분기에 대한 2000 * 8000 호출)은 해당 분기를 외부로 끌어 (ii == NA_INTEGER || jj == NA_INTEGER) ? : 저장할 수 있습니다. 그러나 더 복잡한 반복 코드 비용. 그러나 분기 예측 이 모든 아키텍처에서 안정적으로 시작될 수 있으므로 걱정할 필요가 없습니다.

data.tablememcpy 트릭과 딥 브랜치 저장을 일부 장소에서하지만 모든 장소에서하지는 않습니다. 또한 열 단위로 병렬로 하위 집합을 시작했습니다. 그러나이 경우 아직 새로운 것은 아니고 여전히 롤아웃되고 있습니다 ( setkey 는 매우 유사하고 이미 병렬입니다). SET_STRING_ELTSET_VECTOR_ELT 는 R에서 스레드로부터 안전하지 않으므로 마스터 스레드는 characterlist 열을 하나씩 처리합니다 (병렬이 아님). 다른 스레드는 모든 정수, 실제, 복합 및 원시 열을 병렬로 처리합니다. 그런 다음 메모리가 빠르게 갈 수 있습니다.

61MB에서 볼 수있는 차이점을 실제로 볼 수는 없지만 열 수를 10 배에서 80,000까지 늘리면 (여전히 작은) 610MB로 확장됩니다. 차이가 있습니다.

n = 2000
nc = 8000    # same size as your example (61MB), on my laptop
microbenchmark(m[s,], DF[s,],DT[s,])
Unit: milliseconds
    expr       min        lq      mean    median        uq      max neval
  m[s, ] 108.75182 112.11678 118.60111 114.58090 120.07952 168.6079   100
 DF[s, ] 100.95019 105.88253 116.04507 110.84693 118.08092 163.9666   100
 DT[s, ]  63.78959  69.07341  80.72039  72.69873  96.51802 136.2016   100

n = 2000
nc = 80000     # 10x bigger (610MB)
microbenchmark(m[s,], DF[s,],DT[s,])
Unit: milliseconds
    expr       min        lq      mean    median        uq      max neval
  m[s, ] 1990.3343 2010.1759 2055.9847 2032.9506 2057.2498 2733.278   100
 DF[s, ] 1083.0373 1212.6633 1265.5346 1234.1558 1300.7502 2105.177   100
 DT[s, ]  698.1295  830.3428  865.5918  862.5773  907.7225 1053.393   100

하지만 128MB의 L4 캐시가 있습니다. 캐쉬가 적다는 것. 61MB 전체가 L4 캐시에 들어 맞기 때문에 캐시 크기가 그다지 크지는 않습니다.

$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 70
Model name:            Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Stepping:              1
CPU MHz:               3345.343
CPU max MHz:           4000.0000
CPU min MHz:           800.0000
BogoMIPS:              5587.63
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              6144K
L4 cache:              131072K
NUMA node0 CPU(s):     0-7

일부 부트 스트래핑을 시도하고 colMeans 계산하려고 시도했지만 자연스럽게 데이터를 저장하기 위해 매트릭스를 선택했지만 샘플링 속도가 매우 느립니다.

m[sample(n,replace=TRUE),]

그것은 data.table 가 가장 빠릅니다.

require(microbenchmark)
require(data.table)
n = 2000
nc = 8000
m = matrix(1:(n*nc) ,nrow = n)
DF = as.data.frame(m)
DT = as.data.table(m)

s=sample(n, replace=TRUE)
microbenchmark(m[s,], DF[s,],DT[s,])

# Unit: milliseconds
    # expr      min       lq     mean   median       uq      max neval
  # m[s, ] 371.9271 402.3542 421.7907 420.8446 437.8251 506.1788   100
 # DF[s, ] 182.3189 199.0865 218.0746 213.9451 231.1518 409.8625   100
 # DT[s, ] 129.8225 139.1977 156.9506 150.4321 164.3104 254.2048   100

왜 샘플링 매트릭스가 다른 두 샘플보다 훨씬 느립니까?





data.table