1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
# quote-quot [](https://hackage.haskell.org/package/quote-quot) [](http://stackage.org/lts/package/quote-quot) [](http://stackage.org/nightly/package/quote-quot)
Generate routines for integer division, employing arithmetic
and bitwise operations only, which are __2.5x-3.5x faster__
than `quot`. Divisors must be known
in compile-time and be positive.
```haskell
{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -ddump-splices -ddump-simpl -dsuppress-all #-}
import Numeric.QuoteQuot
-- Equivalent to (`quot` 10).
quot10 :: Word -> Word
quot10 = $$(quoteQuot 10)
```
```haskell
>>> quot10 123
12
```
Here `-ddump-splices` demonstrates the chosen implementation
for division by 10:
```haskell
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:
```haskell
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)``:
```haskell
{-# LANGUAGE TemplateHaskell #-}
import Data.List
import Numeric.QuoteQuot
import System.CPUTime
measure :: String -> (Word -> Word) -> IO ()
measure name f = do
t0 <- getCPUTime
print $ foldl' (+) 0 $ map f [0..100000000]
t1 <- getCPUTime
putStrLn $ name ++ " " ++ show ((t1 - t0) `quot` 1000000000) ++ " ms"
{-# INLINE measure #-}
main :: IO ()
main = do
measure " (`quot` 10)" (`quot` 10)
measure "$$(quoteQuot 10)" $$(quoteQuot 10)
```
```
499999960000000
(`quot` 10) 316 ms
499999960000000
$$(quoteQuot 10) 89 ms
```
Conventional wisdom is that such microoptimizations are negligible in practice,
but this is not always the case. For instance, quite surprisingly,
this trick alone
[made Unicode normalization of Hangul characters twice faster](https://github.com/composewell/unicode-transforms/pull/42)
in [`unicode-transforms`](http://hackage.haskell.org/package/unicode-transforms).
|
