[javascript] JavaScript에서 객체 / 배열의 성능은 무엇입니까? (특히 Google V8의 경우)

JavaScript (특히 Google V8)의 배열 및 객체와 관련된 성능은 문서화하기에 매우 흥미로울 것입니다. 이 주제에 대한 포괄적 인 기사는 인터넷 어디에도 없습니다.

일부 개체는 클래스를 기본 데이터 구조로 사용한다는 것을 이해합니다. 속성이 많은 경우 때때로 해시 테이블로 취급됩니까?

나는 또한 배열이 때때로 C ++ 배열처럼 취급된다는 것을 이해합니다 (즉, 빠른 임의 인덱싱, 느린 삭제 및 크기 조정). 그리고 다른 경우에는 객체 (빠른 인덱싱, 빠른 삽입 / 제거, 더 많은 메모리)처럼 취급됩니다. 그리고 때로는 연결 목록으로 저장 될 수 있습니다 (예 : 느린 임의 인덱싱, 시작 / 끝에서 빠른 제거 / 삽입).

JavaScript에서 배열 / 객체 검색 및 조작의 정확한 성능은 무엇입니까? (특히 Google V8의 경우)

더 구체적으로 말하면, 성능에 미치는 영향 :

객체에 속성 추가
개체에서 속성 제거
객체에서 속성 인덱싱
배열에 항목 추가
배열에서 항목 제거
배열의 항목 인덱싱
Array.pop () 호출
Array.push () 호출
Array.shift () 호출
Array.unshift () 호출
Array.slice () 호출

자세한 내용은 기사 또는 링크도 감사하겠습니다. 🙂

편집 : JavaScript 배열과 객체가 어떻게 작동하는지 정말 궁금합니다. 또한 V8 엔진이 다른 데이터 구조로 “전환”하는 것을 “알고있는” 컨텍스트 는 무엇 입니까?

예를 들어 다음을 사용하여 배열을 생성한다고 가정합니다.

var arr = [];
arr[10000000] = 20;
arr.push(21);

여기서 정말 무슨 일이 일어나고 있습니까?

아니면 … 이건 어때 … ???

var arr = [];
//Add lots of items
for(var i = 0; i < 1000000; i++)
    arr[i] = Math.random();
//Now I use it like a queue...
for(var i = 0; i < arr.length; i++)
{
    var item = arr[i].shift();
    //Do something with item...
}

기존 어레이의 경우 성능이 끔찍합니다. 반면 LinkedList가 사용 되었다면 … 그렇게 나쁘지는 않습니다.

답변

필자 는 이러한 문제 (및 그 이상)를 정확하게 탐색하기 위해 테스트 스위트를 만들었습니다 ( 아카이브 사본 ).

그런 의미에서 50 개 이상의 테스트 케이스 테스터에서 성능 문제를 볼 수 있습니다 (시간이 오래 걸립니다).

또한 이름에서 알 수 있듯이 DOM 구조의 기본 연결 목록 특성을 사용하는 사용법을 탐색합니다.

(현재 다운, 재 구축 중) 이에 관한 내 블로그에 대한 자세한 내용은 .

요약은 다음과 같습니다.

V8 스토리지는 빠르고 매우 빠름
어레이 푸시 / 팝 / 시프트는 동등한 객체보다 약 20 배 이상 빠릅니다.
놀랍게도 Array.shift() 어레이 팝보다 약 6 배 빠르지 만 객체 속성 삭제보다 약 100 배 빠릅니다.
재미있게도 거의 20 (동적 배열)에서 10 (고정 배열) 시간 Array.push( data );보다 빠릅니다 Array[nextIndex] = data.
Array.unshift(data) 예상대로 느리고 새 속성을 추가하는 것보다 약 5 배 느립니다.
값을 Null하는 array[index] = null것이 삭제하는 것보다 빠릅니다.delete array[index] 배열에서 (정의되지 않음) 약 4x ++ 더 빠릅니다.
놀랍게도 객체의 값을 Null obj[attr] = null하면 속성을 삭제하는 것보다 약 2 배 더 느립니다.delete obj[attr]
당연히 중간 어레이 Array.splice(index,0,data) 는 느리고 매우 느립니다.
놀랍게도 Array.splice(index,1,data)최적화되었으며 (길이 변경 없음) 스플 라이스보다 100 배 빠릅니다.Array.splice(index,0,data)
당연히 divLinkedList는 dll.splice(index,1)제거 (테스트 시스템을 망가 뜨린 곳)를 제외하고 모든 섹터에서 배열보다 열등합니다 .
가장 큰 놀라움 [jjrv가 지적했듯이], V8 어레이 쓰기는 V8 읽기 = O보다 약간 빠릅니다.

