Improve BitwiseHamming distance computation in NN Descent
Open
@jinsolp is already working on this.
Since Jul 16, 2025.
improvement
- Dominant language
- Cuda
- Stars
- 854
- Forks
- 236
- Avg merge
- 3d 3h
- Merged PRs (30d)
- 62
Description
InnerProduct in NN Descent is calculated by reinterpret_cast<const uint8_t*> the fp16 data pointer.
Then, based on the data_dim of the int8/uint8 data it calculates the distance like below;
// data_n1 and data_n2 are uint8_t*
for (int d = 0; d < data_dim; d++) {
s_distances[i] += __popc(static_cast<uint32_t>(data_n1[d] ^ data_n2[d]) & 0xff);
}
This can be improved by checking for the divisibility of data_dim. If data is divisible by 2, we can do something like this
Then, based on the data_dim of the int8/uint8 data it calculates the distance like below;
// data_n1 and data_n2 are half*. Say data_dim %2 == 0
for (int d = 0; d < data_dim/2; d++) {
s_distances[i] += __popc(static_cast<uint32_t>(data_n1[d] ^ data_n2[d]) & 0xffff);
}
can do the same for when data_dim%4 == 0
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.