Using array index hash code for string-to-number conversion.

Using array index hash code for string-to-number conversion.

Committed: http://code.google.com/p/v8/source/detail?r=5362

[SeRya, 2010-08-24 09:53:30]

The same optimization added to ParseInt and PartseFloat (v8natives.js).

[Vyacheslav Egorov (Chromium), 2010-08-26 12:52:57]

Here comes bunch of comments.

http://codereview.chromium.org/3141022/diff/14003/53001
File src/arm/codegen-arm.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53001#newcode5635
src/arm/codegen-arm.cc:5635: Register tmp = frame_->scratch0();
tmp is not used?

http://codereview.chromium.org/3141022/diff/14003/53001#newcode5637
src/arm/codegen-arm.cc:5637: ASSERT(String::kHashShift >= kSmiTagSize);
assert also that kSmiTag == 0

http://codereview.chromium.org/3141022/diff/14003/53001#newcode5638
src/arm/codegen-arm.cc:5638: __ and_(value, value,
Operand(String::kArrayIndexValueMask));
There is GenerateIndexFromHash in ic-arm.cc.

It seems to provide better instruction sequence based on Ubfx [kArrayIndexValue
mask is too big for ARM so and_ will produce two instruction: load mask from
memory to ip, then and_(value, value, ip)].

Turn GenerateIndexFromHash into method of MacroAssembler and use it here.

http://codereview.chromium.org/3141022/diff/14003/53003
File src/arm/full-codegen-arm.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53003#newcode2674
src/arm/full-codegen-arm.cc:2674: ASSERT(String::kHashShift >= kSmiTagSize);
assert kSmiTag == 0

http://codereview.chromium.org/3141022/diff/14003/53003#newcode2675
src/arm/full-codegen-arm.cc:2675: __ and_(r0, r0,
Operand(String::kArrayIndexValueMask));
use GenerateIndexFromHash (see comment in codegen-arm.cc).

http://codereview.chromium.org/3141022/diff/14003/53005
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53005#newcode8076
src/ia32/codegen-ia32.cc:8076: string.ToRegister();
should not we string.Unuse() somewhere later?

http://codereview.chromium.org/3141022/diff/14003/53005#newcode8081
src/ia32/codegen-ia32.cc:8081: ASSERT(String::kHashShift > kSmiTagSize);
>=

kSmiTag == 0

http://codereview.chromium.org/3141022/diff/14003/53005#newcode8082
src/ia32/codegen-ia32.cc:8082: __ and_(number.reg(),
String::kArrayIndexValueMask);
to avoid code duplication use GenerateIndexFromHash (make it method of
MacroAssembler).

http://codereview.chromium.org/3141022/diff/14003/53007
File src/ia32/full-codegen-ia32.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53007#newcode2773
src/ia32/full-codegen-ia32.cc:2773: ASSERT(String::kHashShift >= kSmiTagSize);
kSmiTag == 0

http://codereview.chromium.org/3141022/diff/14003/53007#newcode2774
src/ia32/full-codegen-ia32.cc:2774: __ and_(eax, String::kArrayIndexValueMask);
to avoid code duplication use GenerateIndexFromHash (make it method of
MacroAssembler).

http://codereview.chromium.org/3141022/diff/14003/53008
File src/runtime.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53008#newcode4849
src/runtime.cc:4849: } else if ((subject->hash_field() &
String::kHashNotComputedMask) != 0 &&
This condition looks really complicated to me:

1) don't check String::kHashNotComputedMask directly. there is a method for
that. 

2) I do not understand (len == 1 || data[0] != '0') check. Are you trying to
guard against octal literals? I don't think it is necessary here. At least
ParseDecimalInteger is not taking them into account. 

3) Even if len >= String::kMaxCachedArrayIndexLength it worth setting hash any
way

http://codereview.chromium.org/3141022/diff/14003/53008#newcode4854
src/runtime.cc:4854: uint32_t hash = (d << String::kHashShift) |
Do not set hash directly. I am pretty sure there is a static function somewhere
for that. Make it a static method of String and use it. This will remove code
duplication.

http://codereview.chromium.org/3141022/diff/14003/53009
File src/runtime.js (right):

http://codereview.chromium.org/3141022/diff/14003/53009#newcode506
src/runtime.js:506: return %_IsCachedArrayIndex(x) ?
%_CachedArrayIndexToNumber(x)
IsCachedArrayIndex/CachedArrayIndexToNumber are strange names. 

