4 ms·
Frankly I'm shocked that deduplicateTree is two orders of magnitude slower than deduplicateGreybeard, despite having asymptotically better-or-equal performance
by nyanpasu64 4y ago
Frankly I'm shocked that deduplicateTree is two orders of magnitude slower than deduplicateGreybeard, despite having asymptotically better-or-equal performance (TreeSet runtime is O(output log output), whereas sorting an array is O(input log input)). I'd say that perhaps boxing the integers is slowing the algorithm down, but deduplicateGreybeardCollections has only a <3x performance hit rather than >100x. Is the problem due to allocating large amounts of internal memory and branching heavily (binary trees as opposed to B-trees), or less predictable/vectorizable code execution than array traversal, or virtual comparison dispatch slower than `items.sort(Comparator.naturalOrder())`, or some TreeSet-specific slowdown?
- marginalia_nu 4y agoVery good question. I'm away from my work station so I can't do additional profiling, but my overall experience is that TreeSet is hella slow in almost every case. My hunch is that the extreme indirection makes mince out of data locality during traversal, since TreeSet is backed by a red black tree, so conversion to list is O(n) cache misses, whereas the sorting algorithms are reasonably well behaved from a cache perspective (Java uses a dual pivot quicksort for primitives and TimSort for objects IIRC).
- nyanpasu64 4y agoCorrection: Performing O(input) failed insertions into a TreeSet might be O(input log output) runtime, which is slower than what I stated above if input > output.