The Journey of Building GoQuickMap: From Hash Tables to High-Performance Go Library

08 Sep, 2024

Introduction

Hello, Go enthusiasts and data structure nerds! I'm excited to share the journey of creating GoQuickMap, a high-performance hash table library for Go. This project started as an exploration of hash table fundamentals and evolved into a robust, efficient implementation that outperforms built-in Go maps in several scenarios. Let's dive into the process, challenges, and learnings along the way.

The Beginnings: Understanding Hash Tables

Our journey began with a deep dive into the fundamentals of hash tables. Hash tables are ubiquitous in computer science, offering average O(1) time complexity for insertions, deletions, and lookups. The key components I needed to understand were:

1. Hash function
2. Collision resolution
3. Load factor and resizing

I started by implementing a basic hash table with string keys, using the built-in Go hash/fnv package for hashing and separate chaining for collision resolution.

Crafting Our Hashing Function

While the built-in FNV hash worked well, I wanted to optimize further. After researching various non-cryptographic hash functions, I settled on a custom implementation based on FNV-1a with an additional rotation step:

func Hash(s string) uint64 {
    var h uint64 = 14695981039346656037 // FNV offset basis
    for i := 0; i < len(s); i++ {
        h ^= uint64(s[i])
        h *= 1099511628211 // FNV prime
    }
    return bits.RotateLeft64(h, 13)
}

This function provided a good balance of speed and distribution, crucial for our hash table's performance.

The Core Implementation: QuickMap

With our hash function in place, I implemented the core QuickMap structure. Key decisions included:

1. Using an array of buckets, each containing a linked list of nodes
2. Implementing dynamic resizing when the load factor exceeds 0.75
3. Optimizing for string keys, which are common in many applications

The basic structure looked like this:

type QuickMap struct {
    buckets []*node
    size    int
}

type node struct {
    key   string
    value interface{}
    next  *node
}

Then I implemented key operations: Insert, Get, and Delete, ensuring they handled collisions correctly and maintained the desired load factor.

Expanding the Library: QuickSet and QuickDict

With QuickMap as our foundation, I expanded the library to include QuickSet and QuickDict. QuickSet was implemented as a wrapper around QuickMap, using only the keys and ignoring values. QuickDict was essentially a direct use of QuickMap with some additional dictionary-specific methods.

This modular approach allowed us to maintain a single core implementation while providing different interfaces for various use cases.

Optimizations and Performance Tuning

As I developed the library, I made sure to constantly benchmarke and optimize it. Key improvements I thought of after building this were:

1. Implementing batch operations (InsertMany, DeleteMany) for efficient bulk operations
2. Allowing configurable initial capacity to reduce early resizing operations
3. Fine-tuning the resize strategy to balance between memory usage and performance

Benchmarking and Comparisons

I created comprehensive benchmarks to compare GoQuickMap against built-in Go maps and popular third-party libraries. The results were exciting:

• QuickMap outperformed built-in maps by up to 62% for deletions and 45% for lookups
• QuickSet showed up to 66% improvement in Contains and Remove operations compared to a popular set implementation

These results validated our optimization efforts and showed the potential of our library for high-performance applications. I never thought of creating something that would be better in performance than already existing map and set.

Challenges and Learnings

Throughout the development process, I faced several challenges:

1. Balancing performance with memory usage
2. Ensuring thread-safety without sacrificing speed (a challenge I am still working on)
3. Deciding on the trade-offs of supporting only string keys (don't worry I'll be looking into that to later)

Each challenge provided valuable learning opportunities and deepened our understanding of Go's performance characteristics and data structure design.

Current Limitations and Future Plans

While I am proud of GoQuickMap's performance, I acknowledge its current limitations, primarily the support for string keys only. Future plans include:

1. Implementing support for generic key types
2. Developing specialized implementations for numeric keys
3. Adding support for custom hash functions
4. Exploring lock-free implementations for concurrent access

Conclusion

Building GoQuickMap has been an exciting journey from hash table basics to a high-performance Go library. I've learned invaluable lessons about data structure design, Go optimization, and the importance of continuous benchmarking and improvement.

I encourage the community to try out GoQuickMap, provide feedback, and contribute to its future development. Whether you're building a performance-critical application or just curious about efficient data structures in Go, I hope GoQuickMap will be a valuable tool in your arsenal.

Check out the GitHub repository for installation instructions, usage examples, and more detailed performance comparisons.

Follow me X/Twitter for giga chad software takes!!!

Happy coding, and may your lookups always be O(1)!