Bug 115807 - RenderQuote has giant function for language to quotes map
Summary: RenderQuote has giant function for language to quotes map
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Darin Adler
Depends on:
Blocks: 116528
  Show dependency treegraph
Reported: 2013-05-08 09:33 PDT by Darin Adler
Modified: 2013-05-21 03:25 PDT (History)
7 users (show)

See Also:

Patch (37.69 KB, patch)
2013-05-09 09:47 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (37.69 KB, patch)
2013-05-09 10:09 PDT, Darin Adler
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Darin Adler 2013-05-08 09:33:55 PDT
Anders pointed out that RenderQuote has a colossal function that creates a map from language to quotes. It doesn’t need that. Also some other style problems there worth fixing.
Comment 1 Darin Adler 2013-05-09 09:47:24 PDT
Created attachment 201245 [details]
Comment 2 Darin Adler 2013-05-09 10:04:51 PDT
I’m seeing what might be a regression test failure and might need to upload a new version of the patch.
Comment 3 Darin Adler 2013-05-09 10:09:58 PDT
Created attachment 201247 [details]
Comment 4 Darin Adler 2013-05-09 10:10:28 PDT
Had one >= that should have been a >; fixed in the newer patch.
Comment 5 WebKit Commit Bot 2013-05-09 12:23:25 PDT
Comment on attachment 201247 [details]

Clearing flags on attachment: 201247

Committed r149833: <http://trac.webkit.org/changeset/149833>
Comment 6 WebKit Commit Bot 2013-05-09 12:23:27 PDT
All reviewed patches have been landed.  Closing bug.
Comment 7 Eric Seidel (no email) 2013-05-14 00:50:52 PDT
I think the root problem here is HashTable::set.

Each of these set() calls appears to expand to 1.52k of binary size!

See more discussion here:

My template-fu is not strong enough to understand what HashTable.h is doing which is causing this binary size explosion with each :set() call.
Comment 8 Darin Adler 2013-05-14 09:38:52 PDT
(In reply to comment #7)
> I think the root problem here is HashTable::set.

I’m not sure; that’s a significant part of the problem, but I would not call it “the root problem”. One of the best features of HashTable is that the code gets inlined where it needs to be fast.

> Each of these set() calls appears to expand to 1.52k of binary size!

We do expect the calls to be fairly large, because our hash table code is designed to be fully inlined by default.

I see four problems here:

This function’s original code makes the mistake of compiling lots of separate inlined calls to fill out the hash table rather than using a loop. That’s the primary problem. Generating a lot of code instead of a loop. Fixing that would be the minimal fix. I consider that “the root problem”. It’s just not a good approach to generate lots of function calls instead of a table and a loop. There’s no reason that loop needs to be unrolled.

The second problem is that the code to set a hash table entry is big, perhaps bigger than it needs to be. You called that “the root problem”, and it is an area with room for improvement but not really the key here in my opinion.

A third possibly distinct problem is that this code uses the inlined version, but it should instead use a function because it doesn’t benefit from inlining. We might want to look at different inlining for some hash table code in general, or a way to avoid the inlining without hand-writing functions each time.

A fourth problem is that a hash table is not the right data structure for a table that is defined at compile time. Our hash table class optimized for dynamic use at runtime, not a single static table. In other projects I have used gperf to make perfect hash functions for this kind of thing, and JavaScriptCore has something like that too. A simple array with a binary search does the job well. With some helper functions we could make it even easier to do this at other places where this kind of problem arises. Maybe share the code that JavaScriptCore uses.

Anders’s comment to me about this function was that we don’t need this on-time code to be inlined at all. Then Anders and I decided to take it further and not use a hash table at all, because we don’t think a hash table is the right tool for this job.
Comment 9 Darin Adler 2013-05-19 04:49:05 PDT
Elliot mentioned in the Blink code review that this new code is ugly. I think it’s worth considering how to package this for reuse as a way to make it prettier since there are similar problems to be solved elsewhere. That’s probably more practical than turning HashMap into a tool suitable for this use.