141–150 of 175 posts
Earlier quoted context omitted.
This is a drop-in improvement for essentially any binary search over 16-bit integer members.
With "practically benefit" I meant a speedup that is noticable. Is there any software that is significantly bottlenecked by the speed of sorted search?
Earlier quoted context omitted.
Binary searching a sorted array is isomorphic to a sorted binary tree with implicit child pointers. It seems to me like there should be a sort order that stores the items as a fully-dense left-shifted binary tree from top-to-bottom (e.g. like the implicit heap in an in-place heap sort, but a binary search tree instead of a hea). Is there a name for this? Does it show any performance wins in practice?
There's Eytzinger order: https://algorithmica.org/en/eytzinger
See also https://arxiv.org/abs/1509.05053
Earlier quoted context omitted.
> I really can't stand the c-style naming conventions. Honestly I don't see much difference between upb_MiniTable_FindFieldByNumber and upb::MiniTable::FindFieldByNumber
Those are fairly indistinguishable. It's when they start removing letters from words to save... debug symbol bytes or something? That's when c-style naming annoys me.
Earlier quoted context omitted.
With "practically benefit" I meant a speedup that is noticable. Is there any software that is significantly bottlenecked by the speed of sorted search?
I think it's possible to come up with a situation where you want to do a sorted search per every pixel in the screen, for every frame.
Will I get a job if i say i can beat binary search?
[0] A nonsense thing to ask people to implement in an interview
Earlier quoted context omitted.
> I really can't stand the c-style naming conventions. Honestly I don't see much difference between upb_MiniTable_FindFieldByNumber and upb::MiniTable::FindFieldByNumber
Those are fairly indistinguishable. It's when they start removing letters from words to save... debug symbol bytes or something? That's when c-style naming annoys me.
npm -g i package-name
Earlier quoted context omitted.
It's not about doing more or less work; it's about doing the work faster . For instance, it's relatively common to discover that some recomputation can be faster than caching or lookup tables. Similarly, fetching more from memory also can be faster if it means you make less roundtrips.
Well that's where I thought this link was going to go before it went down the simd path... We have a way to beat binary search, it is called b-trees, it has the same basic insight that you can easily take 64 elements from your data set evenly spaced, compare against all of those rapidly, and instead of bifurcating your search space once, you do the same as six times, but because you store the 64 elements in an array…
I did little experiments with search in small arrays (16-32 items) and binary search is one of the worst methods because it requires lot of branches. The fastest method for small arrays was linear branchless search (you walk over all elements without breaking out of the loop. For example, if you want to know whether the array contains a number, you logically OR the checks for all items). I didn't use SIMD though, but…
If you are storing 16-bit integers, wouldn't an 8kB bitmap be even faster?
The library the author is talking about selects between bitmap and array dynamically depending on density. https://roaringbitmap.org/