omap

OMAP an Ordered Map

Yet another sorted map in go.. but not really.

Technically the omap package implements very minital btree using a slice. The drivers of the design process, were the performance objectives. The btree implementation is ordered and does not allow for duplicates; The internals manage keys by splicing the internal slice. The side effect of this design results in what operates exactly like ordered map. Under spesific conditions or very large data sets, omap.SliceTree is faster on "Get" operations than the built in go map. An omap.SliceTree instance uses signifigantly less the memory than the map feature in go.

Performance objectives while maintinaing a sorted map:

• Lookups for both Put and Get operations are always a fixed complexity: o(log n).
• All iteration operations are fixed cost of o(1).
• Finding or removing elements between 2 points is always a fixed cost of o(log(n) + log(n)).
• Finding elements: at, before, or after a given point is always a fixed cost of o(log n)
• Mass Removal of unordered elements that may or may not exist has a maximum complexity of o(log(n) + log(k) + k)
• Pre-emptive but predictable growth, this is done by setting the Growth size.

When Should you use omap.SliceTree in place of a map?

Any one of these is a practical use case:

• An ordered map is required
• Memory constrained systems
• Fuzzy logic is required, IE the ability to find points in between keys
• When a combination of freequent updates and searching by ranges is requried
• Very large data sets where read speed is more important than write speed
• Keys that can not be represented as a comparable value
• When managing elements between ranges is required

Basic usage

The omap package provides a common interface OrderedMap implemented by the following:

• Thread safe ThreadSafeOrderedMap, Wrapper for SliceTree
• Not thread safe SliceTree, but can be converted to a thread safe instance.

Creating ThreadSafe instance Example:

	kv:=NewTs[string,string](cmp.Compare)
	// Save a value
	kv.Put("Hello"," ")
	kv.Put("World","!\n")

	// Itertor
	for k,v :=range kv.All {
		fmt.Printf("%s%s",k,v)
	}

The resulting output will be:

	"Hello World!\n"

We can now make things a bit smaller by removing things by a range.

// Note, both "Sell" and "Universe", were never added to the instance,
// but the between operation works on these keys any ways.
kv.RemoveBetween("Sell","Universe")

// Itertor
for k,v :=range kv.All() {
   fmt.Printf("%s%s\n",k,v)
}

The resulting output will now be:

"Hello \n"

Why this works?

• The string "Sell" comes before the string "World"
• The string "Universe" comes after the string "World"

How this works

The index lookup creates 2 values for each potential key:

• Array postion, example: 0
• Offset can be any of the following: -1,0,1

Since lookups create both an index position and offsett, it becomes possible to look for the following:

• Elements before the array
• Positions between elements of the array
• Elements after the array
• Elements to overwrite

API

Constructors

The omap package supports any key type you can provide a compare function for, but a map in go only supports a comparable key type. This means any map can be converted to an OrderedMap instance, but not every OrderedMap instance can be converted to a map.

As a note, any instance of SliceTree can create a thread safe instance of itself, by calling the s.ToTs() method. If you create a thread safe instance, you should stop using the old instance.

Example conversion from map to a thread safe OrderedMap instance:

s:=omap.NewFromMap(myMap,cb).ToTs()

To check if an instance is thread safe call the s.ThreadSafe() method.

var om OrderedMap[string,int]=New(cb)

if !om.ThreadSafe() {
	om=om.ToTs()
}

Why not always provide a thread safe instance? A thread safe instance requires mutex locking, this limits what can be done even when operations are atomic. Example: You may have a perfectly valid reason to call an iterator from within an iterator on the same instance; This cannot be done when a mutex lock is applied to an existing instance.

OrderedMap Methods

The following table provides a general overview of the methods in OrderedMap.

Between Options

The following table exlains the usage and possible values for functions that support between operations.

Example using s.BetweenKV:

  for k,v :=s.BetweenKV("","Tomorrow",omap.FIRSTKEY) {
    fmt.Printf("Key: [%s], Value: [%d]\n")
  }

Returns all values up to "Tomorrow".

Benchmarks

