Beautiful Branchless Binary Search
https://probablydance.com/2023/04/27/beautiful-branchless-binary-search/ [probablydance.com]
2023-04-28 23:45
tags:
compsci
cxx
programming
I read a blog post by Alex Muscar, “Beautiful Binary Search in D“. It describes a binary search called “Shar’s algorithm”. I’d never heard of it and it’s impossible to google, but looking at the algorithm I couldn’t help but think “this is branchless.” And who knew that there could be a branchless binary search? So I did the work to translate it into a algorithm for C++ iterators, no longer requiring one-based indexing or fixed-size arrays.
https://muscar.eu/shar-binary-search-meta.html
source: L
On Modern Hardware the Min-Max Heap beats a Binary Heap
https://probablydance.com/2020/08/31/on-modern-hardware-the-min-max-heap-beats-a-binary-heap/ [probablydance.com]
2020-09-02 23:22
tags:
compsci
perf
programming
The heap is a data structure that I use all the time and that others somehow use rarely. (I once had a coworker tell me that he knew some code was mine because it used a heap) Recently I was writing code that could really benefit from using a heap (as most code can) but I needed to be able to pop items from both ends. So I read up on double-ended priority queues and how to implement them. These are rare, but the most common implementation is the “Interval Heap” that can be explained quickly, has clean code and is only slightly slower than a binary heap. But there is an alternative called the “Min-Max Heap” that doesn’t have pretty code, but it has shorter dependency chains, which is important on modern hardware. As a result it often ends up faster than a binary heap, even though it allows you to pop from both ends. Which means there might be no reason to ever use a binary heap again.
Code: https://github.com/skarupke/heap/blob/master/minmax_and_dary_heap.hpp
source: HN