Opened 5 years ago

Last modified 6 months ago

#4102 new feature request

Bit manipulation built-ins

Reported by: uzytkownik Owned by: ekmett
Priority: normal Milestone: 7.12.1
Component: Core Libraries Version: 6.12.2
Keywords: Cc: josefs@…, gabriel@…, dterei, rrnewton@…, wren@…, johan.tibell@…, mle+hs@…, dfeuer, hvr, ekmett
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

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).

Change History (20)

comment:1 Changed 5 years ago by igloo

  • Milestone set to 6.16.1

comment:2 Changed 5 years ago by josef

  • Cc josefs@… added

comment:3 Changed 5 years ago by gwicke

  • Cc gabriel@… added

comment:4 follow-up: Changed 5 years ago by 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.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by 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.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 5 years ago by 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.

comment:7 Changed 5 years ago by 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.

comment:8 in reply to: ↑ 6 Changed 5 years ago by 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.

comment:9 Changed 4 years ago by dterei

  • Cc dterei added

comment:10 Changed 4 years ago by rrnewton

  • Cc rrnewton@… added

comment:11 Changed 4 years ago by WrenThornton

  • Cc wren@… added

comment:12 Changed 4 years ago by tibbe

  • Cc johan.tibell@… added

comment:13 Changed 4 years ago by tibbe

Bit population count added in #5413

comment:14 Changed 3 years ago by igloo

  • Milestone changed from 7.4.1 to 7.6.1

comment:15 Changed 3 years ago by igloo

  • Milestone changed from 7.6.1 to 7.6.2

comment:16 Changed 16 months ago by erikd

  • Cc mle+hs@… added
  • difficulty set to Unknown

comment:17 Changed 12 months ago by dfeuer

  • Cc dfeuer hvr ekmett added

comment:18 Changed 12 months ago by thoughtpolice

  • Milestone changed from 7.6.2 to 7.10.1

Moving to 7.10.1.

comment:19 Changed 9 months ago by thoughtpolice

  • Component changed from libraries/base to Core Libraries
  • Owner set to ekmett

Moving over to new owning component 'Core Libraries'.

comment:20 Changed 6 months ago by thoughtpolice

  • Milestone changed from 7.10.1 to 7.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

Note: See TracTickets for help on using tickets.