Introduce fast native caches and use it in String.search.

Introduce fast native caches and use it in String.search.

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

[antonm, 2010-03-30 10:32:40]

Kevin,

may you have a look?  If overall approach is fine, I'd stub other platforms and
add some unit tests.

Next thing I am going to experiment with is to index caches by numbers and thus
both avoid loading fixed array (StringSearch_cache currently) and enable
cleaning caches on major GCs.

Another minor thing to try is to turn objects into strings and cache them as
well.

Many thanks to Vitaly for pointing out that I can only cache strings, not
objects.

[antonm, 2010-04-06 10:29:20]

friendly ping

[Kevin Millikin (Chromium), 2010-04-07 13:34:36]

I looked mainly at the code generator changes, which LGTM.  Maybe Lasse should
take a closer look at the runtime changes.

http://codereview.chromium.org/1563005/diff/2001/3005
File src/heap.h (right):

http://codereview.chromium.org/1563005/diff/2001/3005#newcode896
src/heap.h:896: // Allocate unitialized fixed array.
There's a typo in this comment: unitialized ==> uninitialized.

http://codereview.chromium.org/1563005/diff/2001/3005#newcode898
src/heap.h:898: static Object* AllocateRawFixedArray(int length,
The other functions have a default PretenureFlag argument.  Why is this one
overloaded?

http://codereview.chromium.org/1563005/diff/2001/3006
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/1563005/diff/2001/3006#newcode6508
src/ia32/codegen-ia32.cc:6508: cache.ToRegister();
key and cache could be the same register (if we had JS code %_GetFromCache(x,
x)).  Since that shouldn't be the case (we control the call site), maybe assert
that !key.reg().is(cache.reg()).

[antonm, 2010-04-07 15:01:35]

Thanks a lot, Kevin!

Looping Lasse in (if you don't mind, Lasse.)

http://codereview.chromium.org/1563005/diff/2001/3005
File src/heap.h (right):

http://codereview.chromium.org/1563005/diff/2001/3005#newcode896
src/heap.h:896: // Allocate unitialized fixed array.
On 2010/04/07 13:34:36, Kevin Millikin wrote:
> There's a typo in this comment: unitialized ==> uninitialized.

Done.

http://codereview.chromium.org/1563005/diff/2001/3005#newcode898
src/heap.h:898: static Object* AllocateRawFixedArray(int length,
On 2010/04/07 13:34:36, Kevin Millikin wrote:
> The other functions have a default PretenureFlag argument.  Why is this one
> overloaded?

Those have slight semantic difference formerly hidden in callers---the first one
only allocates in new and large object (if fixed array is too big) spaces.  The
new one, as it could try to allocate in old space, needs a special check if
fixed array still fits into old space.

http://codereview.chromium.org/1563005/diff/2001/3006
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/1563005/diff/2001/3006#newcode6508
src/ia32/codegen-ia32.cc:6508: cache.ToRegister();
On 2010/04/07 13:34:36, Kevin Millikin wrote:
> key and cache could be the same register (if we had JS code %_GetFromCache(x,
> x)).  Since that shouldn't be the case (we control the call site), maybe
assert
> that !key.reg().is(cache.reg()).

Kevin, I quite agree that they always should be different.  However, way assert
that?  It looks like the rest of the code doesn't depend on this assumption.

Still adding ASSERT.

[Kevin Millikin (Chromium), 2010-04-07 15:31:56]

http://codereview.chromium.org/1563005/diff/2001/3006
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/1563005/diff/2001/3006#newcode6508
src/ia32/codegen-ia32.cc:6508: cache.ToRegister();
On 2010/04/07 15:01:35, antonm wrote:
> On 2010/04/07 13:34:36, Kevin Millikin wrote:
> > key and cache could be the same register (if we had JS code
%_GetFromCache(x,
> > x)).  Since that shouldn't be the case (we control the call site), maybe
> assert
> > that !key.reg().is(cache.reg()).
> 
> Kevin, I quite agree that they always should be different.  However, way
assert
> that?  It looks like the rest of the code doesn't depend on this assumption.
> 
> Still adding ASSERT.

Actually you're right.  I must have misread cmp as mov.  Disregard :)

[antonm, 2010-04-07 15:38:59]

http://codereview.chromium.org/1563005/diff/2001/3006
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/1563005/diff/2001/3006#newcode6508
src/ia32/codegen-ia32.cc:6508: cache.ToRegister();
On 2010/04/07 15:31:56, Kevin Millikin wrote:
> On 2010/04/07 15:01:35, antonm wrote:
> > On 2010/04/07 13:34:36, Kevin Millikin wrote:
> > > key and cache could be the same register (if we had JS code
> %_GetFromCache(x,
> > > x)).  Since that shouldn't be the case (we control the call site), maybe
> > assert
> > > that !key.reg().is(cache.reg()).
> > 
> > Kevin, I quite agree that they always should be different.  However, way
> assert
> > that?  It looks like the rest of the code doesn't depend on this assumption.
> > 
> > Still adding ASSERT.
> 
> Actually you're right.  I must have misread cmp as mov.  Disregard :)

Thanks, Kevin.  Disregarded :)

[Lasse Reichstein, 2010-04-08 17:04:28]

I'm not convinced this is a good idea.

It seems like it would be a fairly big overhead for cache misses, and at the
same time there is a lot of error checking missing from the runtime functions
(possibly only from GenerateGetFromCache, if the one in runtime.cc is only
called through the generated code and the arguments have been checked there).

The FixedArray should be boxed, probably as the elements array of a JSArray, and
arguments should be checked.

Also, I think some of the measured speed improvements are spurious, but I need
to check that.

http://codereview.chromium.org/1563005/diff/12001/13004
File src/heap.cc (right):

http://codereview.chromium.org/1563005/diff/12001/13004#newcode3074
src/heap.cc:3074:
reinterpret_cast<Array*>(result)->set_map(Heap::fixed_array_map());
Perhaps cast to HeapObject, so one doesn't start trying to figure out why you
are using Array :)

http://codereview.chromium.org/1563005/diff/12001/13004#newcode3077
src/heap.cc:3077: ASSERT(!Heap::InNewSpace(filler));
Assert this before doing the raw allocation (just for clarity, so I won't have
to worry what happens if the ASSERT fails and the array contains garbage.

http://codereview.chromium.org/1563005/diff/12001/13006
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/1563005/diff/12001/13006#newcode6555
src/ia32/codegen-ia32.cc:6555: // tmp.reg() now holds finger offset as a smi.
Cache.reg is supposed to hold a FixedArray. You should test it before using the
value. You shouldn't trust the parameters of runtime functions.

Also, document the expected input somewhere, e.g.:
"A JSArray with fast elements FixedArray with the following layout ..." (or
refer to where it's already written).

http://codereview.chromium.org/1563005/diff/12001/13006#newcode6557
src/ia32/codegen-ia32.cc:6557: __ cmp(key.reg(), FieldOperand(cache.reg(),
Assert that smi-encoding multiplies by two (i.e., tag == 0 and tagSize == 1),
and that tmp holds a Smi.

http://codereview.chromium.org/1563005/diff/12001/13008
File src/runtime.cc (right):

http://codereview.chromium.org/1563005/diff/12001/13008#newcode9995
src/runtime.cc:9995: return *cache;
You are leaking raw FixedArray's into JavaScript code. 
We haven't done that anywhere else. What we usually do instead is to have a
JSArray with the FixedArray that we want as fast elements.

Ofcourse these cache objects are supposed to be completely opaque to the
JavaScript code and never be visible to the user (although it's not obvious that
a malicious user can't leak it somehow), but I'm still not comfortable with it.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10008
src/runtime.cc:10008: Handle<JSFunction>
factory(JSFunction::cast(cache->get(kFactoryIndex)));
Needs error checking as well, since we haven't checked that this FixedArray
element is a function during this runtime call.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10015
src/runtime.cc:10015: receiver,
So the factory function is the function being cached?
Am I correct that this moves all calls to that function into C++ code, which
then calls back to JavaSscript? It seems like a big detour for a cache-miss.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10018
src/runtime.cc:10018: &pending_exception);
Are we sure that this call can't change the value at key.location()? (I.e., I'm
not, so if you are, please write a comment about it).

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10032
src/runtime.cc:10032: CONVERT_CHECKED(FixedArray, cache, args[0]);
Check the size of the Array as well (must be at least kEntriesIndex or possibly
more).

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10063
src/runtime.cc:10063: }
I'm not sure it's worth the complexity to have two loops instead of just
checking o==key one extra time. Have you checked the impact of just having one
loop?

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10071
src/runtime.cc:10071: int target_index = (finger_index > kEntriesIndex) ?
finger_index - 2
We fill up from left to right, and then evict right-to-left.
Seems more consistent to evict the element after the finger instead.

http://codereview.chromium.org/1563005/diff/12001/13011
File test/mjsunit/fuzz-natives.js (right):

http://codereview.chromium.org/1563005/diff/12001/13011#newcode165
test/mjsunit/fuzz-natives.js:165: "_GetFromCache": true,
That's not a sufficient reason not to check the arguments.
That only goes if you are certain that what it does is always safe (i.e., you
can control its arguments completely).

[antonm, 2010-04-08 17:50:14]

Lasse, thanks a lot for comments.

Let me start with the principal question.  My current plan is to move all the
logic into the codegen eventually.  I've finished calling of JS functions from
codegen in another CL, so the rest of the code could be easily ported into
deferred code.  Thus addressing performance concern of calling JS from C++.

Now to fixed array issue.  To save us from property lookup I plan to index all
the caches with smis and turn %_GetFromCache into %_GetFromCache(cache index,
key).  I'd probably require cache index to be compile time number to save us
some more checks.  The effect would be that fixed arrays are not exposed into
JS.

Up to you how much of this stuff you'd prefer to see in this CL vs. series of
smaller CLs.

And yes, I omit all the checks I could for exactly the reason of performance.

You should be in better position to see if it has any security implications.

http://codereview.chromium.org/1563005/diff/12001/13004
File src/heap.cc (right):

http://codereview.chromium.org/1563005/diff/12001/13004#newcode3074
src/heap.cc:3074:
reinterpret_cast<Array*>(result)->set_map(Heap::fixed_array_map());
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> Perhaps cast to HeapObject, so one doesn't start trying to figure out why you
> are using Array :)

Done.

http://codereview.chromium.org/1563005/diff/12001/13004#newcode3077
src/heap.cc:3077: ASSERT(!Heap::InNewSpace(filler));
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> Assert this before doing the raw allocation (just for clarity, so I won't have
> to worry what happens if the ASSERT fails and the array contains garbage.
> 

Done.

http://codereview.chromium.org/1563005/diff/12001/13006
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/1563005/diff/12001/13006#newcode6555
src/ia32/codegen-ia32.cc:6555: // tmp.reg() now holds finger offset as a smi.
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> Cache.reg is supposed to hold a FixedArray. You should test it before using
the
> value. You shouldn't trust the parameters of runtime functions.
> 
> Also, document the expected input somewhere, e.g.:
> "A JSArray with fast elements FixedArray with the following layout ..." (or
> refer to where it's already written).

I intentionally omit any checks.  It's performance critical code and which is
(apparently) only controlled by us, so I'd rather keep the things as they are
now.

http://codereview.chromium.org/1563005/diff/12001/13006#newcode6557
src/ia32/codegen-ia32.cc:6557: __ cmp(key.reg(), FieldOperand(cache.reg(),
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> Assert that smi-encoding multiplies by two (i.e., tag == 0 and tagSize == 1),
> and that tmp holds a Smi.

Again check for tmp being smi omitted, but assert added.

http://codereview.chromium.org/1563005/diff/12001/13008
File src/runtime.cc (right):

http://codereview.chromium.org/1563005/diff/12001/13008#newcode9995
src/runtime.cc:9995: return *cache;
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> You are leaking raw FixedArray's into JavaScript code. 
> We haven't done that anywhere else. What we usually do instead is to have a
> JSArray with the FixedArray that we want as fast elements.
> 
> Ofcourse these cache objects are supposed to be completely opaque to the
> JavaScript code and never be visible to the user (although it's not obvious
that
> a malicious user can't leak it somehow), but I'm still not comfortable with
it.

That's the crucial idea of the patch---I'd like to have as few levels of
indirection as possible.  Up to you to decide if it's a good or a bad idea.

And please notice, that my next planned move is to get rid of those references
altogether---instead caches would be indexed by smis (to bypass property
lookup).

The code would look:

%NewCache(0 /* cache id */, 16 /* size */, factory);

%_GetFromCache(0, key);

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10008
src/runtime.cc:10008: Handle<JSFunction>
factory(JSFunction::cast(cache->get(kFactoryIndex)));
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> Needs error checking as well, since we haven't checked that this FixedArray
> element is a function during this runtime call.

But we checked that on creation of the cache, no?

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10015
src/runtime.cc:10015: receiver,
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> So the factory function is the function being cached?
> Am I correct that this moves all calls to that function into C++ code, which
> then calls back to JavaSscript? It seems like a big detour for a cache-miss.
> 

That's true.  I plan to move all this code into the codegen eventually, but
rather do it in small steps.  If you'd prefer to see it in one go, just let me
know.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10018
src/runtime.cc:10018: &pending_exception);
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> Are we sure that this call can't change the value at key.location()? (I.e.,
I'm
> not, so if you are, please write a comment about it).

It can if it triggers GC, but this arhv object is not used after the call.  If
you like, I can put it into the block.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10032
src/runtime.cc:10032: CONVERT_CHECKED(FixedArray, cache, args[0]);
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> Check the size of the Array as well (must be at least kEntriesIndex or
possibly
> more).

In debug mode?  Or for both builds?

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10063
src/runtime.cc:10063: }
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> I'm not sure it's worth the complexity to have two loops instead of just
> checking o==key one extra time. Have you checked the impact of just having one
> loop? 
> 

I'm probably missing something.  I need to loop from finger + 1 up to the end of
the cache and then from start of cache up to finger.  I could merge those two
loops doing the check inside, but it looks somewhat more cumbersome to me.

Or did I misinterpret you completely?

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10071
src/runtime.cc:10071: int target_index = (finger_index > kEntriesIndex) ?
finger_index - 2
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> We fill up from left to right, and then evict right-to-left.
> Seems more consistent to evict the element after the finger instead.

I might be missing something, but I hoped to implement LRU eviction policy for
the case when keys rotate in a loop which is bigger than cache.

But I am not insisting.

http://codereview.chromium.org/1563005/diff/12001/13011
File test/mjsunit/fuzz-natives.js (right):

http://codereview.chromium.org/1563005/diff/12001/13011#newcode165
test/mjsunit/fuzz-natives.js:165: "_GetFromCache": true,
On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> That's not a sufficient reason not to check the arguments.
> That only goes if you are certain that what it does is always safe (i.e., you
> can control its arguments completely).

Which I believe to be the case as it should only be used in the library.  What
am I missing?

[antonm, 2010-04-09 05:20:20]

http://codereview.chromium.org/1563005/diff/12001/13008
File src/runtime.cc (right):

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10071
src/runtime.cc:10071: int target_index = (finger_index > kEntriesIndex) ?
finger_index - 2
Thinking more about it.  Looks like everything should be fine if I both iterate
backwards and evict post finger entry---that would give LRU for both partial and
full caches, correct?

I'll implement it, if this CL still has a chance.

On 2010/04/08 17:50:14, antonm wrote:
> On 2010/04/08 17:04:28, Lasse Reichstein wrote:
> > We fill up from left to right, and then evict right-to-left.
> > Seems more consistent to evict the element after the finger instead.
> 
> I might be missing something, but I hoped to implement LRU eviction policy for
> the case when keys rotate in a loop which is bigger than cache.
> 
> But I am not insisting.
>

[Lasse Reichstein, 2010-04-09 07:18:25]

If you make the FixedArrays completely hidden from JS code, then they should be
safe from tampering, and if the cache index is a compile time smi (e.g.,
constant defined in macros.py), then that parameter won't need checking either.
I do believe that would remove any of the security concerns I have.

http://codereview.chromium.org/1563005/diff/12001/13008
File src/runtime.cc (right):

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10015
src/runtime.cc:10015: receiver,
That's ok for now. There doesn't seem to be any significant regressions.
Ofcourse, that may just be because there are no non-pathological uses of
String.search.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10018
src/runtime.cc:10018: &pending_exception);
The reason I'm wary about this is that you are passing the address of a handle
location, but handles can be shared, so if the value is modified by code (apart
from GC, where it should be), it might affect other references to the handle as
well.
In this case, we know that the handle isn't shared (because we created it from
an Object* just above), and it isn't used after this call, so even if the value
is changed, it won't hurt anything. 
So I guess the comment I want here is that the key handle isn't shared and isn't
used later.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10063
src/runtime.cc:10063: }
Probably, it wasn't that clear :);.

I'm considering whether doing a single loop, from 0 to len, without a special
case for finger_index, would be so much simpler than the two loops that it is
worth the overhead of checking against finger_index again (and not be equal).

However, I was missing that the current approach iterates in
Most-Recently-Used-order, which is ofcourse better, so ignore this suggestion.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10071
src/runtime.cc:10071: int target_index = (finger_index > kEntriesIndex) ?
finger_index - 2
I want LRU order too, but I don't think the current code does that for the
entries added before the cache fills up.

The current code fills up the array in increasing order, but evicts in
decreasing. I.e., if there are four positions, they are filled in the order 0,
1, 2, 3, and then when it's full, the first to be evicted/reused is 2, and then
continuing with 1, 0, 3, 2.... (at which point it is doing LRU order).
The LRU element at the time the cache fills up would be the one after the finger
(wrapping to 0).

I'm not sure what you mean by iterating backwards, but if you keep the current
filling strategy and evict the post-finger entry each time, you will keep
cycling in the same order for both partial and full caches.

http://codereview.chromium.org/1563005/diff/12001/13011
File test/mjsunit/fuzz-natives.js (right):

http://codereview.chromium.org/1563005/diff/12001/13011#newcode165
test/mjsunit/fuzz-natives.js:165: "_GetFromCache": true,
We do not assume that the builtins object is secure. A malicious user is assumed
to be able to get a reference to it, and thereby control any builtin function or
variable. In this case, it includes the variable holding the cache. If that is
overwritten by a carefully crafted object (maybe a heap number, maybe a JSObject
with well-designed internal properties), your code can be made to read any
address, and, on a cache miss, write the address with the result of a
user-defined function. I.e., write any writable address. 
I'm pretty sure that would be an "arbitrary code execution" waiting to happen.
:)

