Bit manipulation built-ins

[uzytkownik]

So far Haskell/GHC lacks more HL bit manipulation instructions which on many platform can be compiled to single instruction. Probably the good guide are those implemented in LLVM:

• byte swap
• population count
• number of leading zeros
• number of trailing zeros

All of them can be implemented in terms of Data.Bits - however not quite in efficient way (like looping over patterns).

[gwicke]

I have created preliminary bindings to GCC's built-in bit operations and exposed them in a separate typeclass. The current code is browsable at  http://hg.wikidev.net:8000/trie/file/tip/BitsX/ (see Data/Bits/Extras.hs for the typeclass and instances), but not yet in its own repository or on hackage.

The C code in package can obviously only be compiled with GCC. The external calls introduce some overheads and a dependency on libgcc_s, which can cause issues with GHCi as its built-in linker does not handle sonames properly.

A faster, more general and robust solution would probably involve the introduction of new primops.

The same package currently also bundles a module with atomic bit operations on memory locations (Data.Bits.Atomic), which should probably be split out to a separate package.

Feedback on the code and suggestions for better locations in the module hierarchy would be appreciated. I plan to publish this on hackage once good locations are found.

[uzytkownik]

Replying to gwicke:

I have created preliminary bindings to GCC's built-in bit operations and exposed them in a separate typeclass. The current code is browsable at  http://hg.wikidev.net:8000/trie/file/tip/BitsX/ (see Data/Bits/Extras.hs for the typeclass and instances), but not yet in its own repository or on hackage. (...) A faster, more general and robust solution would probably involve the introduction of new primops. Feedback on the code and suggestions for better locations in the module hierarchy would be appreciated. I plan to publish this on hackage once good locations are found.

I would strongly suggest Data.Bits for the following reasons:

• All of them can be implemented in terms of the Data.Bits primitives. It is simply an extention for specialization.
• They should be handled in-line by compiler as for many architectures they can be optimized to single instruction. LLVM inline shoul handle it perfectly.

[gwicke]

Replying to uzytkownik:

I would strongly suggest Data.Bits for the following reasons: - All of them can be implemented in terms of the Data.Bits primitives. It is simply an extention for specialization. - They should be handled in-line by compiler as for many architectures they can be optimized to single instruction. LLVM inline shoul handle it perfectly.

Is it possible to do this optimization without requiring new primops and have it work across GHC backends? Could this be implemented using rules?

My package is just a stop-gap measure to get access to native instructions, so I do not think this code would be suitable for Data.Bits. Maybe- if there is a way to use e.g. CPP to select the implementation by backend- some of this code could be used in the -fvia-C or -fasm implementations.

[gwicke]

I have moved the code to a separate repository now, you can retrieve it with mercurial using:

hg clone  http://dev.wikidev.net/hg/bits-extras/

Tar/Zip etc download is also available at this url.

[uzytkownik]

Replying to gwicke:

Replying to uzytkownik:

I would strongly suggest Data.Bits for the following reasons: - All of them can be implemented in terms of the Data.Bits primitives. It is simply an extention for specialization. - They should be handled in-line by compiler as for many architectures they can be optimized to single instruction. LLVM inline shoul handle it perfectly.

Is it possible to do this optimization without requiring new primops and have it work across GHC backends? Could this be implemented using rules?

Well. Yes as long as rules would allow LLVM assambly or GHC would perform link-time LLVM optimalization for FFI.

One could easily extend Data.Bits and provide default implementations (it would break nothing). However GHC can provide (possibly it would require small work for each backend) it's own implementations - (.&.) is not implemented for Int/Int8/16/32/64 etc. anyway.

My package is just a stop-gap measure to get access to native instructions, so I do not think this code would be suitable for Data.Bits. Maybe- if there is a way to use e.g. CPP to select the implementation by backend- some of this code could be used in the -fvia-C or -fasm implementations.

I fully understend. However I belive that putting it outside Data.Bits would:

• Make little sense as they are bits operation. Just more optimized version of code
• Make harder for custom types to optimize them

I would really like to see them 'native' - however your package is great when they are not native.

[tibbe]

Bit population count added in #5413