-
Notifications
You must be signed in to change notification settings - Fork 0
A set implmentation which is very fast at the expense of memory. Based upon http://research.swtch.com/sparse
License
LGPL-3.0, GPL-3.0 licenses found
Licenses found
LGPL-3.0
COPYING.LESSER
GPL-3.0
COPYING
ericherman/libfastset
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
An implementation of "Using Uninitialized Memory for Fun and Profit" http://research.swtch.com/sparse This is a set implementation for which add(), contains(), remove(), size(), and clear() operations are all O(1). Set iteration, intersect, and cloning are O(n). This performance boost comes by trading memory for speed. Specifically, this is terribly inefficient in terms of space, because it allocates twice the amount of memory as required to hold the maxinum number of elements. Russ Cox, in "Using Uninitialized Memory for Fun and Profit" writes: The sparse set is as fast or faster than bit vectors for every operation. The only problem is the space cost: two words replace each bit. Still, there are times when the speed differences are enough to balance the added memory cost. Briggs and Torczon point out that liveness sets used during register allocation inside a compiler are usually small and are cleared very frequently, making sparse sets the representation of choice. Dependencies ------------ The tests depend upon libecheck * https://github.com/ericherman/libecheck Packaging --------- autoreconf -iv && ./configure && make && make distcheck && echo "Success." License ------- Unless a file specifically says otherwise, all content is Licensed under the terms of the GNU Lesser General Public License (LGPL), version 3 or later. See COPYING and COPYING.LESSER for details.
About
A set implmentation which is very fast at the expense of memory. Based upon http://research.swtch.com/sparse
Resources
License
LGPL-3.0, GPL-3.0 licenses found
Licenses found
LGPL-3.0
COPYING.LESSER
GPL-3.0
COPYING
Stars
Watchers
Forks
Packages 0
No packages published