121341 - nsPersistentProperties::Load is very inefficient

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Simon Fraser [no longer active]]

nsPersistentProperties::Load, which is used for loading string bundles, reads 
from a stream a character at a time, and does thousands of string appends. 4 
calls to it account for 44ms of early startup time. It should be possible to make 
it much faster.

Comment 1

[Doug Turner (:dougt)]

I think that either I or darin have a dup.  Also, verify that the Load is
reading from a buffered stream so the "inefficient" nature isn't that bad.

Comment 2

[Alec Flett]

Oh baby! I've been wanting to rewrite this thing for a while, but haven't had a
good reason other than "it sucks" - I'm so glad to hear someone wants it rewritten.

I'm taking this.. dougt/darin - if you find the dupe, reassign it to me. 

One of the WORST parts about the whole thing is that we store the string bundles
in pure unicode, which means they take up a boatload of room. We should be
storing them in their native UTF8 and inflating them on demand.

My plan is to keep the entire text of the string bundle in memory, and use
nsDependentStrings to hold references to each string segment. i.e. if a string
bundle looks like:

foo=bar
baz=floop

then we'd keep the string 'foo=bar\nbaz=floop\n' in memory, and keep
nsDependentStrings (or some relative of them) with direct refs to 'foo', 'bar',
'baz', and 'floop' - then when someone does a
getProperty(NS_LITERAL_STRING("foo"), result); we can look up "foo" in a hash
table, and then inflate the dependent string that points to bar.

Comment 3

[Alec Flett]

targetting 1.0 for now.. I sure hope I can get to this

Comment 4

[Alec Flett]

woah, 1.1 came up quick. Throwing these bugs over to 1.2.. little or no work has
been done and there is no way that these bugs can be fixed in 1.1.

Comment 5

[Alec Flett]

pushing a few bugs out to 1.2beta - too much stuff on my 1.2alpha plate!

Comment 6

[Alec Flett]

I've already switched us over to using arenas, so we're much more efficient
w.r.t. memory usage.. however the parser needs some love.

Comment 7

[Alec Flett]

These bugs missed the 1.2 train. Moving these out to 1.3alpha

Comment 8

[Alec Flett]

I had a sudden brainstorm about this last night - we should be using
nsManifestLineReader here! Its fast, has minimal copying, reuses existing code,
and so forth.

Comment 9

[Doug Turner (:dougt)]

only if jband could see us now. :-)

Comment 10

[Alec Flett]

wow, so the use of Read() for one character is only the beginning of this mess.
I just filed bug 189528 about the real mess. This bug and that bug can be fixed
simultaneously though.

Comment 11

[Alec Flett]

Attachment: rewrite the .properties parser

ok, here is a very fast parser, that is oriented around segmented buffers. All
state is held in nsParserState. The idea is that once bug 189528 is fixed, then
I can use ReadSegments() to parse the buffer. 

The parser is relatively straight forward. It has some basic states depending
on if it is parsing a comment, a key, or a value, and then the value parser has
some specific states depending on if it is parsing special values like \t or
\u5e4f. I have tested this with a number of different .properties files with
various combinations of escaped characters and so forth.

I've also included some #if 0'ed code in preparation for fixing bug 189528.

Comment 12

[Alec Flett]

Comment on attachment 112107 [details] [diff] [review]
rewrite the .properties parser

doug/darin - can I get reviews on this new parser? Its pretty straight forward
and I've done a fair amount of testing on edge cases.. see the previous comment
for a little elaboration on how the parser works.

Comment 13

[Alec Flett]

oh, and the member variables mKey and mValue are nsAutoStrings because the whole
nsParserState structure is a stack-based structure.

Comment 14

[Darin Fisher]

Comment on attachment 112107 [details] [diff] [review]
rewrite the .properties parser

>Index: nsPersistentProperties.h

>+#if 0
...
>+#endif

nit: please kill the #if 0'd code or add a comment explaining why
it should remain.  same applies to other #if 0'd code.


>Index: nsPersistentProperties.cpp

>+  eParserSpecial_Special,       // awaiting a special character

