1122523 - Improve knockout compareSmallArrayToBigArray function performance

Status: NEW

(Core :: JavaScript Engine, defect)

Comment 1

[Hannes Verschore [:h4writer]]

Attachment: testcase.js

Reduced the knockout benchmark to a 50 line testcase that has the same issue.

V8: 1866ms
SM: 3360ms
SM --no-ggc: 3894ms

So ggc already helped here. Also I don't see the spikes on this testcase. So this might be showing the non-minorgc slowdowns we have on this benchmark.

Comment 2

[Hannes Verschore [:h4writer]]

So we read out of bounds in a dense array.

We can use a MLoadElementHole in that case, but here we fall back to a MGetElementCache which is off course slower.

When forcing to use MLoadElementHole for all loads in this benchmark we get:
2400ms

Sounds promising!

Comment 3

[Hannes Verschore [:h4writer]]

Observations:
1) We take 25%-50% longer to initialize all holes values when doing:
> a = []
> a[500] = 1

Because we store values having 64bits, while v8 stores 32bit smi values. Therefore depending on bug 1116855, since that will allow us to fix this by only storing objects, instead of object + tag.

2) Using push instead of thisRow[bigIndex] = will decrease performance of V8 a lot. Then they are the same speed as us. Are they doing something special?
> ...
>                } else if (smlArray[smlIndex - 1] === bigArray[bigIndex - 1]) {                   
> +                  if (thisRow.length == bigIndex)
> +                      thisRow.push(lastRow[bigIndex - 1]);
> +                  else
>                        thisRow[bigIndex] = lastRow[bigIndex - 1]; 
>                } else {                                                                              
>                    var northDistance = lastRow[bigIndex] || maxDistance;
>                    var westDistance = thisRow[bigIndex - 1] || maxDistance;
>  +                 if (thisRow.length == bigIndex)
>  +                     thisRow.push( myMin(northDistance, westDistance) + 1);                        
>  +                 else
>                        thisRow[bigIndex] = myMin(northDistance, westDistance) + 1;               
>                }      
> ...


V8: 4118
SM: 4445

V8: 3063
SM: 4437

Very interesting

3) Our thisRow[bigIndex] is using the OOL path the whole time, since we are appending after the length of the array. Now that is why I tried push, which for 99% of the cases uses the inline path. But as seen above, this doesn't help a lot ?!

Comment 4

[Hannes Verschore [:h4writer]]

bug 1106828 is a better bug to depend on, because that is also about unboxed arrays. There is one caveat and that is that the unboxed arrays would get boxed when having holes. (Which we have in this case)!

Comment 5

[Mayank Bansal]

Nightly: https://share.firefox.dev/3v7XTTr (2.2s)
Chrome: https://share.firefox.dev/49OwoNU (1s)

Comment 6

[Iain Ireland [:iain]]

This is spending 84% of its time inside AddOrUpdateSparseElementHelper, with the biggest single chunk in ensureDenseInitializedLength. Taking a look at the CacheIR we generate, I think we may also be hitting the case where we don't transpile any CacheIR for some GetElem stubs because we have a mix of dense and sparse elements.

Broadly speaking, this appears to come down to how we handle sparse arrays. I know we've seen sparse arrays in the wild in the past (Google Docs, IIRC), but I haven't seen it matter much recently. Probably worth keeping this around, although I'm not sure it's a priority yet without additional evidence. This testcase is doing weird things with arrays.