Numeric.QuoteQuot

Quote integer division (quot) by a compile-time known divisor, which generates source code, employing arithmetic and bitwise operations only. This is usually 2.5x-3.5x faster than using normal quot.

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -ddump-splices -ddump-simpl -dsuppress-all #-}
module Example where
import Numeric.QuoteQuot

-- Equivalent to (`quot` 10).
quot10 :: Word -> Word
quot10 = $$(quoteQuot 10)

>>> quot10 12312

Here -ddump-splices demonstrates the chosen implementation for division by 10:

Splicing expression quoteQuot 10 ======>
((`shiftR` 3) . ((\ (W# w_a9N4) ->
  let !(# hi_a9N5, _ #) = (timesWord2# w_a9N4) 14757395258967641293##
  in W# hi_a9N5) . id))

And -ddump-simpl demonstrates generated Core:

quot10 = \ x_a5t2 ->
  case x_a5t2 of { W# w_acHY ->
  case timesWord2# w_acHY 14757395258967641293## of
  { (# hi_acIg, ds_dcIs #) ->
  W# (uncheckedShiftRL# hi_acIg 3#)
  }
  }

Benchmarks show that this implementation is 3.5x faster than (`quot` 10).

Similar to quoteQuot, but for rem.

Similar to quoteQuot, but for quotRem.

astQuot d constructs an AST representing a function, equivalent to quot a for positive a, but avoiding division instructions.

>>> astQuot (10 :: Data.Word.Word8)Shr (MulHi Arg 205) 3

And indeed to divide Word8 by 10 one can multiply it by 205, take the high byte and shift it right by 3. Somewhat counterintuitively, this sequence of operations is faster than a single division on most modern achitectures.

astQuot function is polymorphic and supports both signed and unsigned operands of arbitrary finite bitness. Implementation is based on Ch. 10 of Hacker's Delight by Henry S. Warren, 2012.

An abstract syntax tree to represent a function of one argument.

Reference (but slow) interpreter of AST. It is not meant to be used in production and is provided primarily for testing purposes.

>>> interpretAST (astQuot (10 :: Data.Word.Word8)) 12312

Embed AST into Haskell expression.

Optimize AST, assuming that Arg is non-negative.

Types allowing to multiply wide and return the high word of result.