With your suggested change, I'm no longer worried about this.

[antonm, 2010-04-09 13:48:51]

Lasse, thanks a lot for comments and clarifications.

May you have another look?

Major features: access to caches by indices; reworked search and eviction
algorithm to implement LRU, hopefully this time for real.

http://codereview.chromium.org/1563005/diff/12001/13008
File src/runtime.cc (right):

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10015
src/runtime.cc:10015: receiver,
On 2010/04/09 07:18:25, Lasse Reichstein wrote:
> That's ok for now. There doesn't seem to be any significant regressions.
> Ofcourse, that may just be because there are no non-pathological uses of
> String.search.

Ok, so let's postpone it for a next patch.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10018
src/runtime.cc:10018: &pending_exception);
On 2010/04/09 07:18:25, Lasse Reichstein wrote:
> The reason I'm wary about this is that you are passing the address of a handle
> location, but handles can be shared, so if the value is modified by code
(apart
> from GC, where it should be), it might affect other references to the handle
as
> well.
> In this case, we know that the handle isn't shared (because we created it from
> an Object* just above), and it isn't used after this call, so even if the
value
> is changed, it won't hurt anything. 
> So I guess the comment I want here is that the key handle isn't shared and
isn't
> used later.

Thanks a lot for explanations.  Put into a separate block and comment added.

