Additional `Word` operations

[Skyb0rg007]

Description

Many algorithms require fast implementations of binary operations. For example, Haskell's implementation of big-endian patricia trees (Data.IntMap) uses countLeadingZeros internally.

Because SML/NJ has two different word sizes (31 for 32-bit, 63 for 64-bit), it is very useful to provide optimal implementations specialized to the particular system. Additionally, exposing these operations allows them to be implemented even more efficiently through the future LLVM backend.

popCount, countLeadingZeros, and countTrailingZeros all have clear uses. log2 could be a useful variant of countLeadingZeros which mirrors the function available to IntInf. While I do not currently know any use for rotl or rotr, MLton provides these functions as primitives, and they would be good to add for compatibility's sake.

MLton does also provide bswap : word -> word, which swaps bytes in the word. This does not seem easy to implement in the WORD signature, since 63-bit words don't have an obvious notion of byte swapping. Perhaps this could be considered for Word32 and Word64, or as an addition to Unsafe.Word32 or Unsafe.Word64 if a use-case is found.

signature WORD_EXTRAS =
sig
  type word
  (* Number of set bits in the input. Already implemented in SML/NJ. *)
  val popCount : word -> int

  (* Count number of zero bits preceding the most significant set bit. *)
  val countLeadingZeros : word -> int

  (* Count number of zero bits following the least significant set bit. *)
  val countTrailingZeros : word -> int

  (* The log base 2 of the input
     log2 w = Word.fromInt wordSize - 1 - countLeadingZeros w *)
  val log2 : word -> int

  (* Rotate the input to the left or right by the specified amount.
     rotl (w, s) = (w << s) orb (w >> (wordSize - s))
     rotr (w, s) = (w >> s) orb (w << (wordSize - s)) *)
  val rotl : word * Word.word -> word
  val rotr : word * Word.word -> word
end

[MatthewFluet]

Related to https://github.com/SMLFamily/BasisLibrary/wiki/2016-001-Add-popCount-to-WORD-signature.

[dmacqueen]

Is “popCount” a traditional name for this function? If not, wouldn’t something like “countSetBits” be a better, more descriptive name?

Dave

On Mar 22, 2024, at 12:51 PM, Skye Soss @.***> wrote:

Description

Many algorithms require fast implementations of binary operations. For example, Haskell's implementation of big-endian patricia trees (Data.IntMap https://hackage.haskell.org/package/containers-0.6.7/docs/Data-IntMap.html) uses countLeadingZeros internally.

Because SML/NJ has two different word sizes (31 for 32-bit, 63 for 64-bit), it is very useful to provide optimal implementations specialized to the particular system. Additionally, exposing these operations allows them to be implemented even more efficiently through the future LLVM backend.

popCount, countLeadingZeros, and countTrailingZeros all have clear uses. log2 could be a useful variant of countLeadingZeros which mirrors the function available to IntInf. While I do not currently know any use for rotl or rotr, MLton provides these functions as primitives, and they would be good to add for compatibility's sake.

MLton does also provide bswap : word -> word, which swaps bytes in the word. This does not seem easy to implement in the WORD signature, since 63-bit words don't have an obvious notion of byte swapping. Perhaps this could be considered for Word32 and Word64, or as an addition to Unsafe.Word32 or Unsafe.Word64 if a use-case is found.

signature WORD_EXTRAS = sig type word (* Number of set bits in the input. Already implemented in SML/NJ. *) val popCount : word -> int

(* Count number of zero bits preceding the most significant set bit. *) val countLeadingZeros : word -> int

(* Count number of zero bits following the least significant set bit. *) val countTrailingZeros : word -> int

(* The log base 2 of the input log2 w = Word.fromInt wordSize - 1 - countLeadingZeros w *) val log2 : word -> int

(* Rotate the input to the left or right by the specified amount. rotl (w, s) = (w << s) orb (w >> (wordSize - s)) rotr (w, s) = (w >> s) orb (w << (wordSize - s)) *) val rotl : word * Word.word -> word val rotr : word * Word.word -> word end — Reply to this email directly, view it on GitHub https://github.com/smlnj/legacy/issues/307, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAGXNPKW6ZAZFSRQ74YOS3DYZSDU5AVCNFSM6AAAAABFD4XSPWVHI2DSMVQWIX3LMV43ASLTON2WKOZSGIYDGMRQG43DQNA. You are receiving this because you are subscribed to this thread.

David MacQueen @.***

[JohnReppy]

