Generations-based array · Iskander (Alex) Sharipov technical weblog

Intro

I used to be intrigued by the sparse map/set described in Russ Cox’s article.

And I’m not the one one: this actual implementation is utilized in Go supply code greater than as soon as! The compiler makes use of it for a lot of ID-like maps and units; regexp bundle makes use of it for a queue.

However there’s one factor that’s nonetheless bugging me: it’s arduous to make it very environment friendly. All operations I care about are O(1), however get and set operations clearly turn into slower as compared with a simple slice strategy.

In truth, in case your arrays should not that huge (lower than 0xffff bytes?), you is perhaps higher off utilizing a slice with O(n) clear operation. In the event you do many get+set, the elevated overhead could also be an excessive amount of.

On this article, I’ll suggest a unique knowledge construction that may exchange a sparse-dense map (and set) should you don’t want the iteration over the weather.

This dialogue isn’t Go-specific, however I’ll use Go within the examples.

The Drawback

Let me begin with an issue that we’re making an attempt to deal with.

Think about that you just want a mapping construction you could re-use. One thing like a map[uint16]T, however with a extra predictable allocations sample.

Your perform could appear like this:

func doWork(s *state) end result {
    s.map.Reset() // You need the reminiscence to be re-used

    // Do the work utilizing the map.
    // Solely get+set operations are used right here.
}

In case your “map” can re-use the reminiscence correctly, this code could turn into zero-alloc.

Our necessities could be described as follows:

We wish all of it, plus the environment friendly reminiscence re-use.

We’ll analyze these decisions as we speak:

• map[uint16]T
• []T
• sparseMap
• genMap

The slice and map options don’t match our necessities, however we’ll use them for a comparability.

Benchmark Outcomes

Let’s begin by evaluating the uncooked efficiency.

Observations:

• Map is closely outclassed
• Each sparse and era maps have a crazy-fast reset
• Even with 5000 parts (8*5000=40000 bytes), a slice reset takes noticeable time
• sparse.set() operation is ~7 instances slower than slice!
• sparse.get() operation is ~2 instances slower than slice
• Generations map is sort of as quick as a slice, however reset is way quicker

The sparse and generations map don’t zero their knowledge throughout the reset operation. Due to this fact, keep away from storing pointers in there. These pointers will likely be “held” by the container for a probably lengthy time frame, inflicting reminiscence leaks. I’d solely advocate utilizing each sparse and generations-based knowledge buildings with easy pointer-free.

You will discover the precise benchmarks code here.

Some benchmark notes:

• I used a real-world sparse-dense implementation
• Each get/set goes by way of a noinline wrapper to keep away from the undesirable optimizations
• Each get/set check runs the operation 5000 instances
• Each benchmark is utilizing 5000 parts (it’s vital for slice reset)
• The measurements above are divided by 10 for a better interpretation
• The worth kind used is int (8 bytes on my x86-64 machine)

Now, you need to be cautious about random benchmarks posted on the web. However regardless of the way you write and/or run these, generations map will all the time be quicker than a sparse-dense map (or set). It’s virtually as quick as a slice answer whereas nonetheless having a really quick O(1) reset.

There are causes for it to be quicker. Let’s discuss them.

Sparse Map Points

Why sparse.set() operation is so gradual?

In the case of insertion of a brand new worth, the sparse map has to do two reminiscence writes. One for the sparse and one for the dense. Updating the prevailing worth solely writes to dense.

func (s *sparseMap[T]) Set(ok int32, v T) {
	i := s.sparse[k]
	if i < int32(len(s.dense)) && s.dense[i].key == ok {
		s.dense[i].val = v
		return
	}
	s.dense = append(s.dense, sparseEntry[T]{ok, v})
	s.sparse[k] = int32(len(s.dense)) - 1
}

One other difficulty is that two slices imply twice as a lot boundchecks that may happen. And when you could be cautious and use uint keys and examine for the bounds your self to cease compiler from producing an implicit boundcheck, you’ll nonetheless pay for these if statements.

