Bug 43716 - Use a HashMap for m_continuation to save memory
Summary: Use a HashMap for m_continuation to save memory
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-08-09 04:39 PDT by Kenichi Ishibashi
Modified: 2010-12-29 20:20 PST (History)
10 users (show)

See Also:


Attachments
Patch (10.65 KB, patch)
2010-08-09 06:10 PDT, Kenichi Ishibashi
no flags Details | Formatted Diff | Diff
Patch V1 (10.94 KB, patch)
2010-09-01 02:55 PDT, Kenichi Ishibashi
no flags Details | Formatted Diff | Diff
Patch V2 (11.24 KB, patch)
2010-12-13 17:49 PST, Kenichi Ishibashi
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Kenichi Ishibashi 2010-08-09 04:39:04 PDT
Applying a HashMap convention to continuation pointers of RenderInline and RenderBlock would save chunk of memory. See https://bugs.webkit.org/show_bug.cgi?id=42309 for a detailed discussion.
Comment 1 Kenichi Ishibashi 2010-08-09 06:10:05 PDT
Created attachment 63892 [details]
Patch
Comment 2 Sam Weinig 2010-08-09 08:28:39 PDT
Hyatt should do the review (as it is his idea and he promised he would) but this also needs some performance numbers.
Comment 3 Darin Adler 2010-08-09 09:29:46 PDT
Comment on attachment 63892 [details]
Patch

This is good if continuations are rare. If continuations are common, then it makes the render tree use less memory, but makes things slower. How did you test the performance implications of the change?
Comment 4 Darin Adler 2010-08-09 09:30:05 PDT
Oh, I see that Sam already mentioned that.
Comment 5 Kenichi Ishibashi 2010-08-09 18:14:39 PDT
Thank you for your comments. Actually, I didn't conduct performance test because I'm new to WebKit and I don't know how should I test for that purpose. I would very appreciate if there are usual ways to test performance and letting me know these, if available.
Comment 6 Darin Adler 2010-08-29 12:19:47 PDT
Comment on attachment 63892 [details]
Patch

> +     RenderBoxModelObject* cont = continuation();
> +     if (cont) {
> +         cont->destroy();
> +         setContinuation(0);
> +     }

Please don't abbreviate continuation to "cont"; abbreviations are harder to read and recognize than words, and can also be confusing and ambiguous. We typically use this style in cases like this:

    if (RenderBoxModelObject* continuation = this->continuation()) {
        continuation->destroy();
        setContinuation(0);
    }

> +// The HashMap for storing continuation pointers.
> +// An inline can be split with blocks occuring in between the inline content.
> +// When this occurs we need a pointer to the next object. We can basically be
> +// split into a sequence of inlines and blocks. The continuation will either be
> +// an anonymous block (that houses other blocks) or it will be an inline flow.
> +// <b><i><p>Hello</p></i></b>. In this example the <i> will have a block as
> +// its continuation but the <b> will just have an inline as its continuation.
> +typedef HashMap<const RenderBoxModelObject*, RenderBoxModelObject*> ContinuationMap;
> +static ContinuationMap* gContinuationMap = 0;

I presume that the motivation for moving the continuation pointer into a map is to save memory. Do you have any data on the memory and performance impact of this change?

> --- a/WebCore/rendering/RenderInline.h
> +++ b/WebCore/rendering/RenderInline.h
> @@ -59,8 +59,8 @@ public:
>      InlineFlowBox* firstLineBox() const { return m_lineBoxes.firstLineBox(); }
>      InlineFlowBox* lastLineBox() const { return m_lineBoxes.lastLineBox(); }
>  
> -    RenderBoxModelObject* continuation() const { return m_continuation; }
> -    void setContinuation(RenderBoxModelObject* c) { m_continuation = c; }
> +    RenderBoxModelObject* continuation() const { return RenderBoxModelObject::continuation(); }
> +    void setContinuation(RenderBoxModelObject* c) { RenderBoxModelObject::setContinuation(c); }

Instead of forwarding functions, you can use the "using" statement:

    using RenderBoxModelObject::continuation;
    using RenderBoxModelObject::setContinuation;

I’d like to see a new patch that eliminates the abbreviations and is accompanied by some performance data to show this is a good change.

