Pierre Bertrand: Fast Distribution of Balls into Bins

In the past, the theory on parallel algorithms distributing n balls into n bins has been concerned with deriving asymptotic results. However, all bounds have in common that they are very slow-growing functions, like O(log log n) or O(log* n). We examine how algorithms behave in practice, for realistic values of n. To this end, we study the first round of simple algorithms by means of theory as well as simulation. Furthermore, we introduce a few modifications to further improve their efficiency.