search

dfinity / motoko

Simple high-level language for writing Internet Computer canisters
Apache License 2.0
503 stars 98 forks source link

Type `Nat` uses too much heap memory when boxed #4100

Open timohanke opened 1 year ago

timohanke commented 1 year ago

The Nat value 0x4000_0000 (= 2^30) uses 152 bytes on the heap. This has been verified with Prim.rts_heap_memory(). Any smaller value uses 4 bytes. A jump is expected due to boxing but the fact that the jump is soo large is due to a setting in libTomMath. @ggreif identified the MP_PREC constant. It is suggested to set it to MP_PREC=4 from its previous default value of MP_PREC=32.

We expect that a boxed Nat will use 12 + 12 + 4*MP_PREC bytes. This is was 152 with MP_PREC=32 and would be 40 with MP_PREC=4. The tradeoff is the frequency of allocations while working with bignums which would increase.

timohanke commented 1 year ago

It might be meaningful to set MP_PREC such that a 128 bit Nat can be stored at first allocation, or 256 bit. Though I do not know for what value of MP_PREC that would be.

With MP_PREC = 32 we can store up to 848 bits. I would have expected 32 4 7 = 896 bits. Not sure what the rest of the precision is used for, hence I am also not sure what we would get out of MP_PREC=4, or any other value.