So benchmarks are always very subjective, but the real question is: what do we compare omap too? The only real answer is the native map in go. Now this is in no way a fair comparison.. The omap package can use any data set, so long as a compare function can be provided, while the map in go only needs to be optimized internally for hashing bytes, so we would expected the native map feature to be an order of magnitude faster.

Disclamier: omap.SliceTree is built around a Compare function, this means the benchmark requires creating a proxy key that is equal to the key provided by the Cmp function. In this benchmark the key used for the map has to be generated from the base string, and the original string pointer and value then need to be saved off in an additional data structure, this gives us a like for like compare between the native go map feature and omap.SliceTree.

How well does omap compare native map feature in go?:

BenchmarkNew/Native_map_Put,_keys:_[1600]-10                               26467             44379 ns/op           93056 B/op       1606 allocs/op
BenchmarkNew/Slicetree,_Put,_keys:_[1600]-10                                9781            114559 ns/op           41008 B/op          2 allocs/op
BenchmarkNew/Native_map,_Get,_keys:_[1600]-10                              10000            109108 ns/op               0 B/op          0 allocs/op
BenchmarkNew/SliceTree,_Get,_keys:_[1600]-10                                7849            150049 ns/op               0 B/op          0 allocs/op
BenchmarkNew/Native_map,_Count_between,_keys:_[1600]-10                       67          17179143 ns/op           22552 B/op       2944 allocs/op
BenchmarkNew/SliceTree,_Count_Between_nodes_keys:_[1600]-10                 4364            267578 ns/op               0 B/op          0 allocs/op
BenchmarkNew/Native_map_Put,_keys:_[2500]-10                               15544             77330 ns/op          169264 B/op       2510 allocs/op
BenchmarkNew/Slicetree,_Put,_keys:_[2500]-10                                5958            186216 ns/op           65584 B/op          2 allocs/op
BenchmarkNew/Native_map,_Get,_keys:_[2500]-10                               5620            200192 ns/op               0 B/op          0 allocs/op
BenchmarkNew/SliceTree,_Get,_keys:_[2500]-10                                5156            231305 ns/op               0 B/op          0 allocs/op
BenchmarkNew/Native_map,_Count_between,_keys:_[2500]-10                       27          41700145 ns/op           36988 B/op       4744 allocs/op
BenchmarkNew/SliceTree,_Count_Between_nodes_keys:_[2500]-10                 2847            425970 ns/op               0 B/op          0 allocs/op
BenchmarkNew/Native_map_Put,_keys:_[3600]-10                               10038            119693 ns/op          304880 B/op       3618 allocs/op
BenchmarkNew/Slicetree,_Put,_keys:_[3600]-10                                3668            302038 ns/op           90160 B/op          2 allocs/op
BenchmarkNew/Native_map,_Get,_keys:_[3600]-10                               2881            373605 ns/op               0 B/op          0 allocs/op
BenchmarkNew/SliceTree,_Get,_keys:_[3600]-10                                3358            351491 ns/op               0 B/op          0 allocs/op
BenchmarkNew/Native_map,_Count_between,_keys:_[3600]-10                        9         114708859 ns/op           54710 B/op       6944 allocs/op
BenchmarkNew/SliceTree,_Count_Between_nodes_keys:_[3600]-10                 1914            627752 ns/op               0 B/op          0 allocs/op
BenchmarkNew/Native_map_Put,_keys:_[4900]-10                                7454            159133 ns/op          336080 B/op       4918 allocs/op
BenchmarkNew/Slicetree,_Put,_keys:_[4900]-10                                2288            480656 ns/op          122928 B/op          2 allocs/op
BenchmarkNew/Native_map,_Get,_keys:_[4900]-10                                764           1435220 ns/op               0 B/op          0 allocs/op
BenchmarkNew/SliceTree,_Get,_keys:_[4900]-10                                2323            499635 ns/op               0 B/op          0 allocs/op
BenchmarkNew/Native_map,_Count_between,_keys:_[4900]-10                        4         270712341 ns/op           75738 B/op       9545 allocs/op
BenchmarkNew/SliceTree,_Count_Between_nodes_keys:_[4900]-10                 1357            881794 ns/op               0 B/op          0 allocs/op

