Golang Map 실현 (4) map 의 할당 과 확장

제목: Golang Map 실현 (4) 날짜: 2020 - 04 - 28 18: 20: 30 태그:
golang map 작업 은 map 실현 에서 비교적 복잡 한 논리 입 니 다.할당 할 때 hash 충돌 체인 의 길이 가 너무 긴 문 제 를 줄 이기 위해 map 의 확장 과 데이터 이전 을 할 수 있 기 때 문 입 니 다.맵 의 확장 과 데이터 의 이전 도 관심 사다.
데이터 구조
우선, 우 리 는 맵 이 실현 한 데이터 구 조 를 다시 배 워 야 한다.

type hmap struct {
  count     int
  flags     uint8  
  B         uint8
  noverflow uint16
  hash0     uint32
  buckets    unsafe.Pointer
  oldbuckets unsafe.Pointer
  nevacuate  uintptr
  extra *mapextra
}

type mapextra struct {
  overflow    *[]*bmap
  oldoverflow *[]*bmap
  nextOverflow *bmap
}

hmap 는 map 가 실현 하 는 구조 체 입 니 다.대부분의 필드 는 1 절 에서 이미 배 웠 다.나머지 는 nevacuate 와 extra 입 니 다.
먼저 이전 개념 을 알 아야 합 니 다. hash 에서 데이터 체인 이 너무 길 거나 빈 bucket 이 너무 많 을 때 데 이 터 를 옮 기 고 데 이 터 를 새로운 bucket 에 옮 기 면 bucket 배열 은 oldbuckets 가 됩 니 다.bucket 의 이전 은 한 번 에 다 옮 기 는 것 이 아니 라 해당 하 는 bucket 에 접근 할 때 만 이전 작업 이 실 행 될 수 있 습 니 다.(이 점 은 redis 의 확장 과 비슷 하지 않 습 니까? 여러 방문 에 확대 하여 한 번 의 방문 지연 압력 을 줄 였 습 니 다)

nevactuate 표 지 는 이전 위치 (이전 진 도 를 고려 할 수도 있 습 니 다) 입 니 다. 표 지 는 현재 oldbuckets 중 (array) bucket 이 어디로 옮 겨 졌 습 니까?

extra 는 map 의 구조 체 입 니 다. nextOverflow 표 지 는 신청 한 빈 bucket 입 니 다. 나중에 충돌 을 해결 할 때 사용 합 니 다. overflow 와 oldoverflow 표지 가 넘 치 는 링크 에서 사용 하고 있 는 bucket 데이터 입 니 다. old 와 비 old 의 차이 점 은 old 는 이전 을 위 한 수치 입 니 다.

대략적인 데이터 구 조 를 이해 하면 우 리 는 맵 의 값 부여 조작 을 배 울 수 있다.
map 할당 작업
map 의 할당 동작 은 다음 과 같 습 니 다.

   data := mapExample["hello"]

할당 의 실현, golang 은 서로 다른 유형의 k 를 최적화 하기 위해 다음 과 같은 실현 방법 을 만 들 었 습 니 다.

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {}
func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer {}
func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {}
func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {}
func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer{}
func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer {}

내용 은 대동소이 하 다. 우 리 는 주로 mapassign 의 실현 을 배운다.mapassign 방법의 실현 은 빈 bucket 을 찾 아 key 를 bucket 에 할당 한 다음 에 val 의 주 소 를 되 돌려 주 고 어 셈 블 리 를 통 해 메모리 복사 하 는 것 입 니 다. 그러면 우 리 는 빈 bucket 을 어떻게 찾 는 지 한 걸음 한 걸음 봅 니 다.
① key 를 찾기 전에 이상 검 사 를 합 니 다. map 가 초기 화 되 지 않 았 거나 동시에 쓰 고 있 는 지 확인 합 니 다. 존재 하면 이상 을 던 집 니 다. (이것 이 바로 map 와 함께 panic 을 쓰 는 이유 입 니 다)

if h == nil {
  panic(plainError("assignment to entry in nil map"))
}
//            

if h.flags&hashWriting != 0 {
  throw("concurrent map writes")
}

② key 에 대응 하 는 hash 값 을 계산 해 야 합 니 다. buckets 가 비어 있 으 면 (초기 화 할 때 일정한 길이 보다 작은 map 는 데 이 터 를 초기 화 하지 않 습 니 다) bucket 을 초기 화 해 야 합 니 다.

alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))

//       hash    flags，   alg.hash   panic
h.flags ^= hashWriting

if h.buckets == nil {
  h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}

