86582 - Color parsing can be faster

Status: RESOLVED INVALID

(Core :: DOM: Core & HTML, defect)

Description

[Daniel Bratell]

All the time in |ParseColor| and descendants is spent doing not so needed string
operations. By using iterators instead of strings, that time would be gone and
color parsing would be a noop.

The time right now (or after another related patchs is checked in) is less than
0.5% of the time for the color intensive table stress case so this is nickle and
dime kind of work.

Comment 1

[Daniel Bratell]

This was not as straightforward as I had hoped. Using iterators over a 
nsDependentSubstring is just too expensive. It turns out to be much faster to 
copy the relevant data to a char buffer and work with that. 

I guess it's the multi fragment stuff that makes iterators so slow. In Quantify 
I see a lot of normalize_forward(). 

So what I did was to change the NS_HexToRGB, NS_LooseHexToRGB and 
NS_ColorNameToRGB to take an nsAString so that callers can use Substrings when 
calling them. That makes the lives a little easier for the callers, but the 
color functions a little slower. The net result is a win of about 50%. Not 
nearly as good as I had expected, and part of that win is the result of 
rewriting with the knowledge that we only handles 1 or 2 chars per color in a 
color value.

Comment 2

[Daniel Bratell]

scc, is there a way to, without breaking the abstraction, get fast iterators 
over an nsAString? I _know_ that the buffer is a single flat fragment because 
the buffer comes from an nsAutoString originally so I don't need all the fancy 
_move the iterator between fragments_ code.

It feels so wrong that I can get better performance from copying all the data to 
a local char buffer, than I get when just iterating once over the data with 
iterators.

Comment 3

[Scott Collins]

There are several ways to exploit the knowledge that you are working with a
single fragment string and do faster parsing from there.

  1) You could use |PromiseFlatCString| to get a raw pointer
  2) You could write your parser as a character sink that is handed each hunk
       in turn (works even for multi-fragment strings, if you maintain state)
  3) You could overload your parsing routine so that you have two entry points,
       one for |nsAFlatCString|s, one for |nsACString|s, the flat version would
       use pointers for iterators

All three of these schemes are significantly better than copying the data to a
separate flat buffer in the case that the data already is a single fragment. 
Option 1 is probably the easiest to write, and parallels the solution you are
currently considering.  Option 2 is the most efficient in code (fewer
implementations, but still generally applicable).  In the not too distant
future, |nsAFlatC?String|s will redefine iterators for themselves to be simple
pointers, so when you have knowledge of the class' static type, iteration can be
more efficient.  At that time, option 3 is easily achieved with a template
function implemenation.

Comment 4

[Daniel Bratell]

My strings really interact in a bad way. I really liked the solution in number 
1, but unfortunately nsDependentSubstring doesn't declare a GetFlatBuffer (since 
it doesn't know anything about its buffer I presume) so I end up allocating 
10000 strings (for the test case) which is a magnitude slower then copying to a 
local buffer. 

2 requires redesign of the users I guess and I'm not sure I understand what you 
really mean. 

3 looks good but unfortunately (that word again) the functions are in a 
interface declared export "C". No overloading there. 

I could let the callers use the original string if they detect that the 
substring is identical with the original string (no whitespace stripped), but I 
don't like that "hacky" solution. Suddenly the callers must know that stripped 
strings bring crappy performance.

Back to the nsDependentSubstring. I assume that the problem there is that the 
underlying buffer is limited by two pointers, and not necessarily ended with a 
null char...

Anyway, a nsPromiseFlat[C]String should be very local, right? Then, shouldn't it 
used a stack based buffer? That would make it at efficient as my "copy to a char 
 array" solution?

Comment 5

[Scott Collins]

no, an |PromiseFlatC?String| does not use a stack-based buffer.  The theory is
if it were small, it would already be flat.  Some re-working needs to be done to
change some of the notions of `flat' to the looser requirements of
single-fragment.  Since optimizations are applicable starting at that level. 
Maybe I need a |PromiseSingleFragmentC?String|.

However, option 2 is the thing you want.  There are several ways to get this
without changing your current interface.  You can make a private sink which you
use inside your parse routine, or you can directly iterate over the chunks.  Get
an iterator to the beginning and one to the end and use |size_forward|,
|SameFragment| et al, to determine how much of the current fragment to use. 
Doing it by hand will not be more efficient than writing your own sink, and it
ends up being more complex in code, so I recommend you write a sink.  Then your
parse routine looks like this

  result_type
  NS_XtoY( const nsACString& aSource )
    {
      ConvertXtoY converter;

      nsReadingIterator start, end;
      copy_string(aSource.BeginReading(start),
                  aSource.EndReading(end),
                  converter);
      return converter.GetResult();
    }

|copy_string| will be |inline|d, so this is just like iterating over the chunks
yourself if you make your |ConvertXtoY::write| function |inline| as well. 
Inside your sink, you repeatedly get called with a raw character pointer and a
length.  Usually (according to your analysis) this will be the entire call, just
one hunk.  Within that call, you'll use raw pointers to do your parsing with
(but you can probably just re-use the code that was using iterators, it's
probably close to source compatible).

Comment 6

[Daniel Bratell]

A sink worked fine. The times (which some weeks ago were ~70000 us) are down to 
~7000 us from ~17000 us and I don't think I can get it any faster without 
starting doing really obscure optimizations. Switching to pointer iterators will 
benefit this code though. 

I will attach a patch. I don't know who should review it, but I guess at 
kmcclusk since this is under gfx. This is not a high priority patch, but I would 
appreciate a review so that I can get it off my plate so that I can start 
looking at other microseconds to remove. :-)

Comment 7

[Daniel Bratell]

Attachment: Patch that makes color parsing three times faster (#1)

Comment 8

[mmc]

This bug has a ~4 years old patch that's never been reviewed.

Comment 9

[[e-mail]]

The referred code being so old and having since been rewritten I doubt there's
any longer any gain possible through application of this patch.