참고 : 이러한 메트릭은 v8이 “완전히 최적화”되지 않는 대형 어레이 / 객체에만 적용됩니다. 임의 크기 (24?)보다 작은 어레이 / 객체 크기에 대해 매우 격리 된 최적화 된 성능 사례가있을 수 있습니다. 자세한 내용은 여러 Google IO 비디오에서 광범위하게 볼 수 있습니다.

참고 2 : 이러한 놀라운 성능 결과는 브라우저, 특히 *cough*IE 간에 공유되지 않습니다
. 또한 테스트는 거대하므로 아직 결과를 완전히 분석하고 평가하지 않았습니다. =)에서 편집하십시오.

업데이트 된 노트 (2012 년 12 월) : Google 담당자는 크롬 자체의 내부 작동 (예 : 연결 목록 배열에서 고정 배열로 전환하는 경우 등) 및 최적화 방법을 설명하는 YouTube 동영상을 보유하고 있습니다. 자세한 내용은 GDC 2012 : 콘솔에서 Chrome으로 를 참조 하세요 .

답변

JavaScript 영역 내에있는 기본 수준에서 객체의 속성은 훨씬 더 복잡한 항목입니다. 열거 가능성, 쓰기 가능성 및 구성 가능성이 다른 setter / getter를 사용하여 속성을 만들 수 있습니다. 배열의 항목은 이러한 방식으로 사용자 정의 할 수 없습니다. 존재하거나 존재하지 않습니다. 기본 엔진 수준에서 이것은 구조를 나타내는 메모리 구성 측면에서 훨씬 더 많은 최적화를 허용합니다.

객체 (사전)에서 배열을 식별하는 측면에서 JS 엔진은 항상 둘 사이에 명시적인 줄을 만들어 왔습니다. 그렇기 때문에 하나처럼 작동하지만 다른 기능을 허용하는 반 가짜 배열과 같은 객체를 만드는 방법에 대한 많은 기사가 있습니다. 이 분리가 존재하는 이유는 JS 엔진 자체가 두 가지를 다르게 저장하기 때문입니다.

속성은 배열 객체에 저장할 수 있지만 이것은 JavaScript가 모든 것을 객체로 만드는 방법을 보여줍니다. 배열의 인덱싱 된 값은 기본 배열 데이터를 나타내는 배열 개체에 설정하기로 결정한 속성과 다르게 저장됩니다.

합법적 인 배열 객체를 사용하고 해당 배열을 조작하는 표준 방법 중 하나를 사용할 때마다 기본 배열 데이터에 도달하게됩니다. 특히 V8에서는 기본적으로 C ++ 배열과 동일하므로 이러한 규칙이 적용됩니다. 어떤 이유로 엔진이 자신있게 판단 할 수없는 어레이로 작업하는 것이 어레이 인 경우 훨씬 더 불안정한 위치에있는 것입니다. 최신 버전의 V8에서는 작업 할 여지가 더 많습니다. 예를 들어, Array.prototype을 프로토 타입 으로 사용하는 클래스를 만들 수 있습니다. 다양한 기본 배열 조작 메서드에 계속 효율적으로 액세스 할 수 있습니다. 그러나 이것은 최근의 변화입니다.

배열 조작에 대한 최근 변경 사항에 대한 특정 링크가 여기에 유용 할 수 있습니다.

약간의 추가로, V8 소스에서 직접 만든 Array Pop 및 Array Push는 둘 다 JS 자체에서 구현됩니다.

function ArrayPop() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.pop"]);
  }

  var n = TO_UINT32(this.length);
  if (n == 0) {
    this.length = n;
    return;
  }
  n--;
  var value = this[n];
  this.length = n;
  delete this[n];
  return value;
}


function ArrayPush() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.push"]);
  }

  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();
  for (var i = 0; i < m; i++) {
    this[i+n] = %_Arguments(i);
  }
  this.length = n + m;
  return this.length;
}

답변

증가하는 어레이와 관련하여 구현이 어떻게 작동하는지에 대한 조사를 통해 기존 답변을 보완하고 싶습니다. “일반적인”방식으로 구현하면 구현이 복사되는 지점에서 드물고 산재 된 느린 푸시로 많은 빠른 푸시를 볼 수 있습니다. 하나의 버퍼에서 더 큰 버퍼로의 배열 내부 표현.

