353054 - Optimize slicing via copy-on-write

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, enhancement)

Description

[Robert Sayre]

Array and string slice could be faster.

Comment 1

[Brian Crowder]

Pretty sure this is a dupe of another bug, just not sure which one

Comment 2

[Robert Sayre]

Discovered by Jesse in bug 350531. Searched for a spinoff, and didn't find one.

Comment 3

[Brian Crowder]

String slice already uses a dependent string (thus CoW, unless I am wrong), does it not?  This bug is really just about array slice, right?

Comment 4

[Blake Kaplan (:mrbkap) (inactive)]

Well, strings are immutable, so no CoW needed. But yes, we do create dependent strings for e.g. substr.

Comment 5

[Brian Crowder]

(In reply to comment #4)
> Well, strings are immutable, so no CoW needed. But yes, we do create dependent
> strings for e.g. substr.

We really need a similar concept for arrays (though without the immutability constraint)

Comment 6

[Jeff Walden [:Waldo]]

> thus CoW, unless I am wrong

(Blake's already noted that there's no need for CoW due to immutability; I had a paragraph here that I've omitted due to mid-airing.)

Array are mutable, so you'd have to slow down every every write to check for the need to copy, for all dependent arrays.  Every array thus must keep an essentially unbounded number of pointer/index-pair tuples to a parent array and dependent arrays.  Given that requirement, is this actually a win?  I very, very much doubt it.

Comment 7

[Jeff Walden [:Waldo]]

(In reply to comment #5)
> We really need a similar concept for arrays (though without the immutability
> constraint)

In ES4 you'll be able to fake it with a class with the right method overloading; I think that's good enough.

Comment 8

[Blake Kaplan (:mrbkap) (inactive)]

This might depend on bug 322889 then. With that bug fixed, we could (fairly cheaply) do the required check. I'm hoping to get to that bug this summer...

Comment 9

[Jeff Walden [:Waldo]]

(In reply to comment #6)
> Every array thus must keep an essentially unbounded number of
> pointer/index-pair tuples to a parent array and dependent arrays.

Actually, I'm wrong about this; you'd need exactly two per array (no dynamic allocation!) if you threaded the parent pointers (keep a pointer to one kid of the array, which points to another kid of the array, etc. until you've hit all dependent arrays -- see Jones's GC book).  You can't do cute sorting tricks to minimize the number of checks and so must follow the entire chain, but that might not be a problem.  The chain won't be long in practice anyway, so maybe this *is* efficient enough; I still have my doubts.  (It's also not exactly going to simplify the code, either, although the pointer cycles would provide plenty of fodder for assertions.)

Comment 10

[Brendan Eich [:brendan]]

You want to abstract the pointer-following so it's not smeared all over the source code, of course.

You might heuristically flatten at some depth.

Someone should try a patch, comparing how it speeds up permcomb.js compared to Jesse's generator-based non-recursive, copy-minimizing version.

Waldo, you gonna take this bug? ;-).

/be

Comment 11

[Jeff Walden [:Waldo]]

Why not.  :-)

It's going to be at least a couple weeks, but most likely a month, before I get to this.  Classes, y'know.

Comment 12

[Jeff Walden [:Waldo]]

I think this would probably be way too mutation-hazardous to be effective, so closing as WONTFIX.  If someone ever really really feels like doing this and has some sort of half-working patch (at the least), that person can reopen this bug.