Specialize Numeric.showHex/Bin for Word types

[yaitskov]

Hi,

showHex is defined for Integrals and checks the argument for negative.
For unsigned types (e.g. Word), this check is not needed, but retained and executed.

module Foo where

f :: forall a. (Integral a) => a -> a
f x | x < 0 = 0
    | otherwise = x

fs :: forall a. (Integral a) => a -> a
fs x | x < 0 = 0
     | otherwise = x
{-# NOINLINE fs #-}

fw :: Word -> Word
fw x = x

g :: Word -> Word
g x | x < 0 = 0
    | otherwise = x

fff :: Word -> Word
fff x = x

{-# RULES "f-for-word" fs = fw #-}


module Main where

import Criterion.Main
import Foo
import Numeric

main :: IO ()
main =
  defaultMain
  [
    bgroup "g"
    [
      bench "showHex 1 :: Int" $ whnf showHex (1 :: Int),
      bench "showHex 1 :: Word" $ whnf showHex (1 :: Word),

      bench "fs 1 :: Word" $ whnf fs (1 :: Word),
      bench "f  1 :: Word" $ whnf f (1 :: Word),
      bench "g  1 :: Word" $ whnf g 1,

      bench "fs 1 :: Int" $ whnf fs (1 :: Int),
      bench "f  1 :: Int" $ whnf f (1 :: Int)
    ]
  ]

GHC 9.2.4
ghc-options: -O2 -Wall -threaded -rtsopts

benchmarking g/showHex 1 :: Int
time 14.10 ns (13.91 ns .. 14.33 ns)
0.999 R² (0.998 R² .. 0.999 R²)
mean 14.19 ns (14.03 ns .. 14.38 ns)
std dev 604.2 ps (487.6 ps .. 745.5 ps)
variance introduced by outliers: 67% (severely inflated)

benchmarking g/showHex 1 :: Word
time 14.02 ns (13.88 ns .. 14.20 ns)
0.999 R² (0.998 R² .. 1.000 R²)
mean 14.19 ns (14.06 ns .. 14.41 ns)
std dev 528.0 ps (394.8 ps .. 767.3 ps)
variance introduced by outliers: 60% (severely inflated)

showHex for Int and Word takes same time

benchmarking g/fs 1 :: Word
time 6.494 ns (6.414 ns .. 6.583 ns)
0.999 R² (0.998 R² .. 0.999 R²)
mean 6.480 ns (6.426 ns .. 6.551 ns)
std dev 214.2 ps (159.8 ps .. 296.9 ps)
variance introduced by outliers: 56% (severely inflated)

benchmarking g/f 1 :: Word
time 16.00 ns (15.86 ns .. 16.21 ns)
0.999 R² (0.999 R² .. 1.000 R²)
mean 15.92 ns (15.83 ns .. 16.10 ns)
std dev 415.2 ps (231.2 ps .. 716.8 ps)
variance introduced by outliers: 42% (moderately inflated)

Specializing f makes difference

benchmarking g/g 1 :: Word
time 6.552 ns (6.503 ns .. 6.618 ns)
0.999 R² (0.999 R² .. 1.000 R²)
mean 6.576 ns (6.529 ns .. 6.677 ns)
std dev 213.4 ps (141.9 ps .. 340.8 ps)
variance introduced by outliers: 55% (severely inflated)

benchmarking g/fs 1 :: Int
time 16.36 ns (16.16 ns .. 16.68 ns)
0.999 R² (0.998 R² .. 1.000 R²)
mean 16.64 ns (16.39 ns .. 16.96 ns)
std dev 980.1 ps (726.4 ps .. 1.233 ns)
variance introduced by outliers: 79% (severely inflated)

benchmarking g/f 1 :: Int
time 16.51 ns (16.37 ns .. 16.64 ns)
0.999 R² (0.999 R² .. 1.000 R²)
mean 16.45 ns (16.35 ns .. 16.64 ns)
std dev 433.8 ps (224.3 ps .. 705.8 ps)
variance introduced by outliers: 43% (moderately inflated)

[Bodigrim]

Given that showHex :: Integral a => a -> (String -> String) generates a function operating on strings, does the sign check really matters? I guess it is reasonable to throw {-# INLINABLE showHex #-} anyway, but you are not supposed to use this function anywhere near performance bottlenecks.

I don't follow your benchmarks, why are you using whnf instead of nf? Why are you comparing showHex to essentially id?

[yaitskov]

With benchmark I wanted to show that the check is retained. Formally it is redundant operation.
Advocating to the practical side - I question the existence of this check for signed types, because what does it protects from? showHex is used to see bits. If signed right shift loops on negatives then unsigned right shift doesn't.

I was using Int originally, deriving the type from Data.Char.ord result value.

I stuck a bit with the showHex constrain during debugging - it is hard to decode bits from negative numbers in decimal base in failed assertions and after some time I figured out a casting hack (fromIntegral $ ord 'x') :: Word.

That's why I am biased about the check.

I think inlining might not help if calling place doesn't know type and have same Integral constrain, right?

[yaitskov]

I lost second argument of showHex in benchmark.

Following specialization works with negative Ints and 3.5 faster

showHexWord64 :: Word64 -> String -> String
showHexWord64 w suf =
  case countLeadingZeros w .&. complement 3 of
    0 -> w0
    4 -> w4
    8 -> w8
    12 -> w12
    16 -> w16
    20 -> w20
    24 -> w24
    28 -> w28
    32 -> w32
    36 -> w36
    40 -> w40
    44 -> w44
    48 -> w48
    52 -> w52
    56 -> w56
    60 -> chr w : suf
    64 -> '0' : suf
    o -> error $ "unexpected " <> show o <> " from countLeadingZeros " <> show w
  where
    chr = intToDigit . fromIntegral

    w56 = chr (w `shiftR` 4 .&. 0xf) : chr (w .&. 0xf) : suf
    w52 = chr (w `shiftR` 8 .&. 0xf) : w56
    w48 = chr (w `shiftR` 12 .&. 0xf) : w52
    w44 = chr (w `shiftR` 16 .&. 0xf) : w48
    w40 = chr (w `shiftR` 20 .&. 0xf) : w44
    w36 = chr (w `shiftR` 24 .&. 0xf) : w40
    w32 = chr (w `shiftR` 28 .&. 0xf) : w36
    w28 = chr (w `shiftR` 32 .&. 0xf) : w32
    w24 = chr (w `shiftR` 36 .&. 0xf) : w28
    w20 = chr (w `shiftR` 40 .&. 0xf) : w24
    w16 = chr (w `shiftR` 44 .&. 0xf) : w20
    w12 = chr (w `shiftR` 48 .&. 0xf) : w16
    w8 = chr (w `shiftR` 52 .&. 0xf) : w12
    w4 = chr (w `shiftR` 56 .&. 0xf) : w8
    w0 = chr (w `shiftR` 60 .&. 0xf) : w4

showHexInt64 :: Int64 -> String -> String
showHexInt64 w = showHexWord64 (fromIntegral w)

benchmarking g/showHexWord64
time 111.1 ns (109.8 ns .. 112.5 ns)
0.999 R² (0.999 R² .. 0.999 R²)
mean 111.5 ns (110.4 ns .. 113.1 ns)
std dev 4.246 ns (3.227 ns .. 5.888 ns)
variance introduced by outliers: 58% (severely inflated)

benchmarking g/showHexInt64
time 110.7 ns (109.5 ns .. 112.0 ns)
0.999 R² (0.998 R² .. 0.999 R²)
mean 110.6 ns (109.1 ns .. 112.1 ns)
std dev 4.892 ns (3.717 ns .. 6.820 ns)
variance introduced by outliers: 65% (severely inflated)

benchmarking g/showHex :: Word64
time 586.2 ns (574.2 ns .. 599.5 ns)
0.998 R² (0.997 R² .. 0.998 R²)
mean 581.2 ns (573.1 ns .. 590.5 ns)
std dev 27.91 ns (24.32 ns .. 34.39 ns)
variance introduced by outliers: 66% (severely inflated)

benchmarking g/showHex :: Intd64
time 565.0 ns (556.0 ns .. 574.8 ns)
0.998 R² (0.997 R² .. 0.999 R²)
mean 561.8 ns (555.1 ns .. 571.0 ns)
std dev 26.08 ns (19.86 ns .. 37.33 ns)
variance introduced by outliers: 64% (severely inflated)

showHex for Integer has O(n^2)

[Bodigrim]

@yaitskov could you please raise a specific MR you'd like to champion?

[Bodigrim]

@yaitskov if there is no progress on this proposal within two weeks, I'll close it as abandoned.

[Bodigrim]

Closing as abandoned.