StableSeq

[jackhftang]

Here is another sequence of capacities 1,1,2,2,4,4,8,8... with a growth rate of 
sqrt(2) = 1.414, This seems to be a good balanced choice.
    
    
    import bitops
    
    type
      StableSeq*[T] = object
        len: int
        # sizeof(data[i]) == pow(2, i div 2)
        data: seq[ptr UncheckedArray[T]]
    
    proc size(i: int): int =
      return (1 shl (i shr 1))
    
    proc locate(k: int): (int, int) =
      let a = fastLog2(k+2)
      let w = 1 shl (a-1)
      let i = 2 * (a-1)
      let j = k+2 - 2*w
      let b = int(j >= w)
      return (i+b, j-b*w)
    
    proc add*[T](s: var StableSeq[T], v: sink T): ptr T =
      let (i,j) = locate(s.len)
      while i >= s.data.len:
        let p = cast[ptr UncheckedArray[T]](alloc0(sizeof(T)*size(i)))
        s.data.add p
      s.len += 1
      result = s.data[i][j].addr
      result[] = ensureMove(v)
    
    template checkBound(k) =
      if k < 0 or k >= s.len:
        raise newException(IndexDefect, "index out of bound")
    
    proc `[]`*[T](s: var StableSeq[T], k: int): var T =
      checkBound(k)
      let (i,j) = locate(k)
      return s.data[i][j]
    
    proc `[]=`*[T](s: var StableSeq[T], k: int, v: sink T)=
      checkBound(k)
      let (i,j) = locate(k)
      s.data[i][j] = v
    
    # ... other procs here
    
    when isMainModule:
      var s: StableSeq[int]
      for i in 0 .. 20:
        discard s.add(i)
      s[5] = 15
      for i in 0 ..< s.len:
        echo i, ' ', s[i]
    
    
    Run

If you think the first few allocation is too small, replace `size` and `locate` 
function with
    
    
    const SKIP_INDX = 4 # must be even number
    const SKIP_SIZE = 2*(1 shl (SKIP_INDX shr 1)) - 2
    
    proc size(i: int): int =
      if i == 0: return SKIP_SIZE
      return (1 shl ((i + SKIP_INDX - 1) shr 1))
    
    proc locate(k: int): (int, int) =
      if k < SKIP_SIZE:
        return (0, k)
      else:
        let a = fastLog2(k+2)
        let w = 1 shl (a-1)
        let i = 2 * (a-1)
        let j = k+2 - 2*w
        let b = int(j >= w)
        return (i+b-SKIP_INDX+1, j-b*w)
    
    
    Run