News for hackers. Stuff that matters.
Re:Why modern software is slow by nyanpasu64 on Friday September 30, 2022 @06:01PM (#33041372)
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?
Re:Why modern software is slow by marginalia_nu on Saturday October 01, 2022 @05:48AM (#33045329)
Very 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).

Re:Why modern software is slow by nyanpasu64 on Saturday October 01, 2022 @09:15PM (#33051771)
Correction: 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.