Skip to content

perf(coderd/util/slice): refactor unique method for large lists #8925

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Aug 8, 2023
Merged

perf(coderd/util/slice): refactor unique method for large lists #8925

merged 1 commit into from
Aug 8, 2023

Conversation

beyazit
Copy link
Contributor

@beyazit beyazit commented Aug 6, 2023

This pull request introduces an improved version of the Unique method, which aims to significantly enhance the performance of processing large lists. The original implementation relied on a generic Contains function, resulting in suboptimal performance for large datasets. The proposed modification leverages a more efficient approach using a map-based algorithm, delivering notable speed gains.

Benchmark

The benchmark was conducted under controlled conditions with a list size of one million elements (1,000,000). Two different implementations of the Unique method were tested: BenchmarkUniqueImproved and BenchmarkUnique. The updated version, BenchmarkUniqueImproved, utilizes a more efficient map-based approach for duplicate detection, while BenchmarkUnique represents the original implementation with a generic Contains function.

The results showed that the BenchmarkUniqueImproved version outperformed the BenchmarkUnique implementation significantly. The average elapsed time per operation for BenchmarkUniqueImproved was approximately 6.12 milliseconds (6,120,000 nanoseconds), while BenchmarkUnique took significantly longer with an average elapsed time of approximately 1,493.25 milliseconds (1,493,250,000 nanoseconds).

image

By adopting the optimized map-based algorithm, the updated Unique method demonstrated notable performance improvements, especially for large lists.

@cdr-bot cdr-bot bot added the community Pull Requests and issues created by the community. label Aug 6, 2023
@github-actions
Copy link

github-actions bot commented Aug 6, 2023

CLA Assistant Lite bot All contributors have signed the CLA ✍️ ✅

@beyazit
Copy link
Contributor Author

beyazit commented Aug 6, 2023

I have read the CLA Document and I hereby sign the CLA

cdrcommunity added a commit to coder/cla that referenced this pull request Aug 6, 2023
@matifali matifali requested a review from Emyrk August 8, 2023 06:27
Copy link
Member

@Emyrk Emyrk left a comment

Choose a reason for hiding this comment

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

👍

We only use this on small lists, so the memory cost of the map is not a worry.

@Emyrk Emyrk merged commit 1d4a72f into coder:main Aug 8, 2023
@github-actions github-actions bot locked and limited conversation to collaborators Aug 8, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
community Pull Requests and issues created by the community.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants