How this Integer Pool code works
I was trying to figure out how this integer pool works. This is a lot of bits that I cannot wrap myself up. I guess there is an idea that I am missing with the m2id array and how it is listed with index 'n' which I do not know and clearing up a lot of the confusion. Are there any general concepts / CS theory that explain this seemingly simple looking code. I have added comments to the code to try and outline my current understanding and where I am completely 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 "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 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()
}
+3
source to share
1 answer
Optimization often leads to confusion. Start with a basic concept. The pool of available identifiers is represented by the underlying bit array from a chunk of bytes. Id 19 is represented from left to right byte 2 (19/8) and from right to left bit 3 (19% 8).
Here's a simple implementation, ignoring details like locking and bit array expansion.
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)
}
Output:
ffff0000
fff30000
10
fff70000
We can optimize this cycle
// 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
}
}
replacing it with table ( m2id
) to find the bit shift value.
// 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
The function m2idInit()
shows how the offset values of a table value are calculated 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
}
For example,
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)
}
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.
Literature:
Go programming language specification, arithmetic operations
+4
source to share