The Programming Massively Parallel Processors textbook has a chapter on histograms. You have basically mentioned the main trick though (privatization).

For this problem I think coursening would also help (so everything isn’t queued up on the copy to global memory)