http://codereview.chromium.org/1563005/diff/12001/13008#newcode10071
src/runtime.cc:10071: int target_index = (finger_index > kEntriesIndex) ?
finger_index - 2
On 2010/04/09 07:18:25, Lasse Reichstein wrote:
> I want LRU order too, but I don't think the current code does that for the
> entries added before the cache fills up.
> 
> The current code fills up the array in increasing order, but evicts in
> decreasing. I.e., if there are four positions, they are filled in the order 0,
> 1, 2, 3, and then when it's full, the first to be evicted/reused is 2, and
then
> continuing with 1, 0, 3, 2.... (at which point it is doing LRU order).
> The LRU element at the time the cache fills up would be the one after the
finger
> (wrapping to 0).
> 
> I'm not sure what you mean by iterating backwards, but if you keep the current
> filling strategy and evict the post-finger entry each time, you will keep
> cycling in the same order for both partial and full caches.
> 
> 

Let me try to make code speak for itself---it'd be a good readability check :)

[Lasse Reichstein, 2010-04-13 09:30:13]

Seems much better, and safer.

I would consider creating all caches from C++ code during bootstrap (perhaps
have an enumeration of caches, so you know the number), instead of creating them
in toplevel JSCode in natives files (which is also run during bootstrap anyway).
That would make, e.g., the test for an undefined cache unnecessary, and you can
check the literal smi cache id more strictly.

