[BUG] Excessive compilation time during manipulation of StaticTuple

[MoSafi2]

Bug description

The following code takes around 40 seconds to compile with the actual execution time after build being trivial.
The compilation time is also tied to the Tuple size not the number of calling the __setitem__() function with Tuple size of 2_000 only lasting 3 secs.

    alias size = 5000
    # All numericals + Int are also affected
    var x = StaticTuple[Int8, size]()
    for i in range(2):
     # x[i] = 8 also produces similair effect
        x.__setitem__[50](8)
    print(x[0])

Steps to reproduce

• Include relevant code snippet or link to code that did not work as expected.
• If applicable, add screenshots to help explain the problem.
• If using the Playground, name the pre-existing notebook that failed and the steps that led to failure.
• Include anything else that might help us debug the issue.

System information

- What OS did you do install Mojo on ? Ubuntu 24.04 LTS, also reproducible on Ubuntu 22.04 LTS running in VM  
- Provide version information for Mojo by pasting the output of `mojo -v` mojo 2024.4.2621 (6dff3016) 
- Provide Modular CLI version by pasting the output of `modular -v` modular 0.7.2 (d0adc668)

[lattner]

The issue here is that StaticTuple is defined as register passable despite having arbitrary size. This will never work well - register passable things should only be used for small types, not arbitrary size things like this. We need to get StaticTuple off of being register passable.

[JoeLoser]

The issue here is that StaticTuple is defined as register passable despite having arbitrary size. This will never work well - register passable things should only be used for small types, not arbitrary size things like this. We need to get StaticTuple off of being register passable.

StaticTuple will be removed soon once we replace uses with the InlineArray type that works on memory only types. Have you tried using that with a large size?

[MoSafi2]

@JoeLoser @lattner
I tried the same code with InlineArray from the latest nightly build and the same problem exist. Initialization of the array with a fill value is quite fast but emplace mutation of values is size-dependent.

from utils import InlineArray
fn main():
    var x = InlineArray[Int, 30_000](0)
    for i in range(10):
        # x[i] = i # Similair behavior 
        var ptr = x._get_reference_unsafe(i)
        initialize_pointee_copy(UnsafePointer[Int](ptr), i)

The compilation is also trivial when the index is known at compile time. the following compiles quite fast.

    var x = InlineArray[Int, 30_000](0)
    for i in range(3):
        x[50] = i

[weiweichen]

@JoeLoser @lattner I tried the same code with InlineArray from the latest nightly build and the same problem exist. Initialization of the array with a fill value is quite fast but emplace mutation of values is size-dependent.

from utils import InlineArray
fn main():
    var x = InlineArray[Int, 30_000](0)
    for i in range(10):
        # x[i] = i # Similair behavior 
        var ptr = x._get_reference_unsafe(i)
        initialize_pointee_copy(UnsafePointer[Int](ptr), i)

The compilation is also trivial when the index is known at compile time. the following compiles quite fast.

    var x = InlineArray[Int, 30_000](0)
    for i in range(3):
        x[50] = i

hmm, the compilation time don't seem to be significantly different that I ran this on a quiet mdcm metal machine:

• with var x = InlineArray[Int, 30](0)

ubuntu@ip-10-250-103-160:~/playground/kangaroojack/inlinearray$ /usr/bin/time kgen -emit test.mojo -o 30.o
==== Finish runLLVMOpt pass (us)2466
runLLcPass verifyModule(us): 52
==== Finish runLLVMOpt pass (us)2728
runLLcPass verifyModule(us): 86
==== Finish runLLVMOpt pass (us)4929
runLLcPass verifyModule(us): 79
runLLcPass passMgr run(us): 3342
runLLcPass passMgr run(us): 3114
runLLcPass passMgr run(us): 6581
5.67user 0.57system 0:02.52elapsed 247%CPU (0avgtext+0avgdata 307192maxresident)k
0inputs+2672outputs (1major+98993minor)pagefaults 0swaps

• with var x = InlineArray[Int, 30_000](0)

ubuntu@ip-10-250-103-160:~/playground/kangaroojack/inlinearray$ rm -rf ~/modular/.derived/.*_cache
ubuntu@ip-10-250-103-160:~/playground/kangaroojack/inlinearray$ /usr/bin/time kgen -emit test.mojo -o 30000.o
==== Finish runLLVMOpt pass (us)2307
runLLcPass verifyModule(us): 50
==== Finish runLLVMOpt pass (us)2004
runLLcPass verifyModule(us): 47
==== Finish runLLVMOpt pass (us)4056
runLLcPass verifyModule(us): 74
runLLcPass passMgr run(us): runLLcPass passMgr run(us): 34113230

runLLcPass passMgr run(us): 6542
6.18user 0.54system 0:02.95elapsed 227%CPU (0avgtext+0avgdata 307612maxresident)k
0inputs+2680outputs (0major+99526minor)pagefaults 0swaps

[MoSafi2]

On my PC the initilization time of the array does not change much with the array size. Ex: the following code

alias size = 30_000
var arr = InlineArray[Int, size](0)
print(arr[50])

time mojo build test.mojo
# size = 30_000
real    0m1.118s
# size = 30
real    0m0.335s

However, the compilation of any addition ops on the array are size dependent. Ex: deref, emplace mutation.
The following deref operation are similairy slow to compile.

 alias size = 31_000
 var arr = InlineArray[Int, size](0)
 for i in range(10):
      print(arr.__refitem__(i)[])
 print(arr[50])

time mojo build test.mojo
# size = 31_000
real    0m36.154s
# size = 30
real   0m0.361s