7 ms·
Golang data structures
- vessenes 11y agoSome of these sound really great. A major pain point with go concurrency is the absence of a fast lockfree map implementation that doesn't destroy your GC times. The 'ctrie' sounds very appealing; I'm curious to try it.
- tptacek 11y agoWhoah.
- timmytokyo 11y agoThis point about the B-tree is salient: Unfortunately, to make the B-tree generic we require an interface and the most expensive operation in CPU profiling is the interface method which in turn calls into runtime.assertI2T. We need generics. One of the most frustrating aspects of go is having to resort to interface{} every time you want a generic implementation of a data structure.
- vessenes 11y agoIt's just not worth using interface. And, I think, by the way, that has always been the intent from a syntax point of view. The fact that it's slow on the CPU side is not great, but I don't think it's a major problem in the eyes of the core dev team: as far as I can tell, they do not believe that generics support as commonly envisioned is in line with go's mission. Go is the anti-lisp / anti-unix of languages; designed to not give a team of junior devs enough rope to hang themselves. If we'd like a generics proposal that would get buy-in, I think we need to adhere to that dream while we imagine working generics and propose something; I bet it would be accepted.
- edgyswingset 11y ago> designed to not give a team of junior devs enough rope to hang themselves I find this to be an utterly silly goal.
- pjmlp 11y agoNot really. Go doesn't fit Google hiring process "we only want CS Phds". It is also not one language that one can use on the interview exercises. So given Rob Pike's statement about an easy language for newly hires, one has to wonder where they are coming from.
- timmytokyo 11y agoIsn't that sort of like saying it's not worth using data structures other than maps and slices? In go, if you want a complex data structure you either use interfaces -- as the authors of this library did -- or you rely on some sort of code generation approach. I've followed the go team's discussion of generics for a long time now. They've always claimed they're open to proposals that fit the philosophy of the language, but they're seemingly not in any hurry to address the issue. And that's fine. But I won't pretend it isn't frustrating every time I want to build something with a non-trivial data structure. Sometimes a map or a slice just doesn't cut it.
- 11y ago
- chrissnell 11y agoFor an alternative to Futures, check out tv42's "topic": http://github.com/tv42/topic http://github.com/tv42/topic I used it here in my multiplexing serial-to-TCP adapter: https://github.com/chrissnell/tnc-server/blob/master/tnc-server.go https://github.com/chrissnell/tnc-server/blob/master/tnc-ser...
- ansible 11y agoNow someone will hopefully create "type writers" for gen [1] for compile-time type checking and convenience. [1] http://clipperhouse.github.io/gen/typewriters/ http://clipperhouse.github.io/gen/typewriters/
- nemothekid 11y agoSomething I've always wondered - in the futures packages (https://github.com/Workiva/go-datastructures/blob/master/futures/futures.go https://github.com/Workiva/go-datastructures/blob/master/fut...): The author has a variable `triggered` to check the state of whether or not the future is complete. Now to protect that variable from data races, the author uses a standard lock. Now since you need to protect a simple value what I would do in this situation is use an atomic variable w/ atomic.StoreInt32 (you could also probably not even have to use an atomic load in GetResult). Of course the best option would be to benchmark (and I'm assuming the author did, given that the structures are performant), but I'm wondering if my "gut" is right and under what situations others have seen that would necessitate a lock vs. an atomic instruction (high contention on readers, few writers)?
- simonz05 11y agoI think you are wrong in thinking he is protecting the `triggered` variable with the lock. He's using a Mutex to synchronize access on the entire struct. snippet from https://github.com/Workiva/go-datastructures/blob/master/futures/futures.go#L64 https://github.com/Workiva/go-datastructures/blob/master/fut... f.lock.Lock() f.triggered = true f.item = item f.err = err f.lock.Unlock() f.wg.Done()
- nemothekid 11y agoI'm confident the following is identical (if nothing else about the code changes). Notice how access to `f.item` and `f.err` aren't read protected in `GetResult`. func (f *Future) setItem(item interface{}, err error) { f.item = item f.err = err f.lock.Lock() f.triggered = true f.lock.Unlock() f.wg.Done() } Any reader of `f.item` or `f.err` (in `GetResult`) is essentially waiting for triggered to be true before reading the value of those respective fields. If after an atomic load or synchronized access of triggered returns `true`, both versions of `setItem` should guarantee that a subsequent read of `f.item` will return the "promised" value. In any case, because the reads (in `GetResult`) aren't protected as well, and the call to `setItem` which writes to `item` and `err` only happens on a single thread, the only thing the code perfectly protects now are reads of triggered.
- amelius 11y agoNice work. It is a pity that Go has no generics, though. With them, data structures would be much more efficient and easier to work with.
- ekr 11y agoHas anyone used Ctries in any real scenario (has anyone implemented them in a language like C)? How do they fare as opposed to other data structures? Is the latency of CAS instructions insignificant? I'm thinking of using it in our codebase, in theory it should speed things up quite a bit.
- akavlie 11y agoOur Matchbox[0] library uses a copy of the ctrie in this repo [0] https://github.com/Workiva/matchbox https://github.com/Workiva/matchbox
- deleted 11y ago[deleted]