<story><title>Roaring bitmaps: what they are and how they work</title><url>https://vikramoberoi.com/a-primer-on-roaring-bitmaps-what-they-are-and-how-they-work/</url></story><parent_chain><item><author>celeritascelery</author><text>I see this common theme among very fast practical algorithms (like timsort or pdqsort) where there is not some secret math or algorithm, rather they are just a bunch of special cases based on heuristics. Often they involve specific knowledge of the hardware instead of treating software as abstract. To me this is the big difference between “computer science” and “computer engineering”.</text></item></parent_chain><comment><author>jandrewrogers</author><text>Much of this is just threshold effects for algorithm performance, not special cases per se.&lt;p&gt;You don&amp;#x27;t even need to have specific knowledge of the hardware as long as you can identify cross-over points where one algorithm starts significantly outperforming others. An old HPC trick is to write software that thoroughly measures several algorithm strategies on your specific hardware environment and then code-gens an algorithm that has an optimal set of strategies and strategy-switching thresholds. The meta-algorithm is mostly focused on cheaply detecting these thresholds at runtime.</text></comment>
<story><title>Roaring bitmaps: what they are and how they work</title><url>https://vikramoberoi.com/a-primer-on-roaring-bitmaps-what-they-are-and-how-they-work/</url></story><parent_chain><item><author>celeritascelery</author><text>I see this common theme among very fast practical algorithms (like timsort or pdqsort) where there is not some secret math or algorithm, rather they are just a bunch of special cases based on heuristics. Often they involve specific knowledge of the hardware instead of treating software as abstract. To me this is the big difference between “computer science” and “computer engineering”.</text></item></parent_chain><comment><author>voberoi</author><text>I had the same takeaway when I read these papers. It felt like a game of whack-a-mole.&lt;p&gt;There&amp;#x27;s a massive performance benefit to doing this at the cost of implementation complexity. I haven&amp;#x27;t studied the implementations or tried my hand one, but I get the impression that these are tough to implement correctly in a way that takes full advantage of the hardware.&lt;p&gt;(In that sense, it&amp;#x27;s awesome that the researchers also did the legwork to implement and maintain a library!)</text></comment>