Maybe HasCachedArrayIndex/GetCachedArrayIndex? Or something like that.

http://codereview.chromium.org/3141022/diff/14003/53010
File src/v8natives.js (right):

http://codereview.chromium.org/3141022/diff/14003/53010#newcode114
src/v8natives.js:114: if (!IS_STRING(string)) string =
NonStringToString(string);
we have TO_STRING_INLINE macros

http://codereview.chromium.org/3141022/diff/14003/53010#newcode125
src/v8natives.js:125: if (!IS_STRING(string)) string =
NonStringToString(string);
we have TO_STRING_INLINE macros

http://codereview.chromium.org/3141022/diff/14003/53011
File src/x64/codegen-x64.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53011#newcode7332
src/x64/codegen-x64.cc:7332: 
should not we string.Unuse() somewhere?

http://codereview.chromium.org/3141022/diff/14003/53011#newcode7336
src/x64/codegen-x64.cc:7336: __ andl(number.reg(),
Immediate(String::kArrayIndexValueMask));
to avoid codeduplication use GenerateIndexFromHash

http://codereview.chromium.org/3141022/diff/14003/53013
File src/x64/full-codegen-x64.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53013#newcode2773
src/x64/full-codegen-x64.cc:2773: __ Integer32ToSmi(rax, rax);
GenerateIndexFromHash

[SeRya, 2010-08-26 17:42:26]

http://codereview.chromium.org/3141022/diff/14003/53001
File src/arm/codegen-arm.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53001#newcode5635
src/arm/codegen-arm.cc:5635: Register tmp = frame_->scratch0();
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> tmp is not used?

Removed.

http://codereview.chromium.org/3141022/diff/14003/53001#newcode5637
src/arm/codegen-arm.cc:5637: ASSERT(String::kHashShift >= kSmiTagSize);
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> assert also that kSmiTag == 0

After moving the code into IndexFromHash there is no reason to keep the assert.

http://codereview.chromium.org/3141022/diff/14003/53001#newcode5638
src/arm/codegen-arm.cc:5638: __ and_(value, value,
Operand(String::kArrayIndexValueMask));
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> There is GenerateIndexFromHash in ic-arm.cc.
> 
> It seems to provide better instruction sequence based on Ubfx
[kArrayIndexValue
> mask is too big for ARM so and_ will produce two instruction: load mask from
> memory to ip, then and_(value, value, ip)].
> 
> Turn GenerateIndexFromHash into method of MacroAssembler and use it here.

Done.

http://codereview.chromium.org/3141022/diff/14003/53003
File src/arm/full-codegen-arm.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53003#newcode2674
src/arm/full-codegen-arm.cc:2674: ASSERT(String::kHashShift >= kSmiTagSize);
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> assert kSmiTag == 0

Assert removed.

http://codereview.chromium.org/3141022/diff/14003/53003#newcode2675
src/arm/full-codegen-arm.cc:2675: __ and_(r0, r0,
Operand(String::kArrayIndexValueMask));
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> use GenerateIndexFromHash (see comment in codegen-arm.cc).

Done.

http://codereview.chromium.org/3141022/diff/14003/53005
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53005#newcode8076
src/ia32/codegen-ia32.cc:8076: string.ToRegister();
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> should not we string.Unuse() somewhere later?

Done.

http://codereview.chromium.org/3141022/diff/14003/53005#newcode8081
src/ia32/codegen-ia32.cc:8081: ASSERT(String::kHashShift > kSmiTagSize);
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> >=
> 
> kSmiTag == 0

Assert removed.

http://codereview.chromium.org/3141022/diff/14003/53005#newcode8082
src/ia32/codegen-ia32.cc:8082: __ and_(number.reg(),
String::kArrayIndexValueMask);
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> to avoid code duplication use GenerateIndexFromHash (make it method of
> MacroAssembler).

Done.

http://codereview.chromium.org/3141022/diff/14003/53007
File src/ia32/full-codegen-ia32.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53007#newcode2773
src/ia32/full-codegen-ia32.cc:2773: ASSERT(String::kHashShift >= kSmiTagSize);
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> kSmiTag == 0

Assert removed.

http://codereview.chromium.org/3141022/diff/14003/53007#newcode2774
src/ia32/full-codegen-ia32.cc:2774: __ and_(eax, String::kArrayIndexValueMask);
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> to avoid code duplication use GenerateIndexFromHash (make it method of
> MacroAssembler).

