Documentation ¶
Overview ¶
Package array implements several space effiecient array.
Unlike a normal array, it does not allocate space for an absent element. In some way it is like a map[int32]interface{} .
Memory overhead ¶
Internally it use a bitmap to indicate at which index there is an element.
This implementation allocate 1 bit for every abscent or present element to inidicate if there is an element at this position. Thus the memory overhead is about 1 bit / load-factor.
count(elements) load-factor = ---------------- max(indexes)
An array with load factor = 0.5 requires about 2 extra bit pre present element.
Implementation note ¶
- The bottom level Array32 is a protobuf message that defines in memory and on-disk structure.
- The second level Base provides several basic methods such as mapping an index to its position in memory.
- At the top level there are several ready to use implements. "Array" accepts any fixed-type value as element. Thus it is easy to use but not very efficient. "U32" accepts only uint32 as its element thus its performance is much better.
Array U32 U64 // ready-to-use types `----. | .----' v v v Base // access supporting methods. | v protobuf:Array32 // in-memory and on-disk structure.
Performance note ¶
A Get involves at least 2 memory access to a.Bitmaps and a.Elts.
An "Array" of general type requires one additional alloc for a Get:
// when Decode convert a concrete type to interface{} a.EltEncoder.Decode(bs)
An array of specific type such as "U32" does not requires additional alloc.
Index ¶
- Constants
- Variables
- type Array
- type Array32
- func (*Array32) Descriptor() ([]byte, []int)
- func (m *Array32) GetBMElts() *Bits
- func (m *Array32) GetBitmaps() []uint64
- func (m *Array32) GetCnt() int32
- func (m *Array32) GetEltWidth() int32
- func (m *Array32) GetElts() []byte
- func (m *Array32) GetFlags() uint32
- func (m *Array32) GetOffsets() []int32
- func (*Array32) ProtoMessage()
- func (m *Array32) Reset()
- func (m *Array32) String() string
- func (m *Array32) XXX_DiscardUnknown()
- func (m *Array32) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)
- func (dst *Array32) XXX_Merge(src proto.Message)
- func (m *Array32) XXX_Size() int
- func (m *Array32) XXX_Unmarshal(b []byte) error
- type Base
- type Bits
- func (*Bits) Descriptor() ([]byte, []int)
- func (m *Bits) GetFlags() uint32
- func (m *Bits) GetN() int32
- func (m *Bits) GetRankIndex() []int32
- func (m *Bits) GetWords() []uint64
- func (*Bits) ProtoMessage()
- func (m *Bits) Reset()
- func (m *Bits) String() string
- func (m *Bits) XXX_DiscardUnknown()
- func (m *Bits) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)
- func (dst *Bits) XXX_Merge(src proto.Message)
- func (m *Bits) XXX_Size() int
- func (m *Bits) XXX_Unmarshal(b []byte) error
- type I16
- type I32
- type I64
- type U16
- type U32
- type U64
Constants ¶
const (
ArrayFlagIsBitmap = uint32(0x00000002)
)
Variables ¶
var ( // ErrIndexNotAscending indicates that the indexes to initialize an Array is not // in ascending order. // // Since 0.2.0 ErrIndexNotAscending = errors.New("index must be an ascending ordered slice") // ErrIndexLen indicates that the number of indexes does not equal the number of // elements, when initializing an Array. // // Since 0.2.0 ErrIndexLen = errors.New("the length of indexes and elts must be equal") )
Functions ¶
This section is empty.
Types ¶
type Array ¶
type Array struct {
Base
}
Array is a space efficient array of fixed-size element.
A fixed size type could be:
int32 struct { X int32; Y uint16 }
A non-fixed size type could be:
int []uint32 map etc.
Performance note ¶
A general Array.Get is implemented with reflect. Benchmark shows a Get() costs ~ 168 ns/op and involves 4 alloc.
To achieve the best performance, use a type specific array such as array.U32. The performance is much better: a Get() costs ~ 12 ns/op and involves 0 alloc.
Since 0.2.0
func New ¶
New creates an array from specified indexes and elts. The length of indexes and the length of elts must be the same. "elts" must be a slice of fixed-size values.
Since 0.2.0
func NewEmpty ¶
NewEmpty creates an empty Array with element of type of "v". If v is a pointer, the value type it points to is used.
Since 0.2.0
type Array32 ¶ added in v0.5.4
type Array32 struct { // compatibility guarantee: // reserved field number: 1, 2, 3, 4 // reserved field name: Cnt, Bitmaps, Offsets, Elts // Cnt int32 `protobuf:"varint,1,opt,name=Cnt,proto3" json:"Cnt,omitempty"` Bitmaps []uint64 `protobuf:"varint,2,rep,packed,name=Bitmaps,proto3" json:"Bitmaps,omitempty"` Offsets []int32 `protobuf:"varint,3,rep,packed,name=Offsets,proto3" json:"Offsets,omitempty"` Elts []byte `protobuf:"bytes,4,opt,name=Elts,proto3" json:"Elts,omitempty"` // Flags provides options // // Since 0.5.4 Flags uint32 `protobuf:"varint,10,opt,name=Flags,proto3" json:"Flags,omitempty"` // EltWidth set width of elt in bits. // // Since 0.5.4 EltWidth int32 `protobuf:"varint,20,opt,name=EltWidth,proto3" json:"EltWidth,omitempty"` // BMElts is optimized for elt itself is a bitmap. // // Since 0.5.4 BMElts *Bits `protobuf:"bytes,30,opt,name=BMElts,proto3" json:"BMElts,omitempty"` XXX_NoUnkeyedLiteral struct{} `json:"-"` XXX_unrecognized []byte `json:"-"` XXX_sizecache int32 `json:"-"` }
func (*Array32) Descriptor ¶ added in v0.5.4
func (*Array32) GetBitmaps ¶ added in v0.5.4
func (*Array32) GetEltWidth ¶ added in v0.5.4
func (*Array32) GetOffsets ¶ added in v0.5.4
func (*Array32) ProtoMessage ¶ added in v0.5.4
func (*Array32) ProtoMessage()
func (*Array32) XXX_DiscardUnknown ¶ added in v0.5.4
func (m *Array32) XXX_DiscardUnknown()
func (*Array32) XXX_Marshal ¶ added in v0.5.4
func (*Array32) XXX_Unmarshal ¶ added in v0.5.4
type Base ¶ added in v0.2.1
Base is the base of: Array and U16 etc.
Since 0.2.0
func (*Base) Get ¶ added in v0.2.1
Get retrieves the value at "idx" and return it. If this array has a value at "idx" it returns the value and "true", otherwise it returns "nil" and "false".
Since 0.2.0
func (*Base) GetBytes ¶ added in v0.2.1
GetBytes retrieves the raw data of value in []byte at "idx" and return it.
Performance note ¶
Involves 2 memory access:
a.Bitmaps a.Elts
Involves 0 alloc ¶
Since 0.2.0
func (*Base) Init ¶ added in v0.2.1
Init initializes an array from the "indexes" and "elts". The indexes must be an ascending int32 slice, otherwise, return the ErrIndexNotAscending error. The "elts" is a slice.
Since 0.2.0
type Bits ¶ added in v0.5.4
type Bits struct { // Flags provides options Flags uint32 `protobuf:"varint,1,opt,name=Flags,proto3" json:"Flags,omitempty"` // N is the max index of present elt + 1 N int32 `protobuf:"varint,10,opt,name=N,proto3" json:"N,omitempty"` // Words contains bitmap Words []uint64 `protobuf:"varint,20,rep,packed,name=Words,proto3" json:"Words,omitempty"` // RankIndex speeds up rank() by pre-calcuate it // Choose by Flags // // Since 0.5.4 RankIndex []int32 `protobuf:"varint,30,rep,packed,name=RankIndex,proto3" json:"RankIndex,omitempty"` XXX_NoUnkeyedLiteral struct{} `json:"-"` XXX_unrecognized []byte `json:"-"` XXX_sizecache int32 `json:"-"` }
Bits is an array of bits with rank(how many 1 upto position x, excluding x) index. With option dense, it compresses rank index thus reduces memory usage but a query takes more time, about 14 ns.
func (*Bits) Descriptor ¶ added in v0.5.4
func (*Bits) GetRankIndex ¶ added in v0.5.4
func (*Bits) ProtoMessage ¶ added in v0.5.4
func (*Bits) ProtoMessage()
func (*Bits) XXX_DiscardUnknown ¶ added in v0.5.4
func (m *Bits) XXX_DiscardUnknown()
func (*Bits) XXX_Marshal ¶ added in v0.5.4
func (*Bits) XXX_Unmarshal ¶ added in v0.5.4
type I16 ¶ added in v0.2.1
type I16 struct {
Base
}
I16 is an implementation of Base with int16 element
Since 0.2.0
type I32 ¶ added in v0.2.1
type I32 struct {
Base
}
I32 is an implementation of Base with int32 element
Since 0.2.0
type I64 ¶ added in v0.2.1
type I64 struct {
Base
}
I64 is an implementation of Base with int64 element
Since 0.2.0
type U16 ¶ added in v0.2.1
type U16 struct {
Base
}
U16 is an implementation of Base with uint16 element
Since 0.2.0
type U32 ¶ added in v0.2.1
type U32 struct {
Base
}
U32 is an implementation of Base with uint32 element
Since 0.2.0