Compilation with constant lookup table
In my project I need to have constant lookup table. I wanted to implement it with:
alias LOOKUP = InlineArray[UInt64, 104960](
...here all elements that I want for my table...
)
It doesn't have to be alias but var isn't supported in file scope and I need to initialize this lookup once on the start of the program and it will be constantly accessed by two or three different functions. So I thought that alias would work here like const in Rust or C and I will be able to just have my lookup table in memory while program is running.
I need this lookup to be as fast as possible, that's why I wanted to use InlineArray, if there is any quicker collection let me know.
Given the above context I cannot compile my project after adding this table. I tried normal List instead of InlineArray and it didn't matter. When I compile it takes about 15 minutes (even tho the project is very small at the moment, and compiled in less than second before). After 15 minutes compilation uses up all my RAM (I have 32GB), even tho sys.info.sizeof says that my lookup table should only be 839680 B which is 0.8 MB.
Why this happens? How to implement such constant static lookup table so it would compile as expected?
[I also tried to pack it into struct as var, where I wanted to initialize it with init dunder having the value hardcoded inside, but it gave me such error (after 15 minutes of compilation):
/usr/bin/ld: cannot find -ltinfo: No such file or directory
collect2: error: ld returned 1 exit status
mojo: error: failed to link executable
If you know why, please share, before I could build the project no problem
I thought that maybe if I use alias the table is copied to every place I use it, but even if in my brand new test project I refer to it only once, it still uses all my RAM after 15 minutes of compilation and my OS stops working]
12 Replies
You can write a function which returns the initalized lookup table and run it at compile time.
alias LOOKUP = create_lookup_table()
Using a variadic ctor for this is probably not good, since it's going to run under the MLIR interpreter and need lots of copies. No matter what, doing this init at compile time is going to be somewhat expensive, but a well-written consturctor with an out parameter might have less of a performance hit.Sorry, what is "variadic ctor"?
I have all values and I can hardcode them, coming from Rust, this is quite strange that I need to do this in a function.
How to make constructor with out parameter for an alias? Or what do you mean? I'm not that advanced yet I guess
The variadic constructor is one which forces passing everything as function arguments.
InlineArray is not a language builtin, so what you've done is a lot closer to if you did vec![ $ELEMENTS ]. You're passing almost every single one of those on the stack to a constructor function, then the compiler allocates another 0.8 MB of stack for the array, then copies everything in, then freezes the value from the MLIR interpreter.
If you can re-derive the lookup table, it should be much cheaper from the compiler's perspective.
That is very interesting. You're awesome 🔥@Darkmatter , thanks.
I can re-derive values.
I'm still not sure why it took that much RAM tho. It would need to copy the array at least 2750 times to utilise that much RAM. I'll check using the constructor with re-derived values will fix this.
So is there anything with faster access by index than InlineArray for my case? I don't really need in bound checks or any safety as I'm 100% sure that getters will not go out of bounds. I only care about speed.
Congrats @Korneliusz, you just advanced to level 1!
Do I understand correctly that for each element it makes allocation for whole array? It means 104960 times 0.8MB?
If this is correct then it shouldn't work like that 😅
The MLIR interpreter is not particularly memory friendly. I think it has multiple pointers per value along with other things.
There should be
unsafe versions of the load functions which avoid bounds checking.
This only allocates the array once, then fills it in.There is unsafe_get for InlineArray
That's probably what you want if you don't need vectorized access.
If you do, take a pointer and use gather.
I'll think about that for another more dynamic table that I will need for this project. But for now that's valid info, thanks. When I confirm that it works for me I will mark this as resolved or write message here if it doesn't work
@Darkmatter I was trying to implement this as you said but I came across the fact that along with the big lookuo table I was also generating one smaller lookup and one medium lookup. Logic for that is bound together and I cannot split the generation into three constructors, because generating one optimizes generating another, let's the algorithm pack it better and all of this comes from random numbers, I need to be sure thag same random numbers were used for certain positions in the lookups, so that makes it totally impossible to split the logic to three cobstructors. That
things.
How can I define constructor that would initialize three aliases at once?
I would like to have something like:
Alias LOOKUP_1, LOOKUP_2, LOOKUP_3 = init_lookups()
fn init_lookups(out lookup1: Type, out lookup2: Type, out lookup3: Type) :
...
But this probably won't be that easy, is it even possible?
Initialize a tuple.
I'm so dumb, yeah I actually wrote that as a tuple above and still didn't think about that 😅
I'll try, thank you