dcrafti
BAN USERFor the people who are saying to copy the data before writing (using immutable objects), that only solves dirty reads. It doesn't solve multiple, concurrent writers, because the copy, update, pointer replacement operation is not atomic, so during that process, before the pointer is updated, another thread might start its own copy operation in order to write.
- dcrafti February 07, 2013Of those options, only the queue is fundamentally wrong.
However, none of the other options are particularly good.
A better option would be a tree, as the recursion might require many evaluations at each level, and a tree will be more flexible for that, and also allow parallelisation if the problem is suitable..
As this is an interview question, going beyond the presented options is probably not a bad thing.
Saying that there should be an atomic compare and swap operation doesn't help with actually having one.
- dcrafti February 07, 2013The atomic update doesn't solve the problem of needing to:
- read the value as an input into calculating a new value,
- doing the calculation itself.
Only then can the atomic pointer update take place. In the meantime, other threads can be reading the memory, as an input, that will soon be out of date.
So, while it is possible to do what's being asked for some class of problems, it's not possible for anything that relies an order of execution.
Of course, with literally unlimited memory, if there's also unlimited processing power, then anything is possible, by using predictive execution.