Bug 31839 - JSON.stringify performance on undefined is very poor
Summary: JSON.stringify performance on undefined is very poor
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2009-11-24 10:27 PST by Joseph Pecoraro
Modified: 2009-11-30 13:52 PST (History)
6 users (show)

See Also:


Attachments
[TEST CASE] Shows Poor Performance of Stringify with undefined (1.02 KB, text/html)
2009-11-24 10:27 PST, Joseph Pecoraro
no flags Details
[PATCH] Replace substr() with truncate() in the rollback case (1.81 KB, patch)
2009-11-24 10:32 PST, Joseph Pecoraro
no flags Details | Formatted Diff | Diff
Patch (2.74 KB, patch)
2009-11-24 13:15 PST, Oliver Hunt
ap: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Joseph Pecoraro 2009-11-24 10:27:35 PST
Created attachment 43784 [details]
[TEST CASE] Shows Poor Performance of Stringify with undefined

I recently ran some benchmarks for native JSON in a few browsers and stumbled on the fact that WebKit's performance with the "undefined" value was considerably slow.  A version of my test case is attached which highlights the issues.

Here is a screenshot showing the improvement I got:
http://grab.by/MjK

  Safari 4.0.4    ~120ms
  WebKit Nightly  ~249ms
  My Build         ~10ms

My change still passes all tests. No tests are added, since this is really a benchmark.
Comment 1 Joseph Pecoraro 2009-11-24 10:32:18 PST
Created attachment 43785 [details]
[PATCH] Replace substr() with truncate() in the rollback case

I'm new to this area of WebKit, so please review carefully!

Also, should I add an assert that the new truncate length is less then the existing length?
Comment 2 Eric Seidel (no email) 2009-11-24 10:39:24 PST
Does Dromero test JSON parsing yet?  Would be nice if it did.

I suspect this would work fine, I don't know if this breaks a UString design principle though.  I'm not sure if there are other cases where UString::Rep has more data that its len member claims it does.
Comment 3 Oliver Hunt 2009-11-24 12:10:52 PST
Comment on attachment 43785 [details]
[PATCH] Replace substr() with truncate() in the rollback case

> +        void truncate(int length) const { m_rep->len = length; }

I am concerned about this change -- i'm not convinced that it's safe (as rep's may be shared).  What is the object structure that leads to us need to roll back the string?

I'm also wondering if maybe it's worth just switching to Vector<UChar> while we build the string, which will remove any data sharing issues we could hit.
Comment 4 Joseph Pecoraro 2009-11-24 12:19:44 PST
(In reply to comment #3)
> What is the object structure that leads to us need to roll
> back the string?

The JSON result is continually built by appending onto a string builder (UString).  JSON specifies that we should not put undefined values in the resulting sting.

The case where it is rolled back is when contents were already put on the builder string, and then we encountered an "undefined" value, and we have to remove the contents we already put on the string. So in the following case:

  { a: undefined }

The builder would follow these steps:

  Action                                   Builder So Far
  -----------                              --------------
  1. start object                          {
  2. put key and seperator                 {"a":
  3. encounter undefined value... rollback {
  4. finish properties, close object       {}
  5. done
Comment 5 Oliver Hunt 2009-11-24 12:28:51 PST
(In reply to comment #4)
> (In reply to comment #3)
> > What is the object structure that leads to us need to roll
> > back the string?
> 
> The JSON result is continually built by appending onto a string builder
> (UString).  JSON specifies that we should not put undefined values in the
> resulting sting.
> 
> The case where it is rolled back is when contents were already put on the
> builder string, and then we encountered an "undefined" value, and we have to
> remove the contents we already put on the string. So in the following case:
> 
>   { a: undefined }
> 
> The builder would follow these steps:
> 
>   Action                                   Builder So Far
>   -----------                              --------------
>   1. start object                          {
>   2. put key and seperator                 {"a":
>   3. encounter undefined value... rollback {
>   4. finish properties, close object       {}
>   5. done

Yeah i saw it once i actually looked at the code.  I'm just testing a patch that switches stringification over to basically using a Vector<UChar>.  I'm testing perf, etc now.
Comment 6 Oliver Hunt 2009-11-24 13:15:15 PST
Created attachment 43802 [details]
Patch
Comment 7 Alexey Proskuryakov 2009-11-24 13:30:58 PST
Comment on attachment 43802 [details]
Patch

> +    class StringBuilder : public Vector<UChar> {

Subclassing Vector is unsafe, because it does not have a virtual destructor. Maybe adding private operator delete would make it a little safer? I'm not 100% clear on what the best way to make it safe is.

> +            for (size_t i = 0; i < len; i++)
> +                Vector<UChar>::append(str[i]);

Should we ASSERT that the only low ASCII is used here? Otherwise, conversion from signed to unsigned could go badly (not to mention that we don't know what encoding it is).

> +        inline void append(const char ch)

Someone could ask you why you don't use full words instead of those "ch", "len" and "str".

> +            Vector<UChar>::append(ch);

Would a simple "using Vector<UChar>::append" achieve the same result?

r=me
Comment 8 Oliver Hunt 2009-11-24 13:42:20 PST
Committed r51352
Comment 9 Darin Adler 2009-11-30 13:50:00 PST
(In reply to comment #7)
> (From update of attachment 43802 [details])
> > +    class StringBuilder : public Vector<UChar> {
> 
> Subclassing Vector is unsafe, because it does not have a virtual destructor.
> Maybe adding private operator delete would make it a little safer? I'm not 100%
> clear on what the best way to make it safe is.

Private inheritance might work better. Then you can expose Vector functions with "using" individually.

> Should we ASSERT that the only low ASCII is used here? Otherwise, conversion
> from signed to unsigned could go badly (not to mention that we don't know what
> encoding it is).

Yes.

> > +        inline void append(const char ch)
> 
> Someone could ask you why you don't use full words instead of those "ch", "len"
> and "str".

Like me.

> Would a simple "using Vector<UChar>::append" achieve the same result?

Yes.
Comment 10 Darin Adler 2009-11-30 13:52:38 PST
(In reply to comment #9)
> > Subclassing Vector is unsafe, because it does not have a virtual destructor.
> > Maybe adding private operator delete would make it a little safer? I'm not 100%
> > clear on what the best way to make it safe is.

Since StringBuilder doesn't add any data members or override any virtual functions, I think it's not unsafe.