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

huangapple go评论87阅读模式
英文:

How does this Integer pool code work

问题

我一直在努力理解这个整数池是如何工作的。这是一些我无法理解的位操作。我猜想m2id数组和它与索引'n'进行或运算的概念是我不知道的,这可能会解释清楚我困惑的很多地方。是否有任何一般的概念/计算机科学理论可以解释这段看似简单的代码呢?我在代码中加了注释,试图说明我当前的理解以及我完全困惑的地方。

// 版权所有2009年Go9p作者。保留所有权利。
// 使用本源代码受BSD风格的许可证管辖
// 许可证可以在LICENSE文件中找到。
//原始来源:https://github.com/rminnich/go9p/blob/master/clnt_pool.go
package go9p

import "sync"

var m2id = [...]uint8{  // 我认为这就是魔法所在。
    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++ {
        // 看起来imap的每个0...n位置都会递增到255。
        if p.imap[n] != 0xFF {
            break
        }
    }

    if int(n) >= len(p.imap) {
        // 这似乎只是根据需要增加imap切片的大小。
        // 我不太理解这里的常量'8'。
        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)) {
        // 如果你到达这里,我猜所有的ID都被使用了,putId将返回下一个释放的ID。
        p.need++
        p.Unlock()
        ret = <-p.nchan
    } else {
        // 这部分我很难理解。
        // 看起来imap的每个索引都会递增
        // 从0到255,并与ret进行或运算以递增到下一个数字?
        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
    }

    // 这与我原以为的情况不符。
    // 我原以为imap[0]会以某种方式神奇地返回0到255的所有值,
    // 而imap[1]会返回256 += 255,依此类推。
    // 这是如何工作的?
    p.imap[id/8] &= ^(1 << (id % 8))
    p.Unlock()
}

希望这可以帮助你理解代码的工作原理。如果你有任何进一步的问题,请随时提问。

英文:

I've been trying to understand how this integer pool works. It is a lot of bit fiddling stuff I can't wrap my head around. I'm assuming there is a concept I'm missing with the m2id array and how it is or'ed with index 'n' that I don't know and would clear up a lot of my confusion. Are there are any general concepts/CS-theory that explain this seemingly-looking-simple code. I've put comments in the code to try and state my current understanding and where I am totally confused.

// 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 &quot;sync&quot; 
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 &lt; 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) &gt;= len(p.imap) {
// This seems to be just growing the imap slice as needed.
// I don&#39;t quite understand the constant of &#39;8&#39; here.
m := uint32(len(p.imap) + 32)
if uint32(m*8) &gt; p.maxid {
m = p.maxid/8 + 1
}
b := make([]byte, m)
copy(b, p.imap)
p.imap = b
}
if n &gt;= uint32(len(p.imap)) {
// If you get here the I&#39;m assuming all the ID&#39;s are used up and putId will return you the next released ID.
p.need++
p.Unlock()
ret = &lt;-p.nchan
} else {
// This part I&#39;m having a hard time grasping.  
// It seems that each index of imap is incremented
// from 0 to 255 and magically or&#39;d with ret to increment to the next number?
ret = uint32(m2id[p.imap[n]])
p.imap[n] |= 1 &lt;&lt; ret
ret += n * 8
p.Unlock()
}
return ret
}
func (p *pool) putId(id uint32) {
p.Lock()
if p.need &gt; 0 {
p.nchan &lt;- id
p.need--
p.Unlock()
return
}
// This doesn&#39;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] &amp;= ^(1 &lt;&lt; (id % 8))
p.Unlock()
}

答案1

得分: 4

优化通常会导致代码变得晦涩难懂。从基本概念开始。可用ID的池由字节切片的底层位数组表示。ID 19由从左到右的字节2(19/8)和从右到左的位3(19%8)表示。

这是一个简单的实现,忽略了锁定和扩展位数组等细节。

package main

import "fmt"

// ID池由字节切片的底层位数组表示。
var idPool = make([]byte, 4)

// 从池中获取下一个可用的ID。
func getId() int {
	// 获取下一个可用的字节
	for i := 0; i < len(idPool); i++ {
		b := idPool[i]
		if b != 0xFF {
			// 获取字节中的下一个可用位
			for j := 0; j < 8; j++ {
				if b&(1<<uint(j)) == 0 {
					// 将ID位标记为不可用。
					idPool[i] |= 1 << uint(j)
					// 返回ID。
					return 8*i + j
				}
			}
		}
	}
	panic("ID不足")
}

