Package goque provides embedded, disk-based implementations of stack, queue, and priority queue data structures. Motivation for creating this project was the need for a persistent priority queue that remained performant while growing well beyond the available memory of a given machine. While there are many packages for Go offering queues, they all seem to be memory based and/or standalone solutions that are not embeddable within an application. Instead of using an in-memory heap structure to store data, everything is stored using the Go port of LevelDB (https://github.com/syndtr/goleveldb). This results in very little memory being used no matter the size of the database, while read and write performance remains near constant. See README.md or visit https://github.com/beeker1121/goque for more info. ExampleObject demonstrates enqueuing a struct object. ExamplePrefixQueue demonstrates the implementation of a Goque queue. ExamplePriorityQueue demonstrates the implementation of a Goque queue. ExampleQueue demonstrates the implementation of a Goque queue. ExampleStack demonstrates the implementation of a Goque stack.
Package securecookie is a fast, efficient and safe cookie value encoder/decoder. A secure cookie has its value ciphered and signed with a message authentication code. This prevents the remote cookie owner from knowing what information is stored in the cookie or modifying it. It also prevents an attacker from forging a fake securecookie. What makes this secure cookie package different is that it is fast (faster than the Gorilla secure cookie), and the value encoding and decoding needs no heap allocations. The intended use is to instantiate all secure cookie objects of your web site at program start up. In the following example "session" is the cookie name. The key is a byte sequence generated with the GenerateRandomKey() function. The same key must be used to retrieve the value. An securecookie can also be instantiated as a global variable with the MustNew function. The function will panic if an error occurs. A securecookie object is immutable. It's methods can be called from different goroutines. The Delete(), SetValue() and GetValue() methods are independent. To set a cookie value, call the SetValue() method with a http.ResponseWriter w, and a value val as arguments. A securecookie value is retrieved from an http.Request with the GetValue() method and is appended to the given buffer, extending it if required. If buf is nil, a new buffer is allocated. A securecookie is deleted by calling the Delete() method with the http.ResponseWriter w as argument.
Package fastheap provides a heap implementation specialized on numeric keys and arbitrary stored values. It is faster than containers/heap cause it doesn't use interface call for comparisons, and it manipulates storage by itself. Also, it uses 4 way heap instead of binary heap. May be it makes a deal with CPU cache :)
Package pprof serves via its HTTP server runtime profiling data in the format expected by the pprof visualization tool. For more information about pprof, see http://code.google.com/p/google-perftools/. The package is typically only imported for the side effect of registering its HTTP handlers. The handled paths all begin with /debug/pprof/. To use pprof, link this package into your program: If your application is not already running an http server, you need to start one. Add "net/http" and "log" to your imports and the following code to your main function: Then use the pprof tool to look at the heap profile: Or to look at a 30-second CPU profile: Or to look at the goroutine blocking profile: To view all available profiles, open http://localhost:6060/debug/pprof/ in your browser. For a study of the facility in action, visit
Package heap implements a very similar function to the builtin heap(priority queue) package except the elements are not necessarily interface{}, but can be any type. The trick is using the last element as the in/out place. Push/Pop/Remove are replaced with PushLast/PopToLast/RemoveToLast, respectively. An heap with int value can be easily implemented as follow:
Example of using github.com/dengliu/gocommon/heap import ( )
Package fheap implements the the Fibonacci Heap. This example illustrates queing and dequeuing from a Fibonacci heap.
goheap is a simple implementation of the heap data structure and sorting algorithm. Its intention is for learning purposes of the Go language.
TODO : update An off-heap hash-table for Go (golang). Originally called go-offheap-hashtable, but now shortened to just offheap. The purpose here is to have a hash table that can work away from Go's Garbage Collector, to avoid long GC pause times. We accomplish this by writing our own Malloc() and Free() implementation (see malloc.go) which requests memory directly from the OS. The keys, values, and entire hash table is kept on off-heap storage. This storage can also optionally be backed by memory mapped file for speedy persistence and fast startup times. Initial HashTable implementation inspired by the public domain C++ code of See also for performance studies of the C++ code. The implementation is mostly in offheap.go, read that to start. Maps pointer-sized integers to Cell structures, which in turn hold Val_t as well as Key_t structures. Uses open addressing with linear probing. This makes it very cache friendly and thus very fast. In the t.Cells array, UnHashedKey = 0 is reserved to indicate an unused cell. Actual value for key 0 (if any) is stored in t.ZeroCell. The hash table automatically doubles in size when it becomes 75% full. The hash table never shrinks in size, even after Clear(), unless you explicitly call Compact(). Basic operations: Lookup(), Insert(), DeleteKey(). These are the equivalent of the builtin map[uint64]interface{}. As an example of how to specialize for a map[string]*Cell equivalent, see the following functions in the bytekey.go file: Example use: Note that this library is only a starting point of source code, and not intended to be used without customization. Users of the HashTable will have to customize it by changing the definitions of Key_t and Val_t to suite their needs. I'm experimenting next with storing objects in Capnproto serialized format, but this branch (branch capnp) isn't quite ready for use. Related ideas: https://gist.github.com/mish15/9822474 (using CGO) https://groups.google.com/forum/#!topic/golang-nuts/kCQP6S6ZGh0 not fully off-heap, but using a slice instead of a map appears to help GC quite alot too: https://github.com/cespare/kvcache/blob/master/refmap.go
Package bitfield64 is a simple, quick stack-based bit-field manipulator package of 64 bits (or less) in length. If you need more bits you either need to create an array of bitfield64-s (and stay on the stack) or need to switch to the heap-based bitfield package. Methods are stateless and free from side-effects. It was designed to be chainable. Range for position must be [0, 63]. position outside this range will get the modulo treatment, so 64 will point to the 0th element, -1 will address the last element (i.e. 63rd), -2 the one before (i.e. 62nd), etc.
Package btree implements in-memory B-Trees of arbitrary degree. btree implements an in-memory B-Tree for use as an ordered data structure. It is not meant for persistent storage solutions. It has a flatter structure than an equivalent red-black or other binary tree, which in some cases yields better memory usage and/or performance. See some discussion on the matter here: Note, though, that this project is in no way related to the C++ B-Tree implementation written about there. Within this tree, each node contains a slice of items and a (possibly nil) slice of children. For basic numeric values or raw structs, this can cause efficiency differences when compared to equivalent C++ template code that stores values in arrays within the node: These issues don't tend to matter, though, when working with strings or other heap-allocated structures, since C++-equivalent structures also must store pointers and also distribute their values across the heap. This implementation is designed to be a drop-in replacement to gollrb.LLRB trees, (http://github.com/petar/gollrb), an excellent and probably the most widely used ordered tree implementation in the Go ecosystem currently. Its functions, therefore, exactly mirror those of llrb.LLRB where possible. Unlike gollrb, though, we currently don't support storing multiple equivalent values.
Package gomempool implements a simple memory pool for byte slices. The Go garbage collector runs more often when more bytes are allocated. (For full details, see the runtime package documentation on the GOGC variable.) Avoiding allocations can help the stop-the-world GC run much less often. To determine if you should use this, first deploy your code into as realistic an environment as possible. Extract a runtime.MemStats structure from your running code. Examine the various Pause fields in that structure to determine if you have a GC problem, preferably in conjunction with some other monitoring of real performance. (Remember the numbers are in nanoseconds.) If the numbers you have are OK for your use case, STOP HERE. Do not proceed. If you are generating a lot of garbage collection pauses, the next question is why. Profile the heap. If the answer is anything other than []byte slices, STOP HERE. Do not proceed. Finally, if you are indeed seeing a lot of allocations of []bytes, you may wish to preceed with using this library. gomempool is a power tool; it can save your program, but it can blow your feet off, too. (I've done both.) That said, despite the narrow use case of this library, it can have an effect in certain situations, which I happened to encounter. I suspect the biggest use case is a network application that often allocates large messages, which is what I have, causing an otherwise relatively memory-svelte program to allocate dozens of megabytes per second of []byte buffers to process messages. To use the pool, there are three basic steps: The following prose documentation will cover each step at length. Expand the Example below for concise usage examples and things you can copy & paste. First, create a pool. A *Pool is obtained by calling gomempool.New. All methods on the *Pool are threadsafe. The pool can be configured via the New call. A nil pointer of type *gomempool.Pool is also a valid pool. This will use normal make() to create byte slices and simply discard the slice when asked to .Return() it. This is convenient for testing whether you've got a memory error in your code, because you can swap in a nil Pool pointer without changing any other code. If an error goes away when you do that, you have a memory error. (Probably .Return()ing something too soon.) []bytes in the pool come with an "Allocator" that is responsible for returning them correctly. To obtain an allocator, you call GetNewAllocator() on the pool. This returns an allocator that is not yet used. You may then call .Allocate(uint64) on it to assign a []byte from the pool. This []byte is then associated with that Allocator until you call .Return() on the allocator, after which the []byte goes back into the pool. If you ask for more bytes than the pool is configured to store, the Allocator will create a transient []byte, which it will not manage. You can check whether you are invoking this case by calling .MaxSize on the pool. You MUST NOT call .Return() until you are entirely done with the []byte. This includes shared slices you may have created; this is by far the easiest way to get in trouble with a []byte pool, as it is easy to accidentally introduce sharing without realizing it. You must also make sure not to do anything with your []byte that might cause another []byte to be created instead; for instance, using your pooled []byte in an "append" call is dangerous, because the runtime might decide to give you back a []byte that backs to an entirely different array. In this case your []byte and your Allocator will cease to be related. If the Allocator is correctly managed, your code will not fail, but you won't be getting any benefit, either. You may retrieve the []byte slice corresponding to an Allocator at any time by calling .Bytes(). This means that if you do need to pass the []byte and Allocator around, it suffices to pass just the Allocator. (Though, be aware that the Allocator's []byte will be of the original size you asked for. This can not be changed, as you can not change the original slice itself.) Allocators can be reused freely, as long as they are used correctly. However, an individual Allocator is not threadsafe. Its interaction with the Pool is, but its internal values are not; do not use the same Allocator from more than one goroutine at a time. Once allocated, an allocator will PANIC if you try to allocate again with ErrBytesAlreadyAllocated. Once .Return() has been called, an allocator will PANIC if you try to .Return() the []byte again. If no []byte is currently allocated, .Bytes() will PANIC if called. This is fully on purpose. All of these situations represent profound errors in your code. This sort of error is just as dangerous in Go as it is in any other language. Go may not segfault, but memory management issues can still dish out the pain; better to find out earlier rather than later. You can combine obtaining an Allocator and a particular sized []byte by calling .Allocate() on the pool. The Allocators returned by the nil *Pool use make() to create new slices every time, and simply discard the []byte when done, but they enforce the exact same rules as the "real" Allocators, and panic in all the same places. This is so there is as little difference as possible between the two types of pools. Optionally return the byte slices Calling .Return() on an allocator is optional. If a []byte is not returned to the pool, you do not get any further benefit from the pool for that []byte, but the garbage collector will still clean it up normally. This means using a pool is still feasible even if some of your code paths may need to retain a []byte for a long or complicated period of time. If you have a byte slice that is getting passed through some goroutines, I recommend creating a structure that holds all the relevant data about the object bound together with the allocator: which makes it easy to keep the two bound together, and pass them around, with only the last user finally performing the deallocation. This library does not provide this structure since all I could give you is basically the above struct, with an interface{} in it. You can query the pool for its cache statistics by calling Stats(), which will return a structure describing how the individual buckets are performing. Quality: At the moment I would call this alpha code. Go lint clean, go vet clean, 100% coverage in the tests. You and I both know that doesn't prove this is bug-free, but at least it shows I care.
Package gomempool implements a simple memory pool for byte slices. The Go garbage collector runs more often when more bytes are allocated. (For full details, see the runtime package documentation on the GOGC variable.) Avoiding allocations can help the stop-the-world GC run much less often. To determine if you should use this, first deploy your code into as realistic an environment as possible. Extract a runtime.MemStats structure from your running code. Examine the various Pause fields in that structure to determine if you have a GC problem, preferably in conjunction with some other monitoring of real performance. (Remember the numbers are in nanoseconds.) If the numbers you have are OK for your use case, STOP HERE. Do not proceed. If you are generating a lot of garbage collection pauses, the next question is why. Profile the heap. If the answer is anything other than []byte slices, STOP HERE. Do not proceed. Finally, if you are indeed seeing a lot of allocations of []bytes, you may wish to preceed with using this library. gomempool is a power tool; it can save your program, but it can blow your feet off, too. (I've done both.) That said, despite the narrow use case of this library, it can have an effect in certain situations, which I happened to encounter. I suspect the biggest use case is a network application that often allocates large messages, which is what I have, causing an otherwise relatively memory-svelte program to allocate dozens of megabytes per second of []byte buffers to process messages. To use the pool, there are three basic steps: The following prose documentation will cover each step at length. Expand the Example below for concise usage examples and things you can copy & paste. First, create a pool. A *Pool is obtained by calling gomempool.New. All methods on the *Pool are threadsafe. The pool can be configured via the New call. A nil pointer of type *gomempool.Pool is also a valid pool. This will use normal make() to create byte slices and simply discard the slice when asked to .Return() it. This is convenient for testing whether you've got a memory error in your code, because you can swap in a nil Pool pointer without changing any other code. If an error goes away when you do that, you have a memory error. (Probably .Return()ing something too soon.) []bytes in the pool come with an "Allocator" that is responsible for returning them correctly. To obtain an allocator, you call GetNewAllocator() on the pool. This returns an allocator that is not yet used. You may then call .Allocate(uint64) on it to assign a []byte from the pool. This []byte is then associated with that Allocator until you call .Return() on the allocator, after which the []byte goes back into the pool. Allocations never fail (barring a complete out-of-memory situation, of course). If the pool does not have a correctly-sized []byte on hand, it will create one. If you ask for more bytes than the pool is configured to store, the Allocator will create a transient []byte, which it will not manage. You can check whether you are invoking this case by calling .MaxSize on the pool. You MUST NOT call .Return() until you are entirely done with the []byte. This includes shared slices you may have created; this is by far the easiest way to get in trouble with a []byte pool, as it is easy to accidentally introduce sharing without realizing it. You must also make sure not to do anything with your []byte that might cause another []byte to be created instead; for instance, using your pooled []byte in an "append" call is dangerous, because the runtime might decide to give you back a []byte that backs to an entirely different array. In this case your []byte and your Allocator will cease to be related. If the Allocator is correctly managed, your code will not fail, but you won't be getting any benefit, either. You may retrieve the []byte slice corresponding to an Allocator at any time by calling .Bytes(). This means that if you do need to pass the []byte and Allocator around, it suffices to pass just the Allocator. (Though, be aware that the Allocator's []byte will be of the original size you asked for. This can not be changed, as you can not change the original slice itself.) Allocators can be reused freely, as long as they are used correctly. However, an individual Allocator is not threadsafe. Its interaction with the Pool is, but its internal values are not; do not use the same Allocator from more than one goroutine at a time. Once allocated, an allocator will PANIC if you try to allocate again with ErrBytesAlreadyAllocated. Once .Return() has been called, an allocator will PANIC if you try to .Return() the []byte again. If no []byte is currently allocated, .Bytes() will PANIC if called. This is fully on purpose. All of these situations represent profound errors in your code. This sort of error is just as dangerous in Go as it is in any other language. Go may not segfault, but memory management issues can still dish out the pain; better to find out earlier rather than later. You can combine obtaining an Allocator and a particular sized []byte by calling .Allocate() on the pool. The Allocators returned by the nil *Pool use make() to create new slices every time, and simply discard the []byte when done, but they enforce the exact same rules as the "real" Allocators, and panic in all the same places. This is so there is as little difference as possible between the two types of pools. Optionally return the byte slices Calling .Return() on an allocator is optional. If a []byte is not returned to the pool, you do not get any further benefit from the pool for that []byte, but the garbage collector will still clean it up normally. This means using a pool is still feasible even if some of your code paths may need to retain a []byte for a long or complicated period of time. If you have a byte slice that is getting passed through some goroutines, I recommend creating a structure that holds all the relevant data about the object bound together with the allocator: which makes it easy to keep the two bound together, and pass them around, with only the last user finally performing the deallocation. This library does not provide this structure since all I could give you is basically the above struct, with an interface{} in it. You can query the pool for its cache statistics by calling Stats(), which will return a structure describing how the individual buckets are performing.