You will need to do some native X64 and ARM calls, possibly just to the C++
runtime functions (or it won't compile).

http://codereview.chromium.org/1563005/diff/9012/25002
File src/contexts.h (right):

http://codereview.chromium.org/1563005/diff/9012/25002#newcode85
src/contexts.h:85: V(NATIVE_CACHES_INDEX, Object, native_caches) \
The name seems like we are caching natives (q.v. FUNCTION_CACHE_INDEX). How
about JSFUNCTION_RESULT_CACHES_INDEX?

http://codereview.chromium.org/1563005/diff/9012/25005
File src/heap.cc (right):

http://codereview.chromium.org/1563005/diff/9012/25005#newcode1670
src/heap.cc:1670: // Allocate cache for single character strings.
-> ... for single character ASCII strings.

http://codereview.chromium.org/1563005/diff/9012/25007
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/1563005/diff/9012/25007#newcode6541
src/ia32/codegen-ia32.cc:6541: int cache_id =
Smi::cast(*(args->at(0)->AsLiteral()->handle()))->value();
Would be nice to have an assert that args->at(0) is in fact a literal, just to
crash with a better error message if we write bad code.

http://codereview.chromium.org/1563005/diff/9012/25007#newcode6550
src/ia32/codegen-ia32.cc:6550: if (o->IsUndefined()) {
Why have undefined fields in the FixedArray, instead of just a shorter array?
Then you could just do a check on index vs. length (which is asserted by
FixedArray::get in debug mode, but otherwise not checked).

http://codereview.chromium.org/1563005/diff/9012/25009
File src/runtime.cc (right):

http://codereview.chromium.org/1563005/diff/9012/25009#newcode9984
src/runtime.cc:9984: ASSERT(args.length() == 3);
Is there an advantage to creating new caches at runtime, instead of creating
them all at boot-strap time?

http://codereview.chromium.org/1563005/diff/9012/25009#newcode9992
src/runtime.cc:9992: Handle<JSFunction> factory(factory_obj);
You can use CONVERT_ARG_CHECKED(JSFunction, factory, 2) to create a
Handle<JSFunction> directly backed by the parameter on the stack, instead of
creating a new handle from a JSFunction*.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode9994
src/runtime.cc:9994: int cache_id = cache_id_obj->value();
There's also CONVERT_SMI_CHECKED(cache_id, args[0]) that does what you want in
one line.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10022
src/runtime.cc:10022: cache->set(kCacheSizeIndex, Smi::FromInt(kEntriesIndex));
kEntriesIndex->size

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10025
src/runtime.cc:10025: }
If the cache already exists, but have a different size, is it ok to ignore this
call (just make a comment saying that it is, because we should only initialize
once).

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10065
src/runtime.cc:10065: static Object* Runtime_GetFromCache(Arguments args) {
This function is never called from JS code, but only as the slow case of
%_GetFromCache, correct?
In that case, we don't have to test the arguments as throughly, but it's worth
to make a comment about it, so we don't wonder why we don't check the indices
against the length of the cache array.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10079
src/runtime.cc:10079: // Search the cache in less recently used order.
(Well, possibly LRU, as long as we don't get a hit - which would move the
finger.)

http://codereview.chromium.org/1563005/diff/9012/25011
File src/string.js (right):

http://codereview.chromium.org/1563005/diff/9012/25011#newcode519
src/string.js:519: %NewCache(0, 16, function(re) { return new $RegExp(re); });
Create constants in macros.py, e.g.,  STRING_SEARCH_REGEXP_CACHE_ID = 0
(or something slightly shorter perhaps :)

This cache is created during bootstrapping (when builtins files are run), so you
could also just create the FixedArray from C++-code.

http://codereview.chromium.org/1563005/diff/9012/25011#newcode519
src/string.js:519: %NewCache(0, 16, function(re) { return new $RegExp(re); });
Could you just use $RegExp as the function (it works as a constructor, even if
not called using "new")?

http://codereview.chromium.org/1563005/diff/9012/25012
File test/mjsunit/fuzz-natives.js (right):

http://codereview.chromium.org/1563005/diff/9012/25012#newcode164
test/mjsunit/fuzz-natives.js:164: // additional checks.
Also: It's checked that all call points are using a literal smi as first
argument (perhaps also check that the second argument is a reasonably small smi
literal), and dying violently in the case that they are not is expected
behavior.

[antonm, 2010-04-13 14:41:45]

Lasse, thanks a lot for comments and suggestions.

I am starting on ports to ARM and x64.

http://codereview.chromium.org/1563005/diff/9012/25002
File src/contexts.h (right):

http://codereview.chromium.org/1563005/diff/9012/25002#newcode85
src/contexts.h:85: V(NATIVE_CACHES_INDEX, Object, native_caches) \
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> The name seems like we are caching natives (q.v. FUNCTION_CACHE_INDEX). How
> about JSFUNCTION_RESULT_CACHES_INDEX?

Sure, I like it better as well.

http://codereview.chromium.org/1563005/diff/9012/25005
File src/heap.cc (right):

http://codereview.chromium.org/1563005/diff/9012/25005#newcode1670
src/heap.cc:1670: // Allocate cache for single character strings.
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> -> ... for single character ASCII strings.

Done.

http://codereview.chromium.org/1563005/diff/9012/25007
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/1563005/diff/9012/25007#newcode6541
src/ia32/codegen-ia32.cc:6541: int cache_id =
Smi::cast(*(args->at(0)->AsLiteral()->handle()))->value();
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> Would be nice to have an assert that args->at(0) is in fact a literal, just to
> crash with a better error message if we write bad code.

Done.

http://codereview.chromium.org/1563005/diff/9012/25007#newcode6550
src/ia32/codegen-ia32.cc:6550: if (o->IsUndefined()) {
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> Why have undefined fields in the FixedArray, instead of just a shorter array?
> Then you could just do a check on index vs. length (which is asserted by
> FixedArray::get in debug mode, but otherwise not checked).
> 

Tried to play safe.  Imagine someone who by mistake puts wrong cache id.  But I
think that with your idea of creation of caches in C++, it is not needed
anymore.

http://codereview.chromium.org/1563005/diff/9012/25009
File src/runtime.cc (right):

http://codereview.chromium.org/1563005/diff/9012/25009#newcode9984
src/runtime.cc:9984: ASSERT(args.length() == 3);
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> Is there an advantage to creating new caches at runtime, instead of creating
> them all at boot-strap time?

I don't think so and really like your idea.  Reimplementing with this approach.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode9992
src/runtime.cc:9992: Handle<JSFunction> factory(factory_obj);
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> You can use CONVERT_ARG_CHECKED(JSFunction, factory, 2) to create a
> Handle<JSFunction> directly backed by the parameter on the stack, instead of
> creating a new handle from a JSFunction*.

Thanks, done.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode9994
src/runtime.cc:9994: int cache_id = cache_id_obj->value();
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> There's also CONVERT_SMI_CHECKED(cache_id, args[0]) that does what you want in
> one line.

Done.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10022
src/runtime.cc:10022: cache->set(kCacheSizeIndex, Smi::FromInt(kEntriesIndex));
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> kEntriesIndex->size

sorry, do you suggest to change 2nd arg?  if yes, I am not sure---caches are
originally empty and thus it should be kEntriesIndex.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10025
src/runtime.cc:10025: }
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> If the cache already exists, but have a different size, is it ok to ignore
this
> call (just make a comment saying that it is, because we should only initialize
> once).

It should be obsolete by now when it's not exposed in JS.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10065
src/runtime.cc:10065: static Object* Runtime_GetFromCache(Arguments args) {
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> This function is never called from JS code, but only as the slow case of
> %_GetFromCache, correct?
> In that case, we don't have to test the arguments as throughly, but it's worth
> to make a comment about it, so we don't wonder why we don't check the indices
> against the length of the cache array.

Sure.  Eventually it should all be in codegens.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10079
src/runtime.cc:10079: // Search the cache in less recently used order.
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> (Well, possibly LRU, as long as we don't get a hit - which would move the
> finger.)

Do you want me to change wording?

http://codereview.chromium.org/1563005/diff/9012/25011
File src/string.js (right):

http://codereview.chromium.org/1563005/diff/9012/25011#newcode519
src/string.js:519: %NewCache(0, 16, function(re) { return new $RegExp(re); });
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> Create constants in macros.py, e.g.,  STRING_SEARCH_REGEXP_CACHE_ID = 0
> (or something slightly shorter perhaps :)
> 
> This cache is created during bootstrapping (when builtins files are run), so
you
> could also just create the FixedArray from C++-code.

Cool idea, thanks.

http://codereview.chromium.org/1563005/diff/9012/25011#newcode519
src/string.js:519: %NewCache(0, 16, function(re) { return new $RegExp(re); });
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> Could you just use $RegExp as the function (it works as a constructor, even if
> not called using "new")?

Sure.  Done.  For some reason I couldn't use $RegExp, had to revert to
global.RegExp, any ideas why?

http://codereview.chromium.org/1563005/diff/9012/25012
File test/mjsunit/fuzz-natives.js (right):

http://codereview.chromium.org/1563005/diff/9012/25012#newcode164
test/mjsunit/fuzz-natives.js:164: // additional checks.
On 2010/04/13 09:30:14, Lasse Reichstein wrote:
> Also: It's checked that all call points are using a literal smi as first
> argument (perhaps also check that the second argument is a reasonably small
smi
> literal), and dying violently in the case that they are not is expected
> behavior.

Is this wording good enough?

[Lasse Reichstein, 2010-04-14 09:11:09]

LGTM.

http://codereview.chromium.org/1563005/diff/9012/25009
File src/runtime.cc (right):

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10022
src/runtime.cc:10022: cache->set(kCacheSizeIndex, Smi::FromInt(kEntriesIndex));
My mistake. I was confusing the two meanings of size (initial capacity and
currently used capacity) so I thought this field was holding the capacity, not
the next free entry pointer.

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10079
src/runtime.cc:10079: // Search the cache in less recently used order.
Maybe something to say that LRU only holds as long as we miss.

I'm worrying that if you alternate between two input values, every other
finger-miss will take the maximal time to find the match. And using a new key at
that point is 50% likely to overwrite the second-most-recently-used entry.

On the other hand, we don't want to reorder the cache based on usage, so we only
track the most recently used element (the finger) and don't really know what the
second most recently used element was.
I guess there isn't any simple way to do better.

http://codereview.chromium.org/1563005/diff/9012/25011
File src/string.js (right):

http://codereview.chromium.org/1563005/diff/9012/25011#newcode519
src/string.js:519: %NewCache(0, 16, function(re) { return new $RegExp(re); });
Not sure why you couldn't use $RegExp, but a guess would be that it didn't exist
yet at the time the natives code file was loaded.
Our natives code files really contain two parts: the runtime functions and the
initialization time setup. The setup cannot rely on another natives file having
been loaded before it, but the runtime functions are only called when all
natives files have been loaded and initialized.
In this case, global.RegExp was created by the bootstrapper code before loading
natives, but $RegExp isn't created until regexp.js is loaded (and global.RegExp
doesn't work until that has happened either, because regexp.js sets the code of
the function).

http://codereview.chromium.org/1563005/diff/9012/25012
File test/mjsunit/fuzz-natives.js (right):

http://codereview.chromium.org/1563005/diff/9012/25012#newcode164
test/mjsunit/fuzz-natives.js:164: // additional checks.
Maybe add something saying that the function only accepts a Smi literal as first
argument, which is checked at compile time. That's the real reason we can't test
it properly with fuzz-natives (right?).

[antonm, 2010-04-14 14:32:27]

Lasse, thanks a lot for review!

Running tests and submitting with some minor corrections.  If you'd like to see
something changed, just let me know.

http://codereview.chromium.org/1563005/diff/9012/25009
File src/runtime.cc (right):

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10022
src/runtime.cc:10022: cache->set(kCacheSizeIndex, Smi::FromInt(kEntriesIndex));
On 2010/04/14 09:11:09, Lasse Reichstein wrote:
> My mistake. I was confusing the two meanings of size (initial capacity and
> currently used capacity) so I thought this field was holding the capacity, not
> the next free entry pointer.

np

http://codereview.chromium.org/1563005/diff/9012/25009#newcode10079
src/runtime.cc:10079: // Search the cache in less recently used order.
On 2010/04/14 09:11:09, Lasse Reichstein wrote:
> Maybe something to say that LRU only holds as long as we miss.
> 
> I'm worrying that if you alternate between two input values, every other
> finger-miss will take the maximal time to find the match. And using a new key
at
> that point is 50% likely to overwrite the second-most-recently-used entry.
> 
> On the other hand, we don't want to reorder the cache based on usage, so we
only
> track the most recently used element (the finger) and don't really know what
the
> second most recently used element was.
> I guess there isn't any simple way to do better.

I just decided to drop the comment.  If you think we'de better have one, please,
let me know.

http://codereview.chromium.org/1563005/diff/9012/25011
File src/string.js (right):

http://codereview.chromium.org/1563005/diff/9012/25011#newcode519
src/string.js:519: %NewCache(0, 16, function(re) { return new $RegExp(re); });
On 2010/04/14 09:11:09, Lasse Reichstein wrote:
> Not sure why you couldn't use $RegExp, but a guess would be that it didn't
exist
> yet at the time the natives code file was loaded.
> Our natives code files really contain two parts: the runtime functions and the
> initialization time setup. The setup cannot rely on another natives file
having
> been loaded before it, but the runtime functions are only called when all
> natives files have been loaded and initialized.
> In this case, global.RegExp was created by the bootstrapper code before
loading
> natives, but $RegExp isn't created until regexp.js is loaded (and
global.RegExp
> doesn't work until that has happened either, because regexp.js sets the code
of
> the function).

Thanks a lot for explanations, I think it's indeed the case

http://codereview.chromium.org/1563005/diff/9012/25012
File test/mjsunit/fuzz-natives.js (right):

http://codereview.chromium.org/1563005/diff/9012/25012#newcode164
test/mjsunit/fuzz-natives.js:164: // additional checks.
On 2010/04/14 09:11:09, Lasse Reichstein wrote:
> Maybe add something saying that the function only accepts a Smi literal as
first
> argument, which is checked at compile time. That's the real reason we can't
test
> it properly with fuzz-natives (right?).

That is already done, see patch 8.  Again, going to submit, but if you would
like to have this comment altered, just let me know.