// 将ID放回池中。
func putId(id int) {
	if id < 0 || id >= 8*len(idPool) {
		panic("无效的ID")
	}
	i := id / 8
	j := id % 8
	// 将ID位标记为可用。
	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

我们可以通过使用一个表(m2id)查找位移值来优化这个循环:

// 获取字节中的下一个可用位
j := int(m2id[idPool[i]])
// 将ID位标记为不可用。
idPool[i] |= 1 << uint(j)
// 返回ID。
return 8*i + j

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

func m2idInit() (m2id [256]uint8) {
	// 对于所有字节值。
	for i := uint(0); i < 256; i++ {
		// 查找一个未使用的ID
		for j := uint(0); j < 8; j++ {
			if i&(1<<j) == 0 {
				// 位移值
				m2id[i] = uint8(j)
				break
			}
		}
	}
	return m2id
}

例如:

package main

import "fmt"

// ID池由字节切片的底层位数组表示。
var idPool = make([]byte, 4)

// 从池中获取下一个可用的ID。
func getId() int {
	// 获取下一个可用的字节
	for i := 0; i < len(idPool); i++ {
		b := idPool[i]
		if b != 0xFF {
			// 获取字节中的下一个可用位
			j := int(m2id[idPool[i]])
			// 将ID位标记为不可用。
			idPool[i] |= 1 << uint(j)
			// 返回ID。
			return 8*i + j
		}
	}
	panic("ID不足")
}

// 将ID放回池中。
func putId(id int) {
	if id < 0 || id >= 8*len(idPool) {
		panic("无效的ID")
	}
	i := id / 8
	j := id % 8
	// 将ID位标记为可用。
	idPool[i] &^= 1 << uint(j)
}

var m2id = m2idInit()

func m2idInit() (m2id [256]uint8) {
	// 对于所有字节值。
	for i := uint(0); i < 256; i++ {
		// 查找一个未使用的ID
		for j := uint(0); j < 8; j++ {
			if i&(1<<j) == 0 {
				// 位移值
				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编程语言规范,算术运算符

英文:

Optimization often leads to obscurity. Start with the basic concept. The pool of available Ids is represented by the underlying bit array of a slice of bytes. Id 19 is represented by left-to-right byte 2 (19 / 8) and right-to-left bit 3 (19 % 8).

Here's a simple implementation, ignoring details like locking and growing the bit array.

package main
import &quot;fmt&quot;
// 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 &lt; len(idPool); i++ {
b := idPool[i]
if b != 0xFF {
// Get next available bit in the byte
for j := 0; j &lt; 8; j++ {
if b&amp;(1&lt;&lt;uint(j)) == 0 {
// Mark Id bit as unavailable.
idPool[i] |= 1 &lt;&lt; uint(j)
// Return Id.
return 8*i + j
}
}
}
}
panic(&quot;Insufficient Ids&quot;)
}
// Put the Id back in the pool.
func putId(id int) {
if 0 &gt; id || id &gt;= 8*len(idPool) {
panic(&quot;Invalid Id&quot;)
}
i := id / 8
j := id % 8
// Mark Id bit as available.
idPool[i] &amp;^= 1 &lt;&lt; uint(j)
}
func main() {
for i := 0; i &lt; 16; i++ {
getId()
}
fmt.Printf(&quot;%x\n&quot;, idPool)
for i := 10; i &lt; 12; i++ {
putId(i)
}
fmt.Printf(&quot;%x\n&quot;, idPool)
fmt.Println(getId())
fmt.Printf(&quot;%x\n&quot;, idPool)
}

Output:

ffff0000
fff30000
10
fff70000

We can optimize this loop

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

by replacing it with a table (m2id) lookup for the bit shift value.

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

The m2idInit() function shows how the m2id table bit shift values are calculated.

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

For example,

package main
import &quot;fmt&quot;
// 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 &lt; 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 &lt;&lt; uint(j)
// Return Id.
return 8*i + j
}
}
panic(&quot;Insufficient Ids&quot;)
}
// Put the Id back in the pool.
func putId(id int) {
if 0 &gt; id || id &gt;= 8*len(idPool) {
panic(&quot;Invalid Id&quot;)
}
i := id / 8
j := id % 8
// Mark Id bit as available.
idPool[i] &amp;^= 1 &lt;&lt; uint(j)
}
var m2id = m2idInit()
func m2idInit() (m2id [256]uint8) {
// For all byte values.
for i := uint(0); i &lt; 256; i++ {
// Find an unused id
for j := uint(0); j &lt; 8; j++ {
if i&amp;(1&lt;&lt;j) == 0 {
// Bit shift value
m2id[i] = uint8(j)
break
}
}
}
return m2id
}
func main() {
for i := 0; i &lt; 16; i++ {
getId()
}
fmt.Printf(&quot;%x\n&quot;, idPool)
for i := 10; i &lt; 12; i++ {
putId(i)
}
fmt.Printf(&quot;%x\n&quot;, idPool)
fmt.Println(getId())
fmt.Printf(&quot;%x\n&quot;, idPool)
fmt.Println()
fmt.Println(m2id)
}

Output:

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]

There is no magic.

References:

Bit manipulation

The Go Programming Language Specification, Arithmetic operators

huangapple
  • 本文由 发表于 2015年8月7日 00:14:26
  • 转载请务必保留本文链接:https://go.coder-hub.com/31860816.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定