mstoykov / atlas Goto Github PK
View Code? Open in Web Editor NEWLicense: Apache License 2.0
License: Apache License 2.0
This definitely needs benchmarking, but I've been thinking that atlas will allocate quite a lot of Node
values on the heap, even with optimal usage, and they persist basically forever. So, the Go garbage collector will have its job cut out for it, walking through all of these references between the Node
values, only to end up collecting basically none of them.
What if there was this buffer, say a slice of fixed-length arrays like [][1000]Node
. And we have a couple of atomics and some light locking (around creating a new array buffer block) and instead of creating a new Node
and returning its pointer here:
Lines 135 to 139 in 388f114
We just get the ID of the next free Node in the buffer, fill in the details and return a pointer to the specific array element? I am making some assumptions on how the Go GC works, so this idea might be complete nonsense... ๐ If someone knows better, please share. Otherwise, I think it's worth benchmarking.
I am not sure if this brings in any value:
Line 19 in 23cc720
The IsRoot()
check:
Lines 33 to 36 in 23cc720
func (n *Node) IsRoot() bool {
return n.prev == n
}
Maybe we can add a level int
property in its place instead? That can tells us how deep the current Node
is in the graph, i.e. how many key=value tags it contains. Which will be useful for informational purposes, or if we want to pre-allocate a map or a slice container to put the in. Or, if we want to iterate over the list more easily, though that also be done with for !n.IsRoot() { }
๐ค
Apparently, the second version [TODO: link here when merged] is faster than if n.linkKey == sub.linkKey
. Discover why and evaluate the difference with LinkKey{Key: "abc", Value: "xyz"}
or other alternative solutions.
if n.linkKey == sub.linkKey
goos: linux
goarch: amd64
pkg: github.com/mstoykov/atlas
cpu: AMD Ryzen 7 4800H with Radeon Graphics
BenchmarkContains/1000-16 203409088 5.927 ns/op 0 B/op 0 allocs/op
BenchmarkContains/10000-16 198273142 6.027 ns/op 0 B/op 0 allocs/op
BenchmarkContains/100000-16 193312813 6.105 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/mstoykov/atlas 7.983s
if n.linkKey[0] == sub.linkKey[0] && n.linkKey[1] == sub.linkKey[1]
goos: linux
goarch: amd64
pkg: github.com/mstoykov/atlas
cpu: AMD Ryzen 7 4800H with Radeon Graphics
BenchmarkContains/1000-16 345073720 3.344 ns/op 0 B/op 0 allocs/op
BenchmarkContains/10000-16 348490562 3.390 ns/op 0 B/op 0 allocs/op
BenchmarkContains/100000-16 338773561 3.402 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/mstoykov/atlas 7.036s
A thing that came up is using *Node as a key in a map to cache something. But if that somethign will be needed in multiple places in might be easier to have it in the *Node.
Having multiple key/values will be harder but maybe just a simple Sync.Map will be enough ๐ค
This might not be so great in general as the current use cases is caching the marshalling of the node in different formats - JSON, CSV, w/e else we need. But adding this will mean that at least one more sync.Map
will need to always be allocated.
Node.ValueByKey()
and Node.Contains()
can probably be improved by taking into account that the keys are sorted. So we don't always need to reach the root - if the key of the current Node is "lower' than the one we are comparing it against, we don't need to dig any deeper, right?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.