1// Copyright 2017 Keybase Inc. All rights reserved. 2// Use of this source code is governed by a BSD 3// license that can be found in the LICENSE file. 4 5package cache 6 7import ( 8 "math" 9 "reflect" 10) 11 12/* 13 14Following struct/const definitions are from src/runtime/hashmap.go. We don't 15use them directly, but the estimation of map size is based on them. 16 17const ( 18 // Maximum number of key/value pairs a bucket can hold. 19 bucketCntBits = 3 20 bucketCnt = 1 << bucketCntBits 21 22 // Maximum average load of a bucket that triggers growth. 23 loadFactor = 6.5 24 ... 25) 26 27// A header for a Go map. 28type hmap struct { 29 // Note: the format of the Hmap is encoded in ../../cmd/internal/gc/reflect.go and 30 // ../reflect/type.go. Don't change this structure without also changing that code! 31 count int // # live cells == size of map. Must be first (used by len() builtin) 32 flags uint8 33 B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) 34 noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details 35 hash0 uint32 // hash seed 36 37 buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. 38 oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing 39 nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) 40 41 // If both key and value do not contain pointers and are inline, then we mark bucket 42 // type as containing no pointers. This avoids scanning such maps. 43 // However, bmap.overflow is a pointer. In order to keep overflow buckets 44 // alive, we store pointers to all overflow buckets in hmap.overflow. 45 // Overflow is used only if key and value do not contain pointers. 46 // overflow[0] contains overflow buckets for hmap.buckets. 47 // overflow[1] contains overflow buckets for hmap.oldbuckets. 48 // The first indirection allows us to reduce static size of hmap. 49 // The second indirection allows to store a pointer to the slice in hiter. 50 overflow *[2]*[]*bmap 51} 52 53// A bucket for a Go map. 54type bmap struct { 55 // tophash generally contains the top byte of the hash value 56 // for each key in this bucket. If tophash[0] < minTopHash, 57 // tophash[0] is a bucket evacuation state instead. 58 tophash [bucketCnt]uint8 59 // Followed by bucketCnt keys and then bucketCnt values. 60 // NOTE: packing all the keys together and then all the values together makes the 61 // code a bit more complicated than alternating key/value/key/value/... but it allows 62 // us to eliminate padding which would be needed for, e.g., map[int64]int8. 63 // Followed by an overflow pointer. 64} 65*/ 66 67const ( 68 // MB is a short cut for 1024 * 1024. 69 MB = 1024 * 1024 70 71 // PtrSize is the number of bytes a pointer takes. 72 PtrSize = 4 << (^uintptr(0) >> 63) // stolen from runtime/internal/sys 73 // IntSize is the number of bytes an int or uint takes. 74 IntSize = 4 << (^uint(0) >> 63) 75 76 hmapStructSize = IntSize + // count int 77 1 + 1 + 2 + 4 + // flags, B, noverflow, hash0 78 PtrSize*3 + // buckets, oldbuckets, nevacuate 79 PtrSize + 2*PtrSize // overflow (estimate; not counting the slice) 80 81 bucketSizeWithoutIndirectPointerOverhead = 1 << 3 // tophash only 82 83 mapLoadFactor = 6.5 84) 85 86func mapKeyOrValueSizeWithIndirectPointerOverhead(rawSize int) int { 87 if rawSize > 128 { 88 // In Go maps, if key or value is larger than 128 bytes, a pointer type 89 // is used. 90 return rawSize + PtrSize 91 } 92 return rawSize 93} 94 95// StaticSizeOfMap provides a best-effort estimate of number of bytes that a 96// map takes in memory. It only includes statically sized content (i.e. struct, 97// array, int types, pointer address itself, slice/map's reference address 98// itself, etc.). If needed, dynamic sized stuff (slice/map content, pointer 99// content should be calculated separately by caller. 100func StaticSizeOfMap( 101 zeroValueKey, zeroValueValue interface{}, count int) (bytes int) { 102 return StaticSizeOfMapWithSize(int(reflect.TypeOf(zeroValueKey).Size()), 103 int(reflect.TypeOf(zeroValueValue).Size()), count) 104} 105 106// StaticSizeOfMapWithSize is a slightly more efficient version of 107// StaticSizeOfMap for when the caller knows the static size of key and value 108// without having to use `reflect`. 109func StaticSizeOfMapWithSize( 110 keyStaticSize, valueStaticSize int, count int) (bytes int) { 111 keySize := mapKeyOrValueSizeWithIndirectPointerOverhead(keyStaticSize) 112 valueSize := mapKeyOrValueSizeWithIndirectPointerOverhead(valueStaticSize) 113 114 // See the comment of `B` field of `hmap` struct above. 115 B := math.Ceil(math.Log2(float64(count) / mapLoadFactor)) 116 numBuckets := int(math.Exp2(B)) 117 118 return hmapStructSize + 119 bucketSizeWithoutIndirectPointerOverhead*numBuckets + 120 (keySize+valueSize)*count 121} 122