Use Copy-on-write arrays for cached regexp results.

Use Copy-on-write arrays for cached regexp results.

[Lasse Reichstein, 2010-08-18 15:31:25]

Medium size, but not very complicated, review.

[Vitaly Repeshko, 2010-08-18 16:39:02]

LGTM with comments.


-- Vitaly

http://codereview.chromium.org/3158020/diff/1/2
File src/arm/codegen-arm.cc (right):

http://codereview.chromium.org/3158020/diff/1/2#newcode5301
src/arm/codegen-arm.cc:5301: __ ldm(ib, r0, r3.bit() | r4.bit() | r5.bit() |
r6.bit() | r7.bit());
See ia32 comments on requirements and assertions below.

http://codereview.chromium.org/3158020/diff/1/2#newcode5308
src/arm/codegen-arm.cc:5308: __ str(ip, FieldMemOperand(r4,
HeapObject::kMapOffset));
Move this one line up?

http://codereview.chromium.org/3158020/diff/1/9
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/3158020/diff/1/9#newcode5555
src/ia32/codegen-ia32.cc:5555: __ push(save_register);
push -> pop.

http://codereview.chromium.org/3158020/diff/1/9#newcode7402
src/ia32/codegen-ia32.cc:7402: __ cmp(edx, FieldOperand(eax,
HeapObject::kMapOffset));
Please document when we expect it to have a different map.

http://codereview.chromium.org/3158020/diff/1/9#newcode7421
src/ia32/codegen-ia32.cc:7421: // Copy properties array of input (should be
empty FixedArray).
Consider generating the initialization code in a loop like this:
for (offset = kPointerSize; offset < JSRegExpResult::kSize; offset +=
kPointerSize)
You can add a special case for the elements offset and change the map there.
Changing the map requires that the elements array is not empty (the empty array
is a singleton). Is this requirement satisfied here? Also consider adding an
assert that the property array is empty.

http://codereview.chromium.org/3158020/diff/1/13
File src/runtime.cc (right):

http://codereview.chromium.org/3158020/diff/1/13#newcode1378
src/runtime.cc:1378: if (result->map() != regexp_result_map) {
nit: Can be a one liner.

http://codereview.chromium.org/3158020/diff/1/13#newcode1379
src/runtime.cc:1379: return result;
Please document when this is supposed to happen.

http://codereview.chromium.org/3158020/diff/1/13#newcode1382
src/runtime.cc:1382: ASSERT(result->HasFastElements());
Mention that we don't need runtime checks here because this structure is
guaranteed by the regexp_result_map.

http://codereview.chromium.org/3158020/diff/1/13#newcode1387
src/runtime.cc:1387: NEW_SPACE,
nit: Align parameters.

http://codereview.chromium.org/3158020/diff/1/13#newcode1397
src/runtime.cc:1397: new_array->set_properties(result->properties());  // Is
empty FixedArray.
"Is empty" -> "Empty".

http://codereview.chromium.org/3158020/diff/1/13#newcode1400
src/runtime.cc:1400: FixedArray* elements =
FixedArray::cast(result->elements());
Assert !elements->IsEmpty(). See ia32 comments above.

http://codereview.chromium.org/3158020/diff/1/13#newcode1403
src/runtime.cc:1403: new_array->set_elements(result->elements());  // Is empty
FixedArray.
Remove this line.

http://codereview.chromium.org/3158020/diff/1/15
File src/x64/codegen-x64.cc (right):

http://codereview.chromium.org/3158020/diff/1/15#newcode4834
src/x64/codegen-x64.cc:4834: __ push(save_register);
push -> pop.

http://codereview.chromium.org/3158020/diff/1/15#newcode6637
src/x64/codegen-x64.cc:6637: // Load JSRegExp map into edx. Check that argument
object has this map.
edx -> rdx.

http://codereview.chromium.org/3158020/diff/1/15#newcode6662
src/x64/codegen-x64.cc:6662: // Copy properties array of input (should be empty
FixedArray).
See ia32 comments above.

http://codereview.chromium.org/3158020/diff/1/18
File test/mjsunit/regexp.js (right):

