Resolve issues 4366 and 4420 for better patch performance

I rebased the last two commits here on another change in my PR for branch 'test'. If you take this PR no need for that one. The test changes were necessary but otherwise unrelated, so they were a separate commit.
Not when adding a key/value.