Heap

Package profiler is a client for the Stackdriver Profiler service. This package is still experimental and subject to change. Usage example: Calling Start will start a goroutine to collect profiles and upload to the profiler server, at the rhythm specified by the server. The caller must provide the service string in the config, and may provide other information as well. See Config for details. Profiler has CPU, heap and goroutine profiling enabled by default. Mutex profiling can be enabled in the config. Note that goroutine and mutex profiles are shown as "threads" and "contention" profiles in the profiler UI.

Package nistec implements the NIST P elliptic curves from FIPS 186-4. This package uses fiat-crypto or specialized assembly and Go code for its backend field arithmetic (not math/big) and exposes constant-time, heap allocation-free, byte slice-based safe APIs. Group operations use modern and safe complete addition formulas where possible. The point at infinity is handled and encoded according to SEC 1, Version 2.0, and invalid curve points can't be represented.

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 stealthpool provides a memory pool that allocates blocks off-heap that will NOT be tracked by the garbage collector. The name stealthpool comes from the fact that the memory being allocated by the pool is `stealthy` and will not be garbage collected ever. These blocks should be used in situations where you want to keep garbage collection to a bare minimum. Needless to say, since the GC will not track any of the memory, extreme care must be had in order to avoid memory leaks:

Package bheap implements binomial-heap. This package uses callbacks to compare items. Using tricks to get pointer of empty interface values can avoid data copying and runtime assertions, therefore greatly improve performance. It's your responsibility to assure type safe.

Grind polishes Go programs. Usage: Grind rewrites the source files in the named packages. When grind rewrites a file, it prints a line to standard error giving the name of the file and the rewrites applied. As a special case, if the arguments are a list of Go source files, they are considered to make up a single package, which is then rewritten. If the -diff flag is set, no files are rewritten. Instead grind prints the differences a rewrite would introduce. Grind does not make backup copies of the files that it edits. Instead, use a version control system's “diff” functionality to inspect the changes that grind makes before committing them. Grind is a work in progress. More rewrites are planned. The initial use case for grind is cleaning up Go code that looks like C code. Grind removes unreachable (dead) code. Code is considered unreachable if it is not the target of a goto statement and is preceded by a terminating statement (see golang.org/ref/spec#Terminating_statements), or a break or continue statement. If the target of a goto is a block of code that is only reachable by following that goto statement, grind replaces the goto with a copy of the target code and deletes the original target code. If the target of a goto is an explicit or implicit return statement, replaces the goto with a copy of the return statement. Grind removes unused labels. Grind rewrites := declarations of complex zero types, such as: to use plain var declarations, as in: Grind moves var declarations as close as possible to their uses. When possible, it combines the declaration with the initialization, and it splits disjoint uses of a single variable into multiple variables. For example, consider: Grind deletes the declaration and rewrites both loop initializers to use a combined declaration and assignment (i := 0). Limitation: Grind does not move variable declarations into loop bodies. It may in the future, provided it can determine that the variable is dead on entry to the body and that the variable does not escape (causing heap allocation inside the loop). Limitation: Grind considers variables that appear in closures off limits. A more sophisticated analysis might consider them in the future.

Package heap provides the implementation of a generic binary heap.

Package mmheap provides a drop-in min-max heap for any type that implements heap.Interface. In a min-max heap, the minimum element is at the root at index 0, and the maximum element is in one of the two root children. Thus, a min-max heap provides an efficient way to access either the minimum or maximum elements in a set in O(1) time. Due to the increased number of comparisons to implement a min-heap, its runtime is slower than a general heap (in this implementation, just under 2x). Because of this, unless you need to continually access both the minimum and maximum elements, it may be beneficial to use a different data structure. Even if you do need to continually access the minimum or maximum, a different data structure may be better. This package exists for anybody looking, but I recommend benchmarking this against github.com/google/btree. Generally, a btree is a good and fast data structure for quickly accessing min and max elements. However, a key benefit of heap or mmheap is the ability to change or modify elements and fix their position in the tree. For more information about a min-max heap, read the following paper: Since this package is identical to the stdlib's container/heap documentation, it is elided here.

Package heapanalytics provides a go client for the heap analytics server-side API. See https://heapanalytics.com for more details

Offheap 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. On Save(), serialization of the HashTable itself is done using msgpack to write bytes to the first page (4k bytes) of the memory mapped file. This uses github.com/tinylib/msgp which is a blazing fast msgpack serialization library. It is fast because it avoids reflection and pre-computes the serializations (using go generate based inspection of your go source). If you need to serialize your values into the Val_t, I would suggest evaluating the msgp for serialization and deserialization. The author, Philip Hofer, has done a terrific job and put alot of effort into tuning it for performance. If you are still pressed for speed, consider also omitting the field labels using the '//msgp:tuple MyValueType' annotation. As Mr. Hofer says, "For smaller objects, tuple encoding can yield serious performance improvements." [https://github.com/tinylib/msgp/wiki/Preprocessor-Directives]. Related ideas: https://gist.github.com/mish15/9822474 (using CGO) CGO note: the cgo-malloc branch of this github repo has an implementation that uses CGO to call the malloc/calloc/free functions in the C stdlib. Using CGO gives up the save-to-disk instantly feature and creates a portability issue where you have linked against a specific version of the C stdlib. However if you are making/destroying alot of tables, the CGO approach may be faster. This is because calling malloc and free in the standard C library are much faster than making repeated system calls to mmap(). more related ideas: 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

The heappermutations package implements primitives to generate all possible permutations following Heap's algorithm on typed collection.

Package fibHeap implements the Fibonacci Heap priority queue. This implementation is a bit different from the traditional Fibonacci Heap by having an index map to achieve better encapsulation.