Heap

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 heapanalytics provides a go client for the heap analytics server-side API. See https://heapanalytics.com for more details

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

This example shows a use in the Heapsort algorithm This example shows how to implement your own CompareFunc and the use on a defined type

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

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

Beacon is a command line tool that helps developers stay in sync with breaking changes among their team. Beacon was made as a THE HEAP project, for the month of August 2017. This document details how a user interacts with Beacon as well as a developer map for navigating the project. If you are confused or lost, consider viewing the Terms at the bottom of this document for possible clarification. A user interacts with Beacon by either Reading or Writing from the Beacon log. At the base level, Beacon allows a series of sub commands that you can pass into your usage of the application. Let's take a brief look of the core API: Beacon Init handles setting up beacon for the first time. It creates a `.beaconrc` at the root of your project, and uses git information to provide message log metadata. Will also create a beacon_log.json file at your project root if it does not yet exist. Provides functionality to add new breaking changes to the beacon log file. Displays a variable number of breaking changes as per <INT> Displays all breaking changes. This project heartily welcomes new developers. Please consider looking into contributing. This application was intended to be sketched out in a month's time, with further refinement and polish beyond that deadline. Beyond the time restrictions, the project maintainer (yours truly) is writing in Go for their first time. If you should come across any Go code that could use a refactor to become both cleaner, faster, or in general, more idiomatic, please make a PR along with an explanation of your changes and why it better fits Go idioms, etc. Now, let's consider the main layout and structure of the project: Our project is currently broken into two main pieces of functionality (along with a few extraneous functions / files.) One part of our project (messages.log) handles everything to do with the creation, reading and writing of Logs to the Beacon Log. messages.log interacts closely with the `beacon_log.json` file. Beacon is a project from THE HEAP (http://github.com/the-heap). This project is open source and you are free to do with it as you like. If you enjoy the project, please let us know. Keep up to date with THE HEAP on twitter (http://twitter.com/theheap_) and consider becoming a contributor either on forthcoming projects or work on previous projects. // TODO: put in contributors - Breaking Change: Any change to a codebase that requires all members working on said codebase to upgrade, update, migrate etc in order to get back to a working development environment. - Log: A message in the Beacon Log, describing a breaking change. - Beacon Log - a JSON file responsible for chronicling breaking changes for a team. This file should be checked into your repository

Package heap provides heap operations for string, int64, and uint64. A heap is a tree with the property that each node is the minimum-valued node in its subtree. The minimum element in the tree is the root, at index 0. This package is copied from the standard library container/heap and modified for concrete types such as string. Package heap also provides structs MaxStr, MaxInt64, and MaxUint64 for maximum versions of 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 heapq implements a generic heap-structured priority queue.

Package binaryheap provides an implementation of a slice backed binary heap where the order can be customized by a comparator function.

Package heap implements a priority queue over a slice. The queue is ordered using a compare function.

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.

Package heap implements indexed minimum Fibonacci priority queue.

Package fibheap provides a standard Fibonacci heap pointer implementation. The nodes are linked in a doubly-linked circular list. The parent nodes have a pointer to the left-most child, while all children have a reference to their parent

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