Bug 88528 – Reduce Node object size from 72 byte to 64 byte

• Component: DOM
• Status: RESOLVED FIXED

[Kentaro Hara]

By removing all virtual methods from TreeShared.h, we can remove a virtual method table (8 byte) from each Node object. Consequently, we can reduce each Node object size from 72 byte to 64 byte.

[Kentaro Hara]

Created attachment 146267 [details]
Patch

[Build Bot]

Comment on attachment 146267 [details]
Patch

Attachment 146267 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/12919165

[Build Bot]

Comment on attachment 146267 [details]
Patch

Attachment 146267 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12923053

[Ryosuke Niwa]

Comment on attachment 146267 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=146267&action=review

I don't think this patch buy us any real memory saving.

> Source/WebCore/ChangeLog:14
> +        e.g. The HTML spec (http://www.whatwg.org/specs/web-apps/current-work/)
> +        contains 325640 Nodes. Thus this patch saves 325640 * 8 byte = 2.6 MB.

I don't think this is true. Most of these nodes are Element and CharacterData and they have virtual functions.
So you will have a vtable pointer in those objects anyway.

[Alexey Proskuryakov]

> By removing all virtual methods from TreeShared.h, we can remove a virtual method table (8 byte) from each Node object.

Why are you saying that the table [pointer] would be removed? Node would still have virtual functions of its own. The size taken in each object does not depend on the number of classes with virtual method tables in inheritance chain (ignoring virtual inheritance for simplicity).

[Kentaro Hara]

(In reply to comment #5)
> > By removing all virtual methods from TreeShared.h, we can remove a virtual method table (8 byte) from each Node object.
> 
> Why are you saying that the table [pointer] would be removed? Node would still have virtual functions of its own. The size taken in each object does not depend on the number of classes with virtual method tables in inheritance chain (ignoring virtual inheritance for simplicity).

Oops... that's correct.

[Kentaro Hara]

ap, rniwa: The change saves memory. I confirmed that the patch reduces sizeof(Element) from 104 byte to 96 byte.

> Why are you saying that the table [pointer] would be removed? Node would still have virtual functions of its own. The size taken in each object does not depend on the number of classes with virtual method tables in inheritance chain (ignoring virtual inheritance for simplicity).

It is not true for multiple inheritance. Assuming 'class A : public B, C {};' where B and C have virtual methods, two virtual method table pointers are allocated for each A object. 

Simplified example:

#include <iostream>
using namespace std;

class EventTarget {
  virtual int f1() { }
};

template<typename T>
class TreeShared {
  // Comment out f2(), then sizeof(Element) is reduced from 16 byte to 8 byte.
  virtual int f2() { }
};

class Node : public EventTarget, TreeShared<Node> {
  virtual int f3() { }
};

class Element : public Node {
  virtual int f4() { }
};

int main(void)
{
  Element e;
  cout << sizeof(Element) << endl;
  cout << sizeof(e) << endl;
  return 0;
}

[Ryosuke Niwa]

(In reply to comment #7)
> ap, rniwa: The change saves memory. I confirmed that the patch reduces sizeof(Element) from 104 byte to 96 byte.
> 
> > Why are you saying that the table [pointer] would be removed? Node would still have virtual functions of its own. The size taken in each object does not depend on the number of classes with virtual method tables in inheritance chain (ignoring virtual inheritance for simplicity).
> 
> It is not true for multiple inheritance. Assuming 'class A : public B, C {};' where B and C have virtual methods, two virtual method table pointers are allocated for each A object. 

Ah,that's a good point. Thanks for the clarification. It might be worth noting that in th change log given that both ap and I didn't realize it.

[Kentaro Hara]

Created attachment 146433 [details]
Patch

[Kentaro Hara]

(In reply to comment #8)
> Ah,that's a good point. Thanks for the clarification. It might be worth noting that in th change log given that both ap and I didn't realize it.

Done.

Also added missing symbols.

[Kentaro Hara]

Created attachment 146436 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 146436 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=146436&action=review

> Source/WebCore/ChangeLog:26
> +        - Node and SVGElementInstance are the only classes that inherit TreeShared.

Can we add an assertion or make it impossible to inherit in other classses?
I think we can ensure that T has removeLastRef.

[Ryosuke Niwa]

Namely, you can add a private function in TreeShared that calls removeLastRef, which we never call.

+our clang guru.

[Kentaro Hara]

Created attachment 146439 [details]
Patch

[Kentaro Hara]

(In reply to comment #13)
> Namely, you can add a private function in TreeShared that calls removeLastRef, which we never call.

Good idea. Done.

[Ryosuke Niwa]

Comment on attachment 146439 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=146439&action=review

> Source/WebCore/platform/TreeShared.h:44
> +void callRemovedLastRef(TreeShared<SVGElementInstance>*);

This isn't what I had in my mind. You can just add a dummy function that's never called.
And in that dummy function, you call removeLastRef.
Come to think of it, we don't even have to remove this function.
We can just devirtualize & rename it to something else.

Maybe darin or andersca have a better idea. Basically we need some sort of traits-like construction here.

[Kentaro Hara]

(In reply to comment #16)
> > +void callRemovedLastRef(TreeShared<SVGElementInstance>*);
> 
> This isn't what I had in my mind. You can just add a dummy function that's never called.
> And in that dummy function, you call removeLastRef.
> Come to think of it, we don't even have to remove this function.
> We can just devirtualize & rename it to something else.

What do you mean specifically?

Nit: removedLastRef() might be renamed to lastRefRemoved().

> Basically we need some sort of traits-like construction here.

Plausible. But it might make the code a bit unreadable:)

[Ryosuke Niwa]

Let me get back to you wih a piece of code in an hour or two. My MBP died yesterday, and I just get it replaced.

[Build Bot]

Comment on attachment 146439 [details]
Patch

Attachment 146439 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/12913395

[Kentaro Hara]

Created attachment 146455 [details]
Fixed mac build failure

[Ryosuke Niwa]

So the problem comes down to the fact Node inherits from TreeShared<ContainerNode>. Because of this, we can't do static_cast<T*>(this) in TreeShared<T>::deref.

Does anyone know why we do this?

[Ryosuke Niwa]

Comment on attachment 146455 [details]
Fixed mac build failure

We had a length discussion with andersca & hareken about this but we concluded that it's probably okay to land the patch as is. We can always do a follow up cleanup when someone more familiar with C++ (andersca, darin, eseidel, othermaciej, etc...) comes up with a better solution. For now, let us enjoy 4/8-byte memory savings on all DOM nodes.

[WebKit Review Bot]

Comment on attachment 146455 [details]
Fixed mac build failure

Clearing flags on attachment: 146455

Committed r119802: <http://trac.webkit.org/changeset/119802>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Ojan Vafai]

FYI, looks like this hits an assert in debug: http://build.chromium.org/p/chromium.webkit/builders/Webkit%20Linux%20%28dbg%29/builds/7753/steps/webkit_tests/logs/stdio

STDERR: 	base::debug::StackTrace::StackTrace() [0x877fda]
STDERR: 	base::(anonymous namespace)::StackDumpSignalHandler() [0x838091]
STDERR: 	0x7f756d040af0
STDERR: 	WebCore::Document::removedLastRef() [0x6dce7c]
STDERR: 	WebCore::callRemovedLastRef() [0x6c67ce]
STDERR: 	WebCore::TreeShared<>::deref() [0x49b14b]
STDERR: 	WebCore::DOMDataStore::weakNodeCallback() [0x17c41a1]
STDERR: 	v8::internal::GlobalHandles::Node::PostGarbageCollectionProcessing() [0xbb637c]

[Ryosuke Niwa]

(In reply to comment #25)
> FYI, looks like this hits an assert in debug: http://build.chromium.org/p/chromium.webkit/builders/Webkit%20Linux%20%28dbg%29/builds/7753/steps/webkit_tests/logs/stdio
> 
> STDERR:     base::debug::StackTrace::StackTrace() [0x877fda]
> STDERR:     base::(anonymous namespace)::StackDumpSignalHandler() [0x838091]
> STDERR:     0x7f756d040af0
> STDERR:     WebCore::Document::removedLastRef() [0x6dce7c]
> STDERR:     WebCore::callRemovedLastRef() [0x6c67ce]
> STDERR:     WebCore::TreeShared<>::deref() [0x49b14b]
> STDERR:     WebCore::DOMDataStore::weakNodeCallback() [0x17c41a1]
> STDERR:     v8::internal::GlobalHandles::Node::PostGarbageCollectionProcessing() [0xbb637c]

Thanks for letting us know. Fixed in http://trac.webkit.org/changeset/119803.

[Sudarsana Nagineni (babu)]

This still hits an assert on debug build.

#0  0x00007f73a38b5600 in WebCore::Document::guardRef (this=0x22f00f0) at /build/WebKit/Source/WebCore/dom/Document.h:250
250	        ASSERT(!m_deletionHasBegun);
(gdb) bt
#0  0x00007f73a38b5600 in WebCore::Document::guardRef (this=0x22f00f0) at /build/WebKit/Source/WebCore/dom/Document.h:250
#1  0x00007f73a38de59a in WebCore::Document::removedLastRef (this=0x22f00f0) at /build/WebKit/Source/WebCore/dom/Document.cpp:649
#2  0x00007f73a38c7c4c in WebCore::callRemovedLastRef (self=0x22f0100) at /build/WebKit/Source/WebCore/dom/ContainerNode.cpp:91
#3  0x000000000048fe51 in WebCore::TreeShared<WebCore::ContainerNode>::deref (this=0x22f0100) at /build/WebKit/Source/WebCore/platform/TreeShared.h:94
#4  0x000000000049f9fb in WTF::derefIfNotNull<WebCore::Document> (ptr=0x22f00f0) at /build/WebKit/Source/WTF/wtf/PassRefPtr.h:52
#5  0x00007f73a3935934 in WTF::RefPtr<WebCore::Document>::operator= (this=0x22bdd60, o=...) at /build/WebKit/Source/WTF/wtf/RefPtr.h:134
#6  0x00007f73a3d60e60 in WebCore::Frame::setDocument (this=0x22bd880, newDoc=...) at /build/WebKit/Source/WebCore/page/Frame.cpp:299
#7  0x00007f73a3c82c2f in WebCore::FrameLoader::clear (this=0x22bd918, clearWindowProperties=false, clearScriptObjects=false, clearFrameView=true)
    at /build/WebKit/Source/WebCore/loader/FrameLoader.cpp:536
#8  0x00007f73a3c75df5 in WebCore::DocumentWriter::begin (this=0x23d8ca0, urlReference=..., dispatch=false, ownerDocument=0x0) at /build/WebKit/Source/WebCore/loader/DocumentWriter.cpp:129
#9  0x00007f73a3c688e3 in WebCore::DocumentLoader::commitData (this=0x23d8be0, bytes=
    0x23bcb70 "<!DOCTYPE>\n\n<html>\n<head>\n  <title>Simple composited reflections</title>\n  <style type=\"text/css\" media=\"screen\">\n\n      img {\n        margin: 20px;\n      }\n\n      .compositing {\n        -webkit-trans"..., length=681) at /build/WebKit/Source/WebCore/loader/DocumentLoader.cpp:328
#10 0x00007f73a0b2a4e1 in WebCore::FrameLoaderClientEfl::committedLoad (this=0x22bd620, loader=0x23d8be0, data=
    0x23bcb70 "<!DOCTYPE>\n\n<html>\n<head>\n  <title>Simple composited reflections</title>\n  <style type=\"text/css\" media=\"screen\">\n\n      img {\n        margin: 20px;\n      }\n\n      .compositing {\n        -webkit-trans"..., length=681) at /build/WebKit/Source/WebKit/efl/WebCoreSupport/FrameLoaderClientEfl.cpp:131
#11 0x00007f73a3c68852 in WebCore::DocumentLoader::commitLoad (this=0x23d8be0, data=
    0x23bcb70 "<!DOCTYPE>\n\n<html>\n<head>\n  <title>Simple composited reflections</title>\n  <style type=\"text/css\" media=\"screen\">\n\n      img {\n        margin: 20px;\n      }\n\n      .compositing {\n        -webkit-trans"..., length=681) at /build/WebKit/Source/WebCore/loader/DocumentLoader.cpp:321
#12 0x00007f73a3c68ab7 in WebCore::DocumentLoader::receivedData (this=0x23d8be0, data=
    0x23bcb70 "<!DOCTYPE>\n\n<html>\n<head>\n  <title>Simple composited reflections</title>\n  <style type=\"text/css\" media=\"screen\">\n\n      img {\n        margin: 20px;\n      }\n\n      .compositing {\n        -webkit-trans"..., length=681) at /build/WebKit/Source/WebCore/loader/DocumentLoader.cpp:364
#13 0x00007f73a3c9d69b in WebCore::MainResourceLoader::addData (this=0x23d27c0, data=
    0x23bcb70 "<!DOCTYPE>\n\n<html>\n<head>\n  <title>Simple composited reflections</title>\n  <style type=\"text/css\" media=\"screen\">\n\n      img {\n        margin: 20px;\n      }\n\n      .compositing {\n        -webkit-trans"..., length=681, allAtOnce=false) at /build/WebKit/Source/WebCore/loader/MainResourceLoader.cpp:192
#14 0x00007f73a3cb02e2 in WebCore::ResourceLoader::didReceiveData (this=0x23d27c0, data=
    0x23bcb70 "<!DOCTYPE>\n\n<html>\n<head>\n  <title>Simple composited reflections</title>\n  <style type=\"text/css\" media=\"screen\">\n\n      img {\n        margin: 20px;\n      }\n\n      .compositing {\n        -webkit-trans"..., length=681, encodedDataLength=681, allAtOnce=false) at /build/WebKit/Source/WebCore/loader/ResourceLoader.cpp:272