③ hash 값 을 통 해 해당 하 는 bucket 을 가 져 옵 니 다. map 가 데 이 터 를 옮 기 고 있다 면 oldbuckets 에서 해당 하 는 bucket 을 찾 아 새로운 bucket 으로 옮 겨 야 합 니 다.

//   hash   bucket     
bucket := hash & bucketMask(h.B)

//        ，      
if h.growing() {
  growWork(t, h, bucket)
}

//      bucket   ， top hash  
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash)

④ bucket 을 받 은 후에 링크 방식 에 따라 하나씩 확인 하고 해당 하 는 key 를 찾 아야 한다. 이미 존재 하 는 key 일 수도 있 고 새로 추가 해 야 할 수도 있다.

for {
  for i := uintptr(0); i < bucketCnt; i++ {

    //   tophash     ，   tophash      
    if b.tophash[i] != top {

      //       ， kv     。
      if isEmpty(b.tophash[i]) && inserti == nil {
        inserti = &b.tophash[i]
        insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
        val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
      }

      //       ，        
      if b.tophash[i] == emptyRest {
        break bucketloop
      }
      continue
    }

    //  tophash   

    k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
    if t.indirectkey() {
      k = *((*unsafe.Pointer)(k))
    }

    //   k  ，      
    if !alg.equal(key, k) {
      continue
    }

    //   key    ，       ，    k，   v       
    if t.needkeyupdate() {
      typedmemmove(t.key, k, key)
    }
    val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
    goto done
  }
  //     overflow （    ）
  ovf := b.overflow(t)
  if ovf == nil {
    break
  }
  b = ovf
}

이 절 차 를 정리 하면 주로 몇 가지 부분 이 있다.
a. map hash 가 일치 하지 않 는 경 우 는 빈 kv 인지 확인 합 니 다. delete 를 호출 하면 빈 kv 가 발생 합 니 다. 먼저 주 소 를 남 겨 두 고 뒤에 해당 하 는 k 를 찾 지 못 하면 (즉, 이전 map 에 대응 하 는 Key 가 없 었 다 는 것 입 니 다)b. map hash 가 일치 하 는 경우 키 의 글자 액면가 가 일치 하 는 지 확인 해 야 합 니 다. 일치 하지 않 으 면 찾 아야 합 니 다. 일치 하 는 경우 키 를 업데이트 (인용 이 있 을 수 있 으 므 로) 하고 v 주 소 를 되 돌려 주면 됩 니 다. c. 위 에 도 없 으 면 다음 bucket 을 보십시오.
⑤ 데 이 터 를 삽입 하기 전에 데이터 가 너무 많아 서 용량 을 늘 려 야 합 니 다. 용량 을 늘 려 야 한다 면 ③ 부터 새로운 bucket 을 받 아 해당 하 는 위 치 를 찾 습 니 다.

if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  hashGrow(t, h)
  goto again // Growing the table invalidates everything, so try again
}

⑥ 방금 빈 자리 가 없 는 것 을 보 았 다 면 링크 뒤에 bucket 을 추가 하여 kv 를 받 아야 합 니 다.

if inserti == nil {
  // all current buckets are full, allocate a new one.
  newb := h.newoverflow(t, b)
  inserti = &newb.tophash[0]
  insertk = add(unsafe.Pointer(newb), dataOffset)
  val = add(insertk, bucketCnt*uintptr(t.keysize))
}

⑦ 마지막 으로 tophash 와 key 의 글자 값 을 업데이트 하고 hash Writing 제약 을 해제 합 니 다.

//        （          ），          
if t.indirectkey() {
  kmem := newobject(t.key)
  *(*unsafe.Pointer)(insertk) = kmem
  insertk = kmem
}
if t.indirectvalue() {
  vmem := newobject(t.elem)
  *(*unsafe.Pointer)(val) = vmem
}
//   tophash, k
typedmemmove(t.key, insertk, key)
*inserti = top

done:
if h.flags&hashWriting == 0 {
    throw("concurrent map writes")
  }
  h.flags &^= hashWriting
  if t.indirectvalue() {
    val = *((*unsafe.Pointer)(val))
  }
  return val

