581177 - Have 64 bits for nsINode flags

Status: RESOLVED FIXED

(Core :: General, defect, P1)

Description

[Markus Stange [:mstange]]

Attachment: v1

All 32 bits are taken, I need a new bit in bug 572689, and this seemed like the fastest of the three solutions bz proposed in bug 572689 comment 23.

This patch makes node flags similar to frame state flags which were made 64 bit in bug 570837 and bug 571211.

The cast here seems a little dangerous to me:

    nsSlots* newSlots = CreateSlots();
    if (newSlots) {
      mFlagsOrSlots = reinterpret_cast<nsNodeFlags>(newSlots);

In 32 bit builds, sizeof(newSlots) will be 4 and sizeof(nsNodeFlags) will be 8. Is this guaranteed to work anyway?

Comment 1

[Boris Zbarsky [:bzbarsky]]

If we're just looking for a quickfix, wouldn't separating flags and slots (which we want to do anyway) be better?  I guess not on 64-bit....

> In 32 bit builds, sizeof(newSlots) will be 4 and sizeof(nsNodeFlags) will be 8.
> Is this guaranteed to work anyway?

It should, yes.  I think.

Comment 2

[Boris Zbarsky [:bzbarsky]]

Then again, the worries about that make me think we really should separate slots from flags and be done.

Comment 3

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

While separating slots from flags seems like the quickest fix, and one that i'm fine with doing to unblock bug 572689, it's a very short term one. We'll undoubtedly run into the same problem in a matter of months, if not weeks, again.

I'm not super exited to use a PRUint64. Won't that result in more code at callsites for 32bit builds?

Alternatively we could have GetFlags and GetFlags2 that simply operate on two separate members.

Comment 4

[Boris Zbarsky [:bzbarsky]]

Or switch some things that are currently flags to just |bool x : 1| or |PRUint32 x : 1| members?  This would be especially easy for, say, the "is an element" flag, which no one really accesses via GetFlags/SetFlags other than nsGenericElement and its subclasses setting it initially....  That would have the same effect as using a PRUint64 memory-wise, but lead to better code for accessing the bits, right?

Comment 5

[Boris Zbarsky [:bzbarsky]]

fwiw, webkit uses bool:1 for this sort of thing.

Comment 6

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Yup, that sounds like a great idea. We should definitely check that bool:1 compiles to a compact bitfield on both recent GCCs and MSVCs though. Unless someone already has...

Comment 7

[Markus Stange [:mstange]]

(In reply to comment #4)
> Or switch some things that are currently flags to just |bool x : 1| or
> |PRUint32 x : 1| members?

Would you mind writing that patch? You seem to have a better understanding of what's necessary than I do.

Comment 8

[Markus Stange [:mstange]]

(In reply to comment #4)
> Or switch some things that are currently flags to just |bool x : 1| or
> |PRUint32 x : 1| members?

Can you make a list of these things? I can try to write the patch.

> That would have
> the same effect as using a PRUint64 memory-wise, but lead to better code for
> accessing the bits, right?

Wouldn't it use more memory in a 64 bit build, where the existing flags bitfield is already 64bits wide?

Comment 9

[Boris Zbarsky [:bzbarsky]]

> Can you make a list of these things?

Offhand, NODE_IS_ELEMENT and NODE_HAS_ID and NODE_MAY_HAVE_CLASS and NODE_MAY_HAVE_STYLE can go this way easily.

> Wouldn't it use more memory in a 64 bit build,

Ah, true.

Fwiw, I'm sorry on the lag responding to comment 7; I just hadn't found time to do that patch-writing yet.  :(

Comment 10

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Fwiw, I'm fine with using more memory in 64bit builds. We'll rejiggle this stuff soon enough anyway I'm sure

Comment 11

[Markus Stange [:mstange]]

(In reply to comment #6)
> We should definitely check that bool:1
> compiles to a compact bitfield on both recent GCCs and MSVCs though. Unless
> someone already has...

I've checked GCC 4.2.1 on Mac OS 10.6, it works there.

(In reply to comment #9)
> > Can you make a list of these things?
> 
> Offhand, NODE_IS_ELEMENT and NODE_HAS_ID and NODE_MAY_HAVE_CLASS and
> NODE_MAY_HAVE_STYLE can go this way easily.

Actually, is there a reason to convert those now? I could just add the new flag I need in bug 572689 as bool mNodeMayHaveRenderingObservers : 1; without touching existing flags. That would unblock -moz-element from this bug.

Comment 12

[Boris Zbarsky [:bzbarsky]]

That sounds just fine.  Go for it!

Comment 13

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

jseward's hot field profiler pointed out that, on 64-bit, the current solution bloats nsINode by 64 bits when we actually have all the bits we need already (since the flags are a union with a pointer).

Comment 14

[Markus Stange [:mstange]]

(In reply to comment #13)
> jseward's hot field profiler pointed out that, on 64-bit, the current solution
> bloats nsINode by 64 bits

What causes this? The fact that nsIContent starts with a 64 bit member variable (the primary frame pointer) which needs to be aligned to the next 64 bit multiple?

Comment 15

[Boris Zbarsky [:bzbarsky]]

Yes, exactly.

I'll take this and see what I can do.

Comment 16

[Boris Zbarsky [:bzbarsky]]

Attachment: Test program to test packing

The results I get from this program:

gcc 32-bit (mac+linux): 4  8  8 12 12 12
gcc 64-bit (mac+linux): 8 16 16 16 16 16
MSVC 32-bit:            4 12  8 12 12 12
MSVC 64-bit:            8 16 16 16 16 16

So in other words, bool:1 will pack with itself fine on both, but going from unsigned int to bool aligns to a 4-byte boundary on MSVC.

Comment 17

[Boris Zbarsky [:bzbarsky]]

So I started doing the bool thing, then happened to look at the webkit code and realized that they have in the meantime switched to an unsigned int flag word, as part of a checkin to improve performance.  See http://trac.webkit.org/changeset/58914

So I went and looked at what code gcc generates for a getter that returns bool for two cases: boolean bitfield members and an unsigned int member with explicit mask.

For the former case, you get code like this for accessing bit 14; the bitfield is in 4(%rdi):

	movzbl	5(%rdi), %eax
	shrb	$6, %al
	andl	$1, %eax

For the latter case, you get code like this for accessing bit 14; the int is in 0(%rdi):

	movl	(%rdi), %edx
	shrl	$14, %edx
	andl	$1, %edx

Which _seems_ like a wash to me, if the movzbl is just as fast as the movl.  Which is a bit of an if.

I also looked at initialization (which the webkit folks explicitly mention in the checkin comment there).  If I'm initializing two bits (bit 0 and bit 10), then the code for the boolean bitfield looks like this (with the pointer to the object whose members these things are in %rax):

	movb	$1, 4(%rax)
	movzbl	5(%rax), %edx
	andl	$-128, %edx
	orl	$4, %edx
	movb	%dl, 5(%rax)

The corresponding code for the unsigned int is:

	movl	$1025, (%rax)

So indeed initialization is faster for an integer member.  That's 64-bit code all along; 32-bit equivalents coming up.

Comment 18

[Boris Zbarsky [:bzbarsky]]

For 32-bit, access to boolean bitfield bit 14 looks like this (bitfield is in 4(%ecx)): 

	movl	4(%ecx), %eax
	shrl	$14, %eax
	andl	$1, %eax

while the bit 14 access for the unsigned int (which is in (%ecx)) looks like this:

	movl	(%ecx), %edx
	shrl	$14, %edx
	andl	$1, %edx

One difference is that for the int the move into %edx actually happened up front and then was reused for both bit accesses in my test, whereas for the bitfield the dereference of %ecx happened before each bit access.

For initialization of the boolean bitfield we have (object pointer lives in %eax):

	movl	4(%eax), %edx
	andl	$-32768, %edx
	orl	$1025, %edx
	movl	%edx, 4(%eax)

while for the int the initialization is:

	movl	$1025, (%eax)

I did check, and reordering the members didn't change this behavior.

So conclusions....  Codegen for accessing the int seems to be more consistent across 32 and 64-bit, and most likely better than code for accessing the bool bitfield.  Initializing the bool bitfield is _definitely_ worse than initializing an int.  I'll attach my test file in a sec.

Comment 19

[Boris Zbarsky [:bzbarsky]]

Attachment: Test for bool bitfield codegen

Comment 20

[Boris Zbarsky [:bzbarsky]]

I just tested, and the codegen for the bitfield is the same if I use |unsigned int| instead of bool.  So it looks like just having a bitfield makes gcc do byte-by-byte operations.  Given that, I think we should simply have two 32-bit flag words; one for arbitrary flags and one for boolean flags only; effectively the last paragraph of comment 3.  I'll write that patch series tomorrow.

Comment 21

[Boris Zbarsky [:bzbarsky]]

Oh, and all that was with gcc 4.2 on Mac.  I also looked at 4.4 on Linux; some of the register allocation details differ and it's trickier about instruction ordering, but the overall picture is the same: bitfield initialization is slow and byte by byte; reading from a bitfield involves byte ops.

Comment 22

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Using bit fields produces a whole lot more readable code though :(

It seems like initialization was the only part that was meaningfully different. Aren't we attempting to construct nodes rarely enough that this won't matter anyway. I would expect malloc costs etc to be >> the cost of initializing these fields.

Comment 23

[Boris Zbarsky [:bzbarsky]]

Talked to sicking a bit, and I think I'm sticking with the two-field plan for now, but abstracting it away enough that we can switch as desired.

Patch series coming up that frees up 6 bits in the old flag word and leaves space for 24 more boolean flags.  I only moved over boolean flags that were not set or tested for in conjunction with other flags and whose setters could be protected.

Comment 24

[Boris Zbarsky [:bzbarsky]]

Attachment: part 1. Separate mFlags and mSlots into separate members. Stop storing flags in slots.

Comment 25

[Boris Zbarsky [:bzbarsky]]

Attachment: part 2. Separate mParent from the flags it used to cohabit with.

Comment 26

[Boris Zbarsky [:bzbarsky]]

Attachment: part 3. Make IsElement() use a boolean flag.

Comment 27

[Boris Zbarsky [:bzbarsky]]

Attachment: part 4. Make 'has id' into a boolean flag.

Comment 28

[Boris Zbarsky [:bzbarsky]]

Attachment: part 5. Make 'may have style' into a boolean flag.

Comment 29

[Boris Zbarsky [:bzbarsky]]

Attachment: part 6. Make 'has name' into a boolean flag.

Comment 30

[Boris Zbarsky [:bzbarsky]]

Attachment: part 7. Make 'may have contenteditable attr' into a boolean flag.

Comment 31

[Boris Zbarsky [:bzbarsky]]

Attachment: part 8. Compress the flags so it's clear what's free.

Comment 32

[(no longer active)]

I just remembered that I think we should include clang/llvm in the compiler tests performed here.  The good part is that we have someone to fix clang for us if it can't generate good code for us.  :-)

Comment 33

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

Attachment: Test program with out of line methods

This is a modified version of the test program with the methods out of line to make them easy to compare individually.

Comment 34

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

Attachment: Relevant bits produced by gcc

Comment 35

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

Attachment: relevant bits produced by llvm

Comment 36

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

Interesting things to note:

* LLVM produces the same code for direct bit access and mask.
* I think the llvm code is as good as gcc, except for the method three where it avoids a setne.
* In the combined case gcc does a really smart job at reusing the al register.

Comment 37

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Comment on attachment 523223 [details] [diff] [review]
part 1.  Separate mFlags and mSlots into separate members.  Stop storing flags in slots.

>diff --git a/content/xul/content/src/nsXULElement.cpp b/content/xul/content/src/nsXULElement.cpp
>@@ -1,8 +1,9 @@
>+
> /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
>  *
>  * ***** BEGIN LICENSE BLOCK *****
>  * Version: MPL 1.1/GPL 2.0/LGPL 2.1

Revert this. r=me with that.

Comment 38

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Comment on attachment 523226 [details] [diff] [review]
part 2.  Separate mParent from the flags it used to cohabit with.

>diff --git a/content/base/public/nsIContent.h b/content/base/public/nsIContent.h
>+inline nsIContent*
>+nsINode::GetParent() const
>+{
>+  return NS_LIKELY(GetBoolFlag(ParentIsContent)) ?
>+         static_cast<nsIContent*>(mParent) :
>+         nsnull;
>+}

Why this change? It seems useful to be able to call GetParent and forward the returned pointer to somewhere without having to include nsIContent.h. You should be able to keep the old reinterpret_cast.

r=me with that changed back.

Comment 39

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Comment on attachment 523232 [details] [diff] [review]
part 8.  Compress the flags so it's clear what's free.

But why didn't you do the "may have class" flag as well? Or a large number of the other ones for that matter?

Comment 40

[Boris Zbarsky [:bzbarsky]]

> Revert this.

Done.

> Why this change?

It seemed cleaner, but if you think that there are use cases for not including nsIContent, sure.  I'll revert that.

> But why didn't you do the "may have class" flag as well?

I generally converted, for now, the flags that had the following properties:

1)  Only gotten or set in isolation, not with other flags.
2)  Only needed a protected setter.

"may have class" is set from nsSVGClass, so failed the second test for the moment.

Comment 41

[Boris Zbarsky [:bzbarsky]]

http://hg.mozilla.org/mozilla-central/rev/b7c8a433b9e5
http://hg.mozilla.org/mozilla-central/rev/9ac889e59c24
http://hg.mozilla.org/mozilla-central/rev/c516d83c8519
http://hg.mozilla.org/mozilla-central/rev/45eb833bbc84
http://hg.mozilla.org/mozilla-central/rev/bb540a56e9ee
http://hg.mozilla.org/mozilla-central/rev/f4a7ad868b50
http://hg.mozilla.org/mozilla-central/rev/b8ec52d26284
http://hg.mozilla.org/mozilla-central/rev/2d69df8b61dc

Comment 42

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

(In reply to comment #40)
> > Why this change?
> 
> It seemed cleaner, but if you think that there are use cases for not including
> nsIContent, sure.  I'll revert that.

You forgot to remove

+   * Implemented in nsIContent.h

Comment 43

[Boris Zbarsky [:bzbarsky]]

Good catch.  I pushed http://hg.mozilla.org/mozilla-central/rev/27d6a4a5e20f to do that and also to rev the nsINode and nsIContent IIDs (something I'd been sure I did in the patches above, but apparently forgot).