4 ms·

Fun fact: you can make the time of a push unconditionally O(1) at the cost of extra memory as well. This is useful if you really can't afford the unpredictable

by orlp 4y ago

Fun fact: you can make the time of a push unconditionally O(1) at the cost of extra memory as well. This is useful if you really can't afford the unpredictable spike in performance. The trick is to slowly already start copying data into the next larger buffer as you're filling the previous buffer. As an example in pseudocode C++: template<class T> struct ConstantTimeVector { T* buf; T* next_buf; size_t len; size_t cap; void push(T x) { if (len == cap) { free(buf); buf = next_buf; cap *= 2; next_buf = alloc(cap); } buf[len] = x; next_buf[len] = x; next_buf[len - cap / 2] = buf[len - cap / 2]; len += 1; } } You can apply a similar trick to hash tables to get expected O(1) time inserts without amortization, by already building the re-hashed table during the building of the previous table.

sfink 4y ago
Hah! That's awesome. I'm not sure how well it would work in practice, since you're depending on alloc() giving you uninitialized memory—if it zeroes it, then it's back to being O(n). But that's kind of an unfair quibble. And of course, it adds a branch to the lookup. Still O(1), but you'd need to check which buffer to find a given index in. Really not a problem here since as you say, the whole point is to bound the latency, not minimize it.
- orlp 4y ago
  It does not necessarily add a branch to the lookup, look more closely: all current data exists in buf in its entirety. It is duplicated into next_buf. This might be problematic depending on T in C++ as it would need to invoke copy constructors. In Rust all types can trivially be memcpy'd into another location if you own it, so this design would be entirely valid (as long as next_buf is not publicly accessible at all, and we do not provide mutable access to the data). EDIT: after thinking a bit more, due to interior mutability you can't provide access at all, or you would need to invoke a branch like you said in Rust. If you want to provide mutable access to a piece of data and/or avoid copy constructors in favor of move constructors, then, yes you would need to do a branch.
  - sfink 4y ago
    Doh! You are right, of course. My head is stuck in the standard doubling approach. You are pre-copying into an upcoming buffer. Which, as you say, is going to be weird with the language model, since the "same" thing exists in two different places. In C++, it would encounter problems with either a destructor or a copy constructor. I still think it's a cool trick for a realtime setup for arrays of trivial types.

by orlp 4y ago

sfink 4y ago

Hah! That's awesome. I'm not sure how well it would work in practice, since you're depending on alloc() giving you uninitialized memory—if it zeroes it, then it's back to being O(n). But that's kind of an unfair quibble. And of course, it adds a branch to the lookup. Still O(1), but you'd need to check which buffer to find a given index in. Really not a problem here since as you say, the whole point is to bound the latency, not minimize it.

orlp 4y ago
It does not necessarily add a branch to the lookup, look more closely: all current data exists in buf in its entirety. It is duplicated into next_buf. This might be problematic depending on T in C++ as it would need to invoke copy constructors. In Rust all types can trivially be memcpy'd into another location if you own it, so this design would be entirely valid (as long as next_buf is not publicly accessible at all, and we do not provide mutable access to the data). EDIT: after thinking a bit more, due to interior mutability you can't provide access at all, or you would need to invoke a branch like you said in Rust. If you want to provide mutable access to a piece of data and/or avoid copy constructors in favor of move constructors, then, yes you would need to do a branch.
- sfink 4y ago
  Doh! You are right, of course. My head is stuck in the standard doubling approach. You are pre-copying into an upcoming buffer. Which, as you say, is going to be weird with the language model, since the "same" thing exists in two different places. In C++, it would encounter problems with either a destructor or a copy constructor. I still think it's a cool trick for a realtime setup for arrays of trivial types.