968296 - IonMonkey: Snapshot's constant pool should reuse index of identical values.

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Nicolas B. Pierron [:nbp]]

This is not critical, but this would be nice to avoid saving tens of times the sames constants in the constant pool for multiple reasons:
 - This cause the snapshot to be larger for no reason as we need to encode larger RValueAllocations.
 - This might cause longer iterations during GC marking.
 - This increase the number of bytes of IonScripts.

The code is currently contained in encodeAllocations (was encodeSlots), in js/src/jit/shared/CodeGenerator-shared.cpp.  The best approach would be to make this part of the LAllocation process, but in the mean time, we could have a table to reuse indexes which are encoding already encoded constant.

Note: As snapshots are frequents, and not likely to change a lot between instructions, this is frequent to find the same constants multiple times in successive snapshots.  The index could be attached as some kind of allocation-index on the MConstant structure.

This is a good first bug to discover IonMonkey's backend as well as the generic types of SpiderMonkey (js/public/* and mfbt/*).

Comment 1

[Romain Perier]

Attachment: IonMonkey: Snapshot's constant pool should reuse index of identical values

Comment 2

[Romain Perier]

See my proposal in attachment. Please give me more context if I did something wrong. As I a new comer in the project, this is not a completely trivial project and I might had missed something (that's why you're mentoring this bug ;D)

;)

Comment 3

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8384286 [details] [diff] [review]
IonMonkey: Snapshot's constant pool should reuse index of identical values

Review of attachment 8384286 [details] [diff] [review]:
-----------------------------------------------------------------

This looks like a good approach, I still have some questions.

