sync.Pool misuse binary-trees

[Isaac Gouy]

Is this a misuse of sync.Pool?

How would a Go programmer re-write the ugly `t.left =` `self.left =` ?

    package main

    import (
       "fmt"
       "sync"
    )

    type Node struct {
       left, right   *Node
    }

    var pool = sync.Pool {
       New: func() interface{} {
          return &Node{}
       },
    }

    func bottomUpTree(depth int) *Node {
       if depth <= 0 {
          return pool.Get().(*Node)
       }
       var t = pool.Get().(*Node)
       t.left = bottomUpTree(depth-1)
       t.right = bottomUpTree(depth-1)
       return t
    }

    func (self *Node) itemCheck() int {
       if self.left == nil {
          return 1
       }
       var check = 1 + self.left.itemCheck() + self.right.itemCheck()
       pool.Put(self.left)
       self.left = nil
       pool.Put(self.right)
       self.right = nil
       return check
    }

    func main() {
       const stretchDepth = 22
       check := bottomUpTree(stretchDepth).itemCheck()
       fmt.Printf("stretch tree of depth %v\t check: %v\n", stretchDepth, check)
    }

[robert engels]

Any use of sync.Pool is kind of a misuse in my opinion. If you review the code, it requires unlock/lock to get/put an item - not very cheap, and not great for highly concurrent situations - best to only use it for objects that are shared that are very expensive to instantiate, or unshared pools - but these are probably more efficient with a local free list.

So for uses like highly mutable binary trees - Go’s lack of a generational garbage collector really hurts.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[robert engels]

Unclear… revise… “it requires a lock & unlock for every get and put of an item"

[Isaac Gouy]

Is there a more concise way to write

[Sokolov Yura]

> Unclear… revise… “it requires a lock & unlock for every get and put of an item"

Not quite exactly. One item per scheduler (could be count as native thread) is stored in fast thread local storage. Yes, there are still locks, but for separate lock per thread, and this is quite cheap, since not contended.

[Robert Engels]

I reviewed the code and it is still pretty inefficient compared to a local free list. I don’t think the single local element helps in the binary tree case anyway, as you are probably releasing branches of the tree at a time. Also, in the face of high cpu based concurrency/contention, the local instance quickly becomes not used. The prime use of sync.Pool appears to me to be reusing a buffer that can’t be stack allocated.

On Mar 8, 2019, at 1:24 AM, Sokolov Yura <funny....@gmail.com> wrote:

>> Unclear… revise… “it requires a lock & unlock for every get and put of an item"
>
> Not quite exactly. One item per scheduler (could be count as native thread) is stored in fast thread local storage. Yes, there are still locks, but for separate lock per thread, and this is quite cheap, since not contended.
>