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가 사용 되었다면 ... 그렇게 나쁘지는 않습니다.

---

업데이트 : JSPref가 현재 다운되었습니다.

(테스트 케이스의 사본을 저장했으며 JSPref가 수정 / 후속 작업이 발견되면 답변을 업데이트합니다)

---

흠 ... 대답에 대한 과잉 일 수도 있지만 ... 정확하게 이러한 문제를 탐색하기 위해 테스트 스위트를 만들었습니다 ( 보관 된 사본 ).

그런 의미에서이 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 비디오에서 광범위하게 볼 수 있습니다.

Note 2: These wonderful performance results are not shared across browsers, especially *cough* IE. Also the test is huge, hence i yet to fully analyze and evaluate the results : please edit it in =)

Updated Note (dec 2012): Google representatives have videos on youtubes describing the inner workings of chrome itself (like when it switches from a linkedlist array to a fixed array, etc), and how to optimize them. See GDC 2012: From Console to Chrome for more.

Updated Note (feb 2013): Thx @badunk, for providing the video link at the exact point

Updated Note (june 2016): Thx @Benedikt, regarding array push performance difference in fixed / dynamic arrays.

---

At a basic level that stays within the realms of JavaScript, properties on objects are much more complex entities. You can create properties with setters/getters, with differing enumerability, writability, and configurability. An item in an array isn't able to be customized in this way: it either exists or it doesn't. At the underlying engine level this allows for a lot more optimization in terms of organizing the memory that represents the structure.

In terms of identifying an array from an object (dictionary), JS engines have always made explicit lines between the two. That's why there's a multitude of articles on methods of trying to make a semi-fake Array-like object that behaves like one but allows other functionality. The reason this separation even exists is because the JS engines themselves store the two differently.

Properties can be stored on an array object but this simply demonstrates how JavaScript insists on making everything an object. The indexed values in an array are stored differently from any properties you decide to set on the array object that represents the underlying array data.

Whenever you're using a legit array object and using one of the standard methods of manipulating that array you're going to be hitting the underlying array data. In V8 specifically, these are essentially the same as a C++ array so those rules will apply. If for some reason you're working with an array that the engine isn't able to determine with confidence is an array, then you're on much shakier ground. With recent versions of V8 there's more room to work though. For example, it's possible to create a class that has Array.prototype as its prototype and still gain efficient access to the various native array manipulation methods. But this is a recent change.

Specific links to recent changes to array manipulation may come in handy here:

• http://code.google.com/p/v8/source/detail?r=10024
• http://code.google.com/p/v8/source/detail?r=9849
• http://code.google.com/p/v8/source/detail?r=9747

As a bit of extra, here's Array Pop and Array Push directly from V8's source, both implemented in JS itself:

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;
}

---

I'd like to complement existing answers with an investigation to the question of how implementations behave regarding growing arrays: If they implement them the "usual" way, one would see many quick pushes with rare, interspersed slow pushes at which point the implementation copies the internal representation of the array from one buffer to a larger one.

You can see this effect very nicely, this is from 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

Even though each push is profiled, the output contains only those that take time above a certain threshold. For each test I customized the threshold to exclude all the pushes that appear to be representing the fast pushes.

So the first number represents which element has been inserted (the first line is for the 17th element), the second is how long it took (for many arrays the benchmark is done for in parallel), and the last value is the division of the first number by that of the one in the former line.

All lines that have less than 2ms execution time are excluded for Chrome.

You can see that Chrome increases array size in powers of 1.5, plus some offset to account for small arrays.

For Firefox, it's a power of two:

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

I had to put the threshold up quite a bit in Firefox, that's why we start at #126.

With IE, we get a mix:

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

It's a power of two at first and then it moves to powers of five thirds.

So all common implementations use the "normal" way for arrays (instead of going crazy with ropes, for example).

Here's the benchmark code and here's the fiddle it's in.

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;
    }
}

---

While running under node.js 0.10 (built on v8) I was seeing CPU usage that seemed excessive for the workload. I traced one performance problem to a function that was checking for the existence of a string in an array. So I ran some tests.

• loaded 90,822 hosts
• loading config took 0.087 seconds (array)
• loading config took 0.152 seconds (object)

Loading 91k entries into an array (with validate & push) is faster than setting obj[key]=value.

In the next test, I looked up every hostname in the list one time (91k iterations, to average the lookup time):

• searching config took 87.56 seconds (array)
• searching config took 0.21 seconds (object)

The application here is Haraka (a SMTP server) and it loads the host_list once at startup (and after changes) and subsequently performs this lookup millions of times during operation. Switching to an object was a huge performance win.

참고URL : https://stackoverflow.com/questions/8423493/what-is-the-performance-of-objects-arrays-in-javascript-specifically-for-googl