5 ms·

As someone not familiar with hardware at this level, what is the significance of leaving out popcount?

by cpach 6y ago

Const-me 6y ago
Some algorithms and data formats become couple times faster when appropriate bit manipulation instructions are used. Check this PR where I managed to substantially speed up an open source library: https://github.com/AcademySoftwareFoundation/openvdb/pull/493 https://github.com/AcademySoftwareFoundation/openvdb/pull/49... That's just 3 instructions, bsr, bsf, and popcnt.
- cpach 6y ago
  Cool! Quite interesting discussion in the PR.
- ncmncm 6y ago
  40% overall performance improvements are often welcomed.
  - Const-me 6y ago
    That OpenVDB data structure is a sparse hierarchical collection with a huge count of small 3D blocks of voxels. They use bit masks in the blocks to track which voxels are empty, and which contain the payload data or higher resolution child blocks. That’s why these bit manipulation instructions contributed that much to the overall performance of the library. I saw similar approach in other software as well. Not necessarily for voxels, also 2D data, and trees where nodes use bits to track children.
    - ncmncm 6y ago
      Bitmap representations are seriously underused throughout the software world. I am used to getting 10x performance improvements where they are first introduced. A popcount instruction often accounts for much of that.
yourapostasy 6y ago
Discussion of uses of POPCOUNT instruction. https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/
- ncmncm 6y ago
  I sent him this: It does, however, omit several imporant uses for the operation. Perhaps the most important of these is the integer log-base-2 operation. The popcount instruction follows a bitwise operation to transform the input from the form 0..01x..x into 0..011..1. Often these operations are merged into another instruction, "count leading zeroes". We also find "count leading ones", "count trailing ones", "count trailing zeroes", all relying on the same hardware implementation. Most often the result of one of these operations is used as a shift count, or to provision storage for a corresponding number of larger objects. The importance of the instruction in accelerating algorithms arises from its very slow loopwise implementation, so a software emulation is often worse than useless.

As someone not familiar with hardware at this level, what is the significance of leaving out popcount?

by cpach 6y ago

As someone not familiar with hardware at this level, what is the significance of leaving out popcount?

Some algorithms and data formats become couple times faster when appropriate bit manipulation instructions are used. Check this PR where I managed to substantially speed up an open source library: https://github.com/AcademySoftwareFoundation/openvdb/pull/493 https://github.com/AcademySoftwareFoundation/openvdb/pull/49... That's just 3 instructions, bsr, bsf, and popcnt.

cpach 6y ago
Cool! Quite interesting discussion in the PR.
ncmncm 6y ago
40% overall performance improvements are often welcomed.
- Const-me 6y ago
  That OpenVDB data structure is a sparse hierarchical collection with a huge count of small 3D blocks of voxels. They use bit masks in the blocks to track which voxels are empty, and which contain the payload data or higher resolution child blocks. That’s why these bit manipulation instructions contributed that much to the overall performance of the library. I saw similar approach in other software as well. Not necessarily for voxels, also 2D data, and trees where nodes use bits to track children.
  - ncmncm 6y ago
    Bitmap representations are seriously underused throughout the software world. I am used to getting 10x performance improvements where they are first introduced. A popcount instruction often accounts for much of that.

yourapostasy 6y ago

Discussion of uses of POPCOUNT instruction. https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/

ncmncm 6y ago
I sent him this: It does, however, omit several imporant uses for the operation. Perhaps the most important of these is the integer log-base-2 operation. The popcount instruction follows a bitwise operation to transform the input from the form 0..01x..x into 0..011..1. Often these operations are merged into another instruction, "count leading zeroes". We also find "count leading ones", "count trailing ones", "count trailing zeroes", all relying on the same hardware implementation. Most often the result of one of these operations is used as a shift count, or to provision storage for a corresponding number of larger objects. The importance of the instruction in accelerating algorithms arises from its very slow loopwise implementation, so a software emulation is often worse than useless.