여기까지 맵 의 할당 값 은 기본적으로 소개 되 었 습 니 다. 다음 단계 ⑤ 의 맵 확장 을 배 워 보 겠 습 니 다.
지도의 확장
두 가지 상황 에서 용량 을 늘 려 야 합 니 다. 하 나 는 kv 데이터 가 너무 많아 서 현재 map 의 부 하 를 초과 한 것 입 니 다. 또 하 나 는 overflow 의 bucket 이 너무 많 습 니 다. 이 한도 값 은 하나의 정격 치 이 고 경험 에서 얻 은 결론 이기 때문에 우 리 는 여기 서 연구 하지 않 습 니 다.
조건 이 충족 되면 용량 을 늘 리 기 시작 합 니 다. 조건 2 를 충족 시 키 면 용량 을 늘 린 buckets 의 수량 이 원래 와 같 습 니 다. 빈 kv 가 차지 하 는 구덩이 가 너무 많 을 수도 있 습 니 다. 맵 용량 을 늘 려 메모리 정 리 를 합 니 다. kv 양 이 많아 맵 부하 가 너무 높 으 면 배로 늘 립 니 다.

func hashGrow(t *maptype, h *hmap) {
  bigger := uint8(1)
  //         ，     0
  if !overLoadFactor(h.count+1, h.B) {
    bigger = 0
    h.flags |= sameSizeGrow
  }
  oldbuckets := h.buckets

  //        ，    buckets
  newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

  flags := h.flags &^ (iterator | oldIterator)
  if h.flags&iterator != 0 {
    flags |= oldIterator
  }
  
  //       map    ，oldbuckets    。        
  h.B += bigger
  h.flags = flags
  h.oldbuckets = oldbuckets
  h.buckets = newbuckets
  h.nevacuate = 0
  h.noverflow = 0

  // extra       
  if h.extra != nil && h.extra.overflow != nil {
    // Promote current overflow buckets to the old generation.
    if h.extra.oldoverflow != nil {
      throw("oldoverflow is not nil")
    }
    h.extra.oldoverflow = h.extra.overflow
    h.extra.overflow = nil
  }
  if nextOverflow != nil {
    if h.extra == nil {
      h.extra = new(mapextra)
    }
    h.extra.nextOverflow = nextOverflow
  }
}

맵 의 확장 작업 을 정리 합 니 다. 먼저 확장 크기 를 가 져 온 다음 에 큰 배열 을 신청 한 다음 에 초기 화 된 작업 을 하고 오래된 buckets 와 overflow 를 전환 하면 됩 니 다.
map 데이터 이전
확장 이 완료 되면 데이터 이전 이 필요 합 니 다. 데이터 이전 은 한 번 에 이 루어 지 는 것 이 아니 라 사용 할 때 만 bucket 이전 을 할 수 있 습 니 다. 즉, 점차적으로 이 루어 지 는 데이터 이전 입 니 다. 다음은 배 우 겠 습 니 다.
데이터 할당 ③ 단계 에 서 는 작업 이 필요 한 bucket 이 오래된 buckets 안에 있 는 지, 있 으 면 이전 하 는 지 확인 합 니 다. 다음은 이전 의 구체 적 인 작업 입 니 다.

func growWork(t *maptype, h *hmap, bucket uintptr) {
  //         bucket   
  evacuate(t, h, bucket&h.oldbucketmask())
  
  //        bucket
  if h.growing() {
    evacuate(t, h, h.nevacuate)
  }
}

nevacuate 표 지 는 현재 의 진도 입 니 다. 만약 에 이사 가 끝나 면 2 ^ B 의 길이 와 같 아야 합 니 다. (여기 서 말 하 는 B 는 oldbuckets 안의 B 입 니 다. 왜냐하면 새로운 buckets 길 이 는 2 ^ (B + 1) 일 수 있 습 니 다.)
evacuate 방법 은 이 위치 에 대응 하 는 bucket 과 충돌 체인 의 데 이 터 를 모두 새로운 buckets 로 옮 기 는 것 입 니 다.
① 현재 bucket 이 이전 되 었 는 지 판단 해 야 합 니 다. (oldbucket 표 지 는 이전 해 야 할 bucket 에 대응 하 는 위치)

b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
//   
if !evacuated(b) {
  //      
}

이전 판단 은 tophash 를 통 해 직접 할 수 있 습 니 다. tophash 의 첫 번 째 hash 값 을 판단 하면 됩 니 다. (tophash 의 역할 은 제3 강 을 참고 할 수 있 습 니 다)

func evacuated(b *bmap) bool {
  h := b.tophash[0]
  //      flag       
  return h > emptyOne && h < minTopHash
}

② 옮 겨 지지 않 으 면 데 이 터 를 옮 겨 야 합 니 다. 데 이 터 를 옮 길 때 크기 가 같은 buckets 로 옮 길 수도 있 고 2 배 큰 buckets 로 옮 길 수도 있 습 니 다. 여기 xy 는 모두 목표 의 이전 위 치 를 표시 하 는 표지 입 니 다. x 표 지 는 같은 위치 로 옮 기 는 것 이 고 y 표 지 는 2 배 큰 위치 로 옮 기 는 것 입 니 다. 우 리 는 먼저 목표 의 위 치 를 확인 합 니 다.

