JuliaLang/julia

`allunique(::String)` performance anomaly

Open

#50,360 opened on Jun 29, 2023

View on GitHub
 (17 comments) (0 reactions) (0 assignees)Julia (5,773 forks)batch import
good first issueperformancestrings

Repository metrics

Stars
 (48,709 stars)
PR merge metrics
 (Avg merge 20d 6h) (157 merged PRs in 30d)

Description

It seems that allunique is not short-circuiting efficiently for strings

julia> VERSION
v"1.10.0-DEV.1604"

julia> using Random

julia> using BenchmarkTools

julia> s=randstring(100000);

julia> @btime allunique(s)
  140.850 μs (7 allocations: 848 bytes)
false

julia> @btime allunique(s[1:100]) && allunique(s)
  575.746 ns (8 allocations: 968 bytes)
false

140 μs >> 575 ns

Contributor guide

Research direction
Investigate the performance anomaly of allunique for strings. Look at how allunique is implemented and why it does not short circuit efficiently. Focus on the iteration of characters and the use of hash sets. Consider if the issue is related to the overhead of string indexing or set operations.
Tech stack
julia
Domain
backend
Issue type
Performance
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
2
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
1-3 hours
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
Active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
Clear
Prerequisites
Julia
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
50