algorithm - 这个整数池代码是如何工作的

Question

我一直在努力理解这个整数池是如何工作的。这是很多我无法理解的小东西。我假设我在 m2id 数组中缺少一个概念，以及它是如何与我不知道的索引 'n' 进行或操作的，这会消除我的很多困惑。是否有任何一般概念/CS 理论可以解释这个看似简单的代码。我在代码中添加了注释，试图说明我目前的理解以及我完全困惑的地方。

// Copyright 2009 The Go9p Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
//Original source: https://github.com/rminnich/go9p/blob/master/clnt_pool.go
package go9p

import "sync" 

var m2id = [...]uint8{  // I think this is where the magic is.
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 4,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 5,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 4,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 6,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 4,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 5,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 4,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 7,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 4,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 5,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 4,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 6,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 4,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 5,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 4,
    0, 1, 0, 2, 0, 1, 0, 3,
    0, 1, 0, 2, 0, 1, 0, 0,
}

type pool struct {
    sync.Mutex
    need  int
    nchan chan uint32
    maxid uint32
    imap  []byte
}

func newPool(maxid uint32) *pool {
    p := new(pool)
    p.maxid = maxid
    p.nchan = make(chan uint32)

    return p
}

func (p *pool) getId() uint32 {
    var n uint32 = 0
    var ret uint32

    p.Lock()
    for n = 0; n < uint32(len(p.imap)); n++ {
        // it looks like every 0...n position of imap will be incremented to 255.
        if p.imap[n] != 0xFF {
            break
        }
    }

    if int(n) >= len(p.imap) {
        // This seems to be just growing the imap slice as needed.
        // I don't quite understand the constant of '8' here.
        m := uint32(len(p.imap) + 32)
        if uint32(m*8) > p.maxid {
            m = p.maxid/8 + 1
        }

        b := make([]byte, m)
        copy(b, p.imap)
        p.imap = b
    }

    if n >= uint32(len(p.imap)) {
        // If you get here the I'm assuming all the ID's are used up and putId will return you the next released ID.
        p.need++
        p.Unlock()
        ret = <-p.nchan
    } else {
        // This part I'm having a hard time grasping.  
        // It seems that each index of imap is incremented
        // from 0 to 255 and magically or'd with ret to increment to the next number?
        ret = uint32(m2id[p.imap[n]])
        p.imap[n] |= 1 << ret
        ret += n * 8
        p.Unlock()
    }

    return ret
}

func (p *pool) putId(id uint32) {
    p.Lock()
    if p.need > 0 {
        p.nchan <- id
        p.need--
        p.Unlock()
        return
    }

    // This doesn't play well with what I thought was going on.  I though that.  
    // I was thinking that imap[0] would always somehow magically return all the 
    // values from 0 to 255 and imap[1] would return 256 += 255 and so on.  
    // How does this work?
    p.imap[id/8] &= ^(1 << (id % 8))
    p.Unlock()
}

Answer 1

优化通常会导致模糊。从基本概念开始。可用 ID 池由字节 slice 的底层位数组表示。 Id 19 由从左到右的字节 2 (19/8) 和从右到左的位 3 (19 % 8) 表示。

这是一个简单的实现，忽略了锁定和增长位数组等细节。

package main

import "fmt"

// The Id pool is represented by the underlying bit array of a slice of bytes.
var idPool = make([]byte, 4)

// Get the next available Id from the pool.
func getId() int {
    // Get next available byte
    for i := 0; i < len(idPool); i++ {
        b := idPool[i]
        if b != 0xFF {
            // Get next available bit in the byte
            for j := 0; j < 8; j++ {
                if b&(1<<uint(j)) == 0 {
                    // Mark Id bit as unavailable.
                    idPool[i] |= 1 << uint(j)
                    // Return Id.
                    return 8*i + j
                }
            }
        }
    }
    panic("Insufficient Ids")
}

// Put the Id back in the pool.
func putId(id int) {
    if 0 > id || id >= 8*len(idPool) {
        panic("Invalid Id")
    }
    i := id / 8
    j := id % 8
    // Mark Id bit as available.
    idPool[i] &^= 1 << uint(j)
}

func main() {
    for i := 0; i < 16; i++ {
        getId()
    }
    fmt.Printf("%x\n", idPool)
    for i := 10; i < 12; i++ {
        putId(i)
    }
    fmt.Printf("%x\n", idPool)
    fmt.Println(getId())
    fmt.Printf("%x\n", idPool)
}

输出:

ffff0000
fff30000
10
fff70000

我们可以优化这个循环

// Get next available bit in the byte
for j := 0; j < 8; j++ {
    if b&(1<<uint(j)) == 0 {
        // Mark Id bit as unavailable.
        idPool[i] |= 1 << uint(j)
        // Return Id.
        return 8*i + j
    }
}

通过用表 (m2id) 替换它来查找位移值。

// Get next available bit in the byte
j := int(m2id[idPool[i]])
// Mark Id bit as unavailable.
idPool[i] |= 1 << uint(j)
// Return Id.
return 8*i + j

m2idInit() 函数显示了如何计算 m2id 表位移值。

func m2idInit() (m2id [256]uint8) {
    // For all byte values.
    for i := uint(0); i < 256; i++ {
        // Find an unused id
        for j := uint(0); j < 8; j++ {
            if i&(1<<j) == 0 {
                // Bit shift value
                m2id[i] = uint8(j)
                break
            }
        }
    }
    return m2id
}

例如，

package main

import "fmt"

// The Id pool is represented by the underlying bit array of a slice of bytes.
var idPool = make([]byte, 4)

// Get the next available Id from the pool.
func getId() int {
    // Get next available byte
    for i := 0; i < len(idPool); i++ {
        b := idPool[i]
        if b != 0xFF {
            // Get next available bit in the byte
            j := int(m2id[idPool[i]])
            // Mark Id bit as unavailable.
            idPool[i] |= 1 << uint(j)
            // Return Id.
            return 8*i + j
        }
    }
    panic("Insufficient Ids")
}

// Put the Id back in the pool.
func putId(id int) {
    if 0 > id || id >= 8*len(idPool) {
        panic("Invalid Id")
    }
    i := id / 8
    j := id % 8
    // Mark Id bit as available.
    idPool[i] &^= 1 << uint(j)
}

var m2id = m2idInit()

func m2idInit() (m2id [256]uint8) {
    // For all byte values.
    for i := uint(0); i < 256; i++ {
        // Find an unused id
        for j := uint(0); j < 8; j++ {
            if i&(1<<j) == 0 {
                // Bit shift value
                m2id[i] = uint8(j)
                break
            }
        }
    }
    return m2id
}

func main() {
    for i := 0; i < 16; i++ {
        getId()
    }
    fmt.Printf("%x\n", idPool)
    for i := 10; i < 12; i++ {
        putId(i)
    }
    fmt.Printf("%x\n", idPool)
    fmt.Println(getId())
    fmt.Printf("%x\n", idPool)

    fmt.Println()
    fmt.Println(m2id)
}

输出:

ffff0000
fff30000
10
fff70000

[0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 4
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 5
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 4
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 6
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 4
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 5
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 4
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 7
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 4
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 5
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 4
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 6
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 4
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 5
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 4
 0 1 0 2 0 1 0 3
 0 1 0 2 0 1 0 0]

没有魔法。

引用资料:

Bit manipulation

The Go Programming Language Specification, Arithmetic operators