code review 6843056: net/http, net/textproto: cache common header values

net/http, net/textproto: cache common header values

We use a small, automatically updated cache of recently
seen values in order to avoid allocations for values
like "keep-alive" and "close".

benchmark                          old ns/op    new ns/op    delta
BenchmarkHeaderWriteSubset              2215         2284   +3.12%
BenchmarkClientServer                 360168       382181   +6.11%
BenchmarkClientServerParallel4        382254       371981   -2.69%
BenchmarkClientServerParallel64       319201       304283   -4.67%
BenchmarkServer                       336708       327858   -2.63%

benchmark                         old allocs   new allocs    delta
BenchmarkHeaderWriteSubset                 2            2    0.00%
BenchmarkClientServer                    114          105   -7.89%
BenchmarkClientServerParallel4           114          105   -7.89%
BenchmarkClientServerParallel64          115          106   -7.83%
BenchmarkServer                           36           32  -11.11%

Benchmarks in net/textproto:

benchmark                  old ns/op    new ns/op    delta
BenchmarkReadMIMEHeader        11302        10785   -4.57%
BenchmarkUncommon               1851         1777   -4.00%

benchmark                 old allocs   new allocs    delta
BenchmarkReadMIMEHeader           25           19  -24.00%
BenchmarkUncommon                  5            4  -20.00%

[bradfitz, 2012-11-14 17:13:34]

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader.go
File src/pkg/net/textproto/reader.go (right):

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:595: str    string
s is probably enough

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:598: type stringCache [100]entry
stringPool

