dtr

[utterances-bot]

Dynamic Tensor Rematerialization

https://marisa.moe/dtr.html

[MarisaKirisame]

Testing utteranc.es

[cloud11665]

Is memory planning a transformed version of the backpack problem?

[MarisaKirisame]

@cloud11665 checkpointing is NP complete, but it isnt exactly the backpack problem cause the value to pack one thing change base on what other thing you have pack.
there are also different memory layout problem that also has this backpacky-feel to it, off the top of my head -
a mark-compact garbage collector (it try to order data to maximize spatial locality of the cache)
machine code layout in compiler (try to put code that called together near each other for spatial locality again)
register allocator in compiler (graph coloing)

a very interesting fact is that an approach in register allocation is essentially to set up a LRU cache for all values, and evict when out of register slot, very much like DTR for checkpointing. (it is called linear scan register allocator)

[cloud11665]

@MarisaKirisame thanks for the quick response.
I have one more question, does an optimal memory layout mean bad realloc performance? Is there a way to balance those 2 problems (First thing that comes to my head is a nonlinear physical to virtual mapping, but from my experience, those things destroy cache performance.)?

[MarisaKirisame]

@cloud11665 by realloc, do you mean literally the realloc function?
it is really hard to optimize for that unless you know a lot about the program (because realloc require space while a good layout try to compact everything). the easier route will be to change the datastructure so it doesnt require realloc (e.g. from a std::vector to a std::list<std::array<T, 64>>)