Edit on GitHub

PureFun.Contiguous for small size optimizations

PureFun.Contiguous — Module

PureFun.Contiguous implements small-sized versions of lists, sets, and dictionaries. These structures maintain data in contiguous storage, allowing them to leverage the CPU cache to improve the performance of indexing and iteration.

source

Chunks: densely packed lists

PureFun.Contiguous.StaticChunk — Type
StaticChunk{N,T}
StaticChunk{N}(iter)

Backed by Static Arrays, StaticChunks implement all list functions but are constrained to a maximum size. Useful in conjunction with PureFun.Chunky.@list, which chains together small chunks to build general list types that benefit from data locality.

Examples

This example builds a list with maximum length 8. Until we hit the maximum length, we can use the StaticChunk like any other list type:

julia> xs = Contiguous.StaticChunk{8}(1:3)
3-element PureFun.Contiguous.StaticChunk{8, Int64}
1
2
3

julia> 41 ⇀ 42 ⇀ xs
5-element PureFun.Contiguous.StaticChunk{8, Int64}
41
42
1
2
3

julia> popfirst(xs)
2-element PureFun.Contiguous.StaticChunk{8, Int64}
2
3
source
PureFun.Contiguous.VectorChunk — Type
VectorChunk{N,T}
VectorChunk{N}(iter)

Backed by Base.Vector, VectorChunks implement all list functions but are constrained to a maximum size. Useful in conjunction with PureFun.Chunky.@list, which chains together small chunks to build general list types that benefit from data locality.

Examples

This example builds a list with maximum length 128. Until we hit the maximum length, we can use the VectorChunk like any other list type:

julia> using PureFun, PureFun.Contiguous
julia> xs = Contiguous.VectorChunk{128}(1:3)
3-element PureFun.Contiguous.VectorChunk{128, Int64}
1
2
3


julia> (41 ⇀ 42 ⇀ xs) ⧺ xs
8-element PureFun.Contiguous.VectorChunk{128, Int64}
41
42
1
2
3
1
2
...
source

Bits: a set requiring one integer worth of storage

PureFun.Contiguous.Bits — Type

A sparse set with small integer elements.

Examples

julia> b = PureFun.Contiguous.Bits{UInt16}()
0000000000000000

# the 1s in the bitstring mark the elements that are present
julia> b = reduce(push, [1,9,4,15,15], init=b)
0100000100001001


julia> 15 ∈ b, 4 ∈ b, 2 ∈ b
(true, true, false)
source

bitmap: a small dictionary

PureFun.Contiguous.bitmap — Function
bitmap(n_elems=Val{16}())

Create a BitMap with n_elems elements. See also PureFun.Tries.@trie. If the number of elements are known at compile time, then using Val{N}() rather than N to specify the number might be more efficient.

Examples

julia> using PureFun, PureFun.Contiguous
julia> BM = Contiguous.bitmap(8) # equivalently: Contiguous.bitmap(Val{8}())
PureFun.Contiguous.BitMap{PureFun.Contiguous.Bits{UInt8}}

julia> b = BM{Int,Char}()
PureFun.Contiguous.BitMap{PureFun.Contiguous.Bits{UInt8}, Int64, Char}()

julia> setindex(b, 'a', 1)
PureFun.Contiguous.BitMap{PureFun.Contiguous.Bits{UInt8}, Int64, Char} with 1 entry:
  1 => 'a'
source

biterate: bit-wise iteration over single integers

Contiguous.bitmap is great if you only need a dictionary with small integer keys, but doesn't generalize to other use-cases. Contiguous.biterate takes arbitrary integers and breaks them into smaller integers suitable to be keys in a bitmap. PureFun.Tries.@trie allows you to chain together simpler dictionaries to build more general ones, so biterate, bitmap, and @trie combine to build very efficient BitMapped tries, as described in Fast and Space Efficient Trie Searches and Ideal Hash Trees

PureFun.Contiguous.biterate — Function
biterate(v)
biterate(v, x)

take an integer and iterate over it N bits at a time. The iterated elements are interpreted as integers between 1 and $2^v$ (e.g. if v = 6, then biterate will iterate integers between 1 and 64). The iterated integers are meant to be interpreted as array indexes, and are are always greater than 0.

If the number of bits v is known at compile-time, specifying it as Val{N}() might be more efficient than just passing the number as an integer.

Examples

julia> using PureFun, PureFun.Contiguous
julia> Contiguous.biterate(4, UInt16(79)) |> collect
4-element Vector{Int64}:
 16
  5
  1
  1
source