commit 1524c556c7339e70ea60f5a484d9bab943ea8ec2
parent a454aa8ee282ac37b8f206e61b6de7557fbd1278
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 25 Jan 2025 13:34:20 +0400
meta: readme
Diffstat:
| M | LICENSE | | | 2 | +- |
| A | README.md | | | 143 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | bench/Main.hs | | | 48 | +++++++++++++++++++++++++++++++++--------------- |
3 files changed, 177 insertions(+), 16 deletions(-)
diff --git a/LICENSE b/LICENSE
@@ -1,4 +1,4 @@
-Copyright (c) 2024 Jared Tobin
+Copyright (c) 2025 Jared Tobin
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
diff --git a/README.md b/README.md
@@ -0,0 +1,143 @@
+# ppad-fixed
+
+A pure implementation of large fixed-width integers and supporting operations.
+
+## Usage
+
+A sample GHCi session:
+
+```
+ > -- import qualified
+ > import Data.Word.Extended as W
+ >
+ > -- use 'to_word256' to convert variable-length integers to Word256
+ > let u = W.to_word256 0xFFFFFFFFFF
+ > :t u
+ u :: W.Word256
+ >
+ > -- compare values
+ > let v = W.to_word256 0xFFFFFF
+ > u `W.lt` v
+ False
+ >
+ > -- bitwise operations
+ > u `W.or` v -- == u
+ 1099511627775
+ > u `W.and` v -- == v
+ 16777215
+ >
+ > -- arithmetic operations
+ > (u `add` v) `sub` (u `add` v)
+ 0
+ > u `mul` u `mul` u `mul` u `mul` u `mul` u `mul` u
+ 115779721307862780478962831313825936498328052285500565196053117862789708251135
+ >
+ > u `div` v
+ 65536
+ >
+ > -- modular reduction
+ > u `mod` v
+ 65535
+```
+
+## Documentation
+
+Haddocks (API documentation, etc.) are hosted at
+[docs.ppad.tech/fixed](https://docs.ppad.tech/fixed).
+
+## Performance
+
+The aim is best-in-class performance for pure, highly-auditable Haskell
+code. Most operations beat out their variable-length Integer variants,
+*but*, we have yet to reach parity with the all-important division and
+modulo operations.
+
+Current benchmark figures on 1kb inputs on my mid-2020 MacBook Air look
+like (use `cabal bench` to run the benchmark suite):
+
+```
+ benchmarking baseline comparison/add (baseline)
+ time 24.60 ns (24.42 ns .. 24.78 ns)
+ 1.000 R² (1.000 R² .. 1.000 R²)
+ mean 24.69 ns (24.56 ns .. 24.81 ns)
+ std dev 438.0 ps (373.9 ps .. 550.6 ps)
+ variance introduced by outliers: 25% (moderately inflated)
+
+ benchmarking baseline comparison/add
+ time 13.72 ns (13.46 ns .. 13.97 ns)
+ 0.998 R² (0.998 R² .. 0.999 R²)
+ mean 13.53 ns (13.39 ns .. 13.70 ns)
+ std dev 513.9 ps (413.5 ps .. 660.9 ps)
+ variance introduced by outliers: 61% (severely inflated)
+
+ benchmarking baseline comparison/sub (baseline)
+ time 31.59 ns (31.34 ns .. 31.93 ns)
+ 0.999 R² (0.998 R² .. 0.999 R²)
+ mean 32.32 ns (31.86 ns .. 33.06 ns)
+ std dev 1.987 ns (1.383 ns .. 2.990 ns)
+ variance introduced by outliers: 80% (severely inflated)
+
+ benchmarking baseline comparison/sub
+ time 12.34 ns (12.16 ns .. 12.53 ns)
+ 0.999 R² (0.998 R² .. 0.999 R²)
+ mean 12.39 ns (12.26 ns .. 12.53 ns)
+ std dev 446.6 ps (366.2 ps .. 547.7 ps)
+ variance introduced by outliers: 59% (severely inflated)
+
+ benchmarking baseline comparison/mul (baseline)
+ time 48.55 ns (47.05 ns .. 51.12 ns)
+ 0.990 R² (0.973 R² .. 0.999 R²)
+ mean 47.76 ns (47.02 ns .. 49.82 ns)
+ std dev 3.797 ns (1.911 ns .. 7.726 ns)
+ variance introduced by outliers: 87% (severely inflated)
+
+ benchmarking baseline comparison/mul
+ time 30.70 ns (30.35 ns .. 31.03 ns)
+ 0.999 R² (0.998 R² .. 0.999 R²)
+ mean 30.81 ns (30.46 ns .. 31.23 ns)
+ std dev 1.286 ns (991.8 ps .. 1.903 ns)
+ variance introduced by outliers: 65% (severely inflated)
+
+ benchmarking baseline comparison/div (baseline)
+ time 81.75 ns (80.71 ns .. 82.84 ns)
+ 0.998 R² (0.998 R² .. 0.999 R²)
+ mean 82.12 ns (81.11 ns .. 83.44 ns)
+ std dev 3.844 ns (3.209 ns .. 4.565 ns)
+ variance introduced by outliers: 68% (severely inflated)
+
+ benchmarking baseline comparison/div
+ time 182.2 ns (178.8 ns .. 185.3 ns)
+ 0.997 R² (0.996 R² .. 0.998 R²)
+ mean 182.9 ns (179.3 ns .. 186.3 ns)
+ std dev 11.07 ns (9.342 ns .. 13.50 ns)
+ variance introduced by outliers: 77% (severely inflated)
+```
+
+## Security
+
+This library aims at the maximum security achievable in a
+garbage-collected language under an optimizing compiler such as GHC, in
+which strict constant-timeness can be challenging to achieve.
+
+If you discover any vulnerabilities, please disclose them via
+security@ppad.tech.
+
+## Development
+
+You'll require [Nix][nixos] with [flake][flake] support enabled. Enter a
+development shell with:
+
+```
+$ nix develop
+```
+
+Then do e.g.:
+
+```
+$ cabal repl ppad-base16
+```
+
+to get a REPL for the main library.
+
+[nixos]: https://nixos.org/
+[flake]: https://nixos.org/manual/nix/unstable/command-ref/new-cli/nix3-flake.html
diff --git a/bench/Main.hs b/bench/Main.hs
@@ -152,27 +152,45 @@ quotrem_knuth =
16950798510782491100 2612788699139816405
5146719872810836952 14966148379609982000
-main :: IO ()
-main = defaultMain [
- quotrem_by1
- , quotrem_knuth
- , div_baseline
+arithmetic :: Benchmark
+arithmetic = bgroup "arithmetic" [
+ add
+ , sub
+ , mul
, div
- , div_baseline_small
- , div_small
+ , mod
+ ]
+
+baseline_arithmetic :: Benchmark
+baseline_arithmetic = bgroup "baseline arithmetic" [
+ add_baseline
+ , sub_baseline
, mul_baseline
- , mul
- , add_baseline
+ , div_baseline
+ , mod_baseline
+ ]
+
+baseline_comparison :: Benchmark
+baseline_comparison = bgroup "baseline comparison" [
+ add_baseline
, add
, sub_baseline
, sub
- , mod_baseline
- , mod
- , or_baseline
+ , mul_baseline
+ , mul
+ , div_baseline
+ , div
+ ]
+
+bits :: Benchmark
+bits = bgroup "bits" [
+ and
, or
- , and_baseline
- , and
- , xor_baseline
, xor
]
+main :: IO ()
+main = defaultMain [
+ baseline_comparison
+ ]
+
