lambdaclass / lambdaclass/lambda_compiler_kit
perf: optimize nested foldl in Glushkov/Matcher.lean step/initialStep (O(n²) → O(n log n))
Nobody has claimed this yet.
- Dominant language
- Lean
- Stars
- 2
- Forks
- 1
- PR merge metrics
- No merged PRs in 30d
Description
Problem
The step and initialStep functions in Lck/Regex/Glushkov/Matcher.lean (lines 45-55, 65-75) use nested foldl operations that produce O(n²) complexity for large NFAs.
Impact
For a pattern with n positions, each step scans all active states and for each computes a set union — resulting in O(n²) per character of input.
Suggested Fix
Consider using a more efficient data structure (e.g., a bitset or sorted set with efficient union) to bring the per-step cost to O(n log n).
References
Raised in AI code review.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in Lck/Regex/Glushkov/Matcher.lean, focusing on step and initialStep at the cited lines and tracing their nested foldl operations. Compare candidate state-set data structures against the current behavior; done means preserving matching results while reducing the per-step complexity from O(n²) toward O(n log n).
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers, performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100