Done.

http://codereview.chromium.org/3141022/diff/14003/53008
File src/runtime.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53008#newcode4849
src/runtime.cc:4849: } else if ((subject->hash_field() &
String::kHashNotComputedMask) != 0 &&
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> 1) don't check String::kHashNotComputedMask directly. there is a method for
> that. 

Done.

> 2) I do not understand (len == 1 || data[0] != '0') check. Are you trying to
> guard against octal literals? I don't think it is necessary here. At least
> ParseDecimalInteger is not taking them into account. 

ParseDecimalInteger does eat zero-leading numbers. However this code this code
must not assign array-index-hash to such a string because String::Hash doesn't.
Equivalent strings must not have different hashes.

> 3) Even if len >= String::kMaxCachedArrayIndexLength it worth setting hash any
> way

I changed this condition to String::kMaxArrayIndexSize because the same
condition is used in StringHasher::StringHasher. Again this code may not be less
restrictive than StringHasher.

http://codereview.chromium.org/3141022/diff/14003/53008#newcode4854
src/runtime.cc:4854: uint32_t hash = (d << String::kHashShift) |
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> Do not set hash directly. I am pretty sure there is a static function
somewhere
> for that. Make it a static method of String and use it. This will remove code
> duplication. 
> 

Added StringHasher::MakeCachedArrayIndex.

http://codereview.chromium.org/3141022/diff/14003/53009
File src/runtime.js (right):

http://codereview.chromium.org/3141022/diff/14003/53009#newcode506
src/runtime.js:506: return %_IsCachedArrayIndex(x) ?
%_CachedArrayIndexToNumber(x)
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> IsCachedArrayIndex/CachedArrayIndexToNumber are strange names. 
> 
> Maybe HasCachedArrayIndex/GetCachedArrayIndex? Or something like that.

Done.

http://codereview.chromium.org/3141022/diff/14003/53010
File src/v8natives.js (right):

http://codereview.chromium.org/3141022/diff/14003/53010#newcode114
src/v8natives.js:114: if (!IS_STRING(string)) string =
NonStringToString(string);
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> we have TO_STRING_INLINE macros

Done.

http://codereview.chromium.org/3141022/diff/14003/53010#newcode125
src/v8natives.js:125: if (!IS_STRING(string)) string =
NonStringToString(string);
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> we have TO_STRING_INLINE macros

Done.

http://codereview.chromium.org/3141022/diff/14003/53011
File src/x64/codegen-x64.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53011#newcode7332
src/x64/codegen-x64.cc:7332: 
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> should not we string.Unuse() somewhere?

Done.

http://codereview.chromium.org/3141022/diff/14003/53011#newcode7336
src/x64/codegen-x64.cc:7336: __ andl(number.reg(),
Immediate(String::kArrayIndexValueMask));
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> to avoid codeduplication use GenerateIndexFromHash

Done.

http://codereview.chromium.org/3141022/diff/14003/53013
File src/x64/full-codegen-x64.cc (right):

http://codereview.chromium.org/3141022/diff/14003/53013#newcode2773
src/x64/full-codegen-x64.cc:2773: __ Integer32ToSmi(rax, rax);
On 2010/08/26 12:52:57, Vyacheslav Egorov wrote:
> GenerateIndexFromHash

Done.

[Vyacheslav Egorov (Chromium), 2010-08-27 08:57:59]

LGTM

http://codereview.chromium.org/3141022/diff/28006/34008
File src/arm/macro-assembler-arm.cc (right):

