diff options
Diffstat (limited to 'implementation/primitive')
| -rw-r--r-- | implementation/primitive/sort.md | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/implementation/primitive/sort.md b/implementation/primitive/sort.md index 5a0690eb..cd6f470e 100644 --- a/implementation/primitive/sort.md +++ b/implementation/primitive/sort.md @@ -56,7 +56,7 @@ For binary search `𝕨⍋𝕩`, partitioning allows one pivot element `t` from Reminder that we're talking about simple, not [compound](#compound-data) data. The most important thing is just to have a good branchless binary search (see [above](#on-binary-search)), but there are other possible optimizations. -If `𝕨` is extremely small, use a vector binary search as described in "Sub-nanosecond Searches" ([video](https://dyalog.tv/Dyalog18/?v=paxIkKBzqBU), [slides](https://www.dyalog.com/user-meetings/uploads/conference/dyalog18/presentations/D15_The_Interpretive_Advantage.zip)). For 1-byte elements there's also a vectorized method that works whenever `𝕨` has no duplicates: create two lookup tables that go from multiples of 8 (5-bit values, after shifting) to bytes. One is a bitmask of `𝕨`, so that a lookup gives 8 bits indicating which possible choices of the remaining 3 bits are in `𝕨`. The other gives the number of values in `𝕨` less than the multiple of 8. To find the result of Bins, look up these two bytes. Mask off the bitmask to include only bits for values less than the target, and sum it (each of these steps can be done with another lookup, or other methods depending on instruction set). The result is the sum of these two counts. +If `𝕨` is extremely small, use a vector binary search as described in "Sub-nanosecond Searches" ([video](https://dyalog.tv/Dyalog18/?v=paxIkKBzqBU), [slides](https://www.dyalog.com/user-meetings/uploads/conference/dyalog18/presentations/D08_Searches_Using_Vector_Instructions.zip)). For 1-byte elements there's also a vectorized method that works whenever `𝕨` has no duplicates: create two lookup tables that go from multiples of 8 (5-bit values, after shifting) to bytes. One is a bitmask of `𝕨`, so that a lookup gives 8 bits indicating which possible choices of the remaining 3 bits are in `𝕨`. The other gives the number of values in `𝕨` less than the multiple of 8. To find the result of Bins, look up these two bytes. Mask off the bitmask to include only bits for values less than the target, and sum it (each of these steps can be done with another lookup, or other methods depending on instruction set). The result is the sum of these two counts. It's cheap and sometimes worthwhile to trim `𝕨` down to the range of `𝕩`. After finding the range of `𝕩`, binary cut `𝕨` to a smaller list that contains the range. Stop when the middle element fits inside the range, and search each half of `𝕨` for the appropriate endpoint of the range. |