Speed improvement suggestion: array resizing

[bkDJ]

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?

[kaikalii]

I agree this should be fixed.

If you join to the end instead of the front, does the extra time go away?

[kaikalii]

If you join to 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.

[kaikalii]

Fixed in 67634f73ca02bd5470. This fix only applies to join, but there may be opportunities for other similar optimizations.

[bkDJ]

Super cool, thanks!! And I'll take care to join flip when in a loop.

BTW, if there is still a known performance cost for prepending instead of appending, I'd also recommend the docs call that out.

EDIT: I see you've now done so, in 2bb4caae3db8112e28cb4019d9f009cd137334c6 🎉. Thanks again for the lightning fix.