이 효과를 매우 잘 볼 수 있습니다. 이것은 Chrome에서 가져온 것입니다.

16: 4ms
40: 8ms 2.5
76: 20ms 1.9
130: 31ms 1.7105263157894737
211: 14ms 1.623076923076923
332: 55ms 1.5734597156398105
514: 44ms 1.5481927710843373
787: 61ms 1.5311284046692606
1196: 138ms 1.5196950444726811
1810: 139ms 1.5133779264214047
2731: 299ms 1.5088397790055248
4112: 341ms 1.5056755767118273
6184: 681ms 1.5038910505836576
9292: 1324ms 1.5025873221216042

각 푸시가 프로파일 링 되더라도 출력에는 특정 임계 값을 초과하는 시간이 걸리는 푸시 만 포함됩니다. 각 테스트에서 빠른 푸시를 나타내는 것처럼 보이는 모든 푸시를 제외하도록 임계 값을 사용자 정의했습니다.

따라서 첫 번째 숫자는 삽입 된 요소를 나타내고 (첫 번째 줄은 17 번째 요소 용), 두 번째 숫자는 소요 된 시간 (많은 배열의 경우 벤치 마크가 병렬로 수행됨)이며 마지막 값은 이전 줄의 첫 번째 숫자.

실행 시간이 2ms 미만인 모든 라인은 Chrome에서 제외됩니다.

Chrome이 1.5의 거듭 제곱으로 배열 크기를 늘리고 작은 배열을 설명하기 위해 약간의 오프셋을 더한 것을 볼 수 있습니다.

Firefox의 경우 2의 거듭 제곱입니다.

126: 284ms
254: 65ms 2.015873015873016
510: 28ms 2.0078740157480315
1022: 58ms 2.003921568627451
2046: 89ms 2.0019569471624266
4094: 191ms 2.0009775171065494
8190: 364ms 2.0004885197850513

Firefox에서 임계 값을 상당히 올려야했기 때문에 # 126에서 시작합니다.

IE를 사용하면 다음과 같이 혼합됩니다.

256: 11ms 256
512: 26ms 2
1024: 77ms 2
1708: 113ms 1.66796875
2848: 154ms 1.6674473067915691
4748: 423ms 1.6671348314606742
7916: 944ms 1.6672283066554338

처음에는 2의 거듭 제곱이고 5/3의 거듭 제곱으로 이동합니다.

따라서 모든 일반적인 구현은 배열에 대해 “정상적인”방식을 사용합니다 ( 예를 들어 ropes에 미쳐가는 대신 ).

여기에 벤치 마크 코드가 있고 여기에있는 바이올린이 있습니다.

var arrayCount = 10000;

var dynamicArrays = [];

for(var j=0;j<arrayCount;j++)
    dynamicArrays[j] = [];

var lastLongI = 1;

for(var i=0;i<10000;i++)
{
    var before = Date.now();
    for(var j=0;j<arrayCount;j++)
        dynamicArrays[j][i] = i;
    var span = Date.now() - before;
    if (span > 10)
    {
      console.log(i + ": " + span + "ms" + " " + (i / lastLongI));
      lastLongI = i;
    }
}

답변

node.js 0.10 (v8에서 빌드 됨)에서 실행하는 동안 워크로드에 비해 CPU 사용량이 과도하게 느껴졌습니다. 한 가지 성능 문제를 배열에있는 문자열의 존재를 확인하는 함수로 추적했습니다. 그래서 몇 가지 테스트를했습니다.

90,822 개의 호스트로드
구성을로드하는 데 0.087 초가 걸렸습니다 (배열).
구성을로드하는 데 0.152 초가 걸렸습니다 (객체).

91k 항목을 배열 (유효성 검사 및 푸시 사용)에로드하는 것이 obj [key] = value를 설정하는 것보다 빠릅니다.

다음 테스트에서는 목록의 모든 호스트 이름을 한 번 조회했습니다 (조회 시간을 평균화하기 위해 91,000 회 반복).

구성 검색에 87.56 초 소요 (배열)
구성 검색에 0.21 초 소요 (객체)

여기서 애플리케이션은 Haraka (SMTP 서버)이며 시작시 (및 변경 후) host_list를 한 번로드 한 다음 작업 중에이 조회를 수백만 번 수행합니다. 객체로 전환하는 것은 엄청난 성능 승리였습니다.