pcache.go

Documentation: github.com/bytedance/sonic/internal/caching

     1  /*
     2   * Copyright 2021 ByteDance Inc.
     3   *
     4   * Licensed under the Apache License, Version 2.0 (the "License");
     5   * you may not use this file except in compliance with the License.
     6   * You may obtain a copy of the License at
     7   *
     8   *     http://www.apache.org/licenses/LICENSE-2.0
     9   *
    10   * Unless required by applicable law or agreed to in writing, software
    11   * distributed under the License is distributed on an "AS IS" BASIS,
    12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13   * See the License for the specific language governing permissions and
    14   * limitations under the License.
    15   */
    16  
    17  package caching
    18  
    19  import (
    20      `sync`
    21      `sync/atomic`
    22      `unsafe`
    23  
    24      `github.com/bytedance/sonic/internal/rt`
    25  )
    26  
    27  /** Program Map **/
    28  
    29  const (
    30      _LoadFactor   = 0.5
    31      _InitCapacity = 4096    // must be a power of 2
    32  )
    33  
    34  type _ProgramMap struct {
    35      n uint64
    36      m uint32
    37      b []_ProgramEntry
    38  }
    39  
    40  type _ProgramEntry struct {
    41      vt *rt.GoType
    42      fn interface{}
    43  }
    44  
    45  func newProgramMap() *_ProgramMap {
    46      return &_ProgramMap {
    47          n: 0,
    48          m: _InitCapacity - 1,
    49          b: make([]_ProgramEntry, _InitCapacity),
    50      }
    51  }
    52  
    53  func (self *_ProgramMap) copy() *_ProgramMap {
    54      fork := &_ProgramMap{
    55          n: self.n,
    56          m: self.m,
    57          b: make([]_ProgramEntry, len(self.b)),
    58      }
    59      for i, f := range self.b {
    60          fork.b[i] = f
    61      }
    62      return fork
    63  }
    64  
    65  func (self *_ProgramMap) get(vt *rt.GoType) interface{} {
    66      i := self.m + 1
    67      p := vt.Hash & self.m
    68  
    69      /* linear probing */
    70      for ; i > 0; i-- {
    71          if b := self.b[p]; b.vt == vt {
    72              return b.fn
    73          } else if b.vt == nil {
    74              break
    75          } else {
    76              p = (p + 1) & self.m
    77          }
    78      }
    79  
    80      /* not found */
    81      return nil
    82  }
    83  
    84  func (self *_ProgramMap) add(vt *rt.GoType, fn interface{}) *_ProgramMap {
    85      p := self.copy()
    86      f := float64(atomic.LoadUint64(&p.n) + 1) / float64(p.m + 1)
    87  
    88      /* check for load factor */
    89      if f > _LoadFactor {
    90          p = p.rehash()
    91      }
    92  
    93      /* insert the value */
    94      p.insert(vt, fn)
    95      return p
    96  }
    97  
    98  func (self *_ProgramMap) rehash() *_ProgramMap {
    99      c := (self.m + 1) << 1
   100      r := &_ProgramMap{m: c - 1, b: make([]_ProgramEntry, int(c))}
   101  
   102      /* rehash every entry */
   103      for i := uint32(0); i <= self.m; i++ {
   104          if b := self.b[i]; b.vt != nil {
   105              r.insert(b.vt, b.fn)
   106          }
   107      }
   108  
   109      /* rebuild successful */
   110      return r
   111  }
   112  
   113  func (self *_ProgramMap) insert(vt *rt.GoType, fn interface{}) {
   114      h := vt.Hash
   115      p := h & self.m
   116  
   117      /* linear probing */
   118      for i := uint32(0); i <= self.m; i++ {
   119          if b := &self.b[p]; b.vt != nil {
   120              p += 1
   121              p &= self.m
   122          } else {
   123              b.vt = vt
   124              b.fn = fn
   125              atomic.AddUint64(&self.n, 1)
   126              return
   127          }
   128      }
   129  
   130      /* should never happens */
   131      panic("no available slots")
   132  }
   133  
   134  /** RCU Program Cache **/
   135  
   136  type ProgramCache struct {
   137      m sync.Mutex
   138      p unsafe.Pointer
   139  }
   140  
   141  func CreateProgramCache() *ProgramCache {
   142      return &ProgramCache {
   143          m: sync.Mutex{},
   144          p: unsafe.Pointer(newProgramMap()),
   145      }
   146  }
   147  
   148  func (self *ProgramCache) Get(vt *rt.GoType) interface{} {
   149      return (*_ProgramMap)(atomic.LoadPointer(&self.p)).get(vt)
   150  }
   151  
   152  func (self *ProgramCache) Compute(vt *rt.GoType, compute func(*rt.GoType, ... interface{}) (interface{}, error), ex ...interface{}) (interface{}, error) {
   153      var err error
   154      var val interface{}
   155  
   156      /* use defer to prevent inlining of this function */
   157      self.m.Lock()
   158      defer self.m.Unlock()
   159  
   160      /* double check with write lock held */
   161      if val = self.Get(vt); val != nil {
   162          return val, nil
   163      }
   164  
   165      /* compute the value */
   166      if val, err = compute(vt, ex...); err != nil {
   167          return nil, err
   168      }
   169  
   170      /* update the RCU cache */
   171      atomic.StorePointer(&self.p, unsafe.Pointer((*_ProgramMap)(atomic.LoadPointer(&self.p)).add(vt, val)))
   172      return val, nil
   173  }
   174
View as plain text