469767 - Very slow etags parsing

Status: RESOLVED FIXED

(Calendar :: Provider: CalDAV, defect)

Description

[Ludovic Marcotte]

User-Agent:       Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.0.4) Gecko/2008102920 Firefox/3.0.4
Build Identifier: Lightning 0.9

When it comes to handling a massive (say, 5000) number of etags, Lightning is simply too slow.

Two things can be done to dramatically improve the situation. The first thing is to use a SAX-based parser. To do that, one simply has to define the following handler in calDavCalendar.js :

function cdHandler() {
}

cdHandler.prototype = {
 aRefreshEvent: null,
 calendar: null,
 count: 0,
 index: 0,
 
 characters: function characters(value) {
    if (this.inGetEtag) {
      this.etag += value;
    } else if (this.inHref) {
      this.href += value;
    } else if (this.inStatus) {
      this.status += value;
    }
  },
 startDocument: function startDocument() {
    this.inResponse = false;
    this.inHref = false;
    this.inGetEtag = false;
    this.inStatus = false;
    this.count = 0;
    this.index = 0;
  },
 endDocument: function endDocument() {
  },
 startElement: function startElement(uri, localName, qName, attributes) {
    if (localName == "response") {
      this.inResponse = true;
      this.href = "";
      this.etag = "";
      this.status = "";
    } else if (localName == "href") {
      this.inHref = true;
    } else if (localName == "getetag") {
      this.inGetEtag = true;
    } else if (localName == "status") {
      this.inStatus = true;
    }
  },
 
 endElement: function endElement(uri, localName, qName) {
    if (localName == "response") {
      if (this.status.indexOf(" 200") > 0
	  && this.etag.length
	  && this.href.length) {
	
	var href = this.href;
	
	if (this.count == 0) {
	  href = this.calendar.ensurePath(this.href).toString();
	  if (href != this.href) {
	    this.index = this.href.indexOf(href);
	  }
	}
	else if (this.index > 0) {
	  href = href.substr(this.index);
	}
	  	  
	this.aRefreshEvent.itemsReported[href] = true;
	var itemuid = this.calendar.mHrefIndex[href];
	if (!itemuid
	    || (this.etag
		!= this.calendar.mItemInfoCache[itemuid].etag)) {
	  this.aRefreshEvent.itemsNeedFetching.push(href);
	}
      }
      this.count++;
      this.inResponse = false;
    } else if (localName == "href") {
      this.inHref = false;
    } else if (localName == "getetag") {
      this.inGetEtag = false;
    } else if (localName == "status") {
      this.inStatus = false;
    }
  },
 startPrefixMapping: function startPrefixMapping(prefix, uri) {
  },
 endPrefixMapping: function endPrefixMapping(prefix) {
  },
 ignorableWhitespace: function ignorableWhitespace(whitespace) {
  },
 processingInstruction: function processingInstruction(target, data) {
  },
 
 QueryInterface: function QueryInterface(aIID) {
    return doQueryInterface(this, cdHandler.prototype, aIID,
			    [Components.interfaces.nsISAXContentHandler]);
  }
};

Then, in getUpdatedItems(), we replace the following slow code:

                var multistatus = new XML(str);
                for (var i = 0; i < multistatus.*.length(); i++) {
                    var response = new XML(multistatus.*[i]);
                    var etag = response..D::["getetag"];
                    if (etag.length() == 0) {
                        continue;
                    }
                    var href = response..D::["href"];
                    var resourcePath = thisCalendar.ensurePath(href);
                    aRefreshEvent.itemsReported.push(resourcePath.toString());

                    var itemuid = thisCalendar.mHrefIndex[resourcePath];
                    if (!itemuid || etag != thisCalendar.mItemInfoCache[itemuid].etag) {
                        aRefreshEvent.itemsNeedFetching.push(resourcePath);
                    }
                }

with our handler :

	      var parser =
	      Components.classes["@mozilla.org/saxparser/xmlreader;1"]
	      .createInstance(Components.interfaces.nsISAXXMLReader);
	      var handler = new cdHandler();
	      parser.contentHandler = handler;
	      handler.aRefreshEvent = aRefreshEvent;
	      handler.calendar = thisCalendar;
	      parser.parseFromString(str, "application/xml");

This will actually be 2x to 3x faster.

The second thing that can be done to improve the situation is to replace the O(N^2) loop that compares etags (for deleted items) with something faster that uses a hash. So we replace :

                    // if an item has been deleted from the server, delete it here too
                    for (var path in thisCalendar.mHrefIndex) {
                        if (aRefreshEvent.itemsReported.indexOf(path) < 0 &&
                            path.indexOf(aRefreshEvent.uri.path) == 0) {

with:

                    // if an item has been deleted from the server, delete it here too
                    for (var path in thisCalendar.mHrefIndex) {
		         if (aRefreshEvent.itemsReported[path] != true && 
			     path.indexOf(aRefreshEvent.uri.path) == 0) {


During my testing, parsing 5000 etags (in getUpdatedItems()) and doing the comparison was taking 10-12 seconds on my fast machine. During that time, Lightning was totally blocked.

With the new handler and a faster comparison method, we're now under 1.5s.



Reproducible: Always

Steps to Reproduce:
1.
2.
3.

Comment 1

[Simon Paquet [:sipaq]]

This should block if it gets confirmed.

Comment 2

[Daniel Boelzle [:dbo]]

Ludovic, please post patches/code as attachments.
I am windering: The returned xml is not very complex, most of the data is covered by the ics-parser. Why is SAX based parsing really that faster (2-3 times) in this scenario than e4x DOM parsing? Is this true for trunk, too?

Comment 3

[Philipp Kewisch [:Fallen][☁️📆]]

Attachment: Fix - v1

Aside from performance improvements using the sax parser also greatly simplifies calDavCalendar.js code.

Comment 4

[Daniel Boelzle [:dbo]]

Comment on attachment 359485 [details] [diff] [review]
Fix - v1

looks good, let's give it a try; r=dbo

Comment 5

[Philipp Kewisch [:Fallen][☁️📆]]

Pushed to comm-central <http://hg.mozilla.org/comm-central/rev/50e56618c6ec>

-> FIXED

Comment 6

[Bruno Friedmann]

This has introduced a problem with delete.
see #519225

Comment 7

[Bruno Friedmann]

This has not improved performance as shown in #530423