http://codereview.chromium.org/3158020/diff/1/18#newcode488
test/mjsunit/regexp.js:488: // Test that caching of result doesn't share result
objects.
Put this code in a loop to increase the likelihood of exercising GC-related
paths.

[Lasse Reichstein, 2010-08-20 09:31:34]

http://codereview.chromium.org/3158020/diff/1/2
File src/arm/codegen-arm.cc (right):

http://codereview.chromium.org/3158020/diff/1/2#newcode5301
src/arm/codegen-arm.cc:5301: __ ldm(ib, r0, r3.bit() | r4.bit() | r5.bit() |
r6.bit() | r7.bit());
Added check for EmptyFixedArray.

http://codereview.chromium.org/3158020/diff/1/2#newcode5308
src/arm/codegen-arm.cc:5308: __ str(ip, FieldMemOperand(r4,
HeapObject::kMapOffset));
This was deliberate, to give the load from the root array an extra cycle to
complete.
I've moved the add further up to help another load instead.

http://codereview.chromium.org/3158020/diff/1/9
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/3158020/diff/1/9#newcode5555
src/ia32/codegen-ia32.cc:5555: __ push(save_register);
Amazing that it appears to work!

http://codereview.chromium.org/3158020/diff/1/9#newcode7402
src/ia32/codegen-ia32.cc:7402: __ cmp(edx, FieldOperand(eax,
HeapObject::kMapOffset));
Will do.

