Worst case performance and "impossibly unlikely" conditions
Posted Jan 12, 2012 1:49 UTC (Thu) by rgmoore
In reply to: Worst case performance and "impossibly unlikely" conditions
Parent article: Denial of service via hash collisions
Perl switched sort implementations because they saw bad performance as a performance problem, not because they saw poor performance as a possible DOS problem. It turns out that the oddball pathological data isn't so oddball after all, so performance regressions because of their sort implementation were more common than you'd expect if you assume that you're always sorting random data. They also let the user tweak the sort algorithm with a pragma, so people who really know what they're doing can override the default and use quicksort if they know it won't cause problems.
to post comments)