whoa!  there's got to be a better name for this!


>+      aState.mValue += nsDependentSingleFragmentSubstring(tokenStart, cur);

nit: how about |Substring(tokenStart, cur)| instead?


>+  while (NS_SUCCEEDED(ret)) {
>+    ret = mIn->Read(buf, 0, PROP_BUFFER_SIZE, &nRead);
>+
>+    ParseBuffer(parserState, buf, nRead);
>+    
>+    if (nRead == 0) break;

seems like this check should be placed above ParseBuffer, no?

overall, patch looks really great!  sr=darin modulo these few nits.

Comment 15

[Doug Turner (:dougt)]

Comment on attachment 112107 [details] [diff] [review]
rewrite the .properties parser

what darin said.

Comment 16

[Alec Flett]

fix is in.

Comment 17

[(not reading, please use [e-mail] instead)]

heads up, bug #190215 might be a regression (or side effect) caused by this.

Comment 18

[(not reading, please use [e-mail] instead)]

question for alecf, what about '\"', ascii char 34

I'm hitting this code in ParseValueCharacter() for that:

    default:
      // don't recognize the character, so just append it
      NS_WARNING("Unknown escaped value in properties file");
      aState.mValue += c;
      break;

that does appear in our properties file, should we be handling it (and not 
warning?)

Comment 19

[Boris Zbarsky [:bzbarsky]]

This caused bug 190256

Comment 20

[Robert Kaiser]

This seems to have caused bug 190283 as well, another bad regression, esp. for
L10n people like me :(

Comment 21

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

a=dbaron for 1.3b checkin for backing out (per alecf's email request)

Comment 22

[Alec Flett]

backed out. reopening.

Comment 23

[Alec Flett]

mass moving lower risk 1.4alpha stuff to 1.4beta

Comment 24

[Eli Friedman]

What exactly happened to this patch?  There's still a significant win to be had.

Comment 25

[Michal Novotny [:michal]]

This should be probably blocker for 1.9.

nsPersistentProperty::Load takes about 1.72% of startup time.

Comment 26

[Samuel Sidler (old account; do not CC)]

(In reply to comment #25)
> This should be probably blocker for 1.9.

You should request blocking on such bugs.

Comment 27

[Robert Sayre]

definitely want this, nice find. not going to block though.

Comment 28

[Michal Novotny [:michal]]

There were quite a lot of regressions caused with this patch. I manually reapplied Alec's patch to the current HEAD and also included old parser as an new component. From simple JS I'm parsing properties files with both and comparing the result. I've found some regressions and I'm fixing them. Now I testing all properties files from CVS tree. I would like to test it on as much as possible files. Where can I get all properties files for other languages?

Comment 29

[Michal Novotny [:michal]]

Attachment: fixed properties files parser

Basically there were fixed 3 bugs:
- escaping at the end of buffer was broken
- right trimming at the end trimmed also escaped whitespaces
- leading whitespaces weren't removed in multiline properties

I tested it extensively with 142 properties files I found in CVS in variants with unix and dos line ends. I also tried to set lower PROP_BUFFER_SIZE (even 1) to see if it is working properly.

Comment 30

[Michal Novotny [:michal]]

Attachment: patch + JS for testing new parser against the old one

attached to bug just to have it somewhere...

Comment 31

[Michal Novotny [:michal]]

I also tested how this patch influenced startup time. Number of valgrind's Ir needed to do all nsPersistentProperties::Load() during startup decreased from 16877051 to 5607477. In absolute numbers whole startup took 566ms instead of 573ms on my HW setup.

Comment 32

[Benjamin Smedberg]

Comment on attachment 306257 [details] [diff] [review]
fixed properties files parser

There's absolutely no way I'm going to review this without unit tests.

Comment 33

[Doug Turner (:dougt)]

Michal, thanks for the patch!  It changes a bunch of stuff.  Could you produce a unit test so that we reduce our chances of breaking something accidently?  As you can see a similar change did produce a regression.

Comment 34

[Michal Novotny [:michal]]

Attachment: unit test

Comment 35

[Michal Novotny [:michal]]

Attachment: fixed patch

Thanks to unit test I found a bug parsing shortened unicode escaped sequences like "\uAB\n". This patch handles them correctly.

Comment 36

[Benjamin Smedberg]

Comment on attachment 307514 [details] [diff] [review]
fixed patch

>Index: xpcom/ds/nsPersistentProperties.cpp

>+//
>+// parser stuff
>+//
>+enum {
>+    eParserState_AwaitingKey,
>+    eParserState_Key,
>+    eParserState_AwaitingValue,
>+    eParserState_Value,
>+    eParserState_Comment
>+};

Is "mParserState" below always a value from this enum? Is there any reason you can't name the enum and use it directly below, instead of using PRUint32?

>+  nsAutoString mKey;
>+  nsAutoString mValue;

Why are these public?


>+  // if we see a '\' then we enter this special state
>+  PRUint32 mSpecialState;
>+
>+  PRUint32  mUnicodeValuesRead; // should be 4!
>+  PRUnichar mUnicodeValue;      // currently parsed unicode value
>+  PRBool    mHaveMultiLine;     // if this key is multi-line
>+  PRBool    mMultiLineCanSkipN; // TRUE if "\\\r" was detected
>+  PRUint32  mMinLength;         // limit right trimming at the end to not trim
>+                                // escaped whitespaces

Ore these?

>+
>+private:
>+  PRUint32 mState;
>+  nsCOMPtr<nsIPersistentProperties> mProps; // weak

nsCOMPtr is not weak. Because this class is only instantiated on the stack and you know that the properties file is going to stay around, you can just use a raw nsIPersistentProperties*, I think.

>+#define IS_WHITE_SPACE(c) \
>+  (((c) == ' ') || ((c) == '\t') || ((c) == '\r') || ((c) == '\n'))
>+
>+#define IS_EOL(c) \
>+  (((c) == '\r') || ((c) == '\n'))

Can these be inline functions instead of macros, please?

As for the actual parsing: I read through it and it looks generally correct and documented. However, I don't see where errors are handled: that is, what happens if you feed it invalid input. Does it throw it away? If so, can you at least note where it does that and file a followup bug for us to issue console errors in that case?

>Index: xpcom/ds/nsPersistentProperties.h

> private:
>-  ~nsPersistentProperties();
>+  virtual ~nsPersistentProperties();

I don't think that this is necessary or desirable. We don't ever delete a subclass through a base-class pointer, do we?

In general, this looks good. I'd really like more testcase, though, for properties-as-UTF8, malformed data, etc. See bug 397093 for related parsing issues, I think.

Comment 37

[Michal Novotny [:michal]]

Attachment: patch v3

(In reply to comment #36)
> Is "mParserState" below always a value from this enum? Is there any reason you
> can't name the enum and use it directly below, instead of using PRUint32?

fixed

> >+  nsAutoString mKey;
> >+  nsAutoString mValue;
> 
> Why are these public?
> 
> 
> >+  // if we see a '\' then we enter this special state
> >+  PRUint32 mSpecialState;
> >+
> >+  PRUint32  mUnicodeValuesRead; // should be 4!
> >+  PRUnichar mUnicodeValue;      // currently parsed unicode value
> >+  PRBool    mHaveMultiLine;     // if this key is multi-line
> >+  PRBool    mMultiLineCanSkipN; // TRUE if "\\\r" was detected
> >+  PRUint32  mMinLength;         // limit right trimming at the end to not trim
> >+                                // escaped whitespaces
> 
> Ore these?

They were used in ParseBuffer() and ParseValueCharacter() functions. I've moved these functions into the parser class and I've renamed the class to nsPropertiesParser since I think it isn't state-only class anymore.

> >+
> >+private:
> >+  PRUint32 mState;
> >+  nsCOMPtr<nsIPersistentProperties> mProps; // weak
> 
> nsCOMPtr is not weak. Because this class is only instantiated on the stack and
> you know that the properties file is going to stay around, you can just use a
> raw nsIPersistentProperties*, I think.

fixed 

> >+#define IS_WHITE_SPACE(c) \
> >+  (((c) == ' ') || ((c) == '\t') || ((c) == '\r') || ((c) == '\n'))
> >+
> >+#define IS_EOL(c) \
> >+  (((c) == '\r') || ((c) == '\n'))
> 
> Can these be inline functions instead of macros, please?

fixed

> As for the actual parsing: I read through it and it looks generally correct and
> documented. However, I don't see where errors are handled: that is, what
> happens if you feed it invalid input. Does it throw it away? If so, can you at
> least note where it does that and file a followup bug for us to issue console
> errors in that case?

Correct me if I'm wrong, but neither old parser did check for invalid input. The goal was to have 100% compatible parser that is faster than the old one. IMHO there is also no definition of valid input. If you will pass random data to the parser it will parse it...

> >Index: xpcom/ds/nsPersistentProperties.h
> 
> > private:
> >-  ~nsPersistentProperties();
> >+  virtual ~nsPersistentProperties();
> 
> I don't think that this is necessary or desirable. We don't ever delete a
> subclass through a base-class pointer, do we?

fixed

> In general, this looks good. I'd really like more testcase, though, for
> properties-as-UTF8, malformed data, etc. See bug 397093 for related parsing
> issues, I think.

Unfortunately I don't have access to the bug.

Comment 38

[Michal Novotny [:michal]]

Attachment: unit test v2

Added test of valid and invalid UTF-8 sequence

Comment 39

[Michal Novotny [:michal]]

I've found probably a bug while I've been playing with invalid UTF-8 input. Nothing should be loaded from properties file when there is some invalid input. But it seems that input is buffered by 8kb. When invalid input isn't in the first 8kb then parsing succeeds partially. E.g. when at least 8kb of comments is added between properties utf8Property and latin1Property in http://mxr.mozilla.org/firefox/source/intl/strres/tests/397093.properties then unit test will fail. Since this is problem of old parser as well as new parser I think that new bug should be filed for this. Any opinions?

Comment 40

[Doug Turner (:dougt)]

loading properties files in fennec goes from .75 seconds to .26 seconds w/ this patch + buffering (bug 433098).  Must have.

Great work michal!

Comment 41

[Boris Zbarsky [:bzbarsky]]

Before I start reading through the details (which is likely to take a few weeks, to be honest) I have two questions:

1)  What determined the choice of buffer size?
2)  Is there a reason you're not using ReadSegments?

Comment 42

[Michal Novotny [:michal]]

(In reply to comment #41)
> Before I start reading through the details (which is likely to take a few
> weeks, to be honest) I have two questions:
> 
> 1)  What determined the choice of buffer size?
> 2)  Is there a reason you're not using ReadSegments?

My patch is derived from #112107 and I didn't change this part of code. Code that use ReadSegments was there but it was commented out.

Comment 43

[Boris Zbarsky [:bzbarsky]]

It seems to me that using ReadSegments would be a good idea: avoid extra copying of the buffer, etc...

If we don't plan to do that, I can look at the patch as-is, but otherwise it doesn't make sense to review this and then review a rewrite to use ReadSegments.

Note that attachment 112107 [details] [diff] [review] didn't use ReadSegments because it didn't work right for jar:, but that should be fixed now. 

Comment 44

[Michal Novotny [:michal]]

(In reply to comment #43)
> It seems to me that using ReadSegments would be a good idea: avoid extra
> copying of the buffer, etc...
> 
> If we don't plan to do that, I can look at the patch as-is, but otherwise it
> doesn't make sense to review this and then review a rewrite to use
> ReadSegments.

OK, don't do the review. I'll rewrite it.

> Note that attachment 112107 [details] [diff] [review] didn't use ReadSegments because it didn't work
> right for jar:, but that should be fixed now. 

You mean that it didn't work parsing properties file located in JAR file?

Comment 45

[Boris Zbarsky [:bzbarsky]]

Using ReadSegments back then wouldn't have worked for parsing properties files in a jar, yeah.  It should work now.

Comment 46

[Michal Novotny [:michal]]

Attachment: unit test v3

test at the buffer boundary wasn't actually at the boundary

Comment 47

[Michal Novotny [:michal]]

Attachment: patch v4

ReadSegments() is used for reading file.

Comment 48

[Mike Schroepfer]

Adding this to the 1.9.1 train - we could use help with start time...

Comment 49

[TimoT]

the ReadSegments() patch fails to build for me on VS 2008

DMOZILLA_SKIN_VERSION=\"1.8\"  -D_MOZILLA_CONFIG_H_ -DMOZILLA_CLIENT /e/mozilla-
build/mozilla/src/xpcom/ds/nsPersistentProperties.cpp
nsPersistentProperties.cpp
e:/mozilla-build/mozilla/src/xpcom/ds/nsPersistentProperties.cpp(525) : error C2
664: 'nsIUnicharInputStream::ReadSegments' : cannot convert parameter 1 from 'ns
result (__cdecl *)(nsIUnicharInputStream *,void *,const PRUnichar *,PRUint32,PRU
int32,PRUint32 *)' to 'nsWriteUnicharSegmentFun'
        None of the functions with this name in scope match the target type
e:/mozilla-build/mozilla/src/xpcom/ds/nsPersistentProperties.cpp(526) : fatal er
ror C1903: unable to recover from previous error(s); stopping compilation
make[6]: *** [nsPersistentProperties.obj] Error 2
make[6]: Leaving directory `/e/mozilla-build/mozilla/src/ff-opt/xpcom/ds'

Comment 50

[Boris Zbarsky [:bzbarsky]]

SegmentWriter should be an NS_METHOD.

I'm going to try to get to this review as soon as I'm done moving and stuff, so in about 3 weeks...  I might be able to do before then, but not sure.

Comment 51

[Michal Novotny [:michal]]

Attachment: patch v5

(In reply to comment #49)
> the ReadSegments() patch fails to build for me on VS 2008

I don't have VS 2008. Can you please test this new patch, if it compiles successfully?

Comment 52

[TimoT]

(In reply to comment #51)
> I don't have VS 2008. Can you please test this new patch, if it compiles
> successfully?

Yeah, this one compiles without problems.

Comment 53

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 325534 [details] [diff] [review]
patch v5

>Index: xpcom/ds/nsPersistentProperties.cpp
>+  static NS_METHOD SegmentWriter(nsIUnicharInputStream* aStream,
>+                                void* aClosure,

Fix the indentation here and for the remaining args to this method?

>+  PRBool ParseValueCharacter(PRUnichar c, const PRUnichar* cur,
>+                             const PRUnichar* &tokenStart, nsAString& oldValue);

Might be nice to document the args (especially the inout ones!).

>+  PRBool    mMultiLineCanSkipN; // TRUE if "\\\r" was detected

Isn't it true just if you hit '\r'?

>+inline PRBool IsWhiteSpace(PRUnichar aChar)
>+  return (((aChar) == ' ') || ((aChar) == '\t') ||
>+          ((aChar) == '\r') || ((aChar) == '\n'));

That's overparenthesized (a legacy of its past as a macro?).  Remove the extra parens around aChar throughout?

>+inline PRBool IsEOL(PRUnichar aChar)

Same here.

>+PRBool nsPropertiesParser::ParseValueCharacter(
>+      // handle multilines - since this is the beginning of a line,

How do we know this is the beginning of a line?

>+      // ignore sequential line endings

You mean ignoring \n after \r?  Or something else?

>+        // if this will be at the buffer, characters from tokenStart to end

I'm not sure what the part before the comma means here.

>+        if (c == ' ' || c == '\t') {
>+          // don't allow another '\n' to be skipped
>+          mMultiLineCanSkipN = PR_FALSE;
>+        // if this will be at the buffer, characters from tokenStart to end
>+        // are appended at the end of ParseBuffer()
>+        tokenStart = cur+1;
>+          break;
>+        }

Please fix the indentation.  And again, what does the part before the comma mean?

>+      }
>+      break;
>+    }
>+    break;

That doesn't make sense to me.  Why have the inner break?

>+NS_METHOD nsPropertiesParser::SegmentWriter(nsIUnicharInputStream* aStream,
>+  parser->ParseBuffer(aFromSegment + aToOffset, aCount);

This is wrong.  The first argument should just be aFromSegment.

>+nsresult nsPropertiesParser::ParseBuffer(const PRUnichar* aBuffer,
>+  // points the start/end of the current key or value

"points to"?

>+        // no value at all! mimic the normal value-ending4

What's with the '4' there?

>+  if (mState == eParserState_Value && tokenStart &&
>+      mSpecialState == eParserSpecial_None)
>+    mValue += Substring(tokenStart, cur);
>+  // if we're still parsing the key, then append whatever we have..
>+  else if (mState == eParserState_Key && tokenStart)
>+    mKey += Substring(tokenStart, cur);

This would be a lot easier to read with curlies around the if/else bodies.

>+  while (NS_SUCCEEDED(mIn->ReadSegments(nsPropertiesParser::SegmentWriter, &parser, 2048, &nProcessed)) &&
>+         nProcessed != 0);

I'd use either 4096 or just whateve the stream claims is available, really (or the max of the two).  The fewer function calls and bouncing around on the stack, the better.

>-  mIn->Close();
>-  NS_RELEASE(mIn);

Shouldn't you still close and null out mIn?  What's the benefit of keeping it open?

sr=bzbarsky with these comments addressed.  I'm sorry for the lag....

Comment 54

[Michal Novotny [:michal]]

Attachment: patch v6

(In reply to comment #53)
> >+  PRBool    mMultiLineCanSkipN; // TRUE if "\\\r" was detected
> 
> Isn't it true just if you hit '\r'?

No, it is set to true when mSpecialState == eParserSpecial_Escaped in following case:

    case '\r':
    case '\n':
      mHaveMultiLine = PR_TRUE;
      mMultiLineCanSkipN = (c == '\r');
      mSpecialState = eParserSpecial_None;
      break;

It is really true only when "\\\r" was found.

> >+NS_METHOD nsPropertiesParser::SegmentWriter(nsIUnicharInputStream* aStream,
> >+  parser->ParseBuffer(aFromSegment + aToOffset, aCount);
> 
> This is wrong.  The first argument should just be aFromSegment.

I don't think it is wrong, but it is unnecessary. aToOffset is always 0 because SegmentWriter() consumes always all available data.

> >+  while (NS_SUCCEEDED(mIn->ReadSegments(nsPropertiesParser::SegmentWriter, &parser, 2048, &nProcessed)) &&
> >+         nProcessed != 0);
> 
> I'd use either 4096 or just whateve the stream claims is available, really (or
> the max of the two).  The fewer function calls and bouncing around on the
> stack, the better.

Method available() isn't present in interface nsIUnicharInputStream, so I've changed it to 4096. I've also added error handling to this code and it fixes problem mentioned in comment #39.

Comment 55

[Michal Novotny [:michal]]

Attachment: unit test v4

test at the buffer boundary was moved to proper offset, because buffer size was increased from 2048 to 4096

Comment 56

[Boris Zbarsky [:bzbarsky]]

> No, it is set to true when mSpecialState == eParserSpecial_Escaped

Ah, ok.  Gotcha.

> Method available() isn't present in interface nsIUnicharInputStream

Indeed.  <sigh>.  Maybe file a bug about that?  It could be useful...

Comment 57

[Boris Zbarsky [:bzbarsky]]

> That doesn't make sense to me.  Why have the inner break?

I finally figured it out; the weird indent confused me...

I'll restore this when I land the patch.

Comment 58

[Boris Zbarsky [:bzbarsky]]

Pushed changeset cc82f602d986.  Michal, thanks for picking this up!

Comment 59

[Boris Zbarsky [:bzbarsky]]

Doesn't seem to have obviously improved Ts, though.  :(

Comment 60

[Dave Townsend [:mossop]]

I've backed this out as part of the investigation into bug 450401

Comment 61

[Justin Dolske [:Dolske]]

Relanded.