zond/gotomic

Non blocking data structures for Go

gotomic's Issues

Breaking out of list/map iteration

This is not so much an issue, as it is a request for comment.
The list and map iterators do not appear to have any way to break out of the iteration.

I'm running into a few cases, where I use the iterator to find a specific element. This can not be found by a hash key, as the filter is one of the fields in the value itself.
Once my iterator has found the item I am looking for, it is a bit senseless to continue iterating over the remaining elements in the list/map.

I had a quick look at the source code and noticed that Hash.Each internally uses the list iterator. How hard/sensible would it be to offer a way to break out of the iteration?

I was thinking about altering the signatures of HashIterator and ListIterator to return a boolean value. When the iterator returns false, the iteration should be stopped. This does pose a rather significant API change though.

Any thoughts on this?

put/get is extremely slow?

I wrote a code to test the performance of the concurrent hash table, but I found the performance is extremely slow. Did I miss anything here?

package main

import (
	"github.com/zond/gotomic"
	"fmt"
	"math/rand"
	"time"
)

type key string
func (self key) HashCode() uint32 {
	var rval uint32
	for c := range self {
		rval = rval + uint32(c)
	}
	return rval
}
func (self key) Equals(t gotomic.Thing) bool {
	return t.(key) == self
}


var letterRunes = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func RandStringRunes(localrand *rand.Rand, n int) string {
	b := make([]rune, n)
	for i := range b {
		b[i] = letterRunes[localrand.Intn(len(letterRunes))]
	}
	return string(b)
}


func main() {
	h := gotomic.NewHash()

	ch := make(chan bool)

	for i:=0;i < 10; i ++{
		go func(){
			source := rand.NewSource(time.Now().UnixNano())
			local_rand := rand.New(source)
			for k := 0; k < 100000;k ++ {
				k := RandStringRunes(local_rand, 8)
				v := RandStringRunes(local_rand, 8)
				h.Put(key(k), v)
				if val, _ := h.Get(key(k)); val != v {
					panic("wth?")
				}
			}
			ch <- true
		}()

	}

	for i:=0;i < 10; i ++{
		<- ch
	}

	fmt.Println("done!")
}

go race detector reporting race conditions

We're from dgraph (github.com/dgraph-io/dgraph) and we have been using your lock-free hash.

One thing that puzzled us recently is why the Go race detector detects race conditions in some of our Go packages, for example "query".

go test -race github.com/dgraph-io/dgraph/query/...

We thought the lock-free hash use atomics and should not have race conditions. Are these expected? Here is the output for the above run. Any suggestions would be most welcome!

==================
WARNING: DATA RACE
Read at 0x00c42032cd90 by goroutine 69:
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).getBucketByIndex()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:407 +0x131
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).getBucketByIndex()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:417 +0x285
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).getBucketByIndex()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:417 +0x285
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).getBucketByIndex()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:417 +0x285
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).getBucketByIndex()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:417 +0x285
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).getBucketByHashCode()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:393 +0x66
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).GetHC()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:247 +0x98
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).Get()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:260 +0x6c
  github.com/dgraph-io/dgraph/posting.GetOrCreate()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/posting/lists.go:251 +0x107
  github.com/dgraph-io/dgraph/worker.processTask()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/worker/task.go:106 +0x561
  github.com/dgraph-io/dgraph/worker.ProcessTaskOverNetwork()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/worker/task.go:59 +0x5f0
  github.com/dgraph-io/dgraph/query.ProcessGraph()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/query/query.go:645 +0x12d5

Previous write at 0x00c42032cd90 by goroutine 70:
  sync/atomic.CompareAndSwapInt64()
      /usr/lib/go-1.7/src/runtime/race_amd64.s:298 +0xb
  sync/atomic.CompareAndSwapPointer()
      /usr/lib/go-1.7/src/runtime/atomic_pointer.go:67 +0x43
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).getBucketByHashCode()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:393 +0x66
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).GetHC()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:247 +0x98
  github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic.(*Hash).Get()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/vendor/github.com/zond/gotomic/hash.go:260 +0x6c
  github.com/dgraph-io/dgraph/posting.GetOrCreate()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/posting/lists.go:251 +0x107
  github.com/dgraph-io/dgraph/worker.processTask()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/worker/task.go:106 +0x561
  github.com/dgraph-io/dgraph/worker.ProcessTaskOverNetwork()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/worker/task.go:59 +0x5f0
  github.com/dgraph-io/dgraph/query.ProcessGraph()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/query/query.go:645 +0x12d5

Goroutine 69 (running) created at:
  github.com/dgraph-io/dgraph/query.ProcessGraph()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/query/query.go:692 +0x4db

Goroutine 70 (finished) created at:
  github.com/dgraph-io/dgraph/query.ProcessGraph()
      /home/jchiu/go/src/github.com/dgraph-io/dgraph/query/query.go:692 +0x4db
==================

License?

Under which license do you release this?

Memory leaks

Good day!

We are from dgraph again. We have been using your implementation of a lock-free hash.

We wanted to follow up from:
#5

Since the fix, it seems that we have been seeing memory leaks. We use the hash as a caching mechanism. When there is a miss, we load extra stuff into memory. We wonder if you may have some insights into why the changes / fix might have caused the memory leaks?

Thank you so much.

Jay