::: js/src/jit/shared/CodeGenerator-shared.cpp
@@ +199,5 @@
>            case MIRType_Magic:
>            {
>              uint32_t index;
> +            Value v = MagicValue(JS_OPTIMIZED_ARGUMENTS);
> +            if (constantPoolMap::Ptr p = constantPoolMap_.lookup(v.asRawBits()))

use an AddPtr, such as you do not have to seek in the hash table twice.
Couldn't we just store the index on the MConstant, knowing that GVN already fold similar constants?

Also, why not adding this caching logic inside addConstantToPool?

Comment 4

[Romain Perier]

(In reply to Nicolas B. Pierron [:nbp] from comment #3)
> Comment on attachment 8384286 [details] [diff] [review]
> IonMonkey: Snapshot's constant pool should reuse index of identical values
> 
> use an AddPtr, such as you do not have to seek in the hash table twice.
Ok, looking

> Couldn't we just store the index on the MConstant, knowing that GVN already
> fold similar constants?

Yes but MagicValue does not return a MConstant... so... I mean, that's why I compute the mapping logic using a Value instead of saving the index into the MConstant.

> 
> Also, why not adding this caching logic inside addConstantToPool?
Yes, I had this idea this morning. The problem being that actually we have two copies of each Value in memory:  One into the constant pool (LIRGraph) and another one into this HashMap. Perhaps we could replace LIRGraph::contantPool_ by an HashMap (it is a Vector). In this case the caching logic would be inside addConstantToPool and we will save more memory. What do you think ?

Comment 5

[Nicolas B. Pierron [:nbp]]

(In reply to Romain Perier from comment #4)
> (In reply to Nicolas B. Pierron [:nbp] from comment #3)
> > Also, why not adding this caching logic inside addConstantToPool?
> Yes, I had this idea this morning. The problem being that actually we have
> two copies of each Value in memory:  One into the constant pool (LIRGraph)
> and another one into this HashMap. Perhaps we could replace
> LIRGraph::contantPool_ by an HashMap (it is a Vector). In this case the
> caching logic would be inside addConstantToPool and we will save more
> memory. What do you think ?

I think this would be a good idea, but you will have some issues to dump it to memory in copyConstants.
One way would be to wrap graph.addToConstantPool by adding a wrapper to the codeGen, unless we have a way to serialize the keys of the hash table in the right order?

Comment 6

[Romain Perier]

(In reply to Nicolas B. Pierron [:nbp] from comment #5)
> I think this would be a good idea, but you will have some issues to dump it
> to memory in copyConstants.
> One way would be to wrap graph.addToConstantPool by adding a wrapper to the
> codeGen, unless we have a way to serialize the keys of the hash table in the
> right order?

Ok, perhaps the wrapper might << "generate" >> the HashMap to a Value * before calling copyConstants from jit/CodeGenerator.cpp ? Or even better, as LIRGraph::constantPool() is only called from jit/CodeGenerator.cpp, LIRGraph::constantPool() might construct a Value * from the HashMap. Otherwises... we might use... an OrderedHashMap and try to serialize the keys from it, which would be in the right order ... ?

Comment 7

[Romain Perier]

LIRGraph::constantPool() might return a Range (to the internal OrderedHashMap), and copyConstant might iterate over this Range in order to serialize keys in the right order. The only problem is that OrderedHashMap is not public, so we should move it from builtin/MapObject.cpp to another public file.

Comment 8

[Nicolas B. Pierron [:nbp]]

(In reply to Romain Perier from comment #7)
> LIRGraph::constantPool() might return a Range (to the internal
> OrderedHashMap), and copyConstant might iterate over this Range in order to
> serialize keys in the right order. The only problem is that OrderedHashMap
> is not public, so we should move it from builtin/MapObject.cpp to another
> public file.

I don't think there is any advantage to take an OrderedHashMap in this case, using the value index of an HashMap would be enough.  Knowing that the number of unique allocations per compilation is low (see Bug 962555), I think we should go either for HashMap only, or the vector + hashmap.

Comment 9

[Romain Perier]

Attachment: IonMonkey: Snapshot's constant pool should reuse index of identical values

Comment 10

[Romain Perier]

Perhaps it would make sense to free the generated Vector after calling copyConstants, as this function seems to copy Values internally.

Comment 11

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8386079 [details] [diff] [review]
IonMonkey: Snapshot's constant pool should reuse index of identical values

Review of attachment 8386079 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/LIR.cpp
@@ +31,5 @@
>      entrySnapshot_(nullptr),
>      osrBlock_(nullptr),
>      mir_(*mir)
>  {
> +    constantPoolMap_.init();

Isn't init fallible?

We have to check the returned values and fail properly in case of OOM.
We should never fail in the constructor as constructor do not have any safe way to return a failure.  This is also the reason why most fallible initialization processes are separated into init functions.

@@ +38,5 @@
>  bool
>  LIRGraph::addConstantToPool(const Value &v, uint32_t *index)
>  {
> +    if (!constantPoolMap_.initialized())
> +        return false;

We should assert that the map is initialized.

::: js/src/jit/LIR.h
@@ +1475,4 @@
>      }
>      Value *constantPool() {
> +        JS_ASSERT(constantPoolCount_ > 0);
> +        JS_ASSERT(constantPool_.initCapacity(constantPoolCount_));

We cannot assert that we will never OOM.

@@ +1476,5 @@
>      Value *constantPool() {
> +        JS_ASSERT(constantPoolCount_ > 0);
> +        JS_ASSERT(constantPool_.initCapacity(constantPoolCount_));
> +        for (ConstantPoolMap::Range r = constantPoolMap_.all(); !r.empty(); r.popFront())
> +            constantPool_[r.front().value()] = r.front().key();

Why not initializing both at the same time in addConstantToPool?

Comment 12

[Romain Perier]

(In reply to Nicolas B. Pierron [:nbp] from comment #11)
> Comment on attachment 8386079 [details] [diff] [review]
> IonMonkey: Snapshot's constant pool should reuse index of identical values
> 
> Review of attachment 8386079 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/LIR.cpp
> @@ +31,5 @@
> >      entrySnapshot_(nullptr),
> >      osrBlock_(nullptr),
> >      mir_(*mir)
> >  {
> > +    constantPoolMap_.init();
> 
> Isn't init fallible?
> 
> We have to check the returned values and fail properly in case of OOM.
> We should never fail in the constructor as constructor do not have any safe
> way to return a failure.  This is also the reason why most fallible
> initialization processes are separated into init functions.
> 
Yeah, I know, I am not really fan about this part :/ . I will think about it.
> @@ +38,5 @@
> >  bool
> >  LIRGraph::addConstantToPool(const Value &v, uint32_t *index)
> >  {
> > +    if (!constantPoolMap_.initialized())
> > +        return false;
> 
> We should assert that the map is initialized.
ack
> 
> ::: js/src/jit/LIR.h
> @@ +1475,4 @@
> >      }
> >      Value *constantPool() {
> > +        JS_ASSERT(constantPoolCount_ > 0);
> > +        JS_ASSERT(constantPool_.initCapacity(constantPoolCount_));
> 
> We cannot assert that we will never OOM.
> 
> @@ +1476,5 @@
> >      Value *constantPool() {
> > +        JS_ASSERT(constantPoolCount_ > 0);
> > +        JS_ASSERT(constantPool_.initCapacity(constantPoolCount_));
> > +        for (ConstantPoolMap::Range r = constantPoolMap_.all(); !r.empty(); r.popFront())
> > +            constantPool_[r.front().value()] = r.front().key();
> 
> Why not initializing both at the same time in addConstantToPool?

Because it might take memory for nothing ? Ideally we should instanciate the vector from constantPool and then once it is copied from copyConstants, we should free it. What do you think ?

Comment 13

[Nicolas B. Pierron [:nbp]]

(In reply to Romain Perier from comment #12)
> (In reply to Nicolas B. Pierron [:nbp] from comment #11)
> > @@ +1476,5 @@
> > >      Value *constantPool() {
> > > +        JS_ASSERT(constantPoolCount_ > 0);
> > > +        JS_ASSERT(constantPool_.initCapacity(constantPoolCount_));
> > > +        for (ConstantPoolMap::Range r = constantPoolMap_.all(); !r.empty(); r.popFront())
> > > +            constantPool_[r.front().value()] = r.front().key();
> > 
> > Why not initializing both at the same time in addConstantToPool?
> 
> Because it might take memory for nothing ? Ideally we should instanciate the
> vector from constantPool and then once it is copied from copyConstants, we
> should free it. What do you think ?

IonAllocator is just stacking allocations and free all of them at once (see LifoAlloc).  So there is no proper way to free the memory unless we are using the SystemAllocator or you can guarantee that you know precisely what allocations are stacked.

Comment 14

[Romain Perier]

Attachment: IonMonkey: Snapshot's constant pool should reuse index of identical values

Comment 15

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8386696 [details] [diff] [review]
IonMonkey: Snapshot's constant pool should reuse index of identical values

Review of attachment 8386696 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/LIR.cpp
@@ +36,5 @@
>  bool
>  LIRGraph::addConstantToPool(const Value &v, uint32_t *index)
>  {
> +    JS_ASSERT(constantPoolMap_.initialized());
> +    if (ConstantPoolMap::Ptr p = constantPoolMap_.lookup(v)) {

see lookupForAdd

::: js/src/jit/shared/CodeGenerator-shared.cpp
@@ +258,5 @@
>      if (!mirOperandIter.init())
>          return false;
>  
> +    if (!graph.init())
> +        return false;

The init function should be called when we initialize the LIRGraph, not way later in the code generator.
Also, this encode function will be called multiple times, which is not desirable either.

Comment 16

[Romain Perier]

Attachment: IonMonkey: Snapshot's constant pool should reuse index of identical values

Comment 17

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8386841 [details] [diff] [review]
IonMonkey: Snapshot's constant pool should reuse index of identical values

Review of attachment 8386841 [details] [diff] [review]:
-----------------------------------------------------------------

This looks good!

Comment 18

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/0a0fcc54e630

Comment 19

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/0a0fcc54e630