Skip to content

feat: Optimize UniqMap to reduce unnecessary slice preallocation#710

Merged
samber merged 3 commits intosamber:masterfrom
ivolkoff:20251011-UniqMap
Oct 12, 2025
Merged

feat: Optimize UniqMap to reduce unnecessary slice preallocation#710
samber merged 3 commits intosamber:masterfrom
ivolkoff:20251011-UniqMap

Conversation

@ivolkoff
Copy link
Contributor

Summary:
The current implementation of UniqMapOld preallocates the result slice with the same capacity as the input collection, even though the number of unique elements is usually much smaller.
This leads to excessive memory allocation and higher memory usage.

The proposed change adjusts the allocation strategy to use a slice sized according to the number of unique elements, significantly reducing memory footprint without changing functionality.


⚙️ What Changed

Before (UniqMapOld):

result := make([]R, 0, len(collection))
seen := make(map[R]struct{}, len(collection))

After (UniqMap):

seen := make(map[R]struct{}, len(collection))

// Build 'seen' first, then allocate result slice with exact size
result := make([]R, 0, len(seen))
for r := range seen {
    result = append(result, r)
}

📊 Benchmark Comparison

Benchmark ns/op B/op allocs/op
BenchmarkUniqMapOld 940,730 5,100,690 258
BenchmarkUniqMap 812,035 3,495,054 257

Improvement:

  • ~31% reduction in memory usage (5.1MB → 3.5MB)
  • ~14% faster execution time
  • Same number of allocations

✅ Test Results

Test Description Result
TestUniqMapOld_LenCap Ensures old version retains large capacity cap(result) == 100_000
TestUniqMap_LenCap Ensures new version allocates only necessary capacity cap(result) == 2

💡 Motivation

Using a smaller result slice capacity directly proportional to the number of unique elements significantly reduces memory consumption — especially for large input slices with high repetition rates — without affecting correctness or performance negatively.


🧠 Summary

  • ✅ Same functionality and correctness
  • 🚀 Reduced memory footprint
  • 🧹 Cleaner allocation strategy
  • 🔍 Fully covered by tests and benchmarks

@ivolkoff
Copy link
Contributor Author

func TestUniqMapOld_LenCap(t *testing.T) {
	t.Parallel()
	is := assert.New(t)

	type User struct {
		Name string
		age  int
	}

	users := make([]User, 100_000)
	for i := 0; i < 100_000; i++ {
		users[i] = User{Name: "Alex", age: 25}
	}
	users[50_000] = User{Name: "Alice", age: 25}

	result := UniqMapOld(users, func(item User, index int) string {
		return item.Name
	})

	slices.Sort(result)

	is.Equal([]string{"Alex", "Alice"}, result)
	is.Equal(2, len(result))
	is.Equal(100_000, cap(result))
}

func TestUniqMap_LenCap(t *testing.T) {
	t.Parallel()
	is := assert.New(t)

	type User struct {
		Name string
		age  int
	}

	users := make([]User, 100_000)
	for i := 0; i < 100_000; i++ {
		users[i] = User{Name: "Alex", age: 25}
	}
	users[50_000] = User{Name: "Alice", age: 25}

	result := UniqMap(users, func(item User, index int) string {
		return item.Name
	})

	slices.Sort(result)

	is.Equal([]string{"Alex", "Alice"}, result)
	is.Equal(2, len(result))
	is.Equal(2, cap(result))
}

@samber
Copy link
Owner

samber commented Oct 12, 2025

thanks !

Copy link
Owner

@samber samber left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Go < 1.21 does not support slices.Sort

@codecov
Copy link

codecov bot commented Oct 12, 2025

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 94.53%. Comparing base (da644a7) to head (c606601).
⚠️ Report is 1 commits behind head on master.

Additional details and impacted files
@@            Coverage Diff             @@
##           master     #710      +/-   ##
==========================================
+ Coverage   94.50%   94.53%   +0.02%     
==========================================
  Files          18       18              
  Lines        3439     3437       -2     
==========================================
- Hits         3250     3249       -1     
+ Misses        175      174       -1     
  Partials       14       14              
Flag Coverage Δ
unittests 94.53% <100.00%> (+0.02%) ⬆️

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

@samber samber merged commit 3a67a3f into samber:master Oct 12, 2025
11 of 13 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants