Common list operations exhibit O(n^2) time complexity
Maintainers usually reply within 3 days
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Bug
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- c, erlang
- Domain
- backend, performance
Research direction
The issue reports quadratic behavior in lists:seq/3, lists:flatten/1 and lists:join/2, and suggests either adding NIFs or changing garbage collection. Start by reading these list operations and the garbage collector implementation, then profile the reported cases to locate the cause. Done means the affected operations scale linearly and have tests or benchmarks demonstrating the improvement.
Written by the indexing model from the issue text.
Description
Probably because of aggressive gc implementation, common list operations exhibit a quadratic time complexity.
This was observed with lists:seq/3, lists:flatten/1 and lists:join/2.
We could replace them with nifs that compute size to allocate only once, or fix GC.
- Dominant language
- Erlang
- Stars
- 2.3k
- Forks
- 171
- Avg merge
- 4d 11h
- Merged PRs (30d)
- 20
Getting set up
- No Dockerfile or Docker Compose file
- Has a pull request template
- Read the contributing guide
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.
More from atomvm/AtomVM
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
Maintainers usually reply within 3 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
Maintainers usually reply within 3 days
-
lwIP sockets: a failed listen or connect leaves the socket lock held, a later close hangs foreverOpen
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
Maintainers usually reply within 3 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
Maintainers usually reply within 3 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
Maintainers usually reply within 3 days
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
milind-soni/OpenMausBot#5829 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 80/100
finos/fluxnova-bpm-platform#387 ·
Maintainers usually reply within 4 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
OHDSI/Data2Evidence#3693 ·
Maintainers usually reply within 3 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Project-N-E-K-O/N.E.K.O#3725 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
kubernetes-sigs/headlamp#8408 ·
Maintainers usually reply within 1 day