runtime_faststr.go

     1  // Copyright 2024 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  package maps
     6  
     7  import (
     8  	"internal/abi"
     9  	"internal/goarch"
    10  	"internal/goexperiment"
    11  	"internal/race"
    12  	"internal/runtime/sys"
    13  	"unsafe"
    14  )
    15  
    16  func (m *Map) getWithoutKeySmallFastStr(typ *abi.MapType, key string) unsafe.Pointer {
    17  	g := groupReference{
    18  		data: m.dirPtr,
    19  	}
    20  
    21  	ctrls := *g.ctrls()
    22  	slotKey := g.key(typ, 0)
    23  	var keyStride uintptr
    24  	if goexperiment.MapSplitGroup {
    25  		keyStride = 2 * goarch.PtrSize // keys are contiguous in split layout
    26  	} else {
    27  		keyStride = typ.KeyStride // == SlotSize in interleaved layout
    28  	}
    29  
    30  	// The 64 threshold was chosen based on performance of BenchmarkMapStringKeysEight,
    31  	// where there are 8 keys to check, all of which don't quick-match the lookup key.
    32  	// In that case, we can save hashing the lookup key. That savings is worth this extra code
    33  	// for strings that are long enough that hashing is expensive.
    34  	if len(key) > 64 {
    35  		// String hashing and equality might be expensive. Do a quick check first.
    36  		j := abi.MapGroupSlots
    37  		for i := range abi.MapGroupSlots {
    38  			if ctrls&(1<<7) == 0 && longStringQuickEqualityTest(key, *(*string)(slotKey)) {
    39  				if j < abi.MapGroupSlots {
    40  					// 2 strings both passed the quick equality test.
    41  					// Break out of this loop and do it the slow way.
    42  					goto dohash
    43  				}
    44  				j = i
    45  			}
    46  			slotKey = unsafe.Pointer(uintptr(slotKey) + keyStride)
    47  			ctrls >>= 8
    48  		}
    49  		if j == abi.MapGroupSlots {
    50  			// No slot passed the quick test.
    51  			return nil
    52  		}
    53  		// There's exactly one slot that passed the quick test. Do the single expensive comparison.
    54  		slotKey = g.key(typ, uintptr(j))
    55  		if key == *(*string)(slotKey) {
    56  			if goexperiment.MapSplitGroup {
    57  				return g.elem(typ, uintptr(j))
    58  			} else {
    59  				return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
    60  			}
    61  		}
    62  		return nil
    63  	}
    64  
    65  dohash:
    66  	// This path will cost 1 hash and 1+ε comparisons.
    67  	var hash uintptr
    68  	// See the related comment in runtime_mapaccess2_fast32
    69  	if memHashAESImplemented && UseAeshash {
    70  		hash = memHashAES(unsafe.Pointer(unsafe.StringData(key)), m.seed, uintptr(len(key)))
    71  	} else {
    72  		hash = memHashFallback(unsafe.Pointer(unsafe.StringData(key)), m.seed, uintptr(len(key)))
    73  	}
    74  	h2 := uint8(h2(hash))
    75  	ctrls = *g.ctrls()
    76  	slotKey = g.key(typ, 0)
    77  
    78  	for i := range uintptr(abi.MapGroupSlots) {
    79  		if uint8(ctrls) == h2 && key == *(*string)(slotKey) {
    80  			if goexperiment.MapSplitGroup {
    81  				return g.elem(typ, i)
    82  			} else {
    83  				return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
    84  			}
    85  		}
    86  		slotKey = unsafe.Pointer(uintptr(slotKey) + keyStride)
    87  		ctrls >>= 8
    88  	}
    89  	return nil
    90  }
    91  
    92  // Returns true if a and b might be equal.
    93  // Returns false if a and b are definitely not equal.
    94  // Requires len(a)>=8.
    95  func longStringQuickEqualityTest(a, b string) bool {
    96  	if len(a) != len(b) {
    97  		return false
    98  	}
    99  	x, y := unsafe.Pointer(unsafe.StringData(a)), unsafe.Pointer(unsafe.StringData(b))
   100  	// Check first 8 bytes.
   101  	if *(*[8]byte)(x) != *(*[8]byte)(y) {
   102  		return false
   103  	}
   104  	// Check last 8 bytes.
   105  	x = add(x, uintptr(len(a)-8))
   106  	y = add(y, uintptr(len(a)-8))
   107  	if *(*[8]byte)(x) != *(*[8]byte)(y) {
   108  		return false
   109  	}
   110  	return true
   111  }
   112  
   113  //go:linkname runtime_mapaccess1_faststr runtime.mapaccess1_faststr
   114  func runtime_mapaccess1_faststr(typ *abi.MapType, m *Map, key string) unsafe.Pointer {
   115  	p, _ := runtime_mapaccess2_faststr(typ, m, key)
   116  	return p
   117  }
   118  
   119  //go:linkname runtime_mapaccess2_faststr runtime.mapaccess2_faststr
   120  func runtime_mapaccess2_faststr(typ *abi.MapType, m *Map, key string) (unsafe.Pointer, bool) {
   121  	if race.Enabled && m != nil {
   122  		callerpc := sys.GetCallerPC()
   123  		pc := abi.FuncPCABIInternal(runtime_mapaccess2_faststr)
   124  		race.ReadPC(unsafe.Pointer(m), callerpc, pc)
   125  	}
   126  
   127  	if m == nil || m.Used() == 0 {
   128  		return unsafe.Pointer(&zeroVal[0]), false
   129  	}
   130  
   131  	if m.writing != 0 {
   132  		fatal("concurrent map read and map write")
   133  		return nil, false
   134  	}
   135  
   136  	if m.dirLen <= 0 {
   137  		elem := m.getWithoutKeySmallFastStr(typ, key)
   138  		if elem == nil {
   139  			return unsafe.Pointer(&zeroVal[0]), false
   140  		}
   141  		return elem, true
   142  	}
   143  
   144  	var hash uintptr
   145  	// See the related comment in runtime_mapaccess2_fast32
   146  	if memHashAESImplemented && UseAeshash {
   147  		hash = memHashAES(unsafe.Pointer(unsafe.StringData(key)), m.seed, uintptr(len(key)))
   148  	} else {
   149  		hash = memHashFallback(unsafe.Pointer(unsafe.StringData(key)), m.seed, uintptr(len(key)))
   150  	}
   151  
   152  	// Select table.
   153  	idx := m.directoryIndex(hash)
   154  	t := m.directoryAt(idx)
   155  
   156  	// Probe table.
   157  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   158  	h2Hash := h2(hash)
   159  	for ; ; seq = seq.next() {
   160  		g := t.groups.group(typ, seq.offset)
   161  
   162  		match := g.ctrls().matchH2(h2Hash)
   163  
   164  		for match != 0 {
   165  			i := match.first()
   166  
   167  			slotKey := g.key(typ, i)
   168  			if key == *(*string)(slotKey) {
   169  				if goexperiment.MapSplitGroup {
   170  					return g.elem(typ, i), true
   171  				} else {
   172  					return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize), true
   173  				}
   174  			}
   175  			match = match.removeFirst()
   176  		}
   177  
   178  		match = g.ctrls().matchEmpty()
   179  		if match != 0 {
   180  			// Finding an empty slot means we've reached the end of
   181  			// the probe sequence.
   182  			return unsafe.Pointer(&zeroVal[0]), false
   183  		}
   184  	}
   185  }
   186  
   187  func (m *Map) putSlotSmallFastStr(typ *abi.MapType, hash uintptr, key string) unsafe.Pointer {
   188  	g := groupReference{
   189  		data: m.dirPtr,
   190  	}
   191  
   192  	match := g.ctrls().matchH2(h2(hash))
   193  
   194  	// Look for an existing slot containing this key.
   195  	for match != 0 {
   196  		i := match.first()
   197  
   198  		slotKey := g.key(typ, i)
   199  		if key == *(*string)(slotKey) {
   200  			// Key needs update, as the backing storage may differ.
   201  			*(*string)(slotKey) = key
   202  			slotElem := g.elem(typ, i)
   203  			return slotElem
   204  		}
   205  		match = match.removeFirst()
   206  	}
   207  
   208  	// There can't be deleted slots, small maps can't have them
   209  	// (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
   210  	// more efficient than matchEmpty.
   211  	match = g.ctrls().matchEmptyOrDeleted()
   212  	if match == 0 {
   213  		// No empty slot found. Need to grow the map.
   214  		return nil
   215  	}
   216  
   217  	i := match.first()
   218  
   219  	slotKey := g.key(typ, i)
   220  	*(*string)(slotKey) = key
   221  
   222  	slotElem := g.elem(typ, i)
   223  
   224  	g.ctrls().set(i, ctrl(h2(hash)))
   225  	m.used++
   226  
   227  	return slotElem
   228  }
   229  
   230  func (t *table) uncheckedPutSlotForAssignFastStr(typ *abi.MapType, hash uintptr, key string) unsafe.Pointer {
   231  	if t.growthLeft == 0 {
   232  		panic("invariant failed: growthLeft is unexpectedly 0")
   233  	}
   234  
   235  	// Given key and its hash hash(key), to insert it, we construct a
   236  	// probeSeq, and use it to find the first group with an unoccupied (empty
   237  	// or deleted) slot. We place the key/value into the first such slot in
   238  	// the group and mark it as full with key's H2.
   239  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   240  	for ; ; seq = seq.next() {
   241  		g := t.groups.group(typ, seq.offset)
   242  
   243  		match := g.ctrls().matchEmptyOrDeleted()
   244  		if match != 0 {
   245  			i := match.first()
   246  
   247  			slotKey := g.key(typ, i)
   248  			*(*string)(slotKey) = key
   249  
   250  			slotElem := g.elem(typ, i)
   251  
   252  			t.growthLeft--
   253  			t.used++
   254  			g.ctrls().set(i, ctrl(h2(hash)))
   255  			return slotElem
   256  		}
   257  	}
   258  }
   259  
   260  //go:linkname runtime_mapassign_faststr runtime.mapassign_faststr
   261  func runtime_mapassign_faststr(typ *abi.MapType, m *Map, key string) unsafe.Pointer {
   262  	if m == nil {
   263  		panic(errNilAssign)
   264  	}
   265  	if race.Enabled {
   266  		callerpc := sys.GetCallerPC()
   267  		pc := abi.FuncPCABIInternal(runtime_mapassign_faststr)
   268  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   269  	}
   270  	if m.writing != 0 {
   271  		fatal("concurrent map writes")
   272  	}
   273  
   274  	var hash uintptr
   275  	// See the related comment in runtime_mapaccess2_fast32
   276  	if memHashAESImplemented && UseAeshash {
   277  		hash = memHashAES(unsafe.Pointer(unsafe.StringData(key)), m.seed, uintptr(len(key)))
   278  	} else {
   279  		hash = memHashFallback(unsafe.Pointer(unsafe.StringData(key)), m.seed, uintptr(len(key)))
   280  	}
   281  
   282  	// Set writing after calling Hasher, since Hasher may panic, in which
   283  	// case we have not actually done a write.
   284  	m.writing ^= 1 // toggle, see comment on writing
   285  
   286  	if m.dirPtr == nil {
   287  		m.growToSmall(typ)
   288  	}
   289  
   290  	if m.dirLen == 0 {
   291  		elem := m.putSlotSmallFastStr(typ, hash, key)
   292  		if elem == nil {
   293  			// Can't fit another entry, grow to full size map.
   294  			tab := m.growToTable(typ)
   295  
   296  			elem = tab.uncheckedPutSlotForAssignFastStr(typ, hash, key)
   297  			m.used++
   298  
   299  			tab.checkInvariants(typ, m)
   300  		}
   301  
   302  		if m.writing == 0 {
   303  			fatal("concurrent map writes")
   304  		}
   305  		m.writing ^= 1
   306  
   307  		return elem
   308  	}
   309  
   310  	var slotElem unsafe.Pointer
   311  outer:
   312  	for {
   313  		// Select table.
   314  		idx := m.directoryIndex(hash)
   315  		t := m.directoryAt(idx)
   316  
   317  		seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   318  
   319  		// As we look for a match, keep track of the first deleted slot
   320  		// we find, which we'll use to insert the new entry if
   321  		// necessary.
   322  		var firstDeletedGroup groupReference
   323  		var firstDeletedSlot uintptr
   324  
   325  		h2Hash := h2(hash)
   326  		for ; ; seq = seq.next() {
   327  			g := t.groups.group(typ, seq.offset)
   328  			match := g.ctrls().matchH2(h2Hash)
   329  
   330  			// Look for an existing slot containing this key.
   331  			for match != 0 {
   332  				i := match.first()
   333  
   334  				slotKey := g.key(typ, i)
   335  				if key == *(*string)(slotKey) {
   336  					// Key needs update, as the backing
   337  					// storage may differ.
   338  					*(*string)(slotKey) = key
   339  					slotElem = g.elem(typ, i)
   340  
   341  					t.checkInvariants(typ, m)
   342  					break outer
   343  				}
   344  				match = match.removeFirst()
   345  			}
   346  
   347  			// No existing slot for this key in this group. Is this the end
   348  			// of the probe sequence?
   349  			match = g.ctrls().matchEmptyOrDeleted()
   350  			if match == 0 {
   351  				continue // nothing but filled slots. Keep probing.
   352  			}
   353  			i := match.first()
   354  			if g.ctrls().get(i) == ctrlDeleted {
   355  				// There are some deleted slots. Remember
   356  				// the first one, and keep probing.
   357  				if firstDeletedGroup.data == nil {
   358  					firstDeletedGroup = g
   359  					firstDeletedSlot = i
   360  				}
   361  				continue
   362  			}
   363  			// We've found an empty slot, which means we've reached the end of
   364  			// the probe sequence.
   365  
   366  			// If we found a deleted slot along the way, we can
   367  			// replace it without consuming growthLeft.
   368  			if firstDeletedGroup.data != nil {
   369  				g = firstDeletedGroup
   370  				i = firstDeletedSlot
   371  				t.growthLeft++ // will be decremented below to become a no-op.
   372  			}
   373  
   374  			// If we have no space left, first try to remove some tombstones.
   375  			if t.growthLeft == 0 {
   376  				t.pruneTombstones(typ, m)
   377  			}
   378  
   379  			// If there is room left to grow, just insert the new entry.
   380  			if t.growthLeft > 0 {
   381  				slotKey := g.key(typ, i)
   382  				*(*string)(slotKey) = key
   383  
   384  				slotElem = g.elem(typ, i)
   385  
   386  				g.ctrls().set(i, ctrl(h2Hash))
   387  				t.growthLeft--
   388  				t.used++
   389  				m.used++
   390  
   391  				t.checkInvariants(typ, m)
   392  				break outer
   393  			}
   394  
   395  			t.rehash(typ, m)
   396  			continue outer
   397  		}
   398  	}
   399  
   400  	if m.writing == 0 {
   401  		fatal("concurrent map writes")
   402  	}
   403  	m.writing ^= 1
   404  
   405  	return slotElem
   406  }
   407  
   408  //go:linkname runtime_mapdelete_faststr runtime.mapdelete_faststr
   409  func runtime_mapdelete_faststr(typ *abi.MapType, m *Map, key string) {
   410  	if race.Enabled {
   411  		callerpc := sys.GetCallerPC()
   412  		pc := abi.FuncPCABIInternal(runtime_mapdelete_faststr)
   413  		race.WritePC(unsafe.Pointer(m), callerpc, pc)
   414  	}
   415  
   416  	if m == nil || m.Used() == 0 {
   417  		return
   418  	}
   419  
   420  	m.Delete(typ, abi.NoEscape(unsafe.Pointer(&key)))
   421  }
   422
View as plain text