document what 100 is.  maybe give it a constant and document its meaning (max
cached length).  I might drop down to the length of a date header.  more like
20-40.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:600: func compare(x []byte, y string) bool {
compare generally returns -1, 0, 1.  I'd name this "equal" or "eq"

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:601: for i, b := range x {
redundant, but I'd add:

if len(b) != len(s) {
   return false
}

... in case any other place uses this without realizing the lengths must be
equal.  I doubt it'd matter for performance to check.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:610: if len(x) < len(sc) {
if len(x) >= len(sc) {
     return string(x)
}
// unindent

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:614: if it.str == "" || it.misses > 9 {
where did 9 come from?  just making the microbenchmark fast?  if you have to
convert to a string anyway, why wouldn't you just always populate it.str?

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:623: // this is not threadsafe, but we are only
no non-threadsafe code will be accepted.  it will break our race builder and
other tools.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:630: var theStringCache = stringCache{}
var valuePool stringPool  (no need to assign it a zero value)

[jeff.allen, 2012-11-15 10:50:01]

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader.go
File src/pkg/net/textproto/reader.go (right):

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:595: str    string
On 2012/11/14 17:13:34, bradfitz wrote:
> s is probably enough

Done.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:598: type stringCache [100]entry
I'm going to capture a trace from a webserver and see if there's evidence for a
certain cutoff from looking at the length distributions. The downside of
accidentally tuning this too high is very small, though.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:600: func compare(x []byte, y string) bool {
On 2012/11/14 17:13:34, bradfitz wrote:
> compare generally returns -1, 0, 1.  I'd name this "equal" or "eq"

Done.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:601: for i, b := range x {
On 2012/11/14 17:13:34, bradfitz wrote:
> redundant, but I'd add:
> 
> if len(b) != len(s) {
>    return false
> }
> 
> ... in case any other place uses this without realizing the lengths must be
> equal.  I doubt it'd matter for performance to check.

Done.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:610: if len(x) < len(sc) {
On 2012/11/14 17:13:34, bradfitz wrote:
> if len(x) >= len(sc) {
>      return string(x)
> }
> // unindent

Done.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:614: if it.str == "" || it.misses > 9 {
I guessed it. I need to analyze a real webserver trace to find the right number
for this.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:623: // this is not threadsafe, but we are only
OK, I understand. I'll talk to Dmitry to find out what the correct way is to
code this lock-free; this data structure does not need, and should not have a
lock in it (part of why I chose it).

I'll send it out to all when I've got the tuning done and this locking problem
solved.

https://codereview.appspot.com/6843056/diff/1002/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:630: var theStringCache = stringCache{}
On 2012/11/14 17:13:34, bradfitz wrote:
> var valuePool stringPool  (no need to assign it a zero value)

Done.

[dvyukov, 2012-11-15 11:33:15]

https://codereview.appspot.com/6843056/diff/7001/src/pkg/net/textproto/reader.go
File src/pkg/net/textproto/reader.go (right):

https://codereview.appspot.com/6843056/diff/7001/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:642: sc[len(x)].s = s
That will crash and corrupt memory.

Even an "innocent" race on the miss count can lead to arbitrary behavior,
including security exploits (especially with gccgo).

But this breaks more obviously. String consists of 2 words, that are
read/written non atomically. Consider that one goroutine assigns new string to
sc[i].s, and another goroutine reads the string on line 634. Imagine that the
second goroutine reads len 100, but nil char ptr. Bang!

[dvyukov, 2012-11-15 11:44:16]

https://codereview.appspot.com/6843056/diff/7001/src/pkg/net/textproto/reader.go
File src/pkg/net/textproto/reader.go (right):

https://codereview.appspot.com/6843056/diff/7001/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:642: sc[len(x)].s = s
On 2012/11/15 11:33:15, dvyukov wrote:
> That will crash and corrupt memory.
> 
> Even an "innocent" race on the miss count can lead to arbitrary behavior,
> including security exploits (especially with gccgo).
> 
> But this breaks more obviously. String consists of 2 words, that are
> read/written non atomically. Consider that one goroutine assigns new string to
> sc[i].s, and another goroutine reads the string on line 634. Imagine that the
> second goroutine reads len 100, but nil char ptr. Bang!

You can do some shortcuts with sync/atomic package. E.g. you can freely
manipulate miss counter with atomic.Load/Store(), that will give you roughly the
same performance, but prevent security exploits (and make the race detector
happy). You can manipulate string in atomic fashion if you use *string (but that
will require unsafe).

[dvyukov, 2012-11-15 11:50:02]

On 2012/11/15 11:44:16, dvyukov wrote:
>
https://codereview.appspot.com/6843056/diff/7001/src/pkg/net/textproto/reader.go
> File src/pkg/net/textproto/reader.go (right):
> 
>
https://codereview.appspot.com/6843056/diff/7001/src/pkg/net/textproto/reader...
> src/pkg/net/textproto/reader.go:642: sc[len(x)].s = s
> On 2012/11/15 11:33:15, dvyukov wrote:
> > That will crash and corrupt memory.
> > 
> > Even an "innocent" race on the miss count can lead to arbitrary behavior,
> > including security exploits (especially with gccgo).
> > 
> > But this breaks more obviously. String consists of 2 words, that are
> > read/written non atomically. Consider that one goroutine assigns new string
to
> > sc[i].s, and another goroutine reads the string on line 634. Imagine that
the
> > second goroutine reads len 100, but nil char ptr. Bang!
> 
> You can do some shortcuts with sync/atomic package. E.g. you can freely
> manipulate miss counter with atomic.Load/Store(), that will give you roughly
the
> same performance, but prevent security exploits (and make the race detector
> happy). You can manipulate string in atomic fashion if you use *string (but
that
> will require unsafe).

I think you can make it work if you use

type stringCache [maxCachableLen]*entry

and then only atomic.Store/Load to manipulate the pointer, and atomic.Store/Load
to manipulate the miss count.

[dvyukov, 2012-11-15 11:53:05]

https://codereview.appspot.com/6843056/diff/7001/src/pkg/net/textproto/reader.go
File src/pkg/net/textproto/reader.go (right):

https://codereview.appspot.com/6843056/diff/7001/src/pkg/net/textproto/reader...
src/pkg/net/textproto/reader.go:650: sc[len(x)].miss = 0
You better not update it if it's already 0, it will cause excessive contention
between parallel threads.

[jeff.allen, 2012-11-15 15:54:54]

Cool, my mental model was that a string assign is atomic.

I'm going to play around with simple mutexes first to see the performance impact
before going for the exotic stuff. But your final suggestion (type stringCache
[maxCachableLen]*entry) is also quite nice, maybe I should skip straight to
that.

I try to be really sensitive to performance with these "use less memory" changes
because it seems to me that it is much better to have "this is faster AND causes
fewer GCs" than "this takes a bit of time but causes fewer GCs, so we make it up
in the end".

[dvyukov, 2012-11-15 16:13:57]

On Thu, Nov 15, 2012 at 7:54 PM, <jeff.allen@gmail.com> wrote:

> Cool, my mental model was that a string assign is atomic.
>
>

It's not only about atomicity. Even if a word load/store are atomic, there
are also memory access ordering issues. A goroutine can atomically read the
correct string pointer, but then read garbage data from it. Consider that
that garbage data incidentally passes you eq check, and you return that
pointer; but then user reads through the pointer and sees completely
different data. Ouch.

And there are also compiler optimization issues (especially with gccgo). It
basically means that if you have "innocent" racy statistics counters, your
program can execute arbitrary code.




> I'm going to play around with simple mutexes first to see the
> performance impact before going for the exotic stuff. But your final
> suggestion (type stringCache [maxCachableLen]*entry) is also quite nice,
> maybe I should skip straight to that.
>
> I try to be really sensitive to performance with these "use less memory"
> changes because it seems to me that it is much better to have "this is
> faster AND causes fewer GCs" than "this takes a bit of time but causes
> fewer GCs, so we make it up in the end".
>
>
https://codereview.appspot.**com/6843056/<https://codereview.appspot.com/6843...
>

[jeff.allen, 2012-11-16 15:21:41]

Hello bradfitz@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go

[dfc, 2012-11-20 09:18:35]

Hi Jeff,

Thanks for this proposal. I don't think the performance gain here is worth the
extra code and extra bookkeeping overhead, so i'm -1 on this proposal.

Cheers

Dave

https://codereview.appspot.com/6843056/diff/13001/src/pkg/net/http/request.go
File src/pkg/net/http/request.go (right):

https://codereview.appspot.com/6843056/diff/13001/src/pkg/net/http/request.go...
src/pkg/net/http/request.go:453: defer tpFree.put(tp)
The defer costs you an allocation so I don't think this is a net saving.

https://codereview.appspot.com/6843056/diff/13001/src/pkg/net/http/response.go
File src/pkg/net/http/response.go (right):

https://codereview.appspot.com/6843056/diff/13001/src/pkg/net/http/response.g...
src/pkg/net/http/response.go:107: defer tpFree.put(tp)
see previous

[bradfitz, 2012-11-20 18:01:26]

It's easy to write a benchmark that makes a particular optimization look
good.

I agree with Dave that this is complicated and weird.  Re-using readers
from http might be a good idea (which could be its own CL, if that
matters), but why would each reader have its own valueCache?  Just to avoid
some locking?  I feel like that should be noise compared to GC costs, if
this really saves on that.


On Fri, Nov 16, 2012 at 7:21 AM, <jeff.allen@gmail.com> wrote:

> Hello bradfitz@golang.org (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://code.google.com/p/go
>
>
>
http://codereview.appspot.com/**6843056/<http://codereview.appspot.com/6843056/>
>

[jeff.allen, 2012-11-21 09:42:19]

I agree that it feels like this change is messy.

The performance improvement from reducing garbage comes long after the function
in question is complete. It is hard to measure it, and it is only a win in bulk.
So as I work on reducing garbage, I make it a goal that the function should get
faster as well. That way, the wins are guaranteed: the function is faster
(immediate payoff) AND there's less trash (long-term payoff).

I think I need to build a bit of infrastructure to quantify the GC cost
reduction so that I can make better decisions about the justifiable costs
increases.

Stay tuned. :)