http://codereview.chromium.org/3158020/diff/1/9#newcode7421
src/ia32/codegen-ia32.cc:7421: // Copy properties array of input (should be
empty FixedArray).
I can do the loop, with a few special cases, and even unroll it for speed (my
experience is that copying two values at a time is faster than one at a time,
although I admit that I haven't tested it here.).

As for the empty array - it shouldn't be possible, because the input is a regexp
result which cannot be empty (in that case it just returns null). However
"shouldn't be possible" isn't enough for a runtime function. I'll add a sanity
check.

http://codereview.chromium.org/3158020/diff/1/13
File src/runtime.cc (right):

http://codereview.chromium.org/3158020/diff/1/13#newcode1378
src/runtime.cc:1378: if (result->map() != regexp_result_map) {
Fixed.

http://codereview.chromium.org/3158020/diff/1/13#newcode1379
src/runtime.cc:1379: return result;
Done. Answer: Argument is either null or an unmodified JSRegExpResult - unless
someone is tampering with the runtime system. This is both a null-test and a
sanity check.

http://codereview.chromium.org/3158020/diff/1/13#newcode1382
src/runtime.cc:1382: ASSERT(result->HasFastElements());
Done.

http://codereview.chromium.org/3158020/diff/1/13#newcode1387
src/runtime.cc:1387: NEW_SPACE,
Done.

http://codereview.chromium.org/3158020/diff/1/13#newcode1397
src/runtime.cc:1397: new_array->set_properties(result->properties());  // Is
empty FixedArray.
Done.

http://codereview.chromium.org/3158020/diff/1/13#newcode1400
src/runtime.cc:1400: FixedArray* elements =
FixedArray::cast(result->elements());
That is, sadly, not guaranteed by the map check, only by the intended use of the
function. 
Since this is a runtime function, an assertion isn't enough. I'll add a guard on
the setting-cow-map (which is safe, because having the EmptyFixedArray as
elements is effectively copy-on-write).

http://codereview.chromium.org/3158020/diff/1/13#newcode1403
src/runtime.cc:1403: new_array->set_elements(result->elements());  // Is empty
FixedArray.
Done.

http://codereview.chromium.org/3158020/diff/1/15
File src/x64/codegen-x64.cc (right):

http://codereview.chromium.org/3158020/diff/1/15#newcode4834
src/x64/codegen-x64.cc:4834: __ push(save_register);
Doh.

http://codereview.chromium.org/3158020/diff/1/15#newcode6637
src/x64/codegen-x64.cc:6637: // Load JSRegExp map into edx. Check that argument
object has this map.
Fixed.

http://codereview.chromium.org/3158020/diff/1/15#newcode6662
src/x64/codegen-x64.cc:6662: // Copy properties array of input (should be empty
FixedArray).
Changed to match the new ia32 code.

http://codereview.chromium.org/3158020/diff/1/18
File test/mjsunit/regexp.js (right):

http://codereview.chromium.org/3158020/diff/1/18#newcode488
test/mjsunit/regexp.js:488: // Test that caching of result doesn't share result
objects.
Done.

[Vitaly Repeshko, 2010-08-20 13:29:49]

LGTM.

There's one more requirement to making an array copy-on-write that should be
documented somewhere: its elements must be primitive. AFAIU it is true for
regexp matches which contain either strings or undefined.

http://codereview.chromium.org/3158020/diff/10018/11003
File src/arm/full-codegen-arm.cc (right):

http://codereview.chromium.org/3158020/diff/10018/11003#newcode2539
src/arm/full-codegen-arm.cc:2539: void
FullCodeGenerator::EmitRegExpCloneResult(ZoneList<Expression*>* args) {
Can this be moved to the architecture independent full-codegen?

http://codereview.chromium.org/3158020/diff/10018/11003#newcode2542
src/arm/full-codegen-arm.cc:2542: __
CallRuntime(Runtime::kRegExpConstructResult, 1);
kRegExpConstructResult -> kRegExpCloneResult.

http://codereview.chromium.org/3158020/diff/10018/11008
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/3158020/diff/10018/11008#newcode7407
src/ia32/codegen-ia32.cc:7407: if (FLAG_debug_code) {
Should be checked in arm and x64 versions as well.

http://codereview.chromium.org/3158020/diff/10018/11012
File src/runtime.cc (right):

http://codereview.chromium.org/3158020/diff/10018/11012#newcode1407
src/runtime.cc:1407: // No write barrier is necessary when writing old-space
pointer.
I don't think we need to have this comment or assert for map assignment.

http://codereview.chromium.org/3158020/diff/10018/11014
File src/x64/codegen-x64.cc (right):

http://codereview.chromium.org/3158020/diff/10018/11014#newcode4834
src/x64/codegen-x64.cc:4834: __ push(save_register);
push -> pop.

[Lasse Reichstein, 2010-08-23 12:52:11]

Is the restriction on having only simple values really necessary, as long as you
only expect a shallow copy?

I'll upload the changes as a new CL.

http://codereview.chromium.org/3158020/diff/10018/11003
File src/arm/full-codegen-arm.cc (right):

http://codereview.chromium.org/3158020/diff/10018/11003#newcode2539
src/arm/full-codegen-arm.cc:2539: void
FullCodeGenerator::EmitRegExpCloneResult(ZoneList<Expression*>* args) {
Done.
There actually seems to be a lot of Emit-runtime-call function that can be
generalized.

http://codereview.chromium.org/3158020/diff/10018/11003#newcode2542
src/arm/full-codegen-arm.cc:2542: __
CallRuntime(Runtime::kRegExpConstructResult, 1);
Fixed.

http://codereview.chromium.org/3158020/diff/10018/11008
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/3158020/diff/10018/11008#newcode7407
src/ia32/codegen-ia32.cc:7407: if (FLAG_debug_code) {
Done.

http://codereview.chromium.org/3158020/diff/10018/11012
File src/runtime.cc (right):

http://codereview.chromium.org/3158020/diff/10018/11012#newcode1407
src/runtime.cc:1407: // No write barrier is necessary when writing old-space
pointer.
True, maps are all in Map-space.

http://codereview.chromium.org/3158020/diff/10018/11014
File src/x64/codegen-x64.cc (right):

http://codereview.chromium.org/3158020/diff/10018/11014#newcode4834
src/x64/codegen-x64.cc:4834: __ push(save_register);
Double-doh!
Fixed, for real.

[Vitaly Repeshko, 2010-08-23 13:17:45]

On 2010/08/23 12:52:11, Lasse Reichstein wrote:
> Is the restriction on having only simple values really necessary, as long as
you
> only expect a shallow copy?

If only a shallow copy is expected, then this restriction does not apply. When
deep copying is required (as is the case with literals), non-primitive elements
make it possible to write somewhere into the tree rooted at the array without it
noticing the update and cloning its elements.


-- Vitaly