lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]




On Wed, Sep 23, 2020, 11:56 bel <bel2125@gmail.com> wrote:
> Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.

Even copying is only O(n) for a "larger" number of bytes n. For small n effects memory access, caching, ... (random effects) do have a much bigger effect on execution time than copying a byte more - making it effectively independent from n. The ~32 bytes mentioned before would be "small" from that point of view.

Growing a table is the operation that would cause significant delays when the table is large enough. You would have to keep sizes small or fixed to guarantee constant time operations.

Growing an array by doubling it's size when you run out of space has O(1) complexity, but that is amortized complexity which is not good enough for hard realtime work unless you limit the maximum array size.