I’m also not entirely sure that having this be a protected function in RenderBoxModelObject that then is made public in both RenderInline and RenderBlock is a helpful design. We may simply want it to be public in RenderBoxModelObject instead. Hyatt can weigh in on that.
Comment 7 Darin Adler 2010-08-29 12:20:24 PDT
If we can’t do any performance tests to prove this is a good idea, then we should not make the change!
Comment 8 Kenichi Ishibashi 2010-08-30 22:16:42 PDT
Hi Darin,

Thank you for your review. I agree with you that we need to performance test for this patch. For performance check, I run i-Bench HTML test suites.  Although the results are unstable for each test, I didn't observe any measurable performance regression. Just for information, three results are shown below:

- with the patch
All iterations	  39.94
First iteration (downloaded)	  4.6
Subsequent iteration (cached)	  5.05

All iterations	  39.58
First iteration (downloaded)	  4.57
Subsequent iteration (cached)	  5

All iterations	  39.87
First iteration (downloaded)	  4.58
Subsequent iteration (cached)	  5.04

- without the patch
All iterations	  40.19
First iteration (downloaded)	  5.19
Subsequent iteration (cached)	  5

All iterations	  40.12
First iteration (downloaded)	  5.19
Subsequent iteration (cached)	  4.99

All iterations	  39.7
First iteration (downloaded)	  4.56
Subsequent iteration (cached)	  5.02

