)]}'
{
  "commit": "94e44a9c8edb64f514b6f3b7f7001db0cfeb2d70",
  "tree": "7ed98e7ebfaf6da5846c96995284e1a2097e12c3",
  "parents": [
    "2abd91e26564bd5ddd364b11e74e050a72766339"
  ],
  "author": {
    "name": "Josh Bleecher Snyder",
    "email": "josharian@gmail.com",
    "time": "Tue Apr 18 15:23:24 2017 -0700"
  },
  "committer": {
    "name": "Josh Bleecher Snyder",
    "email": "josharian@gmail.com",
    "time": "Wed Apr 19 13:47:28 2017 +0000"
  },
  "message": "runtime: preallocate some overflow buckets\n\nWhen allocating a non-small array of buckets for a map,\nalso preallocate some overflow buckets.\n\nThe estimate of the number of overflow buckets\nis based on a simulation of putting mid\u003d(low+high)/2 elements\ninto a map, where low is the minimum number of elements\nneeded to reach this value of b (according to overLoadFactor),\nand high is the maximum number of elements possible\nto put in this value of b (according to overLoadFactor).\nThis estimate is surprisingly reliable and accurate.\n\nThe number of overflow buckets needed is quadratic,\nfor a fixed value of b.\nUsing this mid estimate means that we will overallocate a few\ntoo many overflow buckets when the actual number of elements is near low,\nand underallocate significantly too few overflow buckets\nwhen the actual number of elements is near high.\n\nThe mechanism introduced in this CL can be re-used for\nother overflow bucket optimizations.\n\nFor example, given an initial size hint,\nwe could estimate quite precisely the number of overflow buckets.\nThis is #19931.\n\nWe could also change from \"non-nil means end-of-list\"\nto \"pointer-to-hmap.buckets means end-of-list\",\nand then create a linked list of reusable overflow buckets\nwhen they are freed by map growth.\nThat is #19992.\n\nWe could also use a similar mechanism to do bulk allocation\nof overflow buckets.\nAll these uses can co-exist with only the one additional pointer\nin mapextra, given a little care.\n\nname                  old time/op    new time/op    delta\nMapPopulate/1-8         60.1ns ± 2%    60.3ns ± 2%     ~     (p\u003d0.278 n\u003d19+20)\nMapPopulate/10-8         577ns ± 1%     578ns ± 1%     ~     (p\u003d0.140 n\u003d20+20)\nMapPopulate/100-8       8.06µs ± 1%    8.19µs ± 1%   +1.67%  (p\u003d0.000 n\u003d20+20)\nMapPopulate/1000-8       104µs ± 1%     104µs ± 1%     ~     (p\u003d0.317 n\u003d20+20)\nMapPopulate/10000-8      891µs ± 1%     888µs ± 1%     ~     (p\u003d0.101 n\u003d19+20)\nMapPopulate/100000-8    8.61ms ± 1%    8.58ms ± 0%   -0.34%  (p\u003d0.009 n\u003d20+17)\n\nname                  old alloc/op   new alloc/op   delta\nMapPopulate/1-8          0.00B          0.00B          ~     (all equal)\nMapPopulate/10-8          179B ± 0%      179B ± 0%     ~     (all equal)\nMapPopulate/100-8       3.33kB ± 0%    3.38kB ± 0%   +1.48%  (p\u003d0.000 n\u003d20+16)\nMapPopulate/1000-8      55.5kB ± 0%    53.4kB ± 0%   -3.84%  (p\u003d0.000 n\u003d19+20)\nMapPopulate/10000-8      432kB ± 0%     428kB ± 0%   -1.06%  (p\u003d0.000 n\u003d19+20)\nMapPopulate/100000-8    3.65MB ± 0%    3.62MB ± 0%   -0.70%  (p\u003d0.000 n\u003d20+20)\n\nname                  old allocs/op  new allocs/op  delta\nMapPopulate/1-8           0.00           0.00          ~     (all equal)\nMapPopulate/10-8          1.00 ± 0%      1.00 ± 0%     ~     (all equal)\nMapPopulate/100-8         18.0 ± 0%      17.0 ± 0%   -5.56%  (p\u003d0.000 n\u003d20+20)\nMapPopulate/1000-8        96.0 ± 0%      72.6 ± 1%  -24.38%  (p\u003d0.000 n\u003d20+20)\nMapPopulate/10000-8        625 ± 0%       319 ± 0%  -48.86%  (p\u003d0.000 n\u003d20+20)\nMapPopulate/100000-8     6.23k ± 0%     4.00k ± 0%  -35.79%  (p\u003d0.000 n\u003d20+20)\n\nChange-Id: I01f41cb1374bdb99ccedbc00d04fb9ae43daa204\nReviewed-on: https://go-review.googlesource.com/40979\nRun-TryBot: Josh Bleecher Snyder \u003cjosharian@gmail.com\u003e\nTryBot-Result: Gobot Gobot \u003cgobot@golang.org\u003e\nReviewed-by: Keith Randall \u003ckhr@golang.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "5243236f016230eba676705acad990e2640c9ebf",
      "old_mode": 33188,
      "old_path": "src/runtime/hashmap.go",
      "new_id": "0c9505e655be645473f95b078054e682ab07f24f",
      "new_mode": 33188,
      "new_path": "src/runtime/hashmap.go"
    }
  ]
}