News for hackers. Stuff that matters.
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by kragen on Monday August 21, 2023 @10:30PM (#37217908)
i think it's pretty common for a specialized reimplementation of a standard library type or function to outperform it by an order of magnitude or so in some particular case. chris wellons gave an excellent example of this with hashing in golang in https://nullprogram.com/blog/2023/06/26/

commonly (as in wellons's post about the two-sum problem) there's a variation on the standard algorithm that can help significantly, but which the standard library function doesn't have an option for

also i think the cost of reimplementing simple 'algorithms from the book' like insertion sort or even quicksort is pretty low; as you saw in my comment above, insertion sort is six lines of code and only moderately bug-prone. we aren't talking about fibonacci heaps or red-black trees or fm-indexes or rader's algorithm or something. the cost is low enough that it's easy to justify in a lot of cases

There are no comments on this comment yet.