#15 0x00007f73a3c9eb15 in WebCore::MainResourceLoader::didReceiveData (this=0x23d27c0, data=
    0x23bcb70 "<!DOCTYPE>\n\n<html>\n<head>\n  <title>Simple composited reflections</title>\n  <style type=\"text/css\" media=\"screen\">\n\n      img {\n        margin: 20px;\n      }\n\n      .compositing {\n        -webkit-trans"..., length=681, encodedDataLength=681, allAtOnce=false) at /build/WebKit/Source/WebCore/loader/MainResourceLoader.cpp:498
#16 0x00007f73a3cb0bd9 in WebCore::ResourceLoader::didReceiveData (this=0x23d27c0, data=
    0x23bcb70 "<!DOCTYPE>\n\n<html>\n<head>\n  <title>Simple composited reflections</title>\n  <style type=\"text/css\" media=\"screen\">\n\n      img {\n        margin: 20px;\n      }\n\n      .compositing {\n        -webkit-trans"..., length=681, encodedDataLength=681) at /build/WebKit/Source/WebCore/loader/ResourceLoader.cpp:429
#17 0x00007f73a47e8d76 in WebCore::readCallback (source=0x22a2d80, asyncResult=0x229d840, data=0x23af030) at /build/WebKit/Source/WebCore/platform/network/soup/ResourceHandleSoup.cpp:875
#18 0x00007f739e02da99 in async_ready_callback_wrapper (source_object=0x22a2d80, res=0x229d840, user_data=0x23af030) at ginputstream.c:470
#19 0x00007f739e0400e7 in g_simple_async_result_complete (simple=0x229d840) at gsimpleasyncresult.c:767
#20 0x00007f739e040168 in complete_in_idle_cb_for_thread (_data=0x22a4bd0) at gsimpleasyncresult.c:835
#21 0x00007f739f68c623 in g_main_dispatch (context=0x23084f0) at gmain.c:2539
#22 g_main_context_dispatch (context=0x23084f0) at gmain.c:3075
#23 0x00007f73a83715e1 in _ecore_glib_select__locked (ecore_timeout=0x7fff0777ff40, efds=<optimized out>, wfds=<optimized out>, rfds=<optimized out>, ecore_fds=7, ctx=<optimized out>) at ecore_glib.c:171
#24 _ecore_glib_select (ecore_fds=7, rfds=<optimized out>, wfds=<optimized out>, efds=<optimized out>, ecore_timeout=0x7fff0777ff40) at ecore_glib.c:205
#25 0x00007f73a836b9ad in _ecore_main_select (timeout=<optimized out>) at ecore_main.c:1419
#26 0x00007f73a836c445 in _ecore_main_loop_iterate_internal (once_only=0) at ecore_main.c:1835
#27 0x00007f73a836c727 in ecore_main_loop_begin () at ecore_main.c:906
#28 0x00000000004636bb in runTest (cTestPathOrURL=0x7fff07780430 "/build/WebKit/LayoutTests/compositing/masks/direct-image-mask.html")
    at /build/WebKit/Tools/DumpRenderTree/efl/DumpRenderTree.cpp:257
