Closed Bug 937540 Opened 11 years ago Closed 10 years ago

Use placement new syntax for JIT temporary memory allocations

Categories

(Core :: JavaScript Engine: JIT, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla28
Tracking Status
firefox28 --- fixed

People

(Reporter: jandem, Assigned: jandem)

References

(Blocks 1 open bug)

Details

(Whiteboard: [qa-])

Attachments

(12 files, 1 obsolete file)

22.10 KB, patch
jandem
: review+
Details | Diff | Splinter Review
6.46 KB, patch
sstangl
: review+
Details | Diff | Splinter Review
3.85 KB, patch
mjrosenb
: review+
Details | Diff | Splinter Review
4.38 KB, patch
djvj
: review+
Details | Diff | Splinter Review
499.03 KB, patch
bhackett1024
: review+
Details | Diff | Splinter Review
93.64 KB, patch
luke
: review+
Details | Diff | Splinter Review
1.46 KB, patch
terrence
: review+
Details | Diff | Splinter Review
98.80 KB, patch
nbp
: review+
Details | Diff | Splinter Review
10.57 KB, patch
bhackett1024
: review+
Details | Diff | Splinter Review
219.50 KB, patch
luke
: review+
Details | Diff | Splinter Review
7.81 KB, patch
luke
: review+
Details | Diff | Splinter Review
3.04 KB, patch
Details | Diff | Splinter Review
The idea is to explicitly pass a TempAllocator pointer to avoid slow GetIonContext() calls, see bug 937287.

I'm attaching a patch that adds an extra |operator new| and uses it for the regalloc allocations.

Luke, I don't know if |operator new| should take a pointer or a reference to TempAllocator. If we use a reference, we could accidentally call the overload that takes a |void *pos| if somebody passes a pointer instead of a reference, so this patch uses a pointer. Any thoughts?
Attachment #830718 - Flags: review?(luke)
Comment on attachment 830718 [details] [diff] [review]
Part 1 - Add operator new, use for regalloc allocations

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

Re: TempAlloc* vs. TempAlloc&: good thought!  I'm a bit rusty on my type rules for operator new, but from my quick experimentation, if you have:

TempAlloc alloc;

// global
void *operator new(size_t size, void *mem) { return mem; }

class A {
  void *operator new(size_t size, TempAlloc &) { ... }
};

and you try to call

new(&alloc) A();

you'll get a type error because the class-level operator new shadows the global operator new.

Given that, TempAlloc& doesn't seem harmful.  In fact, TempAlloc* could be more harmful: let's say you call new(alloc()) A() (where alloc() returns a TempAlloc*) and A doesn't derive TempObject: that will compile using global placement new whereas if alloc() returned a TempAlloc&, it'd be a type error, which is what you'd expect.
Attachment #830718 - Flags: review?(luke) → review+
(In reply to Luke Wagner [:luke] from comment #1)
> you'll get a type error because the class-level operator new shadows the
> global operator new.

But it's not the global operator new, it's this other guy in TempObject:

    inline void *operator new(size_t nbytes, void *pos) {
        return pos;
    }

Vector uses it I think... Before I wrote comment 0 I tried this and it did crash. Could we use template magic for that "void *pos" or is that overkill?

I just want to make sure this |operator new| is the best we can do before 2163 lines of code depend on it :)
Flags: needinfo?(luke)
(In reply to Luke Wagner [:luke] from comment #1)
> In fact, TempAlloc* could be
> more harmful: let's say you call new(alloc()) A() (where alloc() returns a
> TempAlloc*) and A doesn't derive TempObject: that will compile using global
> placement new whereas if alloc() returned a TempAlloc&, it'd be a type
> error, which is what you'd expect.

Good argument btw. Atm we have the same problem with "new A()" using the standard operator new (== memory leaks) if you forget to inherit from TempObject, would be great to prevent these problems.
(In reply to Jan de Mooij [:jandem] from comment #2)
Ohhh, I see.  So we have some TempObjects that get Vector-allocated and thus they do really want placement-new.

I *was* about to suggest just adding an overload to TempObject:

inline void *operator new(size_t nbytes, TempAllocator *pos);  // intentionally undefined

but then I realized we could *change* the existing void*-taking operator new to instead be:

inline void *operator new(size_t nbytes, T *pos) {
    return pos;
}

because Vector<T> always passes a T*.  This change is nice because it will catch a whole range of accidental arguments to placement 'new'.
(In reply to Jan de Mooij [:jandem] from comment #3)
> Atm we have the same problem with "new A()" using the
> standard operator new (== memory leaks) if you forget to inherit from
> TempObject, would be great to prevent these problems.

Well, then the move to an explicit alloc() argument (once everyone gets used to always writing 'new (alloc()) T()' should catch those errors since non-TempObject classes will produce an error.

Furthermore, we can add:

 private:
   void *operator new(size_t nbytes);  // intentionally left undefined

to TempObject to catch accidental 'new T()'.
Flags: needinfo?(luke)
Blocks: 935929
This changes the existing placement new operator's argument from void* to TempObject*, and the one I added now wants a TempAllocator &.

(In reply to Luke Wagner [:luke] from comment #5)
> Furthermore, we can add:
> 
>  private:
>    void *operator new(size_t nbytes);  // intentionally left undefined
> 
> to TempObject to catch accidental 'new T()'.

Good idea, I'll do this after moving everything to placement new.
Attachment #830718 - Attachment is obsolete: true
Attachment #831063 - Flags: review+
Also removes an explicit GetIonContext call from BitSet::init.
Attachment #831071 - Flags: review?(sstangl)
Use placement new for ValueNumberData allocations.
Attachment #831079 - Flags: review?(mrosenberg)
Also removes an unused MUse::New method.

(There aren't that many classes inheriting from TempObject. The main ones are MIR-instructions, LIR-instructions and Range; patches for these tomorrow.)
Attachment #831095 - Flags: review?(kvijayan)
Brian, this is a huge patch (500K or so) but it's mostly mechanical changes.
Attachment #831467 - Flags: review?(bhackett1024)
Attachment #831467 - Flags: review?(bhackett1024) → review+
This patch gives IonAllocPolicy a constructor that takes a TempAllocator& and uses it instead of calling GetIonContext(). This means a ton of Vectors now have to be initialized explicitly, but most of these turned out to be pretty straight-forward.

This is the last patch for now; will continue once these patches are in.
Attachment #831734 - Flags: review?(luke)
Attachment #831734 - Flags: review?(luke) → review+
Attachment #831095 - Flags: review?(kvijayan) → review+
I pushed the first 4 patches to Try, and everything is fine on Linux and OS X, but Windows is as orange as it can be. After some debugging, I think the problem is the change from:

    void *operator new(size_t nbytes, void *pos) { return pos; }

to 

    void *operator new(size_t nbytes, TempObject *pos) { return pos; }

It looks like MSVC is passing us a different (aligned?) pointer now :( This sucks because changing it back to void* loses type safety again: somebody could pass a TempAllocator* instead of TempAllocator& and end up in that constructor. I will see if there's a way to make this work somehow.
Maybe use #ifdef XP_WIN, so you still get compilation errors on other platforms?
Attachment #831079 - Flags: review?(mrosenberg) → review+
Attachment #831071 - Flags: review?(sstangl) → review+
The problem was that we were passing a Derived* to placement new and |operator new| expected a Base* (TempObject*), so in case of multiple inheritance the compiler can pass a different pointer.

This is the fix you suggested yesterday, it templatizes operator new, then static_asserts it's a valid type. I double checked and the static_assert fails when passing a TempAllocator* instead of TempAllocator&.

Will fold this into part 1.
Attachment #832880 - Flags: review?(luke)
Comment on attachment 832880 [details] [diff] [review]
Part 1b - Fix Windows orange

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

Pretty straightforward. Stealing review to get this moving before it needs a rebase.
Attachment #832880 - Flags: review?(luke) → review+
Part 5:

https://hg.mozilla.org/integration/mozilla-inbound/rev/1fe0f523e644
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Whiteboard: [leave open]
This class adds a temporary OldTempObject class, and moves the "operator new" that calls GetIonContext() to that class. This way, we can convert one class at a time from OldTempObject to TempObject and then we can remove it again. This caught some places where I forgot to use placement new for MIR instructions. 

It also makes Range allocation use placement new. This adds some boilerplate but is much faster than calling GetIonContext().

Only 3 classes left so we're getting there.
Attachment #8340075 - Flags: review?(nicolas.b.pierron)
(In reply to Jan de Mooij [:jandem] from comment #22)
> This class adds a ...

Er, this /patch/ :)
Comment on attachment 8340075 [details] [diff] [review]
Part 7 - Range analysis + some other classes

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

::: js/src/jit/RangeAnalysis.cpp
@@ +2000,5 @@
>  
>          for (MDefinitionIterator iter(block); iter; iter++) {
>              MDefinition *def = *iter;
>  
> +            def->computeRange(alloc());

Having to give this TempAllocator to every operation is really hard to read.
I think we can work around that in 3 way, the first one only prevent writing Range::New…(alloc, …), and the second solution prevent giving any alloc with a little write overhead, the third one just store the TempAllocator as part of the graph.

(1) Currently we have code such as

  Range::NewDoubleRange(alloc, 0.0, 1.0)

In such case we will always allocate a Range with some special initialization, but such initialization is not fallible, so if we add some inheritance, we can obtain:

  struct DoubleRange: public Range { … };

  new(alloc) DoubleRange(0.0, 1.0)

Which would definitely look nicer.

And for MIR constructors, we can do another trick where we call an init function which will unwind the LifoAlloc 

class MMyMir {
  MMyMir *init(TempAlloc &alloc) {
    …
    if (…) {
      // unwind up to this allocation
      alloc.unwind(this);
      return nullptr;
    }

    return this;
  }
};

  MMyMir *ins = new(alloc) MMyMir(… …)
              ->init(alloc);

(2) This other solution is more about Range Analysis special case.  The computeRange function is only allocating a Range for the current MIR Instruction.  So it will always allocate only one Range class.  As it will only allocate one, instead of changing the prototype of every function to include the TempAllocator, we can just eagerly set a full Range with the setRange function, and reset the Range to nullptr if it is indeed no used.  In which case the code above would become:

  def->setRange(tmp);
  def->computeRange();
  if (def->range())
    tmp = new(alloc()) Range();

And the last Range can be removed at the end of the computeRange function.

(3) Another, would be to avoid adding this TempAllocator at every location on the stack, but only where it is needed, and recover it from the basic block / graph.

Within a computeRange function, one might access its own block and get its own graph from which we can collect the TempAllocator.

  setRange(new (block()->graph()->alloc()) Range(…))

of course this can be hidden with an accessor:

  setRange(new(alloc()) Range(…))


What do you think?
Attachment #8340075 - Flags: review?(nicolas.b.pierron)
Comment on attachment 8340075 [details] [diff] [review]
Part 7 - Range analysis + some other classes

Unfortunately, as we discussed on IRC, using a subclass for DoubleRange doesn't work because NewDoubleRange atm can also return nullptr. So I'm resetting the review flag :)
Attachment #8340075 - Flags: review?(nicolas.b.pierron)
Attachment #8340075 - Flags: review?(nicolas.b.pierron) → review+
Comment on attachment 8340075 [details] [diff] [review]
Part 7 - Range analysis + some other classes

Just to comment, I personally hate this patch even if the intention is good, but the limiting factor for having a lightweight syntax is the C++ here.

I want us to investigate more if there is any clean way to get read of all the TempAllocator.  As discuss on IRC, these TempAllocator should at least be renamed to something smaller such as JitContext (I do not recommend not JitAlloc, because I think many other places in the code might want to take advantage of this one common argument)
Attachment #8342536 - Flags: review?(bhackett1024)
Attachment #8342536 - Flags: review?(bhackett1024) → review+
https://hg.mozilla.org/integration/mozilla-inbound/rev/efaee7511571

(In reply to Nicolas B. Pierron [:nbp] from comment #26)
> As discuss on IRC, these TempAllocator should at least
> be renamed to something smaller such as JitContext (I do not recommend not
> JitAlloc, because I think many other places in the code might want to take
> advantage of this one common argument)

IonContext/JitContext is already in use, I'm not sure about passing that class instead of the allocator. We could easily shorten it from TempAllocator to TempAlloc though, I can do that after posting/landing the last patches here.
This is the last big patch. The only remaining OldTempObject we need to convert to TempObject is PendingMove - that one can be fixed in a small patch because there are only a few uses but it's a bit complicated so I'll do that one separately.
Attachment #8343206 - Flags: review?(luke)
Comment on attachment 8343206 [details] [diff] [review]
Part 9 - LIR instructions, OOL code

That's a lotta alloc()
Attachment #8343206 - Flags: review?(luke) → review+
The last TempObject class.
Attachment #8343695 - Flags: review?(luke)
This patch reverts to the old behavior (using GetIonContext()->temp) so that we can measure the impact of the patches in this bug. It's not entirely accurate because we still pass an extra argument around in some places (though the compiler can probably get rid of that in many cases), but since the patches landed incrementally it's the best we can do I think.

For the asmjs-apps benchmarks on OS X, 32-bit shell I get the following compilation times in ms:

box2d before: 123 123 126 126 126 (avg: 124.8)
box2d after:  113 114 115 118 113 (avg: 114.6, 8.2% faster)

bullet before: 408 407 406 407 410 (avg: 407.6)
bullet after:  365 368 368 366 366 (avg: 366.6, 10.1% faster)

lua_binarytrees before: 339 340 341 339 340 (avg: 339.8)
lua_binarytrees after:  302 304 303 305 311 (avg: 305.0, 10.2% faster)

zlib before: 119 118 119 118 121 (avg: 119)
zlib after:  112 111 111 112 112 (avg: 111.6, 6.2% faster)

So it seems to be a 6-10% win in compilation time. Improvement is biggest on the larger benchmarks.

On Octane-TypeScript, a profile shows that PR_GetThreadPrivate self time decreased from 85 ms (2nd place) to 12 ms. The remaining 12 ms is from other GetIonContext() calls, most of these should be easy to eliminate as well.
Comment on attachment 8343695 [details] [diff] [review]
Part 10 - PendingMove

ooc, could the TempAllocator be taken out of GetIonContext() or are there still a lot of scattered uses?
Attachment #8343695 - Flags: review?(luke) → review+
And part 10:

https://hg.mozilla.org/integration/mozilla-inbound/rev/2f8a83944e71

I think that's enough for this bug. TempObject and IonAllocPolicy no longer call GetIonContext().

(In reply to Luke Wagner [:luke] from comment #37)
> ooc, could the TempAllocator be taken out of GetIonContext() or are there
> still a lot of scattered uses?

There are still a number of uses unfortunately. Not that many though; I will post a patch for that next week.
Whiteboard: [leave open]
https://hg.mozilla.org/mozilla-central/rev/2f8a83944e71
Status: REOPENED → RESOLVED
Closed: 11 years ago10 years ago
Resolution: --- → FIXED
Whiteboard: [qa-]
You need to log in before you can comment on or make changes to this bug.