5164889797

Committed 03 Jun 2023 05:39PM UTC coverage: 94.708% (+0.6%) from 94.156%

Build # 5164889797

Build Type

push

github

Committed by

web-flow

Commit Message

Optimise memory for structures (#15)

* optimise memory usage so that fingers are dynamic
* open api for extensibility so that internal skip list structure is exposed to clients

Run Details

375 of 375 new or added lines in 5 files covered. (100.0%)

519 of 548 relevant lines covered (94.71%)

1.05 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.51

/skipmap.go

//
// Copyright (C) 2022 Dmitry Kolesnikov
//
// This file may be modified and distributed under the terms
// of the MIT license.  See the LICENSE file for details.
// https://github.com/fogfish/skiplist
//

package skiplist

import (
        "fmt"
        "math"
        "math/rand"
        "strings"
        "time"
)

// Each key-value pair is represented by a Pair in a skip structures. Each node has
// a height or level (length of fingers array), which corresponds to the number
// of forward pointers the node has. When a new element is inserted into the list,
// a node with a random level is inserted to represent the element. Random levels
// are generated with a simple pattern: 50% are level 1, 25% are level 2, 12.5% are
// level 3 and so on.
type Pair[K Key, V any] struct {
        Key     K
        Value   V
        Fingers []*Pair[K, V]
}

// Rank of node
func (el *Pair[K, V]) Rank() int { return len(el.Fingers) }

// Return next element in the set.
// Use for-loop to iterate through set elements
//
//        for e := set.Successor(...); e != nil; e.Next() { /* ... */}
func (el *Pair[K, V]) Next() *Pair[K, V] { return el.Fingers[0] }

// Return next element in the set on level.
// Use for-loop to iterate through set elements
//
//        for e := set.ValuesOn(...); e != nil; e.NextOn(...) { /* ... */}
func (el *Pair[K, V]) NextOn(level int) *Pair[K, V] {
        if level >= len(el.Fingers) {
                return nil
        }

        return el.Fingers[level]
}

// Cast Element into string
func (el *Pair[K, V]) String() string {
        fingers := ""
        for _, x := range el.Fingers {
                if x != nil {
                        fingers = fingers + fmt.Sprintf(" %v", x.Key)
                } else {
                        fingers = fingers + " _"
                }
        }

        return fmt.Sprintf("{ %4v\t|%s }", el.Key, fingers)
}

// --------------------------------------------------------------------------------------

// Map of Elements
type Map[K Key, V any] struct {
        //
        // head of the list, the node is a lowest element
        head *Pair[K, V]

        // null element of type T
        null K

        //
        // number of elements in the set, O(1)
        length int

        //
        // random generator
        random rand.Source

        //
        // buffer to estimate the skip path during insert / remove
        // the buffer implements optimization of memory allocations
        path [L]*Pair[K, V]

        //
        ptable [L]float64

        // memory allocator for elements
        malloc Allocator[K, Pair[K, V]]
}

// New create instance of SkipList
func NewMap[K Key, V any](opts ...MapConfig[K, V]) *Map[K, V] {
        head := &Pair[K, V]{Fingers: make([]*Pair[K, V], L)}

        set := &Map[K, V]{
                head:   head,
                null:   *new(K),
                length: 0,
                random: rand.NewSource(time.Now().UnixNano()),
                path:   [L]*Pair[K, V]{},
                ptable: probabilityTable,
                malloc: nil,
        }

        for _, opt := range opts {
                opt(set)
        }

        return set
}

// Cast set into string
func (kv *Map[K, V]) String() string {
        sb := strings.Builder{}
        sb.WriteString(fmt.Sprintf("--- SkipMap[%T] %p ---\n", kv.null, &kv))

        v := kv.head
        for v != nil {
                sb.WriteString(v.String())
                sb.WriteString("\n")
                v = v.Fingers[0]
        }

        return sb.String()
}

func (kv *Map[K, V]) Length() int {
        return kv.length
}

// Max level of skip list
func (kv *Map[K, V]) Level() int {
        for i := 0; i < L; i++ {
                if kv.head.Fingers[i] == nil {
                        return i - 1
                }
        }
        return L - 1
}

// skip algorithm is similar to search algorithm that traversing forward pointers.
// skip maintain the vector path that contains a pointer to the rightmost node
// of level i or higher that is to the left of the location of the
// insertion/deletion.
func (kv *Map[K, V]) Skip(level int, key K) (*Pair[K, V], [L]*Pair[K, V]) {
        path := kv.path

        node := kv.head
        next := node.Fingers
        for lev := L - 1; lev >= level; lev-- {
                for next[lev] != nil && next[lev].Key < key {
                        node = node.Fingers[lev]
                        next = node.Fingers
                }
                path[lev] = node
        }

        return next[level], path
}

func (kv *Map[K, V]) Put(key K, val V) (bool, *Pair[K, V]) {
        el, path := kv.Skip(0, key)

        if el != nil && el.Key == key {
                el.Value = val
                return false, el
        }

        rank, el := kv.CreatePair(L, key, val)

        // re-bind fingers to new node
        for level := 0; level < rank; level++ {
                el.Fingers[level] = path[level].Fingers[level]
                path[level].Fingers[level] = el
        }

        kv.length++
        return true, el
}

// creates a new node, randomly defines empty fingers (level of the node)
func (kv *Map[K, V]) CreatePair(maxL int, key K, val V) (int, *Pair[K, V]) {
        // See: https://golang.org/src/math/rand/rand.go#L150
        p := float64(kv.random.Int63()) / (1 << 63)

        level := 0
        for level < maxL && p < kv.ptable[level] {
                level++
        }

        node := kv.NewPair(key, level)
        node.Key = key
        node.Value = val

        return level, node
}

// allocate new pair
func (kv *Map[K, V]) NewPair(key K, rank int) *Pair[K, V] {
        if kv.malloc != nil {
                return kv.malloc.Alloc(key)
        }

        return &Pair[K, V]{Fingers: make([]*Pair[K, V], rank)}
}

// Check is element exists in set
func (kv *Map[K, V]) Get(key K) (V, *Pair[K, V]) {
        el, _ := kv.Skip(0, key)

        if el != nil && el.Key == key {
                return el.Value, el
        }

        return *new(V), nil
}

// Cut element from the set, returns true if element is removed
func (kv *Map[K, V]) Cut(key K) (bool, *Pair[K, V]) {
        rank := L
        v, path := kv.Skip(0, key)

        if v == nil || v.Key != key {
                return false, nil
        }

        for level := 0; level < rank; level++ {
                if path[level].Fingers[level] == v {
                        if len(v.Fingers) > level {
                                path[level].Fingers[level] = v.Fingers[level]
                        } else {
                                path[level].Fingers[level] = nil
                        }
                }
        }

        kv.length--

        if kv.malloc != nil {
                kv.malloc.Free(key)
        }

        return true, v
}

// Head of skiplist
func (kv *Map[K, V]) Head() *Pair[K, V] {
        return kv.head
}

// All set elements
func (kv *Map[K, V]) Values() *Pair[K, V] {
        return kv.head.Fingers[0]
}

// Successor elements from set
func (kv *Map[K, V]) Successor(key K) *Pair[K, V] {
        el, _ := kv.Skip(0, key)
        return el
}

// Split set of elements by key
func (kv *Map[K, V]) Split(key K) *Map[K, V] {
        node, path := kv.Skip(0, key)

        for level, x := range path {
                x.Fingers[level] = nil
        }

        head := &Pair[K, V]{Fingers: make([]*Pair[K, V], L)}

        tail := &Map[K, V]{
                head:   head,
                null:   *new(K),
                length: 0,
                random: kv.random,
                path:   [L]*Pair[K, V]{},
                ptable: kv.ptable,
                malloc: kv.malloc,
        }
        tail.head.Fingers[0] = node

        length := 0
        for n := node; n != nil; n = n.Fingers[0] {
                length++
        }

        tail.length = length
        kv.length -= length

        return tail
}

// --------------------------------------------------------------------------------------

// Configure Set properties
type MapConfig[K Key, V any] func(*Map[K, V])

// Configure Random Generator
func MapWithRandomSource[K Key, V any](random rand.Source) MapConfig[K, V] {
        return func(kv *Map[K, V]) {
                kv.random = random
        }
}

// Configure Memory Allocator
func MapWithAllocator[K Key, V any](malloc Allocator[K, Pair[K, V]]) MapConfig[K, V] {
        return func(kv *Map[K, V]) {
                kv.malloc = malloc
        }
}

// Configure Probability table
// Use math.Log(B)/B < p < math.Pow(B, -0.5)
//
// The probability help to control the "distance" between elements on each level
// Use p = math.Pow(B, -0.5), where B is number of elements
// On L1 distance is √B, L2 distance is B, Ln distance is (√B)ⁿ
func MapWithProbability[K Key, V any](p float64) MapConfig[K, V] {
        return func(kv *Map[K, V]) {
                var ptable [L]float64

                for i := 1; i <= L; i++ {
                        ptable[i-1] = math.Pow(p, float64(i-1))
                }

                kv.ptable = ptable
        }
}

// Configure Probability table so that each level takes (√B)ⁿ elements
func MapWithBlockSize[K Key, V any](b int) MapConfig[K, V] {
        return MapWithProbability[K, V](math.Pow(float64(b), -0.5))
}

1	//
2	// Copyright (C) 2022 Dmitry Kolesnikov
3	//
4	// This file may be modified and distributed under the terms
5	// of the MIT license. See the LICENSE file for details.
6	// https://github.com/fogfish/skiplist
7	//
8
9	package skiplist
10
11	import (
12	"fmt"
13	"math"
14	"math/rand"
15	"strings"
16	"time"
17	)
18
19	// Each key-value pair is represented by a Pair in a skip structures. Each node has
20	// a height or level (length of fingers array), which corresponds to the number
21	// of forward pointers the node has. When a new element is inserted into the list,
22	// a node with a random level is inserted to represent the element. Random levels
23	// are generated with a simple pattern: 50% are level 1, 25% are level 2, 12.5% are
24	// level 3 and so on.
25	type Pair[K Key, V any] struct {
26	Key K
27	Value V
28	Fingers []*Pair[K, V]
29	}
30
31	// Rank of node
32	func (el *Pair[K, V]) Rank() int { return len(el.Fingers) }	×
33
34	// Return next element in the set.
35	// Use for-loop to iterate through set elements
36	//
37	// for e := set.Successor(...); e != nil; e.Next() { /* ... */}
38	func (el Pair[K, V]) Next() Pair[K, V] { return el.Fingers[0] }	1✔
39
40	// Return next element in the set on level.
41	// Use for-loop to iterate through set elements
42	//
43	// for e := set.ValuesOn(...); e != nil; e.NextOn(...) { /* ... */}
44	func (el Pair[K, V]) NextOn(level int) Pair[K, V] {	1✔
45	if level >= len(el.Fingers) {	1✔
46	return nil	×
47	}	×
48
49	return el.Fingers[level]	1✔
50	}
51
52	// Cast Element into string
53	func (el *Pair[K, V]) String() string {	1✔
54	fingers := ""	1✔
55	for _, x := range el.Fingers {	2✔
56	if x != nil {	2✔
57	fingers = fingers + fmt.Sprintf(" %v", x.Key)	1✔
58	} else {	2✔
59	fingers = fingers + " _"	1✔
60	}	1✔
61	}
62
63	return fmt.Sprintf("{ %4v\t\|%s }", el.Key, fingers)	1✔
64	}
65
66	// --------------------------------------------------------------------------------------
67
68	// Map of Elements
69	type Map[K Key, V any] struct {
70	//
71	// head of the list, the node is a lowest element
72	head *Pair[K, V]
73
74	// null element of type T
75	null K
76
77	//
78	// number of elements in the set, O(1)
79	length int
80
81	//
82	// random generator
83	random rand.Source
84
85	//
86	// buffer to estimate the skip path during insert / remove
87	// the buffer implements optimization of memory allocations
88	path [L]*Pair[K, V]
89
90	//
91	ptable [L]float64
92
93	// memory allocator for elements
94	malloc Allocator[K, Pair[K, V]]
95	}
96
97	// New create instance of SkipList
98	func NewMap[K Key, V any](opts ...MapConfig[K, V]) *Map[K, V] {	1✔
99	head := &Pair[K, V]{Fingers: make([]*Pair[K, V], L)}	1✔
100		1✔
101	set := &Map[K, V]{	1✔
102	head: head,	1✔
103	null: *new(K),	1✔
104	length: 0,	1✔
105	random: rand.NewSource(time.Now().UnixNano()),	1✔
106	path: [L]*Pair[K, V]{},	1✔
107	ptable: probabilityTable,	1✔
108	malloc: nil,	1✔
109	}	1✔
110		1✔
111	for _, opt := range opts {	2✔
112	opt(set)	1✔
113	}	1✔
114
115	return set	1✔
116	}
117
118	// Cast set into string
119	func (kv *Map[K, V]) String() string {	1✔
120	sb := strings.Builder{}	1✔
121	sb.WriteString(fmt.Sprintf("--- SkipMap[%T] %p ---\n", kv.null, &kv))	1✔
122		1✔
123	v := kv.head	1✔
124	for v != nil {	2✔
125	sb.WriteString(v.String())	1✔
126	sb.WriteString("\n")	1✔
127	v = v.Fingers[0]	1✔
128	}	1✔
129
130	return sb.String()	1✔
131	}
132
133	func (kv *Map[K, V]) Length() int {	1✔
134	return kv.length	1✔
135	}	1✔
136
137	// Max level of skip list
138	func (kv *Map[K, V]) Level() int {	1✔
139	for i := 0; i < L; i++ {	2✔
140	if kv.head.Fingers[i] == nil {	2✔
141	return i - 1	1✔
142	}	1✔
143	}
144	return L - 1	×
145	}
146
147	// skip algorithm is similar to search algorithm that traversing forward pointers.
148	// skip maintain the vector path that contains a pointer to the rightmost node
149	// of level i or higher that is to the left of the location of the
150	// insertion/deletion.
151	func (kv Map[K, V]) Skip(level int, key K) (Pair[K, V], [L]*Pair[K, V]) {	1✔
152	path := kv.path	1✔
153		1✔
154	node := kv.head	1✔
155	next := node.Fingers	1✔
156	for lev := L - 1; lev >= level; lev-- {	2✔
157	for next[lev] != nil && next[lev].Key < key {	2✔
158	node = node.Fingers[lev]	1✔
159	next = node.Fingers	1✔
160	}	1✔
161	path[lev] = node	1✔
162	}
163
164	return next[level], path	1✔
165	}
166
167	func (kv Map[K, V]) Put(key K, val V) (bool, Pair[K, V]) {	1✔
168	el, path := kv.Skip(0, key)	1✔
169		1✔
170	if el != nil && el.Key == key {	2✔
171	el.Value = val	1✔
172	return false, el	1✔
173	}	1✔
174
175	rank, el := kv.CreatePair(L, key, val)	1✔
176		1✔
177	// re-bind fingers to new node	1✔
178	for level := 0; level < rank; level++ {	2✔
179	el.Fingers[level] = path[level].Fingers[level]	1✔
180	path[level].Fingers[level] = el	1✔
181	}	1✔
182
183	kv.length++	1✔
184	return true, el	1✔
185	}
186
187	// creates a new node, randomly defines empty fingers (level of the node)
188	func (kv Map[K, V]) CreatePair(maxL int, key K, val V) (int, Pair[K, V]) {	1✔
189	// See: https://golang.org/src/math/rand/rand.go#L150	1✔
190	p := float64(kv.random.Int63()) / (1 << 63)	1✔
191		1✔
192	level := 0	1✔
193	for level < maxL && p < kv.ptable[level] {	2✔
194	level++	1✔
195	}	1✔
196
197	node := kv.NewPair(key, level)	1✔
198	node.Key = key	1✔
199	node.Value = val	1✔
200		1✔
201	return level, node	1✔
202	}
203
204	// allocate new pair
205	func (kv Map[K, V]) NewPair(key K, rank int) Pair[K, V] {	1✔
206	if kv.malloc != nil {	1✔
207	return kv.malloc.Alloc(key)	×
208	}	×
209
210	return &Pair[K, V]{Fingers: make([]*Pair[K, V], rank)}	1✔
211	}
212
213	// Check is element exists in set
214	func (kv Map[K, V]) Get(key K) (V, Pair[K, V]) {	1✔
215	el, _ := kv.Skip(0, key)	1✔
216		1✔
217	if el != nil && el.Key == key {	2✔
218	return el.Value, el	1✔
219	}	1✔
220
221	return *new(V), nil	1✔
222	}
223
224	// Cut element from the set, returns true if element is removed
225	func (kv Map[K, V]) Cut(key K) (bool, Pair[K, V]) {	1✔
226	rank := L	1✔
227	v, path := kv.Skip(0, key)	1✔
228		1✔
229	if v == nil \|\| v.Key != key {	2✔
230	return false, nil	1✔
231	}	1✔
232
233	for level := 0; level < rank; level++ {	2✔
234	if path[level].Fingers[level] == v {	2✔
235	if len(v.Fingers) > level {	2✔
236	path[level].Fingers[level] = v.Fingers[level]	1✔
237	} else {	1✔
238	path[level].Fingers[level] = nil	×
239	}	×
240	}
241	}
242
243	kv.length--	1✔
244		1✔
245	if kv.malloc != nil {	1✔
246	kv.malloc.Free(key)	×
247	}	×
248
249	return true, v	1✔
250	}
251
252	// Head of skiplist
253	func (kv Map[K, V]) Head() Pair[K, V] {	1✔
254	return kv.head	1✔
255	}	1✔
256
257	// All set elements
258	func (kv Map[K, V]) Values() Pair[K, V] {	1✔
259	return kv.head.Fingers[0]	1✔
260	}	1✔
261
262	// Successor elements from set
263	func (kv Map[K, V]) Successor(key K) Pair[K, V] {	1✔
264	el, _ := kv.Skip(0, key)	1✔
265	return el	1✔
266	}	1✔
267
268	// Split set of elements by key
269	func (kv Map[K, V]) Split(key K) Map[K, V] {	1✔
270	node, path := kv.Skip(0, key)	1✔
271		1✔
272	for level, x := range path {	2✔
273	x.Fingers[level] = nil	1✔
274	}	1✔
275
276	head := &Pair[K, V]{Fingers: make([]*Pair[K, V], L)}	1✔
277		1✔
278	tail := &Map[K, V]{	1✔
279	head: head,	1✔
280	null: *new(K),	1✔
281	length: 0,	1✔
282	random: kv.random,	1✔
283	path: [L]*Pair[K, V]{},	1✔
284	ptable: kv.ptable,	1✔
285	malloc: kv.malloc,	1✔
286	}	1✔
287	tail.head.Fingers[0] = node	1✔
288		1✔
289	length := 0	1✔
290	for n := node; n != nil; n = n.Fingers[0] {	2✔
291	length++	1✔
292	}	1✔
293
294	tail.length = length	1✔
295	kv.length -= length	1✔
296		1✔
297	return tail	1✔
298	}
299
300	// --------------------------------------------------------------------------------------
301
302	// Configure Set properties
303	type MapConfig[K Key, V any] func(*Map[K, V])
304
305	// Configure Random Generator
306	func MapWithRandomSource[K Key, V any](random rand.Source) MapConfig[K, V] {	1✔
307	return func(kv *Map[K, V]) {	2✔
308	kv.random = random	1✔
309	}	1✔
310	}
311
312	// Configure Memory Allocator
313	func MapWithAllocator[K Key, V any](malloc Allocator[K, Pair[K, V]]) MapConfig[K, V] {	1✔
314	return func(kv *Map[K, V]) {	2✔
315	kv.malloc = malloc	1✔
316	}	1✔
317	}
318
319	// Configure Probability table
320	// Use math.Log(B)/B < p < math.Pow(B, -0.5)
321	//
322	// The probability help to control the "distance" between elements on each level
323	// Use p = math.Pow(B, -0.5), where B is number of elements
324	// On L1 distance is √B, L2 distance is B, Ln distance is (√B)ⁿ
325	func MapWithProbability[K Key, V any](p float64) MapConfig[K, V] {	1✔
326	return func(kv *Map[K, V]) {	2✔
327	var ptable [L]float64	1✔
328		1✔
329	for i := 1; i <= L; i++ {	2✔
330	ptable[i-1] = math.Pow(p, float64(i-1))	1✔
331	}	1✔
332
333	kv.ptable = ptable	1✔
334	}
335	}
336
337	// Configure Probability table so that each level takes (√B)ⁿ elements
338	func MapWithBlockSize[K Key, V any](b int) MapConfig[K, V] {	1✔
339	return MapWithProbability[K, V](math.Pow(float64(b), -0.5))	1✔
340	}	1✔

fogfish / skiplist / 5164889797

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous