array.push가 때때로 array [n] = value보다 빠른 이유는 무엇입니까?

array.push가 때때로 array [n] = value보다 빠른 이유는 무엇입니까?

---

일부 코드를 테스트 한 결과, array.push 메서드 사용 속도와 직접 주소 지정 (array [n] = value)을 사용하는 속도를 비교하는 작은 함수를 작성했습니다. 놀랍게도 푸시 방법은 특히 Firefox와 때로는 Chrome에서 더 빠른 것으로 나타났습니다. 호기심에서 : 누구든지 그것에 대한 설명이 있습니까? 이 페이지 에서 테스트를 찾을 수 있습니다 ( '배열 방법 비교'클릭).

---

모든 종류의 요소가 작용합니다. 대부분의 JS 구현은 나중에 필요할 경우 희소 스토리지로 변환하는 플랫 배열을 사용합니다.

기본적으로 희소 화 결정은 설정되는 요소와 평평하게 유지하기 위해 얼마나 많은 공간이 낭비되는지를 기반으로하는 휴리스틱입니다.

귀하의 경우에는 마지막 요소를 먼저 설정합니다. 즉, JS 엔진은 길이가 n하나만 필요한 배열을 보게 됩니다. 경우 n충분한은이 즉시 배열에게 스파 스 배열을 만들 것입니다 - 모든 후속 삽입이 느린 스파 스 배열 경우 걸릴 것으로 대부분의 엔진이 의미합니다.

인덱스 0에서 인덱스 n-1까지 배열을 채우는 추가 테스트를 추가해야합니다. 훨씬 빨라야합니다.

@Christoph에 대한 응답과 미루고 자하는 욕구로, 여기에 배열이 JS에서 (일반적으로) 구현되는 방법에 대한 설명이 있습니다. 특징은 JS 엔진마다 다르지만 일반적인 원칙은 동일합니다.

모든 JS Object(문자열, 숫자, true, false, undefined또는 null아님)는 기본 개체 유형에서 상속합니다. 정확한 구현은 다양하며 C ++ 상속 일 수도 있고 C에서 수동으로 수행 할 수도 있습니다 (양쪽 방법으로 수행하면 이점이 있습니다). )-기본 객체 유형은 기본 속성 액세스 방법을 정의합니다.

interface Object {
    put(propertyName, value)
    get(propertyName)
private:
    map properties; // a map (tree, hash table, whatever) from propertyName to value
}

이 객체 유형은 모든 표준 속성 액세스 논리, 프로토 타입 체인 등을 처리합니다. 그러면 Array 구현이

interface Array : Object {
    override put(propertyName, value)
    override get(propertyName)
private:
    map sparseStorage; // a map between integer indices and values
    value[] flatStorage; // basically a native array of values with a 1:1
                         // correspondance between JS index and storage index
    value length; // The `length` of the js array
}

이제 JS에서 Array를 만들 때 엔진은 위의 데이터 구조와 유사한 것을 만듭니다. 객체를 Array 인스턴스에 삽입 할 때 Array의 put 메서드는 속성 이름이 0에서 2 ^ 32 사이의 정수인지 (또는 정수로 변환 할 수 있는지 (예 : "121", "2341"등)) 확인합니다. -1 (또는 아마도 2 ^ 31-1, 정확히 잊어 버림). 그렇지 않은 경우 put 메서드가 기본 개체 구현으로 전달되고 표준 [[Put]] 논리가 수행됩니다. 그렇지 않으면 값이 어레이의 자체 스토리지에 배치되고, 데이터가 충분히 압축되면 엔진은 플랫 어레이 스토리지를 사용합니다.이 경우 삽입 (및 검색)은 표준 어레이 인덱싱 작업 일뿐입니다. 그렇지 않으면 엔진이 어레이를 변환합니다. 희소 스토리지에 넣고 map을 사용하여 propertyName에서 값 위치로 가져옵니다.

변환이 발생한 후 JS 엔진이 현재 스파 스에서 플랫 스토리지로 변환되는지 여부는 솔직히 잘 모르겠습니다.

Anyhoo, 그것은 무슨 일이 일어나는지에 대한 상당히 높은 수준의 개요이며 더 많은 세부 사항을 생략했지만 그것은 일반적인 구현 패턴입니다. 추가 스토리지 및 put / get이 전달되는 방법에 대한 세부 사항은 엔진마다 다르지만 이것이 설계 / 구현을 실제로 설명 할 수있는 가장 분명합니다.

사소한 추가 지점은 ES 사양 propertyName이 문자열을 가리키는 반면 JS 엔진은 정수 조회도 전문화하는 경향이 있으므로 someObject[someInteger]정수 속성이있는 객체를보고있는 경우 정수를 문자열로 변환하지 않습니다. 배열, 문자열 및 DOM 유형 ( NodeLists 등).

---

이것이 내가 당신의 테스트로 얻은 결과입니다.

Safari에서 :

• Array.push (n) 1,000,000 개 값 : 0.124 초
• 배열 [n .. 0] = 값 (내림차순) 1,000,000 개 값 : 3.697 초
• 배열 [0 .. n] = 값 (오름차순) 1,000,000 값 : 0.073 초

FireFox에서 :

• Array.push (n) 1,000,000 개 값 : 0.075 초
• 배열 [n .. 0] = 값 (내림차순) 1,000,000 개 값 : 1.193 초
• 배열 [0 .. n] = 값 (오름차순) 1,000,000 개 값 : 0.055 초

IE7 :

• Array.push (n) 1,000,000 개 값 : 2.828 초
• Array [n .. 0] = 값 (내림차순) 1,000,000 개 값 : 1.141 초
• 배열 [0 .. n] = 값 (오름차순) 1,000,000 개 값 : 7.984 초

에 따르면 테스트 푸시 의 차이가 작은 다른 브라우저에 있기 때문에 방법은 IE7 (큰 차이)에 더 나은 것 같다, 그리고, 것 같다 푸시 정말 방법 배열에 요소를 추가하는 가장 좋은 방법.

But I created another simple test script to check what method is fast to append values to an array, the results really surprised me, using Array.length seems to be much faster compared to using Array.push, so I really don't know what to say or think anymore, I'm clueless.

BTW: on my IE7 your script stops and browsers asks me if I want to let it go on (you know the typical IE message that says: "Stop runnign this script? ...") I would recoomend to reduce a little the loops.

---

push() is a special case of the more general [[Put]] and therefore can be further optimized:

When calling [[Put]] on an array object, the argument has to be converted to an unsigned integer first because all property names - including array indices - are strings. Then it has to be compared to the length property of the array in order to determine whether or not the length has to be increased. When pushing, no such conversion or comparison has to take place: Just use the current length as array index and increase it.

Of course there are other things which will affect the runtime, eg calling push() should be slower than calling [[Put]] via [] because the prototype chain has to be checked for the former.

---

As olliej pointed out: actual ECMAScript implementations will optimize the conversion away, ie for numeric property names, no conversion from string to uint is done but just a simple type check. The basic assumption should still hold, though its impact will be less than I originally assumed.

---

Here is a good testbed, which confirms that direct assignment is significantly faster than push: http://jsperf.com/array-direct-assignment-vs-push.

Edit: there seems to be some problem in showing cumulative results data, but hopefully it gets fixed soon.

---

Push adds it to the end, while array[n] has to go through the array to find the right spot. Probably depends on browser and its way to handle arrays.

참고URL : https://stackoverflow.com/questions/614126/why-is-array-push-sometimes-faster-than-arrayn-value