Speed improvement suggestion: array resizing
Closed this issue · 4 comments
Example:
◌ ⍥(⊂⚂)1e5 []
Obviously that is not how you would write code for the same result. But sometimes, a join in a do/repeat is the simplest way to accomplish something (such as generating all permutations of a list that satisfy a certain condition). When I run the above with uiua run 'file.ua' --time-instrs | grep ⊂, the time taken seems to increase proportionally to the current length of the array on every single call.
# first few lines
⏲ 0.01ms - ⊂
⏲ 0.00ms - ⊂
⏲ 0.00ms - ⊂
# last few lines
⏲ 0.36ms - ⊂
⏲ 0.36ms - ⊂
⏲ 0.40ms - ⊂How do you feel about having the backing Rust array pre-allocate higher amounts (e.g. instead of "exact fit", leave some head-room up to the next power of two? Ruby does something similar.) when an array is too small to fit its next element?
I agree this should be fixed.
If you join to the end instead of the front, does the extra time go away?
If you
jointo the end instead of the front, does the extra time go away?
I did some testing and yes, joining to the end has no extra cost.
I'm going to push a change that fixes joining to the front.
It will still technically be O(n), since all the existing elements have to get shifted over. But in my testing, it's 1 or 2 orders of magnitude faster since there is no longer an allocator call on every join.