#29 0x0000000000463834 in runTestingServerLoop () at /build/WebKit/Tools/DumpRenderTree/efl/DumpRenderTree.cpp:283
#30 0x0000000000463e84 in main (argc=2, argv=0x7fff07781588) at /build/WebKit/Tools/DumpRenderTree/efl/DumpRenderTree.cpp:419

[Kentaro Hara]

I am fixing it. Ten mins please.

[Kentaro Hara]

Reopening to attach new patch.

[Kentaro Hara]

Created attachment 146509 [details]
Patch

[Kentaro Hara]

Created attachment 146517 [details]
Patch

[Kentaro Hara]

Committed r119814: <http://trac.webkit.org/changeset/119814>

[Kentaro Hara]

(In reply to comment #21)
> So the problem comes down to the fact Node inherits from TreeShared<ContainerNode>. Because of this, we can't do static_cast<T*>(this) in TreeShared<T>::deref.
> 
> Does anyone know why we do this?

Filed bug 88653 and uploaded a patch to fix TreeShared<ContainerNode> to TreeShared<Node>.

[Darin Adler]

(In reply to comment #21)
> So the problem comes down to the fact Node inherits from TreeShared<ContainerNode>. Because of this, we can't do static_cast<T*>(this) in TreeShared<T>::deref.
> 
> Does anyone know why we do this?

We do this because the correct type for the parent of a Node is ContainerNode*, not Node*.

The right way to do this is to add a second type argument to TreeShared for the type of the element itself. The type currently passed in is the type of the parent. There’s no reason we can’t pass two types to the TreeShared template.

Please remove the messy callRemovedLastRef workaround and just change TreeShared so that it takes two types. Since TreeShared is only used for Node and SVGElementInstance that should be an easy change to make.

[Darin Adler]

I wish this change hadn’t been made in such a hurry; it could have waited another day or two. That messy callRemovedLastRef thing is completely unnecessary and there was no need to ever land it.

[Darin Adler]

I’m going to fix the problems here. Patch coming soon. There were other minor mistakes in this patch:

There was a bad cast to ContainerNode* in callRemovedLastRef, which can be called on nodes that are not derived from ContainerNode.

There was no reason for SVGElementInstance's removedLastRef function to be a virtual function.

Adding new public removedLastRef functions was not good. I suggest using friend instead so these can be private.

The patch modified order files, which is not necessary or helpful.

[Darin Adler]

Please, next time, wait until someone with experience with the class is available for review. The way this patch got the assertions in removedLastRef wrong caused churn, too, and indicates this was landed without sufficient testing.

[Darin Adler]

I believe that this regression, an increase in Node size, was *not* caused by TreeShared. It was caused when the EventTarget was created, causing Node to have multiple inheritance with virtual functions. TreeShared predated EventTarget by many years.

So this patch is a fix to a problem, increase in size of all nodes, caused by whoever added EventTarget. Someone should track down who that was and talk to them!

[Ojan Vafai]

(In reply to comment #38)
> I believe that this regression, an increase in Node size, was *not* caused by TreeShared. It was caused when the EventTarget was created, causing Node to have multiple inheritance with virtual functions. TreeShared predated EventTarget by many years.
> 
> So this patch is a fix to a problem, increase in size of all nodes, caused by whoever added EventTarget. Someone should track down who that was and talk to them!

Looks like you reviewed it. :) http://trac.webkit.org/changeset/18238

IMO, I don't think we gain anything from multiple inheritance here. If you rename TreeShared to NodeBase or something like that and have that inherit from EventTarget. Then you have a clean simple single-inheritance structure.

[Darin Adler]

(In reply to comment #39)
> If you rename TreeShared to NodeBase or something like that and have that inherit from EventTarget. Then you have a clean simple single-inheritance structure.

Yes, that’s a good plan.

TreeShared does not need to be a general purpose class. It can just be the class for what’s shared between SVGElementInstance and Node.

If we had done that we would not have had to do this work to devirtualize TreeShared.

We could consider rolling out all of this work and just doing that instead.

[Darin Adler]

For anyone who wants to make improvements to TreeShared, I can think of a few changes that might be improvements:

1) We can make the type of the parent be a typedef in the node class rather than a template argument. It would work like this: a) We'd remove the ParentNodeType argument from the template. b) We'd add a ParentNodeType typedef to the template class itself that would default to NodeType. c) In Node, we’d do a typedef ContainerNode ParentNodeType. d) In the two places in the template where we use the parent type, we’d use "typename NodeType::ParentNodeType", which would resolve to ContainerNode.

