reddit

“I recently got involved in trying to improve performance of a large customer application.  Azul's JVMs come with an always-on profiling tool - RTPM - so it was easy to spot where the time was going.  The name has been changed to protect the guilty but the name might as well have been "addToSet".  A quick check of the JIT'd assembly showed that all time was spent in spinning down a long array (an ArrayList actually), checking for duplicates.  In the end, no dup gets found and the new element gets appended.  Adding N elements gives us a classic O(N^2) algorithm.  The array was already >32000 elements in length at the time we profiled it, so time is proportional to (32K^2) ~ 1billion.  Ugly stuff.” source...