CODEWITHSUNDEEP
algorithmgo
Marcin Sleziak
Marcin Sleziak

Reputation: 127

Golang maps/hashmaps, optimizing for iteration speed

When migrating a production NodeJS application to Golang I've noticed that iteration of GO's native Map is actually slower than Node.

I've come up with an alternative solution that sacrifices removal/insertion speed with iteration speed instead, by exposing an array that can be iterated over and storing key=>index pairs inside a separate map.

While this solution works, and has a significant performance increase, I was wondering if there is a better solution to this that I could look into.

The setup I have is that its very rare something is removed from the hashmaps, only additions and replacements are common for which this implementation 'works', albeit feels like a workaround more than an actual solution.

The maps are always indexed by an integer, holding arbitrary data.

FastMap:    500000 Iterations -  0.153000ms
Native Map: 500000 Iterations -  4.988000ms

/*
  Unordered hash map optimized for iteration speed.
  Stores values in an array and holds key=>index mappings inside a separate hashmap
*/

type FastMapEntry[K comparable, T any] struct {
    Key   K
    Value T
}

type FastMap[K comparable, T any] struct {
    m       map[K]int            // Stores key => array index mappings
    entries []FastMapEntry[K, T] // Array holding entries and their keys
    len     int                  // Total map size
}

func MakeFastMap[K comparable, T any]() *FastMap[K, T] {
    return &FastMap[K, T]{
        m:       make(map[K]int),
        entries: make([]FastMapEntry[K, T], 0),
    }
}

func (m *FastMap[K, T]) Set(key K, value T) {
    index, exists := m.m[key]
    if exists {
        // Replace if key already exists
        m.entries[index] = FastMapEntry[K, T]{
            Key:   key,
            Value: value,
        }
    } else {
        // Store the key=>index pair in the map and add value to entries. Increase total len by one
        m.m[key] = m.len
        m.entries = append(m.entries, FastMapEntry[K, T]{
            Key:   key,
            Value: value,
        })
        m.len++
    }
}

func (m *FastMap[K, T]) Has(key K) bool {
    _, exists := m.m[key]

    return exists
}

func (m *FastMap[K, T]) Get(key K) (value T, found bool) {
    index, exists := m.m[key]
    if exists {
        found = true
        value = m.entries[index].Value
    }

    return
}

func (m *FastMap[K, T]) Remove(key K) bool {
    index, exists := m.m[key]
    if exists {
        // Remove value from entries
        m.entries = append(m.entries[:index], m.entries[index+1:]...)
        // Remove key=>index mapping
        delete(m.m, key)
        m.len--

        for i := index; i < m.len; i++ {
            // Move all index mappings up, starting from current index
            m.m[m.entries[i].Key] = i
        }
    }

    return exists
}

func (m *FastMap[K, T]) Entries() []FastMapEntry[K, T] {
    return m.entries
}

func (m *FastMap[K, T]) Len() int {
    return m.len
}

The test code that was ran is:

// s.Variations is a native map holding ~500k records

start := time.Now()
iterations := 0
for _, variation := range s.Variations {
    if variation.Id > 0 {

    }
    iterations++
}
log.Printf("Native Map: %d Iterations -  %fms\n", iterations, float64(time.Since(start).Microseconds())/1000)

// Copy data into FastMap
fm := helpers.MakeFastMap[state.VariationId, models.ItemVariation]()
for key, variation := range s.Variations {
    fm.Set(key, variation)
}

start = time.Now()
iterations = 0
for _, variation := range fm.Entries() {
    if variation.Value.Id > 0 {

    }
    iterations++
}
log.Printf("FastMap: %d Iterations -  %fms\n", iterations, float64(time.Since(start).Microseconds())/1000)

Upvotes: 3

Views: 1709

Answers (1)

AminMal
AminMal

Reputation: 3173

I think this kind of comparison and benchmarking is a little off-topic. Go implementation of map is quite different from your implementation, basically because it needs to cover a wider area of entries, the structs used in compile time are actually kind of heavy (not so much though, they basically store some information about the types you use in your map and so on), and the implementation approach is different! Go implementation of map is basically a hashmap (yours is not obviously, or it is, but the actual hashing implementation is delegated to the m map you hold internally).

One of the other factors makes you get this result is, if you take a look at this:

for _, variation := range fm.Entries() {
    if variation.Value.Id > 0 {

    }
    iterations++
}

Basically, you're iterating over a slice, which is much easier and faster to iterate rather than a map, you have a view to an array, which holds elements of the same types next to each other, makes sense, right?
What you should do to make a better comparison would be something like this:

for _, y := range fastMap.m {
        _ = fastMap.Entries()[y].Value + 1 // some simple calculation
}

If you're really looking for performance, a well written hash function and a fixed size array would be your best choice.

Upvotes: 1

Related Questions