popCount is a traditional name for the operation. As Matthew noted, I proposed it back in 2016 and added it to the SML/NJ Basis Library implementation around the same time.

[Skyb0rg007]

Here's a chart with some details about the choices that other languages make around naming. After looking through these, there are two other common bitwise operators: reverseBits : word -> word and reverseBytes : word -> word. Though I have even less idea where those are used.

Language	Name for Hamming weight	SML Equivalent Type
LLVM	llvm.cntpop.*	word -> word
C++	popcount	word -> Int.int
C23	count_ones	word -> Int.int
Java	bitCount	word -> Int.int
C#	PopCount	word -> word
Python	bit_count	N/A
Go	OnesCount	word -> Int.int
MySQL	BIT_COUNT	word -> word
Haskell	popCount	word -> Int.int
Rust	count_ones	word -> Word.word

Language	Name for counting leading/trailing zeros	SML Equivalent Type
LLVM	llvm.cntlz.*, llvm.cnttz.*	word -> word
C++	countl_zero, countl_one, countr_zero, countr_one	word -> Int.int
C23	leading_zeros, leading_ones, trailing_zeros, trailing_ones	word -> Int.int
Java	numberOfLeadingZeros, numberOfTrailingZeros	word -> int
C#	LeadingZeroCount, TrailingZeroCount	word -> word
Go	LeadingZeros, TrailingZeros	word -> int
Haskell	countLeadingZeros, countTrailingZeros	word -> Int.int
Rust	leading_zeros, leading_ones, trailing_zeros, trailing_ones	word -> Word.word

Language	Name for circular shift	Notes
LLVM	llvm.fshl.*, llvm.fshr.*	The funnel shift, which is more general
C++	rotl, rotr
C23	rotate_left, rotate_right
Java	rotateLeft, rotateRight
C#	RotateLeft, RotateRight
Go	RotateLeft, RotateRight
Haskell	rotateL, rotateR	Also implements generic rotate
Rust	rotate_left, rotate_right
MLton	rol, ror

[Skyb0rg007]

I have an implementation of these operations for SML/NJ here, which has specialized implementations for 8,32,63,64 bit words, a generic reference implementation, and a test-suite. I can submit this to the SMLBasisLibrary too if that would be useful though it hasn't been updated in more than a year.

[JohnReppy]

I think that the natural place for this proposal is the SML Basis Library Wiki. As noted before, popCount has already been proposed as an extension to the Basis Library (and implemented in SML/NJ).

With respect to naming conventions, we have previously used the "l" and "r" suffixes to indicate direction in most cases (e.g., foldl/foldr), so I think that we ought to follow that convention for the rotate operations. Either rotatel/rotater or the shorter rotl/rotr. Or just follow the precedent set by MLton and use rol/ror.

Another operation that I recently used when implementing big-endian Patricia trees is highestBitSet (I don't know what the standard name for this operation is). Its signature is

val highestBitSet : word -> word

and it returns a word with one bit set that corresponds to the highest set bit in its argument (0w0 if the argument is 0w0). It has the following bit twiddling implementation (from Hacker's Delight) for 63 and 64-bit words:

fun highestBitSet w = let
      (* each step doubles the number of high bits set;
       * e.g., 0b1000 ==> 0b1100 ==> 0b1111.
       *)
      val w = Word.orb(w, Word.>>(w, 0w1))
      val w = Word.orb(w, Word.>>(w, 0w2))
      val w = Word.orb(w, Word.>>(w, 0w4))
      val w = Word.orb(w, Word.>>(w, 0w8))
      val w = Word.orb(w, Word.>>(w, 0w16))
      val w = Word.orb(w, Word.>>(w, 0w32))
      in
        (* `w` is all ones from the highest bit down, so we mask out the low bits by a shift and xor. *)
        Word.xorb(w, Word.>>(w, 0w1))
      end

If you have hardware support for nlz (# leading zeros), then you can accelerate the implementation.

[Skyb0rg007]

I don't believe that operation has a name: searching stack overflow only gives one result (this one), and it doesn't appear on the Bit Twiddling Hacks page either.

This would be the implementation with the proposed additions:

fun highestBitSet w = Word.<< (0w1, Word.fromInt (Word.wordSize - 1 - Word.leadingZeros w))

Unfortunately, if you don't have hardware support for nlz nor popcnt then you are doing extra work this way (by performing a popCount instead of an xorb).

[Skyb0rg007]

My appologies: the operation is named and implemented in Java as highestOneBit : int -> int (link).

[JohnReppy]

This proposal should be moved to the SML Basis Library wiki, so I am closing it here.