3

我一直试图了解这个整数池是如何工作的。这是很多我无法理解的摆弄东西。我假设 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()
}
4

1 回答 1

4

优化通常会导致晦涩难懂。从基本概念开始。可用 ID 池由字节切片的底层位数组表示。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]

没有魔法。

参考：

位操作

Go 编程语言规范，算术运算符

于 2015-08-07T06:07:09.417 回答