intern.go

     1  // Copyright 2022 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  //go:build goexperiment.jsonv2
     6  
     7  package json
     8  
     9  import (
    10  	"encoding/binary"
    11  	"math/bits"
    12  )
    13  
    14  // stringCache is a cache for strings converted from a []byte.
    15  type stringCache = [256]string // 256*unsafe.Sizeof(string("")) => 4KiB
    16  
    17  // makeString returns the string form of b.
    18  // It returns a pre-allocated string from c if present, otherwise
    19  // it allocates a new string, inserts it into the cache, and returns it.
    20  func makeString(c *stringCache, b []byte) string {
    21  	const (
    22  		minCachedLen = 2   // single byte strings are already interned by the runtime
    23  		maxCachedLen = 256 // large enough for UUIDs, IPv6 addresses, SHA-256 checksums, etc.
    24  	)
    25  	if c == nil || len(b) < minCachedLen || len(b) > maxCachedLen {
    26  		return string(b)
    27  	}
    28  
    29  	// Compute a hash from the fixed-width prefix and suffix of the string.
    30  	// This ensures hashing a string is a constant time operation.
    31  	var h uint32
    32  	switch {
    33  	case len(b) >= 8:
    34  		lo := binary.LittleEndian.Uint64(b[:8])
    35  		hi := binary.LittleEndian.Uint64(b[len(b)-8:])
    36  		h = hash64(uint32(lo), uint32(lo>>32)) ^ hash64(uint32(hi), uint32(hi>>32))
    37  	case len(b) >= 4:
    38  		lo := binary.LittleEndian.Uint32(b[:4])
    39  		hi := binary.LittleEndian.Uint32(b[len(b)-4:])
    40  		h = hash64(lo, hi)
    41  	case len(b) >= 2:
    42  		lo := binary.LittleEndian.Uint16(b[:2])
    43  		hi := binary.LittleEndian.Uint16(b[len(b)-2:])
    44  		h = hash64(uint32(lo), uint32(hi))
    45  	}
    46  
    47  	// Check the cache for the string.
    48  	i := h % uint32(len(*c))
    49  	if s := (*c)[i]; s == string(b) {
    50  		return s
    51  	}
    52  	s := string(b)
    53  	(*c)[i] = s
    54  	return s
    55  }
    56  
    57  // hash64 returns the hash of two uint32s as a single uint32.
    58  func hash64(lo, hi uint32) uint32 {
    59  	// If avalanche=true, this is identical to XXH32 hash on a 8B string:
    60  	//	var b [8]byte
    61  	//	binary.LittleEndian.PutUint32(b[:4], lo)
    62  	//	binary.LittleEndian.PutUint32(b[4:], hi)
    63  	//	return xxhash.Sum32(b[:])
    64  	const (
    65  		prime1 = 0x9e3779b1
    66  		prime2 = 0x85ebca77
    67  		prime3 = 0xc2b2ae3d
    68  		prime4 = 0x27d4eb2f
    69  		prime5 = 0x165667b1
    70  	)
    71  	h := prime5 + uint32(8)
    72  	h += lo * prime3
    73  	h = bits.RotateLeft32(h, 17) * prime4
    74  	h += hi * prime3
    75  	h = bits.RotateLeft32(h, 17) * prime4
    76  	// Skip final mix (avalanche) step of XXH32 for performance reasons.
    77  	// Empirical testing shows that the improvements in unbiased distribution
    78  	// does not outweigh the extra cost in computational complexity.
    79  	const avalanche = false
    80  	if avalanche {
    81  		h ^= h >> 15
    82  		h *= prime2
    83  		h ^= h >> 13
    84  		h *= prime3
    85  		h ^= h >> 16
    86  	}
    87  	return h
    88  }
    89
View as plain text