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]
25 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
Hey, I'm back, implemented the solution and wanted to compile again, but... this line of code generates an error:
for i in range(pop_count(123123)):
I have from bit import count_leading_zeros, pop_count at the top of this file.
Why does it give me this error?:
Included from /home/eyeless/Desktop/Projects/theproject/theproject.mojo:1:
/home/eyeless/Desktop/Projects/theproject/basics/generic/magic.mojo:87:29: note: call expansion failed
for i in range(pop_count(123123)):
^
open-source/mojo/stdlib/stdlib/bit/bit.mojo:230:68: note: call expansion failed
open-source/mojo/stdlib/stdlib/sys/intrinsics.mojo:90:14: note: failed to interpret operation pop.call_llvm_intrinsic{fastmathFlags: #pop<fmf none>, hasSideEffects: false, intrin: "llvm.ctpop" : !kgen.string}(#kgen.pack<123123> : !kgen.pack<[[typevalue<#kgen.typeref<@"stdlib::builtin::int::Int">>, index]]>)
Included from /home/eyeless/Desktop/Projects/mochess/mochess.mojo:1:
/home/eyeless/Desktop/Projects/theproject/basics/generic/magic.mojo:87:29: note: call expansion failed
for i in range(pop_count(123123)):
^
open-source/mojo/stdlib/stdlib/bit/bit.mojo:230:68: note: call expansion failed
open-source/mojo/stdlib/stdlib/sys/intrinsics.mojo:90:14: note: LLVM could not constant fold intrinsic: llvm.ctpop
mojo: error: failed to run the pass manager
@Darkmatter Maybe you know, since you know everything I guess 😄
Mojo version is mojo 24.6.0 if that's relevant
Try casting the result of
pop_count to an Int.I did, it changed nothing if I did this via Int(pop_count(123123)), and when I tried to use .cast there was an error that Int doesn't have attribute cast
Can I see more of the code? There was a similar issue a while ago for compile-time popcount, but that should have been fixed.
Sure, I'll push it to remote
Sent you link on private
Congrats @Korneliusz, you just advanced to level 2!
@Darkmatter Sorry for bothering you with so easy thing (probably), but after update to nightly a lot have changed... How do I even cast from UInt8 to Int? 😅
Int(uint8_val)I need to update the plugin then that was saying that no valid candidate was found. So misleading
You might want to restart your ide.
And make sure you're using the nightly plugin.
Yeah, now it's fine
@Darkmatter After fixing everything I got the same error as before
Huh
Sending you link to repo
For me I had to use int(…) or you can call uint8_val.int()
I think that’s still kind of messy but the simplest solution