http://codereview.chromium.org/3141022/diff/28006/34008#newcode1340
src/arm/macro-assembler-arm.cc:1340: void MacroAssembler::IndexFromHash(Register
key, Register hash) {
makes sense to rename key to index and reorder arguments so that out reg goes
last.

http://codereview.chromium.org/3141022/diff/28006/34008#newcode1343
src/arm/macro-assembler-arm.cc:1343: //   hash - holds the key's hash.
Clobbered.
Worth moving this comment to header file. It is important to state that hash
will be clobbered.

http://codereview.chromium.org/3141022/diff/28006/34008#newcode1355
src/arm/macro-assembler-arm.cc:1355: // there is no difference in using either
key.
this comment about clobbering makes no sense after this function became public
and generic.

http://codereview.chromium.org/3141022/diff/28006/34008#newcode1356
src/arm/macro-assembler-arm.cc:1356: STATIC_ASSERT(String::kHashShift >=
kSmiTagSize);
This assert makes no sense (we do not use expression kHashShift - kSmiTagSize)

Better assert kSmiTag == 0

http://codereview.chromium.org/3141022/diff/28006/34015
File src/ia32/macro-assembler-ia32.cc (right):

http://codereview.chromium.org/3141022/diff/28006/34015#newcode1055
src/ia32/macro-assembler-ia32.cc:1055: // Register use:
see comments from arm macroassembler, all of them [except for comment about
String::kHashShift >= kSmiTagSize assert] apply to this method.

http://codereview.chromium.org/3141022/diff/28006/34017
File src/runtime.cc (right):

http://codereview.chromium.org/3141022/diff/28006/34017#newcode4864
src/runtime.cc:4864: ASSERT_EQ((subject->Hash(),
static_cast<int>(subject->hash_field())),
This usage of comma-expression looks a bit hackerish to me. Can we avoid it?

http://codereview.chromium.org/3141022/diff/28006/34024
File src/x64/macro-assembler-x64.cc (right):

http://codereview.chromium.org/3141022/diff/28006/34024#newcode395
src/x64/macro-assembler-x64.cc:395: // Register use:
comments are same as for ia32 macroassembler

[SeRya, 2010-08-27 10:23:30]

http://codereview.chromium.org/3141022/diff/28006/34008
File src/arm/macro-assembler-arm.cc (right):

http://codereview.chromium.org/3141022/diff/28006/34008#newcode1340
src/arm/macro-assembler-arm.cc:1340: void MacroAssembler::IndexFromHash(Register
key, Register hash) {
On 2010/08/27 08:57:59, Vyacheslav Egorov wrote:
> makes sense to rename key to index and reorder arguments so that out reg goes
> last.

Done.

http://codereview.chromium.org/3141022/diff/28006/34008#newcode1343
src/arm/macro-assembler-arm.cc:1343: //   hash - holds the key's hash.
Clobbered.
On 2010/08/27 08:57:59, Vyacheslav Egorov wrote:
> Worth moving this comment to header file. It is important to state that hash
> will be clobbered.

Done.

http://codereview.chromium.org/3141022/diff/28006/34008#newcode1355
src/arm/macro-assembler-arm.cc:1355: // there is no difference in using either
key.
On 2010/08/27 08:57:59, Vyacheslav Egorov wrote:
> this comment about clobbering makes no sense after this function became public
> and generic.

The comment removed.

http://codereview.chromium.org/3141022/diff/28006/34008#newcode1356
src/arm/macro-assembler-arm.cc:1356: STATIC_ASSERT(String::kHashShift >=
kSmiTagSize);
On 2010/08/27 08:57:59, Vyacheslav Egorov wrote:
> This assert makes no sense (we do not use expression kHashShift - kSmiTagSize)
> 
> Better assert kSmiTag == 0

The comment replaced.

http://codereview.chromium.org/3141022/diff/28006/34015
File src/ia32/macro-assembler-ia32.cc (right):

http://codereview.chromium.org/3141022/diff/28006/34015#newcode1055
src/ia32/macro-assembler-ia32.cc:1055: // Register use:
On 2010/08/27 08:57:59, Vyacheslav Egorov wrote:
> see comments from arm macroassembler, all of them [except for comment about
> String::kHashShift >= kSmiTagSize assert] apply to this method.

Done.

http://codereview.chromium.org/3141022/diff/28006/34017
File src/runtime.cc (right):

http://codereview.chromium.org/3141022/diff/28006/34017#newcode4864
src/runtime.cc:4864: ASSERT_EQ((subject->Hash(),
static_cast<int>(subject->hash_field())),
On 2010/08/27 08:57:59, Vyacheslav Egorov wrote:
> This usage of comma-expression looks a bit hackerish to me. Can we avoid it?

Comma-expression well defined in the C++ Standard so I don't think i's
hackerish. However I moved subject->Hash() to a separate statement in "#ifdef
DEBUG" block.

http://codereview.chromium.org/3141022/diff/28006/34024
File src/x64/macro-assembler-x64.cc (right):

http://codereview.chromium.org/3141022/diff/28006/34024#newcode395
src/x64/macro-assembler-x64.cc:395: // Register use:
On 2010/08/27 08:57:59, Vyacheslav Egorov wrote:
> comments are same as for ia32 macroassembler

Done.