New issue
Advanced search Search tips

Issue 687230 link

Starred by 1 user

Issue metadata

Status: Fixed
Owner:
Closed: Feb 2017
Cc:
Components:
EstimatedDays: ----
NextAction: ----
OS: ----
Pri: 3
Type: Bug



Sign in to add a comment

ServiceWorkerURLRequestJob::CreateResponseHeader() is inefficient.

Project Member Reported by xunji...@chromium.org, Jan 31 2017

Issue description

ServiceWorkerURLRequestJob::CreateResponseHeader() is inefficient when there are a large number of response headers. In my local debugging, google servers can send hundreds of experiment ids, so we can end up with ~500 pairs of response headers. HttpResponseHeaders::AddHeader() has a bad performance O(n^2).

We should move away from using HttpResponseHeaders::AddHeader in ServiceWorkerURLRequestJob. mmenke@ suggested that the simplest approach is to just create a single full bogus HTTP/1.x response headers string, and pass that into HttpUtil::AssembleRawHeaders, and then pass the result of that to HttpResponseHeaders().  Or, perhaps better, do what the disk cache does and create a pickle from the HttpResponseHeaders, and use that to re-constitute the headers (The latter won't work with old ServiceWorker cache files, presumably, which wouldn't be great)


An example of such a header is:
["x-google-experiment"] = "17259,750339,750721,751571,1351459,1351563,1351587,1351702,1351810,1351830,1351860,1351903,1352026,1352048,1352081,1352114,1352174,1352193,1352206,1352219,1352241,1352247,1352274,1352277,1352293,13523"...


----------------------------------------------------------
void ServiceWorkerURLRequestJob::CreateResponseHeader(
    int status_code,
    const std::string& status_text,
    const ServiceWorkerHeaderMap& headers) {
  // TODO(kinuko): If the response has an identifier to on-disk cache entry,
  // pull response header from the disk.
  std::string status_line(
      base::StringPrintf("HTTP/1.1 %d %s", status_code, status_text.c_str()));
  status_line.push_back('\0');
  http_response_headers_ = new net::HttpResponseHeaders(status_line);
  for (ServiceWorkerHeaderMap::const_iterator it = headers.begin();
       it != headers.end();
       ++it) {
    std::string header;
    header.reserve(it->first.size() + 2 + it->second.size());
    header.append(it->first);
    header.append(": ");
    header.append(it->second);
    http_response_headers_->AddHeader(header);  <-- Can we avoid this?
  }
}
----------------------------------------------------------
 

Comment 1 by mmenke@chromium.org, Jan 31 2017

Note that the case where performance is really bad here is when there are a lot of AddHeader calls, so one AddHeader call with a bunch of commas isn't the bad case, the base case is:

Exp-1:  foo,
Exp-2:  foo,
...
Exp-950: foo.

Performance is a bad O(n^2), at least, since each time it re-parses the entire header string.  Making one big string and passing it in is much more performant.

Comment 2 by kinuko@chromium.org, Jan 31 2017

Good catch, that's good to know...

I slightly prefer having something like HttpResponseHeaders::AddHeaders(...) that works efficiently for multiple headers, as it'd make more future code use that one instead.

Comment 3 by horo@chromium.org, Feb 10 2017

Status: Available (was: Untriaged)

Comment 4 by horo@chromium.org, Feb 10 2017

Owner: falken@chromium.org
Status: Assigned (was: Available)
falken@
Can you fix this problem?

Comment 5 by falken@chromium.org, Feb 13 2017

xunjieli@ do you still recommend to do this:
"just create a single full bogus HTTP/1.x response headers string, and pass that into HttpUtil::AssembleRawHeaders, and then pass the result of that to HttpResponseHeaders()" 
Yes, that's right. Either that or the pickle way.

Comment 7 by falken@chromium.org, Feb 14 2017

Status: Started (was: Assigned)
Project Member

Comment 8 by bugdroid1@chromium.org, Feb 15 2017

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/cd398136c4992574a2161d68acb39c716095eedd

commit cd398136c4992574a2161d68acb39c716095eedd
Author: falken <falken@chromium.org>
Date: Wed Feb 15 05:37:08 2017

service worker: Optimize response header creation.

HttpResponseHeaders::AddHeader has O(n^2) performance. Avoid using it.

I verified on Linux that constructing the headers from a
ServiceWorkerHeaderMap of 1000 headers goes from ~500ms to <1ms.

BUG= 687230 

Review-Url: https://codereview.chromium.org/2690333003
Cr-Commit-Position: refs/heads/master@{#450563}

[modify] https://crrev.com/cd398136c4992574a2161d68acb39c716095eedd/content/browser/service_worker/service_worker_url_request_job.cc
[modify] https://crrev.com/cd398136c4992574a2161d68acb39c716095eedd/content/browser/service_worker/service_worker_url_request_job_unittest.cc

Comment 9 by falken@chromium.org, Feb 15 2017

Labels: M-58
Status: Fixed (was: Started)

Sign in to add a comment