2) We can change the template's name to NodeBase and then feel free to move other code that Node wants to share with SVGElementInstance there. That does mean that the reference counting code might not be isolated from other concerns so it’s not entirely clear this is the right way to go.

3) Longer term, we can investigate doing the reference counting itself with RefCountedBase rather than repeating so much of what RefCountedBase does. We have talked about designs where we would find a different way for a parent to keep child nodes alive, perhaps by making firstChild and nextSibling be RefPtr, but it could be challenging to do that without creating a slowdown.

[Ryosuke Niwa]

(In reply to comment #35)
> I wish this change hadn’t been made in such a hurry; it could have waited another day or two. That messy callRemovedLastRef thing is completely unnecessary and there was no need to ever land it.

(In reply to comment #35)
> I wish this change hadn’t been made in such a hurry; it could have waited another day or two. That messy callRemovedLastRef thing is completely unnecessary and there was no need to ever land it.

Sorry, it's my fault :( I should have waited 'til you or Sam could take a look. Adding another type in the template is a brilliant idea indeed. Not sure why none of us involved in the initial discussion could think of that. Anyway, I'm glad we got rid of the mess at the end.

[Ojan Vafai]

(In reply to comment #41)
> 2) We can change the template's name to NodeBase and then feel free to move other code that Node wants to share with SVGElementInstance there. That does mean that the reference counting code might not be isolated from other concerns so it’s not entirely clear this is the right way to go.

I think we should do this even though you've addressed the specific issue in this bug. I don't think there is much code to be shared between SVGElementInstance and Node other than what's already in TreeShared. So, renaming is more about making the code more understandable and making it so EventTarget can semantically be the super-class of TreeShared.

In my experience, TreeShared confuses everyone who first encounters it in a way that NodeBase wouldn't because it sounds like it needs to be something much more generic (a general tree data structure) than what it actually is (a common base class for Node and SVGElementInstance).