I am a bit concerned about the comparison. Your plain JS assignment of item 50005 clones the whole object with the change applied to the new object. No surprise that it is expensive. But if the mutable object is simply mutated using the simple assignment:
todos.t2148bf88.completed = true
Would that not be super fast?
I am not trying to be dismissive of Immutable.js, but I want to make sure I understand the kind of performance scenario is applicable to me. Currently, my method is to never clone, and to be very careful of unintended mutation.