11

I want to limit a map to be maximum X bytes. It seems there is no straightforward way of computing the byte length of a map though.

"encoding/binary" package has a nice Size function, but it only works for slices or "fixed values", not for maps.

I could try to get all key/value pairs from the map, infer their type (if it's a map[string]interface{}) and compute the length - but that would be both cumbersome and probably incorrect (because that would exclude the "internal" Go cost of the map itself - managing pointers to elements etc).

Any suggested way of doing this? Preferably a code example.

Dave C
  • 7,729
  • 4
  • 49
  • 65
orcaman
  • 6,263
  • 8
  • 54
  • 69
  • You cannot do what you want in a reliable way: E.g. the "internal golang costs" depend on the word size of your machine. I although think the concept of "map uses X bytes" is flawed; consider a map containing a slice: Do you count the bytes of the backing array to the map? I'd recommend to search a different solution, especially as the use of `interface{}` has an ugly smell. – Volker Aug 06 '15 at 06:55
  • Thanks for the comment. The use case is rather simple actually: I want to impose a size limitation on a cache (instead of a time limitation). If I want to do so using a map - arguably the most appropriate primitive to be used as a cache object in Go - (let's even assume that it's not a map of string/interface) what are my options within the language (using an external tool for this seems like overkill)? – orcaman Aug 06 '15 at 07:06
  • 1
    Limiting the amount of data in a cache is a valid use case, but this is only sensible if you store substantial amount of variable sized data in the cache which means that the overhead of the map itself will be negligible. If you have fixed size data you can limit by len of the map. – Volker Aug 06 '15 at 07:20

1 Answers1

11

This is the definition for a map header:

// A header for a Go map.
type hmap struct {
    // Note: the format of the Hmap is encoded in ../../cmd/gc/reflect.c and
    // ../reflect/type.go.  Don't change this structure without also changing that code!
    count int // # live cells == size of map.  Must be first (used by len() builtin)
    flags uint32
    hash0 uint32 // hash seed
    B     uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
}

Calculating its size is pretty straightforward (unsafe.Sizeof).

This is the definition for each individual bucket the map points to:

// A bucket for a Go map.
type bmap struct {
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt values.
    // NOTE: packing all the keys together and then all the values together makes the
    // code a bit more complicated than alternating key/value/key/value/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

bucketCnt is a constant defined as:

bucketCnt     = 1 << bucketCntBits // equals decimal 8
bucketCntBits = 3

The final calculation would be:

unsafe.Sizeof(hmap) + (len(theMap) * 8) + (len(theMap) * 8 * unsafe.Sizeof(x)) + (len(theMap) * 8 * unsafe.Sizeof(y))

Where theMap is your map value, x is a value of the map's key type and y a value of the map's value type.

You'll have to share the hmap structure with your package via assembly, analogously to thunk.s in the runtime.

thwd
  • 23,956
  • 8
  • 74
  • 108
  • 2
    JFYI `thunk.s` has been replaced with the [`//go:linkname` compiler directive](https://golang.org/cmd/compile/#hdr-Compiler_Directives). – tsuna Jul 18 '17 at 03:53
  • 3
    Can you update this answer? Clearly none of this works anymore. The hmap struct is completely different, your answer doesn't factor in capacity and you can't share structures via assembly (nor can you via go:linkname) – Luxalpa Mar 06 '18 at 13:54
  • 1
    Smaug: Hi, the truth is that the implementation of map will vary again and again in the future. So I leave the answer as a guide rather than a solution. You can still use assembly to share names. – thwd Mar 07 '18 at 11:05
  • 1
    @thwd A complete snippet would be helpful rather than a partial response and then we have to look somewhere else how to use assembly to share names, why would not you put a self-contained response please? – Melardev Mar 11 '21 at 21:57