cURL / Mailing Lists / curl-library / Single Mail

curl-library

Re: [PATCH v3] rawstr: Speed up Curl_raw_toupper by 40%

From: Tim Ruehsen <tim.ruehsen_at_gmx.de>
Date: Tue, 03 Nov 2015 12:41:23 +0100

On Tuesday 03 November 2015 12:11:28 Lauri Kasanen wrote:
> > Thanks for alerting us about this!
> >
> > I found this case so intersting I ran my own test. I ran the function
> > over 500MB of data from /dev/urandom and on this test data I could see
> > a slightly better than 40% performance gain (with gcc -O3 on my 3.5GHz
> > Intel i7 CPU).
> >
> > Still: "This was causing a two-second startup delay"
> > seems unlikely. I could run the unoptimized version through 500MB of
> > data in 1.5 seconds, and surely any sensible cookie use cases would be
> > several magnitudes away of that?
>
> Hi,
>
> I have less than 1mb of cookies, 9203 according to wc -l. The timing
> wasn't scientifically exact, but my senses aren't that far off to
> mistake 0.something to 2 ;)
>
> When I ran oprofile on just the app startup, curl was using 90% of cpu,
> most of it in Curl_add_cookie and Curl_raw_equal. After this change,
> Curl_raw_equal dropped from 55% to 29%. (function names from memory)
>
> I could also separate the delay to curl by starting to an empty tab
> instead of a web page: the delay would appear as soon as I wrote an
> address and pressed enter, ie at the first invocation of curl code.
>
> Now with this change, the startup delay has approximately halved, to
> about one sec. I'm running on a Phenom 2. I didn't delve deep into the
> cookie code, but it seems every cookie's every field is matched against
> every other's on a quick look. 10k ^ 2 = 100M checks, times the number
> of fields.

Curl uses a linked list for cookies. That's fine when you have just a bunch of
entries. Adding an entry takes O(n^2). Using a hash table would reduce it to
O(n). In other words: if 10k entries now take 1s, with a hashtable it would be
(best case) 0.1ms. With a bunch of overhead per entry (a constant factor to be
multiplied to the 0.1ms), let's say it is 1ms for 10k entries.

Curl has a hash API, so it should be straight forward to improve the cookie
code.

Tim

-------------------------------------------------------------------
List admin: http://cool.haxx.se/list/listinfo/curl-library
Etiquette: http://curl.haxx.se/mail/etiquette.html
Received on 2015-11-03