How to read the benchmark

So what do these numbers really tell us? Well nothing we didn't all ready know prior to the benchmark. The map feature of go trades memory for read and write speed, in particular on wirte. Usually platforms are more cpu constrained than memory constrained, but that isn't always the case.

On write:

• Go map is faster

On read:

• Go map is faster with smaller sets of keys
• omap.SliceTree is faster on larger sets of keys

Where the native map in go always perfoms worse is in memory usage:

• Go map uses about 45%-70% more memory than omap.SliceTree.

Scanning for any key between 2 strings:

• Go map must be iterated over and each key must be compared o(n)
• omap.SliceTree is just o(log(n)+log(n))

So which is better for performance? Depends.. If you need very large sets of keys and you would have to create a proxy key to represent the raw key, then use omap.SliceTree, other wise use map.

Scanning all keys for every key is a known worst case.. so why include it? People do it, and most ordered map packages on pkg.go.dev will force you do do that at least until you reach the end of your range.

Why does the native go map read slow down so much after 2500 elements?

Simple: memory bandwidth, omap.SliceTree for the same kind of work, uses between 45%-70% less memory than a native map in go. The inner workings of omap.SliceTree is a single slice in memory. This means memory reads for SliceTree are usually contiguous. Although the native go map hashing operation is cheaper when it comes to cpu cycles. omap.SliceTree is built entierly around a single slice and can often times stay entierly inside the cpu cache on reads. Even when going to main memory, a slice is usually a sequential set of reads, which greatly improve memory read performance.

Why is SliceTree always slower on write?

Simple: memory bandwidth. omap.SliceTree uses a slice in memory and the elemetns are copied back and forth in blocks. Although the lookup and storage uses less memory, the write operation involes splicing an array, which will go to main memory more often. The very thing that gives omap.SliceTree its read speed at scale slows it down in write operations.

So which is better SliceTree or a map?

Very subjective, omap.Slicetree is built entirly around being able to find a range of keys without scanning. A map in go is built around hashing bytes. After a certan point omap.Slicetree will always read faster, but the go native map feature will aways write faster. The go map implementation will always use more memory than omap.SliceTree, but the native go map perfoms sligtly less than half the memory modification of omap.SliceTree on insertion/update.

Why include memory in benchmarks?

This is a complex topic, but here is a short answer: Try turning memory benchmarks on for other ordered map pacakges on pkg.go.dev, they use orders of magnitued more memory than the native map in go. Most ordered map implementations arn't performacne competative with the native map in go. The omap.SliceTree is at least competative with the native go map implementation. In spesific use cases omap.SliceTree is signifigantly faster than the native map feature of go. An omap.SliceTree instance does all this while being an ordered map, that is no small feat.

Comapring go map o(1) and omap.SliceTee o(log(n))

Go map: o(1) How so? In truth go map uses the first 2 bytes as keys in a 2 tier tree, the remaing bytes then hit the o(1) or full scan. This is the sweet spot on most use cases. The side effect is, keys are never going to be ordered.

omap.Slicetree is o(log n)? The omap.SliceTree is a btree with inifinite depth, indexed by sequence order. An omap.SliceTree instance is never a full scan, but depth of search is always more expensive in smaller sets and always cheaper in larger sets. Effectivly omap.SliceTree is pure an Order First search with the root at the median of the tree. This hits the sweet spot for range based lookups and massive data sets. The side effect is an ordered index of keys.

Odd Quirks of indexing

So which is faster a 1 byte key using a map or omap.SliceTree?

• at a one byte key omap.SliceTree is faster

So which is faster a 2 byte key using a map in go with 65535 elements or omap.SliceTree?

• at 2 bytes a normal map in go is faster

So when does omap.Slicetree actually become faster?

• when a map in go would end up with colisions on the 3rd tier, this causes a full scan of that tier.
• when does that happen? Usually after a few thousand unique strings, but it depends on which buckets they land.

Is omap.SliceTree ever faster with ints or floats?

• Yes on range scans
• On Writes, Never
• On Read, never on a16 bit number
• On Read after: the first 16 bits cause a collision and ternary logic is faster operating on the entire integer or float value