For memory consumption, I couldn't find good way to test for this patch. I'm going to continue to look for the way to test memory consumption.
Comment 9 Kenichi Ishibashi 2010-08-31 18:53:48 PDT
I counted up how many RenderBlock and RenderInline are created, and check how many continuations are created for some web pages. Continuations are rarely created. For instance, when I load cnn.com, the total creation number of RenderBlock and RenderInline objects is 1081, while the number of continuation created is just 9. In this case, approximately 4KBytes might be able to reduce on 32bit machines ideally (Of course, there are many other factors affecting memory usage, such as memory allocation strategy and alignments, so it's just for expectation).

I also checked actual memory usage by using activity monitor. In most cases, this change would consume less memory. As an instance, when I load cnn.com, I observed following memory usage on my 64bit SnowLeopard:
- with the patch
Real Mem: 72.7MB, Private Mem: 43.2MB
- without the patch
Real Mem: 73.8MB, Private Mem: 43.4MB

Needless to say, this result doesn't convince that this change will reduce memory usage in general, but I think it might show the effect of this patch.

I'll send the revised patch later.

Thanks,
Comment 10 Kenichi Ishibashi 2010-09-01 02:55:40 PDT
Created attachment 66184 [details]
Patch V1
Comment 11 Kenichi Ishibashi 2010-09-01 02:58:03 PDT
(In reply to comment #6)
> Please don't abbreviate continuation to "cont"; abbreviations are harder to read and recognize than words, and can also be confusing and ambiguous. We typically use this style in cases like this:
> 
>     if (RenderBoxModelObject* continuation = this->continuation()) {
>         continuation->destroy();
>         setContinuation(0);
>     }

Thank you letting me know this. I've fixed it.

> I presume that the motivation for moving the continuation pointer into a map is to save memory. Do you have any data on the memory and performance impact of this change?

Please refer the previous comment. I'm aware that it's not enough, but since there are many factors affecting memory and performance, I couldn't find a way to see the actual effect of the change.

> Instead of forwarding functions, you can use the "using" statement:
> 
>     using RenderBoxModelObject::continuation;
>     using RenderBoxModelObject::setContinuation;

I couldn't use "using" at this time because I defined these functions as protected. The reason of why these functions were defined as protected comes from the inheritance hierarchy. The RenderBlock class isn't derived from RenderBoxModelObject directry; There is RenderBox class between RenderBoxModelObject and RenderBlock, and RenderBox doesn't define these functions. While the code and the hash table should share between RenderBlock and RenderInline (because these are almost the same), it might not be good idea making these functions to be public because RenderBox should not provide these functions. However, I'm not sure why RenderBox doesn't provide these functions, so I'd like to ask your opinions.

> I'm also not entirely sure that having this be a protected function in RenderBoxModelObject that then is made public in both RenderInline and RenderBlock is a helpful design. We may simply want it to be public in RenderBoxModelObject instead. Hyatt can weigh in on that.

As mentioned above, I'd like to ask some advice on that.

Thanks,
Comment 12 Eric Seidel (no email) 2010-12-12 02:35:52 PST
CCing folks who have historically been interested in performance.
Comment 13 Darin Adler 2010-12-13 10:08:19 PST
(In reply to comment #11)
> > Instead of forwarding functions, you can use the "using" statement:
> > 
> >     using RenderBoxModelObject::continuation;
> >     using RenderBoxModelObject::setContinuation;
> 
> I couldn't use "using" at this time because I defined these functions as protected.

I don’t know what you mean. The using statement can be used to change the visibility of functions. Defining the functions as protected and then making use of using to make them public in a derived class is perfectly normal; it’s exactly what the using statement is good for.
Comment 14 Darin Adler 2010-12-13 10:11:47 PST
Comment on attachment 66184 [details]
Patch V1

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

> WebCore/rendering/RenderBlock.h:135
> +    RenderBoxModelObject* continuation() const { return RenderBoxModelObject::continuation(); }
> +    void setContinuation(RenderBoxModelObject* continuation) { RenderBoxModelObject::setContinuation(continuation); }

As I said before, this should be “using” rather than a forwarding inline function.

> WebCore/rendering/RenderBoxModelObject.cpp:63
> +static ContinuationMap* gContinuationMap = 0;

The use of the “g” prefix here is not common in WebKit code. I did a search and found that most global variables of this type do not use this sort of prefix.

> WebCore/rendering/RenderBoxModelObject.cpp:1796
> +    if (!gContinuationMap)
> +        gContinuationMap = new ContinuationMap;
> +
> +    if (continuation)
> +        gContinuationMap->set(this, continuation);
> +    else
> +        gContinuationMap->remove(this);

The creation of the map could be moved inside the non-zero case, since is no need to create the map to remove something from it. Probably OK the way it is, though, since we’d still need a null check of gContinuationMap.

> WebCore/rendering/RenderInline.h:63
> +    RenderBoxModelObject* continuation() const { return RenderBoxModelObject::continuation(); }
> +    void setContinuation(RenderBoxModelObject* continuation) { RenderBoxModelObject::setContinuation(continuation); }

Again, I think “using” is the way to go.
Comment 15 Kenichi Ishibashi 2010-12-13 17:46:59 PST
Comment on attachment 66184 [details]
Patch V1

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

Hi Darin,

Thank you very much for reviewing! I've applied your comments and updated to ToT. I'll send the patch soon.

>> WebCore/rendering/RenderBlock.h:135
>> +    void setContinuation(RenderBoxModelObject* continuation) { RenderBoxModelObject::setContinuation(continuation); }
> 
> As I said before, this should be “using” rather than a forwarding inline function.

Done. I misunderstood the usage of "using." Thank you!

>> WebCore/rendering/RenderBoxModelObject.cpp:63
>> +static ContinuationMap* gContinuationMap = 0;
> 
> The use of the “g” prefix here is not common in WebKit code. I did a search and found that most global variables of this type do not use this sort of prefix.

Thanks for the advice. Removed the "g" prefix.

>> WebCore/rendering/RenderBoxModelObject.cpp:1796
>> +        gContinuationMap->remove(this);
> 
> The creation of the map could be moved inside the non-zero case, since is no need to create the map to remove something from it. Probably OK the way it is, though, since we’d still need a null check of gContinuationMap.

I agree with you. Moved the creation of the map inside the non-zero case.

>> WebCore/rendering/RenderInline.h:63
>> +    void setContinuation(RenderBoxModelObject* continuation) { RenderBoxModelObject::setContinuation(continuation); }
> 
> Again, I think “using” is the way to go.

Done.
Comment 16 Kenichi Ishibashi 2010-12-13 17:49:45 PST
Created attachment 76472 [details]
Patch V2
Comment 17 WebKit Commit Bot 2010-12-29 19:16:17 PST
Comment on attachment 76472 [details]
Patch V2

Clearing flags on attachment: 76472

Committed r74775: <http://trac.webkit.org/changeset/74775>
Comment 18 WebKit Commit Bot 2010-12-29 19:16:25 PST
All reviewed patches have been landed.  Closing bug.
Comment 19 WebKit Review Bot 2010-12-29 20:20:09 PST
http://trac.webkit.org/changeset/74775 might have broken Leopard Intel Debug (Tests)