The sparse.get() operation additionally suffers from a double reminiscence learn.

Generations Map

It’s doable to make use of a number of the concepts behind the sparse-dense map and create an much more specialised knowledge construction.

kind genMapElem[T any] struct {
	seq uint32
	val T
}

kind genMap[T any] struct {
	elems []genMapElem[T]
	seq   uint32
}

func newGenMap[T any](n int) *genMap[T] {
	return &genMap[T]{
		elems: make([]genMapElem[T], n),
		seq:   1,
	}
}

Each factor could have a era counter (seq). The container itself could have its personal counter. The container’s counter begins with 1, whereas parts begin with 0.

Each get and set operations look similar to the slice model, however with a seq examine.

See Also

Why NASA Selected WordPress for Revamping Its Flagship Web site – WP Tavern

func (m *genMap[T]) Set(ok uint, v T) {
	if ok < uint(len(m.elems)) {
		m.elems[k] = genMapElem[T]{val: v, seq: m.seq}
	}
}

Setting the factor means updating the factor’s counter to the container’s counter together with the worth.

func (m *genMap[T]) Get(ok uint) T {
	if ok < uint(len(m.elems)) {
		el := m.elems[k]
		if el.seq == m.seq {
			return el.val
		}
	}
	var zero T
	return zero
}

If seq of the factor is an identical to the container’s counter, then this factor is outlined. In any other case, it doesn’t matter what are the contents of this factor.

You’ll be able to most likely already guess how Reset will appear like:

func (m *genMap[T]) Reset() {
	m.seq++
}

Nicely, that is adequate for essentially the most use circumstances, however there’s a small probability that our uint32 will overflow, making some undefined parts outlined. Growing the seq measurement to uint64 might assist, however it’s going to enhance the per-element measurement overhead. As a substitute, we will do an actual clear operation as soon as in MaxUint32 resets.

func (m *genMap[T]) Reset() {
	if m.seq == math.MaxUint32 {
		m.seq = 1
		clear(m.elems)
	} else {
		m.seq++
	}
}

It’s undoubtedly doable to make use of uint8 or uint16 for the seq subject. That may imply much less per-element measurement overhead on the worth of a extra frequent knowledge clear.

• The generations map does precisely 1 reminiscence learn and write
• It’s simpler to do away with all implicit boundchecks
• Its reminiscence consumption is similar to the sparse-dense array
• The Reset complexity is fixed (amortized)
• Arguably, it’s even simpler to implement and perceive than a sparse-dense map

It’s doable to make a generations-based set too. The get operation could be became incorporates with ease. With units, solely the counters are wanted.

func (m *genSet) Accommodates(ok uint) bool {
	if ok < uint(len(m.counters)) {
		return m.counters[k] == m.seq
	}
	return false
}

It might sound fascinating, proper? Nicely, you possibly can’t use this knowledge construction as a drop-in substitute for a sparse-dense. For example, a generations-based map can’t be iterated effectively.

You’ll be able to add a size counter if you actually need it, however that can add some further overhead to the set operation. I’d advise you not to take action. The primary motive this construction could be so quick is its simplicity.

The common reminiscence utilization will likely be increased, since a referenced sparse-dense implementation doesn’t allocate n parts for the dense immediately; it solely allocates your entire sparse storage. So, should you solely ever populate the array as much as n/2, the approximate measurement utilization can be 1.5n as an alternative of a worst-case 2n situation. The generations-based array would require your entire slice to be allotted immediately, resulting in a 2n reminiscence utilization situation.

Conclusion

I used this knowledge construction in my pathfinding library for Go. The outcomes had been nice: 5-8% speedup only for a easy knowledge construction change. Understand that this library is already closely optimized, so each couple of percentages depend.

In flip, this pathfinding library was utilized in a recreation I launched on Steam: Roboden.

Due to this fact, I’d take into account this knowledge construction to be production-ready.