var xy [2]evacDst
x := &xy[0]
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
x.k = add(unsafe.Pointer(x.b), dataOffset)
x.v = add(x.k, bucketCnt*uintptr(t.keysize))
if !h.sameSizeGrow() {
  //    2    ，      y   
  y := &xy[1]
  y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
  y.k = add(unsafe.Pointer(y.b), dataOffset)
  y.v = add(y.k, bucketCnt*uintptr(t.keysize))
}

③ bucket 위 치 를 확인 한 후 kv 에 따라 하나씩 이동 해 야 합 니 다. (남 은 kv 를 제거 하 는 것 이 목적 입 니 다)

//     bucket
for ; b != nil; b = b.overflow(t) {
  k := add(unsafe.Pointer(b), dataOffset)
  v := add(k, bucketCnt*uintptr(t.keysize))

  //   bucket      kv
  for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
    top := b.tophash[i]

    //       
    if isEmpty(top) {
      b.tophash[i] = evacuatedEmpty
      continue
    }
    if top < minTopHash {
      throw("bad map state")
    }
    k2 := k
    if t.indirectkey() {
      k2 = *((*unsafe.Pointer)(k2))
    }
    var useY uint8
    if !h.sameSizeGrow() {
      // 2          hash，
      hash := t.key.alg.hash(k2, uintptr(h.hash0))
      if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.alg.equal(k2, k2) {
        useY = top & 1
        top = tophash(hash)
      } else {
        if hash&newbit != 0 {
          useY = 1
        }
      }
    }

    //          ，    
    if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
      throw("bad evacuatedN")
    }

    //   oldbucket  tophash     
    b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
    dst := &xy[useY]                 // evacuation destination
    if dst.i == bucketCnt {
      //   dst bucket        kv，       overflow
      dst.b = h.newoverflow(t, dst.b)
      dst.i = 0
      dst.k = add(unsafe.Pointer(dst.b), dataOffset)
      dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
    }
    //   tophash ， kv   
    dst.b.tophash[dst.i&(bucketCnt-1)] = top
    if t.indirectkey() {
      *(*unsafe.Pointer)(dst.k) = k2
    } else {
      typedmemmove(t.key, dst.k, k)
    }
    if t.indirectvalue() {
      *(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v)
    } else {
      typedmemmove(t.elem, dst.v, v)
    }

    //      bucket
    dst.i++
    dst.k = add(dst.k, uintptr(t.keysize))
    dst.v = add(dst.v, uintptr(t.valuesize))
  }
}

key 비 간접 적 으로 사용 되 는 데이터 (즉 비 포인터 데이터) 에 대해 메모리 회수

if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
  b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
  ptr := add(b, dataOffset)
  n := uintptr(t.bucketsize) - dataOffset

  // ptr  kv   ，    topmap   ，         
  memclrHasPointers(ptr, n)
}

④ 현재 이전 하 는 bucket 과 전체 이전 하 는 bucket 의 위치 가 같다 면 전체적인 진도 표 시 를 업데이트 해 야 합 니 다 nevacuate

// newbit  oldbuckets    ，  nevacuate    
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
  //       
  h.nevacuate++

  //     2^10  bucket
  stop := h.nevacuate + 1024
  if stop > newbit {
    stop = newbit
  }

  //           ，     
  for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
    h.nevacuate++
  }

  //          ，oldbukets       ，  oldbuckets
  if h.nevacuate == newbit {
    h.oldbuckets = nil
    if h.extra != nil {
      h.extra.oldoverflow = nil
    }
    h.flags &^= sameSizeGrow
  }
}

총결산

Map 의 할당 난점 은 데이터 의 확장 과 데이터 의 이전 작업 에 있다.

bucket 이전 은 점차적으로 진행 되 고 한 번 의 할당 을 할 때마다 적어도 한 번 의 이전 작업 을 합 니 다.

확장 이 반드시 공간 을 늘 리 는 것 이 아니 라 메모리 정리 만 했 을 수도 있다.

tophash 의 표 지 는 비어 있 는 지 여 부 를 판단 할 수 있 고 이전 여 부 를 판단 할 수 있 으 며 이전 위 치 는 X or Y 이다.

delete map 의 key 는 빈 kv 가 많이 발생 하여 이전 작업 을 할 수 있 습 니 다. 피 할 수 있다 면 되도록 피하 십시오.