Benchmarking GHC's Integer Libraries
overview
GHC has two official Integer libraries, integer-gmp and integer-simple, the latter of which is significantly poorer that the former. This report shows the performance integer-gmp in comparison to a new library that aims to compete.
These tests are being carried out with GHC 8.0.0.20160316 on x86_64/linux and the git HEAD version of integer-gmp.
New1, New2, New3 and New4 use slightly different definitions of the Integer data structure to investigate how much difference that makes.
The meaning of Small/Medium/Big is as follows:
- A Small Integer is one that fits in a single machine Word (eg 32 bits on 32 bit CPUs, 64 bits on 64 bit CPUs). Special casing Small by Small operations (addition as well as multiplication) and Small by Big operations has significant performance benefits.
- A Big Integer is one that requires two or more machine Words to store it.
- A Medium Integer is one that requires a small number of machine words (currently four).
want to understand this report?
Small Integer addition and subtraction/GMP
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 3.364841203411682e-5 | 3.371659253170882e-5 | 3.38186850378348e-5 |
| Standard deviation | 1.7267125945544537e-7 | 2.856303199282955e-7 | 5.013192830222032e-7 |
Outlying measurements have no (7.1424874488897425e-3%) effect on estimated standard deviation.
Small Integer addition and subtraction/New1
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.760043589778215e-5 | 2.7644606978478918e-5 | 2.76921544289897e-5 |
| Standard deviation | 1.1883200261976774e-7 | 1.4916479821624747e-7 | 1.84387279098382e-7 |
Outlying measurements have no (6.944104846202771e-3%) effect on estimated standard deviation.
Small Integer addition and subtraction/New2
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.675711165311071e-5 | 2.6789693653456702e-5 | 2.6872450210381646e-5 |
| Standard deviation | 6.734490237483768e-8 | 1.610954386044152e-7 | 3.2682775024375254e-7 |
Outlying measurements have no (6.896219135802552e-3%) effect on estimated standard deviation.
Small Integer addition and subtraction/New3
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.0089215120681407e-5 | 2.0142275699244743e-5 | 2.0245360568535316e-5 |
| Standard deviation | 1.4095808994184803e-7 | 2.2939157043174918e-7 | 3.6201708482503875e-7 |
Outlying measurements have slight (6.901422813412146e-2%) effect on estimated standard deviation.
Small Integer addition and subtraction/New4
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.7630877309782094e-5 | 2.766388073151453e-5 | 2.772397569426418e-5 |
| Standard deviation | 8.78039326043803e-8 | 1.389447732993506e-7 | 2.1199331932444973e-7 |
Outlying measurements have no (6.944104846202924e-3%) effect on estimated standard deviation.
Big Integer addition and subtraction/GMP
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 7.336880081340186e-5 | 7.366754257241238e-5 | 7.407103084959849e-5 |
| Standard deviation | 7.545178137160844e-7 | 1.197892809580022e-6 | 1.816524484143338e-6 |
Outlying measurements have moderate (0.1075970288844186%) effect on estimated standard deviation.
Big Integer addition and subtraction/New1
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.0766150416277193e-4 | 2.087140680330832e-4 | 2.0972385736910162e-4 |
| Standard deviation | 2.966919286566626e-6 | 3.6158163674979007e-6 | 4.816071134725103e-6 |
Outlying measurements have moderate (0.10190711399087529%) effect on estimated standard deviation.
Big Integer addition and subtraction/New2
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 1.5242246214148422e-4 | 1.5307293962746666e-4 | 1.5405529983666396e-4 |
| Standard deviation | 2.1343545871981028e-6 | 2.7813306902084833e-6 | 4.265723392602398e-6 |
Outlying measurements have moderate (0.11402105274538095%) effect on estimated standard deviation.
Big Integer addition and subtraction/New3
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 7.04093756746059e-5 | 7.05604782299794e-5 | 7.073268035784648e-5 |
| Standard deviation | 4.432463636559248e-7 | 5.271104926206756e-7 | 6.853214547405795e-7 |
Outlying measurements have no (7.999479708636771e-3%) effect on estimated standard deviation.
Big Integer addition and subtraction/New4
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 7.397585445811292e-5 | 7.423809257744463e-5 | 7.451757975428919e-5 |
| Standard deviation | 7.403025420202242e-7 | 9.09779365259385e-7 | 1.2840580737301527e-6 |
Outlying measurements have slight (6.864205669738446e-2%) effect on estimated standard deviation.
Small Integer multiplication/GMP
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 1.2439971173406223e-4 | 1.2452204258921618e-4 | 1.2471463199883686e-4 |
| Standard deviation | 3.6704585291189363e-7 | 5.050056725176201e-7 | 6.910404182603182e-7 |
Outlying measurements have no (8.848852040816209e-3%) effect on estimated standard deviation.
Small Integer multiplication/New1
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 1.0025567770521861e-4 | 1.0052056794391802e-4 | 1.0096263991395952e-4 |
| Standard deviation | 7.064280772552149e-7 | 1.0947104727667492e-6 | 1.5471791040535174e-6 |
Outlying measurements have no (8.473957191906193e-3%) effect on estimated standard deviation.
Small Integer multiplication/New2
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 8.641735761665461e-5 | 8.651575075376743e-5 | 8.66426353514231e-5 |
| Standard deviation | 2.9655634239901384e-7 | 3.756239725063784e-7 | 5.400690066088771e-7 |
Outlying measurements have no (8.263888888888767e-3%) effect on estimated standard deviation.
Small Integer multiplication/New3
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 5.26190589583836e-5 | 5.27355419176357e-5 | 5.2949176489517646e-5 |
| Standard deviation | 3.1765411125989753e-7 | 5.449750547187164e-7 | 8.363919955614985e-7 |
Outlying measurements have no (7.633136094674381e-3%) effect on estimated standard deviation.
Small Integer multiplication/New4
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 6.32257383930283e-5 | 6.330291314802529e-5 | 6.343317784296564e-5 |
| Standard deviation | 1.9384792683185406e-7 | 3.116899463810251e-7 | 4.6688403060786077e-7 |
Outlying measurements have no (7.873519778281714e-3%) effect on estimated standard deviation.
Small-Big Integer multiplication/GMP
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 3.624571823132312e-5 | 3.6295830453443524e-5 | 3.637078513001725e-5 |
| Standard deviation | 1.5514696032659623e-7 | 2.1243949065899554e-7 | 2.879002410130687e-7 |
Outlying measurements have no (7.193866834698571e-3%) effect on estimated standard deviation.
Small-Big Integer multiplication/New1
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 1.2308538308213594e-4 | 1.2363194934567282e-4 | 1.24576146850756e-4 |
| Standard deviation | 1.8206176688382595e-6 | 2.5117590709061463e-6 | 3.918089912735659e-6 |
Outlying measurements have moderate (0.15079171724372542%) effect on estimated standard deviation.
Small-Big Integer multiplication/New2
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 1.2341344127790542e-4 | 1.2363163668556494e-4 | 1.240366106816104e-4 |
| Standard deviation | 6.598737564005749e-7 | 9.809629717815813e-7 | 1.615332835246063e-6 |
Outlying measurements have no (8.771242853786443e-3%) effect on estimated standard deviation.
Small-Big Integer multiplication/New3
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.5223012032053636e-5 | 2.535388426728557e-5 | 2.5532368284395414e-5 |
| Standard deviation | 3.50179625028334e-7 | 5.248307016449866e-7 | 7.867656353217877e-7 |
Outlying measurements have moderate (0.18372604433556877%) effect on estimated standard deviation.
Small-Big Integer multiplication/New4
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.398830428511888e-5 | 2.4024286445409614e-5 | 2.408549331644466e-5 |
| Standard deviation | 1.0376461243213666e-7 | 1.4827528292638489e-7 | 2.2904124926932884e-7 |
Outlying measurements have no (6.8024019515857985e-3%) effect on estimated standard deviation.
Medium Integer multiplication/GMP
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 4.578271146359087e-4 | 4.5963534869539007e-4 | 4.6219958149601724e-4 |
| Standard deviation | 5.19909549802417e-6 | 6.945980354657495e-6 | 9.79208171932148e-6 |
Outlying measurements have slight (6.589498209654271e-2%) effect on estimated standard deviation.
Medium Integer multiplication/New1
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 5.760835935472333e-3 | 5.769622120687385e-3 | 5.78145323421158e-3 |
| Standard deviation | 2.575889930753178e-5 | 3.093096407846146e-5 | 3.7355794955350934e-5 |
Outlying measurements have slight (2.4983563445101907e-2%) effect on estimated standard deviation.
Medium Integer multiplication/New2
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 5.8135079062568975e-3 | 5.830717263330699e-3 | 5.867069790075113e-3 |
| Standard deviation | 4.2358251700061276e-5 | 7.225487856365227e-5 | 1.2607430858566394e-4 |
Outlying measurements have slight (2.5623268698060846e-2%) effect on estimated standard deviation.
Medium Integer multiplication/New3
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 4.908619770004058e-4 | 4.914027461239266e-4 | 4.92331755109076e-4 |
| Standard deviation | 1.6156367466119493e-6 | 2.319505928878343e-6 | 3.2602133429343405e-6 |
Outlying measurements have slight (1.1626297577854423e-2%) effect on estimated standard deviation.
Medium Integer multiplication/New4
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 8.413735073391709e-4 | 8.435055888594968e-4 | 8.465470695053504e-4 |
| Standard deviation | 5.968069497746767e-6 | 8.32223626941022e-6 | 1.1628785917467408e-5 |
Outlying measurements have slight (1.3330898466033346e-2%) effect on estimated standard deviation.
Big Integer multiplication/GMP
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 4.147008571901491e-3 | 4.163662495392427e-3 | 4.199857450740307e-3 |
| Standard deviation | 3.536788773906398e-5 | 7.505855877854214e-5 | 1.301531778027649e-4 |
Outlying measurements have slight (2.2210743801652784e-2%) effect on estimated standard deviation.
Big Integer multiplication/New1
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.966480101048207e-2 | 2.9703498618129265e-2 | 2.9760393301943508e-2 |
| Standard deviation | 5.974321685275908e-5 | 9.840526468510625e-5 | 1.5483549311188895e-4 |
Outlying measurements have slight (5.536332179930795e-2%) effect on estimated standard deviation.
Big Integer multiplication/New2
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.9860166421340293e-2 | 3.004925647457504e-2 | 3.0296578476016658e-2 |
| Standard deviation | 3.232579785033782e-4 | 4.7070229000704066e-4 | 7.004971601405029e-4 |
Outlying measurements have slight (5.536332179930796e-2%) effect on estimated standard deviation.
Big Integer multiplication/New3
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.1149260979254247e-2 | 2.118330491605016e-2 | 2.1234447082070954e-2 |
| Standard deviation | 6.750836067221978e-5 | 9.195637995900087e-5 | 1.3230685585444198e-4 |
Outlying measurements have slight (4.5351473922902424e-2%) effect on estimated standard deviation.
Big Integer multiplication/New4
| lower bound | estimate | upper bound | |
|---|---|---|---|
| OLS regression | xxx | xxx | xxx |
| R² goodness-of-fit | xxx | xxx | xxx |
| Mean execution time | 2.118720819170904e-2 | 2.130511921221939e-2 | 2.14855986089404e-2 |
| Standard deviation | 2.2004786634523043e-4 | 3.284994768186348e-4 | 4.70906655610996e-4 |
Outlying measurements have slight (4.535147392290227e-2%) effect on estimated standard deviation.
understanding this report
In this report, each function benchmarked by criterion is assigned a section of its own. The charts in each section are active; if you hover your mouse over data points and annotations, you will see more details.
- The chart on the left is a kernel density estimate (also known as a KDE) of time measurements. This graphs the probability of any given time measurement occurring. A spike indicates that a measurement of a particular time occurred; its height indicates how often that measurement was repeated.
- The chart on the right is the raw data from which the kernel density estimate is built. The x axis indicates the number of loop iterations, while the y axis shows measured execution time for the given number of loop iterations. The line behind the values is the linear regression prediction of execution time for a given number of iterations. Ideally, all measurements will be on (or very near) this line.
Under the charts is a small table. The first two rows are the results of a linear regression run on the measurements displayed in the right-hand chart.
- OLS regression indicates the time estimated for a single loop iteration using an ordinary least-squares regression model. This number is more accurate than the mean estimate below it, as it more effectively eliminates measurement overhead and other constant factors.
- R² goodness-of-fit is a measure of how accurately the linear regression model fits the observed measurements. If the measurements are not too noisy, R² should lie between 0.99 and 1, indicating an excellent fit. If the number is below 0.99, something is confounding the accuracy of the linear model.
- Mean execution time and standard deviation are statistics calculated from execution time divided by number of iterations.
We use a statistical technique called the bootstrap to provide confidence intervals on our estimates. The bootstrap-derived upper and lower bounds on estimates let you see how accurate we believe those estimates to be. (Hover the mouse over the table headers to see the confidence levels.)
A noisy benchmarking environment can cause some or many measurements to fall far from the mean. These outlying measurements can have a significant inflationary effect on the estimate of the standard deviation. We calculate and display an estimate of the extent to which the standard deviation has been inflated by outliers.