atomvm
Common list operations exhibit O(n^2) time complexity
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.
It seems like fixing GC may bring performance improvements across the board, but it may be easier to replace these functions with nifs.
My vote would be for fixing GC, even when running a simple blinky, a device observed using OpenOCD/GDB seems to spend the vast majority of the time doing garbage collection.
My vote would be for fixing GC, even when running a simple blinky, a device observed using OpenOCD/GDB seems to spend the vast majority of the time doing garbage collection.
I think both actions should be taken, starting from the NIFs. Functions in lists are so widely used that anyway a super efficient C implementation might be good anyway.
I think both actions should be taken, starting from the NIFs. Functions in
listsare so widely used that anyway a super efficient C implementation might be good anyway.
Agreed, that makes the most sense, and I suspect fixing garbage collection will not be a small undertaking.