3 ms·

I'd like to understand what you mean by this. I'm no expert on Rust lock-free designs, but what are the "amortization guarantees" that you refer to? Is there so

I'd like to understand what you mean by this. I'm no expert on Rust lock-free designs, but what are the "amortization guarantees" that you refer to? Is there something that I can read that explains this in greater detail?

bsder 6y ago
Basically any background about java.util.concurrent (the development mailing list is archived, IIRC). Also, anything by Cliff Click and Azul. Okasaki talks about it in the context of functional data structures rather than concurrent: https://en.wikipedia.org/wiki/Purely_functional_data_structure https://en.wikipedia.org/wiki/Purely_functional_data_structu... But, let's talk about something like CopyOnWriteArrayList. If I add() a CopyOnWriteArrayList(), a copy of the underlying data comes into existence with the new element. That should certainly get charged to the thread doing the add(). Fine. Some Iterators are probably still pointing at the old underlying data. Not a big deal. So, the final Iterator() with references to old data finally finishes and gets deallocated/dropped. Now, all the underlying data that got copied is no longer relevant and needs to be deallocated/dropped. So, who does that? Does that happen on a thread that next calls get()? If so, get() is now O(n) worst case. That certainly doesn't make people happy. Does that happen on a thread that next calls add()? Well, we can have a lot of iterators that were all working and now ended. So, that add() might be deallocating a LOT of copied stuff. This might be where it has to be done, but the fact that your O() performance is dependent upon the size of the data and the number of copies that got made makes you O(n^2)-ish (O(n*k) to be more precise). That's not good. Does the deallocate happen on thread where the last Iterator() got dropped? Having to deallocate the universe because you just happened to be the last one using the underlying data store doesn't seem like a good idea. Perhaps you do a little bit of deallocation work on every get()? Probably good for throughput, but it sure makes the data structure a lot more complicated. Perhaps you have an explicit deallocation call. That kind of defeats the whole point of using a language like Rust. In a GC language, this all gets charged to the GC thread and swept under the carpet. That's what I'm thinking about when I say "amortized". There's also a slightly different amortized. In C++, for example, when you insert() into an unordered_map(), the "normal" time is O(1), but every now and then you get an O(n) while the structure reallocates. This results in an "average/amortized" cost of O(1) if the reallocation is done intelligently (generally doubling in size every overflow).

bsder 6y ago

Basically any background about java.util.concurrent (the development mailing list is archived, IIRC). Also, anything by Cliff Click and Azul. Okasaki talks about it in the context of functional data structures rather than concurrent: https://en.wikipedia.org/wiki/Purely_functional_data_structure https://en.wikipedia.org/wiki/Purely_functional_data_structu... But, let's talk about something like CopyOnWriteArrayList. If I add() a CopyOnWriteArrayList(), a copy of the underlying data comes into existence with the new element. That should certainly get charged to the thread doing the add(). Fine. Some Iterators are probably still pointing at the old underlying data. Not a big deal. So, the final Iterator() with references to old data finally finishes and gets deallocated/dropped. Now, all the underlying data that got copied is no longer relevant and needs to be deallocated/dropped. So, who does that? Does that happen on a thread that next calls get()? If so, get() is now O(n) worst case. That certainly doesn't make people happy. Does that happen on a thread that next calls add()? Well, we can have a lot of iterators that were all working and now ended. So, that add() might be deallocating a LOT of copied stuff. This might be where it has to be done, but the fact that your O() performance is dependent upon the size of the data and the number of copies that got made makes you O(n^2)-ish (O(n*k) to be more precise). That's not good. Does the deallocate happen on thread where the last Iterator() got dropped? Having to deallocate the universe because you just happened to be the last one using the underlying data store doesn't seem like a good idea. Perhaps you do a little bit of deallocation work on every get()? Probably good for throughput, but it sure makes the data structure a lot more complicated. Perhaps you have an explicit deallocation call. That kind of defeats the whole point of using a language like Rust. In a GC language, this all gets charged to the GC thread and swept under the carpet. That's what I'm thinking about when I say "amortized". There's also a slightly different amortized. In C++, for example, when you insert() into an unordered_map(), the "normal" time is O(1), but every now and then you get an O(n) while the structure reallocates. This results in an "average/amortized" cost of O(1) if the reallocation is done intelligently (generally doubling in size every overflow).