We’re going to do a number of different things to optimise the code developed in the previous article, but before we do that, we need to do some baseline performance measurements, so that we know that our “improvements” really are improving things. The performance results we see will also help to guide us a little in the optimisations that we need to do.
Benchmarking is a fundamental activity when working with numerical code, but it can be quite difficult to do it correctly in a lazy language like Haskell. It’s very easy to get into a situation where a benchmarking loop (perhaps to run a computation 1000 times to collect accurate timing information) performs the computation on the first time round the loop, then reuses the computed result for all the other 999 times round.
We can bypass these worries quite effectively using Bryan O’Sullivan’s Criterion library. As well as providing a clean framework for ensuring that pure calculations really do get rerun for timing purposes, Criterion gives us a nice API for setting up benchmarks, running them and collecting results.
Here’s an example of the most basic use of Criterion:
module Main where
import Criterion.Main
import Data.Complex
import Data.Vector
import qualified DFT
import qualified FFT
import qualified Numeric.FFT.Vector.Invertible as FFTW
main :: IO ()
main = do
let v = generate 256 (\i -> realToFrac $ sin (2*pi*fromIntegral i / 256)) ::
Vector (Complex Double)
fftwPlan = FFTW.plan FFTW.dft 256
defaultMain [ bench "DFT" $ nf DFT.dft v
, bench "FFT" $ nf FFT.fft v
, bench "FFTW" $ nf (FFTW.execute fftwPlan) v ]
Here, we’re comparing the performance for three FFT implementations on a single input vector length. The defaultMain function from Criterion runs a set of benchmarks one after another after collecting some information about the system clock for the machine you’re using. The bench function is a simple way of defining a benchmark for a pure function–you give a name for the benchmark and a function to call. The tricky bit here is the use of the nf function. This takes two arguments, a function applied to all but its last argument, and the last argument, and it ensures that the result of applying the function to the argument is evaluated to normal form (which basically means it gets evaluated as far as possible, so for our FFT algorithms, we perform the whole of the algorithm to get a final result). Note that for the FFTW library, we perform the “plan creation” step outside the benchmark so that we only measure the time taken by the FFT computation itself. Criterion also has facilities for benchmarking monadic code, but we won’t be using those here.
If we compile and run this code, we get output that looks something like this (the numbers and probably also some of the messages will be different on another machine):
[seneca:benchmark-demo] $ ./benchmark-demo
warming up
estimating clock resolution...
mean is 1.170747 us (640001 iterations)
found 96871 outliers among 639999 samples (15.1%)
4 (6.3e-4%) low severe
96867 (15.1%) high severe
estimating cost of a clock call...
mean is 31.18633 ns (12 iterations)
found 2 outliers among 12 samples (16.7%)
2 (16.7%) high mild
benchmarking DFT
mean: 21.87155 ms, lb 21.85268 ms, ub 21.90904 ms, ci 0.950
std dev: 131.1261 us, lb 76.22067 us, ub 212.3907 us, ci 0.950
benchmarking FFT
mean: 878.7273 us, lb 876.9702 us, ub 884.2682 us, ci 0.950
std dev: 14.47592 us, lb 5.361621 us, ub 32.03430 us, ci 0.950
found 12 outliers among 100 samples (12.0%)
5 (5.0%) high mild
7 (7.0%) high severe
variance introduced by outliers: 9.424%
variance is slightly inflated by outliers
benchmarking FFTW
mean: 6.682681 us, lb 6.582545 us, ub 6.768512 us, ci 0.950
std dev: 470.4364 ns, lb 421.4242 ns, ub 508.7335 ns, ci 0.950
variance introduced by outliers: 64.627%
variance is severely inflated by outliers
Before running any benchmarks, Criterion measures the timing resolution of the system clock, printing some statistical information. It then runs enough repetitions of each of the benchmarks to give a good estimate of the mean time consumed by the computation. The defaultMain function causes some statistics to be printed for each of the benchmarks.
What we really want to do is to collect timing information for each of the three algorithms for a range of input vector lengths. Here’s how we do this:
module Main where
import Prelude hiding (enumFromTo, length, sum)
import Control.Monad
import Control.Monad.IO.Class
import Criterion
import Criterion.Config
import Criterion.Monad
import Criterion.Environment
import Data.Complex
import Data.Vector hiding (forM, forM_, map, (++))
import qualified Data.Vector.Unboxed as VU
import qualified DFT
import qualified FFT
import qualified Numeric.FFT.Vector.Invertible as FFTW
import System.IO
tstvec :: Int -> Vector (Complex Double)
tstvec sz = generate sz (\i -> let ii = fromIntegral i
in sin (2*pi*ii/1024) + sin (2*pi*ii/511))
doit :: Environment
-- ^ Criterion timing environment.
-> Int
-- ^ Problem size to benchmark.
-> Criterion (Int, Double, Double, Double)
-- ^ (Problem size, DFT, my FFT, FFTW) result.
doit env sz = do
let v = tstvec sz
dfts <- runBenchmark env $ nf DFT.dft v
myffts <- runBenchmark env $ nf FFT.fft v
let fftwPlan = FFTW.plan FFTW.dft sz
fftws <- runBenchmark env $ nf (FFTW.execute fftwPlan) v
let mean xs = VU.sum xs / fromIntegral (VU.length xs)
return (sz, mean dfts, mean myffts, mean fftws)
main :: IO ()
main = do
hSetBuffering stdout LineBuffering
putStrLn "Size DFT FFT FFTW"
withConfig (defaultConfig { cfgVerbosity = ljust Quiet }) $ do
env <- measureEnvironment
forM_ [8..1024] $ \sz -> do
(_, dft, fft, fftw) <- doit env sz
liftIO $ putStrLn $ show sz ++
" " ++ show (1.0E6 * dft) ++
" " ++ show (1.0E6 * fft) ++
" " ++ show (1.0E6 * fftw)
Here, we’re not using Criterion’s defaultMain, but instead we’re setting some configuration options and using the withConfig function to run some Criterion actions. Criterion has a monadic interface (with a monad called, naturally enough, Criterion) that allows us to sequence benchmarking actions ourselves. Before running any benchmarks, we use the measureEnvironment function to measure the system clock resolution. This information is encapsulated in a value of type Environment that we need to pass into the benchmarking functions. We use the usual monadic sequencing operators to loop over the range of input sizes we want to test and, because the Criterion monad is an instance of MonadIO, we can output results from within the Criterion code.
The benchmarks themselves are run by the function doit, which creates a test vector then uses the runBenchmark function to measure the performance of each of the three FFT algorithms in turn. The runBenchmark function takes a timing environment and a Benchmarkable value–pure functions are instances of Benchmarkable, so we can pass a call to nf here, set up appropriately to trigger execution of our FFT functions. Criterion runs each of our functions enough times to get a reasonable idea of the distribution of the time the function takes to complete. The results of the benchmarks are returned as values of type Sample, which is basically just an unboxed vector of double values, from which we can extract statistics for plotting. (For detailed comparison later on, we’ll calculate some uncertainty bounds on these measurements as well, but for a first look, we’re just taking the mean of each sample.)
And here are some results:
Size DFT FFT FFTW
8 4.535224801811631 12.639463811986355 0.24938881591305798
9 6.094768776425294 8.736674729826417 0.26731460663313233
10 8.069465291077051 8.804382741569526 0.2942983045555254
11 10.310516349806875 10.380956440575579 0.3196872608330018
12 12.938803838397611 13.872901035576875 0.3209970827222453
13 15.729148052567119 15.67607784292265 0.3680135388505838
14 18.968579007872655 13.47541584885229 0.37034526398208456
15 22.794941136119323 13.325086684155279 0.3898011107771677
16 26.656055024691995 25.843759136540573 0.4279096195752498
17 30.487043776578574 30.670567931613864 0.5506488472704437
18 35.63588934521826 20.9353702192445 0.4942082353205466
19 40.81010091774569 41.42859159725642 0.6130806516757266
20 46.93383743207919 21.792728802547096 0.49209099887037067
21 53.69921472872267 21.85874608496728 0.560216259637847
22 61.304677916424595 30.05221342525609 0.5818372207536819
23 69.30323595565464 70.19730562728557 0.7614838389545701
24 78.72150923524585 30.520771282890507 0.6017087892230069
25 87.24756097915223 28.66354376658218 0.6343946699121987
26 99.51569867276012 42.05333891277487 0.6610752248626569
27 109.7490379175583 33.44736046584926 0.6877993269039607
28 122.43006506136477 33.42715762835697 0.6841965539812218
29 133.29170026949473 135.04407682589118 1.623419778687614
30 146.84966182897963 34.7208275412961 0.7236494450111195
31 161.09016883586145 161.39623868678308 1.6663351229258954
32 175.14464228737117 55.66689362807301 0.7183178204855758
33 185.51755346813988 49.28468847340277 0.8245653672188906
34 200.6959563919476 74.74813904581964 1.0152825193341601
35 218.2678030360312 45.95943106984605 0.8461991971757613
36 232.00866047825133 50.459757958139654 1.6091146639415204
37 250.6575162921633 248.68524535780872 1.9905843905040215
38 265.4442365680421 97.91922782148643 1.156409166762138
39 282.97610836369637 67.00389154423449 1.0311044115327124
40 302.3447568927492 51.15098110267095 1.6520300081798018
41 322.2268292946477 322.6971099419256 2.2290029696055846
42 340.07603621908595 56.594445561029914 0.9779414883333609
43 359.3772122902528 362.1673057121889 2.255229013306757
44 383.3221862358704 72.12425756549077 1.0346969198175189
45 401.0873506111754 54.304392298772214 1.0408572616974372
46 423.95425765287325 158.58856189463836 1.449169094928002
47 447.7532002187913 459.51836236885634 2.5580206087657418
48 482.8929198639736 72.26558680099157 1.857069986207146
49 491.99971485705606 81.0995566259538 1.1588448299509506
50 526.2851012604579 72.15684143796794 1.1401256463134113
51 543.1214265880133 122.33602168498108 1.4965385709694539
52 570.1175622996832 97.67200609484878 1.1986360860376104
53 598.2080392894294 597.6517292715258 2.856043832642696
54 641.107453831605 78.82489436971298 2.0978727510997253
55 653.3275981034554 96.35428494804506 1.2732105013984967
56 685.1886649216924 78.53357666837326 1.2353482912911014
57 709.7219367112432 156.91277730677822 1.6954376373833382
58 741.8464560593874 287.5775869403565 2.596167581421992
59 772.213830479553 775.2310175980834 3.1945982149669145
60 802.2986788834836 86.0897559495199 2.178935067994257
61 832.3942561234737 836.1016650285029 3.36625959192004
62 869.0225024308465 332.7005574745792 2.8345861605235547
63 911.6648573960564 87.37181212220874 1.4552336581136656
64 939.1807456101675 129.3051032083374 1.3380359827505774
65 964.9526019181508 137.14359083345954 1.4795298582213439
66 997.8650946702257 116.49910138024913 1.5086468439820082
67 1034.4575781907336 1038.3843321885363 4.696635263306759
68 1073.7167735184921 170.5202196857759 1.9179495525912156
69 1108.3864111985458 256.4162786517823 2.138300478385627
70 1148.4800715531599 115.21142430893785 1.5366427170441734
71 1203.6954302872905 1192.139281758238 4.269866006714962
72 1230.9501447847924 123.8775042550904 2.6533880404063677
73 1276.3259687594016 1275.760916726931 4.887370126588009
74 1361.9730749300547 504.2170775788172 3.7834921053477744
75 1452.979830758912 122.10104742220462 1.666420607179541
76 1405.9374609163826 225.52009884800236 2.189249057065953
77 1437.0916166475838 170.00583160136426 1.7805447221211799
78 1490.4043951204837 166.5353511593172 1.7590659677221219
79 1547.8823461702882 1556.0386457613524 4.963664071900509
80 1676.0895528963613 130.7170180337769 2.7296819857188668
81 1621.908930795532 140.66084533456777 1.899710959140531
82 1775.8748808077378 704.0630717362675 4.126814859254025
83 1780.643252389769 1795.8853521517317 5.419043557984488
84 1778.383044259886 128.04291525057374 2.7916708162852735
85 1808.3093443087143 236.6117285121056 2.396836729211122
86 1859.2236318758526 721.1612601365359 4.200724618775509
87 1961.6768636873753 442.8123725312097 3.9646902254649627
88 1963.417319314817 162.62737262461877 1.9893701600484326
89 2070.2383794954803 2020.5591001680882 4.168037638815373
90 2062.7687254122284 152.14069991830797 2.9371061495372266
91 2134.401587503293 231.1261143712772 2.060231248172373
92 2214.9393835238 347.7376172585146 2.9599852726014446
93 2355.377463357784 548.9873183625085 4.124430673463009
94 2412.0376386812704 898.9154238786003 4.474905984742306
95 2339.031485574581 299.81179790837416 2.7349313357362735
96 2419.497756021358 176.5853717010849 2.999094980103633
97 2497.565535562374 2500.7269659212607 5.781439798218861
98 2523.7629690340536 211.5706251490683 2.1574949094110143
99 2591.075686471798 195.0847751327924 2.276180065227346
100 2628.037718789912 188.74710342105558 3.1421461275645703
101 2750.704077737666 2763.4308614901074 6.668356912476667
102 2789.8810186556348 275.2403791461671 2.957018459965656
103 2847.3327436617387 2855.891970651485 5.556426997880756
104 2918.81778623376 240.67120218560814 2.2641179805215206
105 2959.942606942988 189.44022029030072 2.309662066869627
106 3018.891600625849 1200.8940119828471 5.166319864136835
107 3070.618895547724 3085.694102304316 5.592096391551775
108 3134.515074746943 201.9268824737899 3.278044717652462
109 3221.1706915071964 3243.3054723909854 6.6516676119395575
110 3269.660262124872 244.09012460992466 2.4278463618043906
111 3341.5863790682315 770.1217074479371 4.839686410767698
112 3408.965853708124 199.00421129197485 3.4187116793223837
113 3478.4648695162296 3492.2049322298526 5.405236026409816
114 3580.60577298913 369.29959750601205 3.309223533367099
115 3630.6593694857115 463.9203640676682 3.5216561301849056
116 3702.897814767694 597.9211422659107 4.62510968957629
117 3763.1151952913756 270.26935177189955 2.6804345223577735
118 3832.3042669466486 1517.9918089083253 6.046084421021593
119 3932.187346475458 378.93111205526736 3.4433581422476434
120 3989.5818510225768 219.4757905034793 3.719119088990353
121 4069.8430814913268 333.4629008812565 2.8976772542205897
122 4147.794035928583 1627.323416726928 6.274966256959092
123 4237.4108114412775 987.5427622880236 5.438117044312614
124 4309.723166482781 701.2223143662724 4.985121744019649
125 4387.790946023796 231.52251797062996 2.8734756309358462
126 4471.6284551790695 232.61623049066196 3.838328378541134
127 4553.961543100213 4572.765616433953 6.716040628296979
128 4635.133532541131 325.10454154440356 4.365233438355587
129 4694.7119512728195 1101.4949221696152 5.802897470338002
130 4804.4226446321945 341.79384208151276 2.9527083308551254
131 4867.706088083122 4900.8534231356125 8.153704660279395
132 4952.695158975456 291.9420774493898 3.838328378541134
133 5029.537467019891 497.3498277720951 3.8737714408882087
134 5124.89059354577 2019.626883523801 6.436303095028631
135 5216.1286153963565 220.53516372328704 4.110125558716915
136 5295.908240335323 403.0209252876891 3.78734312579677
137 5376.2243070772665 5416.276244180539 8.029726999146583
138 5470.783499734738 562.2767699616298 4.156323180159807
139 5563.025263803343 5602.187899606565 6.790057454149485
140 5652.973441140991 269.07975173422295 4.1077413729259
141 5748.619822519164 1328.5754003695085 6.484774606568465
142 5872.566489236695 2362.7374448946493 7.746008890015726
143 6035.07020856653 546.8081725495205 3.44996186297541
144 6460.187224405156 336.25418639608796 3.938464181763791
145 6122.25511457239 792.8930659379271 5.595473306519644
146 6337.976244943485 2609.4029226473344 8.654383676392674
147 6395.842818277226 398.55355716177354 3.433299009663344
148 6437.110690133915 1055.7972331132187 6.096152322632921
149 6523.444441812382 6565.325049417363 8.282450692994239
150 6599.397448556769 352.18889213034083 4.181651132447384
151 6702.263144510137 6777.524737375129 8.373049753052833
152 6880.18300916468 485.6053285655522 5.514410989625113
153 6998.410014169564 455.6631339447839 4.381207416167149
154 7005.924967782844 432.65277839132654 3.5873202705869867
155 7112.0856084993975 890.0820155228873 6.003169076783312
156 7220.439700143685 363.8022611183778 4.412917154175901
157 7331.008700387827 7379.982260721079 7.064582412258194
158 7433.4619321993505 2994.8065557650098 8.301524179322364
159 7541.3582601717635 1741.2398138216538 7.242945688111431
160 7674.615172403209 336.8347356362003 4.417685525757931
161 7744.57195188319 679.7586817826543 5.158934973969988
162 7868.253973977916 386.60521007009885 4.818228738648557
163 7956.440238016003 8027.579573648329 9.784487741334077
164 8089.062956827039 1292.090205209597 6.823328988892683
165 8198.88570691859 398.4736869377746 3.736671320080348
166 8304.02591611659 3346.531180398798 9.376791971070405
167 8410.08403684413 8453.988818185684 8.596723770724553
168 8559.987334268448 370.40645575949105 4.534510629517697
169 8630.88825132167 730.85416746991 4.023175297693893
170 8753.59037305629 518.3711938914798 4.761970646999117
171 8867.32318784511 552.4817400035407 4.969316759975242
172 8993.67072965419 1431.009558694703 7.388381021363382
173 9100.520400064346 9152.748374002334 8.686886353445757
174 9215.476302163956 892.7105803574822 6.539610879761824
175 9356.484202401994 447.17304834297727 4.053470090038513
176 9470.743922250627 447.72141107491086 4.768160837037229
177 9565.152911203264 2278.113154428341 8.61862088952744
178 9694.564131753801 3926.7180242708673 9.436396615845796
179 9829.988268869281 9857.692507760883 8.831939690715663
180 9945.058611886858 407.5806806130064 4.66325666223254
181 10091.743258493303 10112.38792325771 10.154036538941503
182 10194.468287485002 584.9106404043381 4.352741636940349
183 10320.343760507465 2460.021761911251 9.059695260865329
184 10445.809153573873 747.7342028703005 6.329802530152451
185 10570.809630411031 1331.7749777010513 7.443217294556741
186 10709.309367196918 1064.551963337828 6.9830694368907285
187 10830.29964353359 835.6033701981805 5.60625830340007
188 10965.008524911764 1803.099898355345 8.229998605591895
189 11135.842589395406 441.39616617134635 5.278376596314568
190 11215.00709440029 707.7168364609989 5.470679237605623
191 11391.031531350975 11420.9053793124 10.027674692017674
192 11503.507880227928 470.2241512991132 4.949358957154415
193 11629.805354135398 11667.010573404197 9.97999097619736
194 11784.314898507957 4790.429858224725 10.278014200074313
195 11945.10200406826 589.4278426255505 4.407494837458068
196 12044.265059488182 561.6544974701751 5.38566495691027
197 12149.112013833885 12246.868399637107 8.713651226744757
198 12288.498667734031 525.9195261058352 5.621699350220815
199 12454.499987619285 12515.990523355369 8.92061434341388
200 12575.917033212547 497.95620569161 5.202082651002069
201 12769.672659891014 3050.133971231318 9.66150763667743
202 12927.045611398584 5247.313765542842 12.137679117066515
203 12994.100836770898 1204.5251269425637 7.4932851961680695
204 13144.075659768945 680.3130049790656 6.456164377076278
205 13275.916365640527 1700.475005166869 8.530406015259864
206 13414.292124765283 5486.32839109216 12.149600046021593
207 13560.690669076806 899.3529219712516 6.468161169450415
208 13711.366442697412 564.757117912883 5.512026803834098
209 13849.603919046289 1041.1452193345324 6.399843433873212
210 14002.00584317959 552.3569676138109 5.46195890222277
211 14185.633448617824 14233.925131814844 11.63700010095323
212 14342.260149972806 2385.6900015047568 9.388712900025485
213 14523.272303598294 3460.848120706415 11.081484811646588
214 14604.174880044826 5984.5230856112075 12.67173673425402
215 14755.728034036527 1891.7653837374248 9.028700845582126
216 14915.895251291166 534.3428545054936 5.645541208130972
217 15073.771266000638 1389.0621938875743 8.151320474488381
218 15245.208529489408 6244.0846243074975 12.075690286500109
219 15406.927851693998 3679.7521391085143 12.059000985963
220 15553.252486245998 620.7743578013923 5.762366311890736
221 15696.36323835171 1156.633986958433 6.579328102680311
222 15861.81381131924 1589.7939481905512 8.713988321168065
223 16070.10343457974 16125.890997903714 12.872008340699331
224 16361.338881509673 513.5805699087329 5.893496530396595
225 16407.239226358302 630.2459332205004 5.888728158814563
226 16502.334860818755 6786.975649850715 11.039803145373975
227 16890.48507596768 16960.687426584136 12.819556253296987
228 16895.117548959624 846.2535281266474 7.307318704468851
229 17009.613303201568 17060.930518167384 10.967418662509564
230 17165.884760873687 1052.46652556317 7.707861917359475
231 17377.772120492828 762.4815840806275 5.6875497725782465
232 17531.30176450528 1289.1814985445576 8.361128824097754
233 17800.621775644195 18042.928961770904 11.180385790989884
234 18055.705813424956 678.771628865174 6.351260202271591
235 18093.986300485503 2345.1350011995814 10.082510965211032
236 18192.603377359283 3013.5891714266304 10.967043893677836
237 18425.44773008145 4472.269801156854 12.378481881959093
238 18581.99098493375 942.2420401658316 7.099621906804811
239 18745.21711255826 18826.138762491122 11.207063886067367
240 18893.742350595367 565.1473296540125 5.938796060425891
241 19062.280444162265 19110.648421304595 14.381197946412229
242 19222.476271646396 1049.969090947081 6.913928048951275
243 19587.979105966464 688.6433501328742 5.820750209976275
244 19595.014838235747 3287.467745797968 11.7848196199962
245 20052.22299482144 812.4398131455685 5.981353482827037
246 20295.419482248202 2070.0691023043187 9.770182626587983
247 20318.136004465 1471.366671579224 7.747446157363257
248 20721.7643537692 1516.5159979036864 9.62474729333603
249 21046.22342969693 5052.65691663537 13.897208230836055
250 21171.915320413482 776.3670821275023 6.718424814087995
251 21412.310389535796 21066.822794931308 12.874392526490348
252 21332.452086465728 668.02252722638 6.835249917847761
253 21515.483645456206 1500.8638181856693 8.199739945509881
254 21613.63580610074 9238.664893167374 12.826708810670036
255 21719.505576150787 957.7952761735219 7.196866810418569
256 22104.491976755035 891.8475051011344 6.310729043824326
257 22380.649832742587 22671.63732435025 14.939097421509887
258 22864.682463662994 2300.1215734652064 10.807303445679787
259 22672.55762006558 2028.2790937593966 9.994296090943456
260 22883.46746351041 853.6337752427362 6.897238748414167
261 23113.457945840728 1489.3172063997804 9.751109140259858
262 23363.475588815585 9636.065749185442 14.989165323121215
263 23454.673079507724 23795.38514997281 13.64996868516899
264 23955.113677041903 771.8275923814085 6.935385721070416
265 24120.116023080718 3078.4557142427925 12.402323739869251
266 24410.233286874667 1161.3928217973005 8.303584418910788
267 24711.353568094146 6051.828650491579 14.79127790246692
268 24998.698023813144 4079.3345251253604 13.17956830774035
269 24757.34928037442 25037.92741681851 13.91164227610543
270 25250.20578290738 746.9188113297731 7.242945688111431
271 25700.664309518706 25574.550417917148 15.110758798463012
272 25787.799147622954 1001.0646720017687 8.73306180749619
273 25631.203440683257 975.4823584641713 6.605218964329883
274 25752.851752298247 10759.658602731586 14.85088254724231
275 26040.608672159087 929.7131438340444 6.77938605137313
276 26579.75652601041 1276.991156595095 9.639052408082124
277 26500.286845224273 26326.846865671054 13.585392759382545
278 26475.98245527066 11151.93107511318 15.413550393922
279 26979.045657174956 1723.6063757113022 10.227946298462985
280 27160.823134439364 859.8672289933467 7.12373639856065
281 27875.821379678622 27725.47700788297 13.856099301377329
282 27352.080134408847 2856.4737119844917 11.794356363160265
283 27952.08909894742 27962.281493204013 14.152085962162426
284 28233.496932046786 4708.134917276238 14.242915170533323
285 27938.58030225553 1193.9631838883647 8.468907932558702
286 28345.463065164466 1399.2998876741956 8.291987436158301
287 28497.981814401523 2522.4015989473837 11.5559377840587
288 28992.965010660067 953.3749957169789 7.347849862916118
289 28879.043845193763 2297.029284494259 10.582487982601517
290 29311.463622110266 1676.792887704711 10.151652353150487
291 29282.085684793372 7247.900752084603 15.001086252076293
292 29890.544203775306 5122.813967721795 15.864161508423953
293 30326.69523145475 29903.216151254554 16.467360513550908
294 30367.98932935514 1096.0649390305769 7.972506540162209
295 30855.924872415442 3984.5369138887877 14.199999826295041
296 30299.84214689054 2145.5643453768284 11.122015970093855
297 30919.017581003085 902.7515788163442 7.820975516318459
298 31373.941687600985 13244.70022107876 15.926150338990361
299 31819.426802652255 2115.952757852414 10.766772287232525
300 31993.4985914401 1025.7910628403915 7.521895425660258
301 32278.818873422522 2911.679533975459 12.26642514978136
302 32321.893958108798 13678.324011819726 16.40060331140247
303 32682.02283765592 7949.759749429578 17.85734082971302
304 32426.059035318278 1186.972751149107 9.751109140259858
305 33141.98234464444 4330.320147531365 14.974860208375121
306 33732.368735330485 1170.3394789780864 10.347155588013766
307 33688.2589140109 33405.284670846835 18.698958413941543
308 33315.36987211026 1188.4902854050883 8.749751108033301
309 33549.6828832797 8348.834303872938 18.973139779908337
310 34272.37728025235 1993.0980482271705 11.29844571862901
311 34264.831332223795 34401.27113248624 17.3905704990317
312 34732.005385415934 1026.238097676207 8.284834878785254
313 35023.34096814908 34496.829298990146 17.50169288812918
314 34824.921874063395 14794.695166604886 16.045359628541142
315 35426.55685331144 1072.3768611039413 8.539942758423926
316 35933.90682126798 6115.767745035037 16.200331704957158
317 35852.84688855924 35425.200251596354 15.90469266687122
318 35812.08207990445 3645.109919565057 13.756541269166133
319 35991.33470441617 2414.2167844942583 11.71329404626573
320 36494.650630014316 1001.0670561875598 7.989195840699317
321 37298.56470014371 9341.585425393938 18.72995282922474
322 37178.46610929288 1799.6213712862532 10.653436929897218
323 37475.26624585904 2716.688899057246 11.818296635750102
324 37356.33829023161 1204.0852446641215 8.28721906457627
325 37504.44867994108 1257.5624265841088 8.169160703293729
326 38265.21613981046 16305.022028940093 19.16149045739857
327 38689.54875852384 9600.9419241122 18.079070108277474
328 38296.49665738859 2702.5554456881055 12.836245553834097
329 38524.489192026034 3524.024275796747 14.135626809937618
330 39291.04545499601 1204.4989008988628 8.940485971314548
331 39480.871943490885 38912.50350858488 19.845751779420056
332 39688.46300031461 6772.517947213995 18.324641244752083
333 40276.38175870694 2582.3638715914267 13.16764737878527
334 39911.68954755582 16864.065913217437 18.830088632447396
335 40073.59006788053 5239.4697942904 16.58479079958939
336 40646.56713392057 1046.5918917741074 8.628157632691503
337 40858.35197355069 40895.28062726773 17.863509112170757
338 40993.642596261874 2139.463213937619 9.381560342652438
339 41900.4581251315 10500.998286264303 17.215139531030623
340 41452.87969495572 1428.525237100465 10.502127664429787
341 42102.71098996915 2785.856513040401 12.988833444459098
342 42602.906016366855 1501.6505994967044 11.14585782800401
343 42584.12340070523 1788.2702627352278 8.710909080622821
344 43811.59761335172 3165.1017942598824 14.149931924683711
345 43777.956751840495 1849.829939859251 12.137679117066515
346 42863.58573819913 18314.094332712066 19.17579557214467
347 44174.356249826335 44410.38825895108 19.452361123902474
348 44465.38188840665 2141.5899076632054 12.433318155152454
349 44883.179453866855 44393.53921796598 18.444943823376477
350 44347.02136899747 1277.5943556002217 9.27665616784775
351 44574.66104413786 1256.4347067049582 8.930579451273898
352 45817.73260022917 1196.1958685091577 9.267119424683688
353 45450.53699399748 45510.31091596402 18.243337424151886
354 46365.82830335416 4799.947527902458 17.833498971802864
355 45934.97255231656 6010.389117257936 16.876080643874104
356 46229.37181379117 7883.405474679821 18.19589521203724
357 46165.935782449626 1663.4724416903066 10.975403899965997
358 47067.487029092685 20102.25036527432 19.26162626062123
359 47104.928282754794 47303.86951352873 18.17678394062179
360 47508.444575326816 1259.0000906160913 9.009627359254
361 47104.79953672208 3394.295958536005 13.747418096171716
362 47462.7778806857 20380.27742292203 20.556239145142705
363 48170.25163556852 2110.461977975705 10.349539773804786
364 48485.56497480191 1545.6817426851803 10.003832834107516
365 49318.957118051425 6579.6754636934875 19.933966653687627
366 49689.38568021573 5129.709033029412 16.93704511438099
367 50255.09097959317 49051.54683973111 21.10698606286731
368 49726.23803998747 1903.8269796541726 12.790946023804802
369 49101.24280835904 3176.5959539583687 14.76266767297473
370 50102.53646756925 2998.3542242220406 14.362124460084104
371 50957.63900663175 4492.418555276727 16.200331704957158
372 50975.365427987956 2428.602961557247 13.64925290857043
373 51592.71695997037 50736.756114023105 20.010468101763475
374 51410.03349210539 2348.7732687166713 13.131884591920038
375 51652.71499540128 1684.1957845858144 9.58183194909775
376 52302.822855966464 3796.2124624422545 15.961913125855594
377 52613.220004098795 3489.4631185701846 14.259604471070432
378 51769.93587400235 1219.4702902010522 9.867934244019626
379 52595.777300851725 51702.32513334073 19.144801156861462
380 53028.514174478434 1730.0722875765368 11.603621499879011
381 52421.17145444669 13239.009169595605 18.25549985681263
382 52614.29765607633 22468.349722879302 18.85154630456654
383 53027.18856717863 54096.49351026334 17.975906358689684
384 55113.75883008756 1356.6754141024185 9.286192911011813
385 53848.81713773527 1887.9888334444563 9.78146113303243
386 54480.731276529215 23090.860632913482 19.10665418420521
387 54511.60409833707 3601.9776144197936 15.6424322298595
388 54362.86428357877 9403.009203927873 19.159106271607556
389 55309.22391797818 55381.555346506015 22.14887525354113
390 55903.02207853116 1493.6945715120853 10.108737008912204
391 55723.93396283903 3725.466517465448 15.306728765394112
392 56214.98802091398 1682.6865949801015 9.877470987183687
393 56263.01982785978 14552.333144204984 22.959498422486433
394 56233.448771493815 24410.910395639316 19.070891397339977
395 57423.25761701383 7609.135893838755 19.52150251184193
396 57079.787043588534 1371.02344419275 10.118273752076268
397 57643.43479062834 57198.58625318326 19.449662849573173
398 58020.29827024259 24801.137236612212 19.078043954713024
399 58038.83293058194 2002.2676267794163 12.268786560149861
400 58057.30798627653 1509.4707288912352 9.481696145875095
401 58799.662379281894 59028.00538923063 23.202685373170027
402 58708.579329507724 6034.731654184206 19.447592752320446
403 59600.43647672452 3704.6811857393736 14.714983957154418
404 59712.006835000895 10503.351477640035 23.302821176392683
405 59641.74487973966 1530.2679815462648 10.492590921265723
406 60639.25722028531 2729.4395246675977 14.390734689576291
407 60837.991026895426 4022.8555479219904 16.83929349694935
408 61216.20633985318 1686.2390318087148 12.640742318970814
409 61319.25561811246 61571.554926889316 22.36583616052355
410 61996.3929929904 3641.8483534029474 16.295699136597783
411 62611.66551496305 15926.64697553433 22.136954324586053
412 62590.839652078525 10776.841429727436 23.512629526002062
413 62380.87394620694 5753.37627317224 18.896845834595837
414 62808.625487344645 2134.9427976778534 13.830451028687618
415 62987.44657422818 8345.157889383192 21.34540464196887
416 63464.99898816861 1442.048338907105 10.211256997925878
417 63636.29320050993 16193.074969308745 22.086886422974725
418 63965.99986936369 2685.990122812129 13.906744974000118
419 64408.38077451505 64784.023551004306 21.507571960611287
420 65295.798567788974 1682.503012674193 10.525969522339942
421 66737.9234113864 65064.604071634196 21.666849354155982
422 65290.705946939364 28178.159979837317 22.51842405114855
423 65669.77003003874 4212.6987257174005 17.54262830529896
424 65998.42050458706 4911.854056375359 18.071917550904427
425 66269.5906438998 2147.929457681516 12.778576821870779
426 66634.53796293058 6925.6112852266915 20.26060010705677
427 67137.76805784025 6163.637427347049 19.955424325806767
428 67444.14546872891 11754.7414579562 24.697569864136817
429 67749.38562299528 2734.5917501619824 11.66561033044542
430 68000.97444440641 3964.576510446405 17.757205026490364
431 68546.64304639616 68595.40203000822 21.7502245248245
432 68754.98989011564 1875.781802194456 10.52835370813096
433 68997.48781110562 69199.10409833708 23.808268564087996
434 69460.37509824551 3326.7925062349796 15.759257333619264
435 69741.14158536709 2773.7806120089067 14.900950448853639
436 70478.67277051725 12348.854331033592 22.792605417115347
437 70954.94010831632 4568.912772195672 17.642764108521614
438 71116.31610776701 7327.303675668588 22.733000772339956
439 71383.65486051358 71822.12808515348 23.03458635926878
440 71926.24071027555 1821.310309427122 11.14108945642198
441 72343.52805997647 1954.226283090452 11.458186166627058
442 72901.38938810148 3139.3454351595406 14.238146798951293
443 73245.95907117643 73453.74801542082 23.10691797114038
444 73716.02991010464 3397.488383310175 16.414908426148564
445 73404.24278165617 9744.22910596645 22.892741220338
446 73933.32221891203 31927.816657083415 24.3590154818126
447 74908.54003812588 19061.31723310269 22.42305661950792
448 75689.56115628996 1602.7806081942133 11.343745248658308
449 75547.2014227084 75102.94416333952 23.06469620822311
450 75254.76434613981 2017.4095907381563 11.2054624727794
451 75598.39227582731 5027.878073709343 18.19589521203724
452 75950.78447248257 13644.988326089746 23.15977002893175
453 76265.83555127897 19730.875281350982 23.519782083375105
454 76722.56448652067 33107.58569623747 23.27659513269151
455 77130.01468564787 2399.699477212765 11.299825387493692
456 77467.45326902188 2257.351664560177 14.71498395715442
457 77890.41259671965 78154.61852933683 24.08244993005479
458 78471.5340414218 33835.403708475016 23.417262094361433
459 78861.56061078825 1967.7493848970926 14.574316995484494
460 79717.16144468107 2630.734232919551 15.134600656373168
461 79399.20881177702 79353.36807157316 22.379697956048048
462 79562.46831800259 2159.9672117403534 11.856345193726671
463 80000.32880689419 80097.06714536465 22.566314680235728
464 80364.43689252652 2930.01630689416 15.733031289918092
465 80741.26937772549 3375.5753317049503 16.314772622925908
466 81039.88149549282 35048.48697568692 23.49117185388292
467 81470.7682409457 81618.04654981411 23.1306731313854
468 81959.87441922938 1937.4773779085672 11.763361947877062
469 82259.6857824496 7392.332343118539 22.91713678217554
470 82632.82993222987 4940.254477517937 19.03512861047474
471 83033.64017392909 21367.09907438077 23.15738584314073
472 83409.44269086633 6110.996989267214 21.07837583337512
473 83790.69307233606 5472.442893045285 19.476202981812634
474 84188.5230817965 8741.290358560438 22.928504007203237
475 84590.7185354403 2639.0478887728227 14.858035104615357
476 85020.28444196495 2493.7269964388383 14.76266767297473
477 85386.6122045687 5537.9865446260965 20.754126565796998
478 85827.12152387411 37134.54940702238 23.469714181763777
479 86148.71242429527 86283.36408521445 23.36024854864392
480 86569.57366849692 1960.832861917356 11.465338724000105
481 86960.77087308676 5110.769061105584 18.60359098230091
482 87289.56201459676 37792.58468534269 27.925757425171955
483 87717.81900312215 2997.1573629549507 15.741363325447002
484 88075.79257871419 2832.19554807458 13.07466413293566
485 88477.87597562581 11865.532187478904 24.471072213990333
486 88877.35822583943 2225.837496774533 12.318877237183704
487 89300.97797300128 89424.59323789386 26.874331491334072
488 89722.14677716998 6556.27944852625 22.189406411988394
489 90068.86222745685 23240.558890359775 27.382163064820396
490 90524.77100278644 2579.965380685665 12.47384931359972
491 90953.91252424028 91082.03866864946 25.458617763859877
492 91353.64034559038 4327.606944101189 18.837241189820446
493 91753.46353437212 5253.958491342402 20.155695932252083
494 92171.93820859697 3561.420229928827 16.684321420533333
495 92609.96559049393 2233.4430494478725 12.669352548463003
496 93029.60851575636 3347.162989633417 16.982344644410286
497 93375.97110654616 8579.561499612686 22.954416778180516
498 93787.16447736527 9861.740855234028 26.306895273072353
499 94221.19119550491 94363.61768628859 25.19464071307861
500 94691.7174139192 2395.3054227999232 12.092379587037218
501 95069.61086179518 24647.87700559415 27.508524911744228
502 95473.73989011548 41435.49659635343 24.058608072144633
503 96017.78486158155 96011.95075895093 24.785784738404395
504 96290.41650678418 2097.685126321652 12.302187936646595
505 96729.69320203566 12926.411417978174 29.10354520593367
506 97151.39844800733 3797.521380441522 17.413882272584114
507 97557.2631635835 3532.1996488741397 13.444212930543085
508 98043.56792356273 17453.84433652676 23.593691842896586
509 98428.81896878978 98535.65910245678 23.400382271834786
510 98807.29177381298 2533.0374517611044 15.675810830933719
511 99320.5378332307 9048.726347940325 26.74320127282821
512 99689.97695829174 2639.686850564815 12.20682050500597
513 100074.26240827341 2616.896418588497 16.4506712130138
514 100488.49323179026 43620.738772409335 28.126029031617268
515 100877.98335935373 13536.414889352685 29.37057401452742
516 101359.61749936838 4732.885149972772 20.031718271119274
517 101725.239542978 6278.50034620081 21.998671548707147
518 102182.37617398996 4448.003558175897 19.6693220308849
519 102593.66252805488 26654.22418500699 28.006819742066487
520 102985.05762006537 2273.8907613924525 12.76471998010363
521 103480.92773343819 103619.12229444283 28.486041086060627
522 103819.45588971871 3461.0936918428897 18.281725900513802
523 104321.07665921944 104499.21586896676 27.884054798928524
524 104765.82029248969 18674.094466226474 28.88420011316023
525 105141.7157926728 2593.0164137056845 13.172415750367302
526 105525.46003247992 45870.66629316129 28.564719217164143
527 105993.45424558416 6134.292868631228 21.99628736291613
528 106420.36178495185 2082.524088876584 13.136652963502069
529 106865.30807401435 6874.663619058479 21.80555249963488
530 107369.15328885808 6197.731284158573 22.625712411744253
531 107835.8290472199 6943.199423807014 24.602202432496195
532 108173.97811795963 3221.540240304804 16.90128232751575
533 108639.9243154694 6244.632987039431 21.264342325074338
534 109071.45717527164 11469.440249460105 28.137949960572346
535 109550.25651838077 14893.550662057767 29.792574899537186
536 110020.18669034733 8145.1771536043825 25.682238595826266
537 110393.43097593082 28753.690508859534 28.30007459436141
538 110882.7016630341 48205.630568521396 28.96287824426375
539 111319.14594556582 3191.385058420039 13.63261826851401
540 111809.26063443911 2381.4032354525107 13.260630624634882
541 112178.89287854922 112402.62487317812 30.97274686608991
542 112698.48325635683 49041.05403806486 28.731612222535233
543 113151.93870450747 29593.50088025846 28.63147641931258
544 113667.77637388003 2473.594931619503 16.011981027466923
545 114048.86939908755 15491.628436105617 28.4359731844493
546 114491.35759259948 2921.4046278170113 14.011649148804805
547 114917.46642972718 115071.76854993592 30.374351660816032
548 115540.58053876647 20744.073180215728 28.98433591638289
549 115861.16292859802 7627.377299325816 25.417593973023532
550 116329.91054441223 2850.71828748498 13.830451028687618
551 116748.16587354432 6675.76530362879 22.907046335084093
552 117252.68819715272 3012.435225503779 17.864493387086068
553 117694.56127073058 10695.06147290981 27.09606076989852
554 118171.33405591734 51443.171290414706 28.81505872522078
555 118599.07844449767 4566.674021737908 20.563391702515748
556 119169.84298612364 21387.38372709073 28.421668069703205
557 119572.47712995298 119765.01205350645 30.359918570944217
558 119998.09720899351 3839.788226144647 19.974497812134892
559 120536.7801466156 6820.6308164766915 22.711543100220815
560 121009.13503553161 2491.8649473360556 13.546732919556758
561 121384.04348279722 3869.6334638765807 18.20066358361927
562 121886.31751920469 53069.23368360319 28.877047555787186
563 122359.55455686337 122515.54468061215 30.634171145708383
564 122813.73718168026 5869.295386331421 22.723464029175894
565 123324.63004972225 16687.33337308682 28.888968484742264
566 123792.02821637875 53931.21459867276 28.91281034265242
567 124416.38925458676 2555.6609907320517 14.59815885339465
568 124771.33253003842 9121.281889932512 26.88386823449813
569 125280.64706708674 125410.59234525448 29.492167489869217
570 125731.7612447906 3325.7172384432315 17.77627851281849
571 126218.19236661677 126358.90224363095 28.4211853666911
572 126721.34616758113 3688.54501630578 15.346793191773562
573 127279.24564267878 33357.26716901578 28.445509927613358
574 127680.67100431207 5601.749209421018 22.69246961389269
575 128188.75530149226 3825.602320688104 18.777636545045056
576 128715.26935483699 2655.541686075069 14.178542154175902
577 129121.29857923271 129819.29519559623 31.635550515992254
578 130020.20337964776 5626.3587751558825 21.583823221070432
579 130077.57642652276 34203.457621591464 27.99966718469344
580 130646.14274884942 4147.026328103875 19.621638315064587
581 131070.16542340996 11992.635516183738 31.413821237427804
582 131491.86590101005 14043.144969003566 28.74353315149031
583 131997.7042951751 7990.302828805799 26.06370832238876
584 132549.51694394829 9687.449721353412 30.300406473023507
585 132996.59946347956 3013.090876596308 14.7578993013927
586 133440.74228193046 58194.737223642245 31.52587796960554
587 133998.57261564018 134148.93129255058 30.79652259392396
588 134527.70450498344 3017.0414724520215 15.110758798463012
589 134936.65674115898 7682.990817087046 24.959830301148536
590 135532.42423917534 7915.522841470594 26.43325711999618
591 136022.60091687916 35752.84459974088 28.378752725464924
592 136440.91346647026 4869.167593973015 21.798399942261835
593 137025.14865781544 137136.4400663543 30.5711037549032
594 137439.29365064384 2805.225638406612 15.425471322877078
595 137952.8782644439 3606.7269125154967 18.45338727746693
596 138533.02457715748 25003.051547067535 28.686312692505936
597 139100.87802793263 36597.71659757413 28.69108106408797
598 139473.2377805877 5317.837981241085 20.351199167115357
599 140113.29391385792 140210.28497602223 31.05442184396737
600 140610.66129590748 2899.563101785517 14.464644449097776
601 141077.78289701222 141220.30475522755 36.18934537683209
602 141549.75631620167 6067.638186471803 24.34947873864854
603 142079.12185575248 9070.837286966202 31.29938031945905
604 142660.52463437794 25840.954569833648 29.723433511597733
605 143132.77700330492 4368.1857862642755 16.398219125611455
606 143669.19258023976 15272.006777780423 35.226134317261774
607 144120.16132261037 144274.5707311797 35.25885685332236
608 144618.10329343556 3193.650034921504 18.51299192224232
609 145184.91247083424 4694.213656442497 21.528986947877073
610 145641.7582311797 8407.130030649061 27.839926736695393
611 146104.50485135792 8366.930274026747 25.713233011109466
612 146688.10823346852 3185.1408758333687 18.782404916627083
613 147253.8326063323 147379.58171750783 37.193087594849665
614 147718.7083044219 64507.68926526823 35.798338907105524
615 148397.76971723314 5793.702391641478 23.57461835656846
616 148773.18122770067 3234.052447336054 15.768794076783328
617 149334.07285596605 149556.2813558745 35.71659575919712
618 149891.14501859422 15976.819781320462 34.129408853394594
619 150433.77616788622 150607.74305249925 36.90634836920174
620 150897.22850705858 4605.262068765495 21.36686231408801
621 151453.442362802 3784.1222562960143 20.87333585534778
622 152001.48561383958 66422.78411771574 36.24656583581646
623 152454.8957624602 13784.923342721826 30.934599893433667
624 153139.9700918364 2856.2925138643755 15.34202482019153
625 153584.32510282274 3748.2235708406915 16.26947309289661
626 154085.41658307784 67327.94025327482 36.18934537683209
627 154604.41329862352 4582.865027444695 21.021155374390744
628 155295.57922269576 28323.03264524259 30.19550229821882
629 155775.12481595748 8469.629076974745 27.77316953454696
630 156250.51954175706 3114.4235410860542 15.72826291833606
631 156837.7158918547 156960.3750982451 33.92913724694928
632 157351.99430371993 11637.639788644676 29.945162790162186
633 157885.78727628462 41750.96967603482 33.60727216516217
634 158462.73878003831 69316.43941785612 30.951289193970776
635 158982.5985708403 21901.039866464507 29.34434797082625
636 159611.03895093672 7302.39847089564 26.986388223511806
637 160098.86720563643 4135.3390493563165 16.294073190662886
638 160693.31863309615 5609.607485788207 23.2742109469005
639 161241.4977827238 10515.212801950338 30.69141294275007
640 161802.27735425704 2796.132353799678 14.786509530884887
641 162357.98576261272 162445.05384351485 35.51700498376568
642 162816.61727811568 17556.175974862945 34.575251596314516
643 163349.03219129314 163535.8188429045 35.15733027505497
644 163866.21215726607 4303.915289895867 21.335867898804807
645 164498.48153974288 6274.454382913455 25.243548410279388
646 165056.6051283049 6490.006236093388 24.587897317750098
647 165561.28480817546 165697.50287915938 35.098387904110396
648 166165.1346960234 3257.3364057711124 15.730647104127078
649 166666.85321714156 10398.430613534809 30.44345762048445
650 167207.10018064253 3578.924922006463 16.181258218629033
651 167764.95674039592 5294.611243265011 23.605612771851664
652 168424.763468759 30821.747569101233 35.90324308191021
653 168878.71482755415 169033.18860913985 37.472037332398486
654 169530.81825162642 18263.780859964263 33.69310285363873
655 170003.13976194136 23557.06670667447 35.96523191247661
656 170681.21650602095 5768.892554300171 24.890688913209083
657 171183.14721967452 11076.938895242574 34.13417722497662
658 171737.01026822795 7379.982260721079 27.43938352380477
659 172270.57912732832 172414.87481977217 36.07435986703756
660 172906.2531271147 3287.937430398798 16.650942819459114
661 173387.12671186202 173536.19792844527 35.923270607481186
662 174031.85108091103 76192.36925031462 36.64710904870709
663 174633.92475034465 5369.87045194421 21.33348371301379
664 175114.90085508098 12886.61220456875 34.76121808801373
665 175745.11983777749 4416.470316903924 21.226195352418088
666 176269.75038434734 5465.221194284299 25.183943765503997
667 176915.3759756254 9710.194853799701 28.822211282593827
668 177520.52524472942 32542.94374372282 36.43730069909771
669 178018.10481931438 47288.927821176425 36.7257871798106
670 178595.068243997 10341.238764779926 32.481936471802804
671 179124.20013334023 11125.5476751498 31.86204816613874
672 179722.46148969402 3047.430304544306 16.09542753015247
673 180359.0033331083 180457.92320157756 37.47161077100694
674 180920.2096738981 79265.05544568814 37.193087594849665
675 181519.8943891691 3552.715567605829 16.777304666382943
676 181963.18366910686 5428.397444742062 17.552165048463024
677 182698.28536893596 182860.79624082317 37.14778806482037
678 183153.37636853923 19749.736575143706 34.327296274048884
679 183807.2488584684 16744.074610727203 33.697871225220766
680 184375.9177007841 3700.8331098726744 21.02592374597278
681 184960.06944562664 49155.93603040494 34.85658551965435
682 185560.88426496257 6661.3171377352355 25.38659955774033
683 186184.47521116008 186316.76175977458 36.26141627224126
684 186770.04554654824 3669.9936666658873 21.300105111939573
685 187293.10729886757 25918.25702573575 36.16788770471294
686 187859.9951543974 4711.363104837273 17.342356698853646
687 188525.23782636394 50279.99380018033 35.02586271081646
688 189176.37327100502 6637.649325387823 26.483325021607513
689 189802.2387304472 10803.227213876607 30.538825052125073
690 190282.70938779583 4370.345858590936 22.50650312219347
691 190988.2710256742 191023.1468954252 36.65392137303645
692 191506.1209478544 35364.74206830777 36.81161786828716
693 192127.1560468839 3877.0768919161314 18.110064523560677
694 192735.0399770902 84539.42993070398 37.03811551843364
695 193383.2071104215 26979.257849710357 36.33478071008404
696 194028.27718641027 4687.928942697381 24.029997842652445
697 194548.77832319005 10181.798724191545 31.542567270142648
698 195265.4288091825 85638.24870969565 37.21931363855083
699 195864.91563703286 52188.30802823819 35.49077894006451
700 196490.75248624547 3883.1947126558775 17.015723245484505
701 196939.65890790685 197157.05612088906 36.73125095978506
702 197708.94506360753 3499.9773779085635 18.224505441529427
703 198210.88769819005 10369.224337594867 31.28030683313093
704 198908.33833600744 3242.1181478670596 17.423419015748173
705 199433.8677206205 7681.989459054819 28.50034620080672
706 199923.1765546964 87825.29333020955 37.27891828332622
707 200740.90936567055 18451.742915170562 41.057852762086
708 201271.87707807287 9262.778548257707 31.735686319214913
709 201871.96472074257 202186.74161817296 36.16700251491706
710 202339.1101637052 11870.279101388816 33.519057290894594
711 203129.329470651 13264.202860849267 34.76121808801373
712 203806.8697729276 15151.262072580226 36.730555551392634
713 204337.40833188756 11154.789713876607 31.31845380578718
714 205112.5977316068 4329.8790731600275 22.184638040406366
715 205612.9548826383 5729.6536245516345 19.171027200562634
716 206305.58469678625 38197.20724012174 36.67095090661724
717 206963.37678815587 55318.105010049716 35.650519388062555
718 207480.66642667516 91192.93668653276 37.712840097291064
719 208282.40611936315 208338.24136640294 37.598603725934254
720 208759.79879285558 3448.149947183466 17.211226480347783
721 209380.48103238808 19221.069602029693 41.43455411706647
722 209926.07334043251 8218.64583875453 27.904299753052815
723 210646.50514508944 56437.22036268033 41.87562848840437
724 211254.91359616976 39069.89314939298 37.853507058960986
725 211984.9083700345 5624.3751325777575 25.474814432007904
726 212531.82866956454 5356.5380850008505 19.531039255005993
727 213163.05377866488 213385.996607797 47.781256692750105
728 213779.7973432706 4374.735144632195 18.245963113648568
729 214442.9323949979 4102.442053811883 18.985060708863415
730 214981.5795698331 12515.258578317527 37.62224103723247
731 215672.96483899813 10894.992140787008 33.75032331262311
732 216343.93909360628 9892.048625009418 33.44991590295514
733 217052.13287259798 217190.21060849886 40.73598768029889
734 217642.53118421297 95698.78557111525 40.499953286988344
735 218261.27984906893 4549.715308206413 18.572596567017712
736 218914.82808973055 4469.239501016473 23.395804422242293
737 219593.83943464022 13448.37167646206 39.99927427087506
738 221056.05342771273 6960.205821054328 29.008177774293046
739 220967.86954786043 221089.3891134427 40.19773837977225
740 221583.54499723177 6469.297198312626 27.193812387330162
741 222244.40553571444 6611.022738473761 24.25887967858995
742 222757.41079236727 9448.270586984514 32.558230417115304
743 223444.3972387479 223754.89929105502 40.254735321338714
744 224159.06885053377 5516.078261392454 26.104239480836025
745 224759.5403471158 31539.871481912513 36.28709699426373
746 225462.10267926913 99172.14610959789 40.905264871461
747 226029.708174722 14612.49092008389 39.59396268640239
748 226861.2454214261 5981.328276651247 23.958472268921977
749 227431.61418821078 20792.670039194003 41.947154062134835
750 227968.24672605257 4341.773776071404 18.334177987916146
751 228640.80169584017 229024.0977087186 40.2353086641856
752 229428.4627714322 7802.979735391491 29.99046232019148
753 230133.1017294095 61892.361430185214 35.73158170495709
754 230670.14673139315 7933.025149362439 27.172354715211025
755 231326.06246854525 32503.52600003995 37.42673780236919
756 232015.2399816678 3680.6843557528014 18.667963998658337
757 232707.4597158597 232962.53898526888 38.70515473735281
758 233443.37919141512 102873.52779294747 36.90221692834576
759 234152.1928587125 6820.6308164766915 26.352194803101654
760 234789.57393552523 4462.961939828729 23.53170301233018
761 235427.4413862393 235652.7946272061 38.94745644980247
762 236112.03411008575 25925.23553754605 34.942416208130915
763 236857.4688711331 21888.71362592496 39.829997079712946
764 237590.19115354278 44190.56394483365 36.58035184655865
765 238242.00370694854 4443.838385598992 24.02761365686143
766 238879.54452420928 105219.09931089179 37.166861551148486
767 239600.9991445706 13178.205279367336 35.733965890748095
768 240210.36365415313 4262.227801339959 18.17920591150013
769 240675.50876523711 240989.16747953155 41.072157876832094
770 241416.56854535796 4857.234744088982 19.70746900354115
771 242093.8895025418 65034.804133432284 42.08066846643172
772 242860.80100919463 45325.004843728915 36.94513227258403
773 243348.1858053372 243729.8176565335 39.841675133045264
774 244010.64374829986 7512.3665609530135 30.94652082238874
775 244955.85897351956 6431.72004606043 27.560976999146565
776 245420.19107724883 18363.058356302154 36.94036390100201
777 246111.90297986724 7697.651175516002 29.69720746789656
778 246738.080767648 108716.2182607819 40.83850766931256
779 247610.25884534576 12140.645770089988 35.83171750817974
780 248400.02277280547 4467.77799512658 19.314078348023575
781 248935.17711545684 15193.156985299955 38.17298795495707
782 249554.17135144927 8737.830904977676 30.917910592896558
783 250310.05599881866 5633.3849706820065 27.859000223023518
784 250946.8529501126 4553.8780965975275 19.032744424683727
785 251671.02554227566 35386.57167341031 38.230208413941455
786 252200.84884549832 27613.494185464755 42.83168699060164
787 252971.31994153716 253215.57500745513 41.43380416291101
788 253587.26480390286 47354.83625318326 37.398127572877
789 254384.16221524935 68400.03230954923 42.53843213830671
790 255024.1968908475 14921.221522348293 37.31706525598247
791 255849.07272245144 23573.567656534087 40.197161691529345
792 256516.99521924715 4163.415221231317 19.907740609986462
793 257188.4582319424 13921.344069497949 37.42673780236919
794 257816.54813672762 113703.96116163027 40.81943418298444
795 258627.4168768094 9842.977313058735 34.18186094079694
796 259462.97862912872 48455.41932966031 37.32421781335552
797 260053.1075277493 260317.62102033358 41.25363918996993
798 260792.12406064727 5533.5805692843 25.262621896607513
799 261455.33540631988 12645.24677182949 38.01324750695904
800 262196.0113325283 4345.705298440788 18.92307187829701
801 262878.1626501248 17137.79189969815 39.73701383386334
802 263534.09746076324 116187.41252805482 45.418528573853614
803 264409.3058386014 15934.741286294828 41.53230573449812
804 265111.9993009732 12509.815482156639 38.89539624963481
805 265712.54709150054 6377.880362527713 27.43699933801376
806 266346.1802282498 8929.65534116542 29.592303293091867
807 267163.38374997827 71863.61530210295 42.82930280481062
808 267868.58537580224 20004.725245492828 44.97268583093369
809 268579.3731489346 268833.82537748077 45.935896890504004
810 269312.1264257595 4366.731432931756 20.205763833863408
811 270109.48636914947 270359.2512884304 44.66512586389267
812 270783.1452169583 6818.296698587287 28.46219922815047
813 271487.89384748193 73131.12953092373 42.4907484224864
814 272229.78809262963 9246.73059369838 32.05039884362897
815 272941.31496335723 38521.35637189665 45.39945508752549
816 273586.7998876736 4405.99182035241 24.471072213990333
817 274308.96499540063 12945.65179731167 38.044241922242236
818 275038.440016763 121320.39525892025 44.410017984254
819 275809.77657224395 5442.189959543088 21.211890237671998
820 276547.0383443997 8356.764105813856 31.027583139283273
821 277329.1275777981 277506.7398824856 44.60769781631789
822 277952.0819463894 30651.29020597257 42.1998777559825
823 278727.58367444726 279006.4523496792 44.5395429880161
824 279463.5293760464 21153.4402647189 44.79625608239853
825 280183.83481885644 4958.426741617058 20.866183297974732
826 280965.10150815704 12382.142333047752 38.14199353967388
827 281766.1760130093 281937.3653211758 44.56493783057956
828 282508.23953534814 5236.37273694787 27.184275644166103
829 283173.54419614526 283371.7415609524 44.559062515594555
830 283908.1070699856 16440.28165723599 42.285708444459054
831 284776.2820997403 76736.15911390104 43.03434278283797
832 285398.1516637967 4130.947379129267 20.491866128785283
833 285993.804720895 6566.870001809941 26.247695664919565
834 286720.8454885647 31622.972277658362 41.88278104577741
835 287618.92536069604 40964.68904401578 45.15865232263291
836 288291.1918440029 7113.05358793055 27.508524911744228
837 289092.485693948 6529.946116464482 30.212191598755933
838 289752.4879255459 127890.57233716731 44.76764585290634
839 290553.33354856225 290825.3190794156 43.71395380217201
840 291301.1524954007 4562.918929117059 20.3726568392345
841 292019.2740240262 16144.423274057282 38.20159818444926
842 292797.0788755581 129221.30563642268 45.161036508423926
843 293616.034773843 79255.94308759489 43.060568826539146
844 294379.7705450222 55290.20288373746 44.510153787476646
845 295084.78382016876 7563.22839643275 22.27046872888292
846 295759.9137106106 9117.7556791476 35.29527570520123
847 297433.2783498929 7650.880602853647 23.03340818200792
848 297659.12034894683 10023.698596017719 35.94139005456646
849 298074.7554578945 80465.93168165005 43.25368787561141
850 298749.9211111233 5573.022154825072 26.00648786340439
851 299578.6092558071 14246.64237882412 39.27209760461528
852 300467.1619215176 14621.66765119351 39.880064981324274
853 301174.5760717556 301380.99887754174 46.08647411271015
854 301920.35892392846 13097.069052713281 40.41173841272076
855 302701.2203016445 5671.3698187044665 26.809958474976646
856 303509.73585035064 22908.03411390103 45.37799741540635
857 304231.0927190945 304566.8051519558 45.812973942683676
858 304984.0257444546 6677.300719278204 23.243216531617293
859 305826.43964673736 306039.4594946072 45.906127487518326
860 306525.75233365747 9183.170584695694 33.47852613244733
861 307356.5719404385 9537.572649972795 34.091261880738344
862 307986.2854757473 136077.5015630889 45.38753415857041
863 308862.1757307217 309134.63333036157 45.720416444296724
864 309661.1140051052 5123.3599462679385 20.66114331994739
865 310386.7481031582 44037.279871957675 45.81668760095322
866 311113.69350339624 137521.13559629204 47.57621671472277
867 312079.9157896206 9420.985964792131 32.57730390344343
868 312692.98770810815 7974.951056497448 31.35898496423444
869 313460.38320447656 18690.461901681792 42.83407117639265
870 314148.8740720913 7033.071307199348 30.26225950036726
871 315061.3544264004 16529.404906289947 44.44816495691025
872 315737.3354711697 23810.915736215487 45.10858442102158
873 316638.7698927089 20710.811404245273 42.719630258423905
874 317397.6228513882 10918.72909452236 35.307196634156305
875 318302.4308958218 5819.928435342652 22.928504007203237
876 318998.75858213153 14811.856535928615 43.689993875367264
877 319801.5497007534 320079.40509702417 48.777846353394644
878 320504.98702909204 141751.19855787038 47.955302255494246
879 321264.62200071063 86776.21820356161 47.52614881311143
880 322231.7693510219 4896.936205880974 21.972445505005975
881 322883.46746350976 323300.4877844021 48.74953046277327
882 323660.0182333156 5610.236910837035 22.384909646851675
883 324523.83258725854 324808.8810720608 48.198325047781175
884 325354.49006940576 7843.742159860485 28.290537851197346
885 326227.7052679226 12721.438197152976 40.054110544068415
886 326959.19731046405 144560.93051816698 48.024443643433706
887 327714.75294019433 328034.16946317407 49.093678511761034
888 328508.70826627465 8141.040591256971 33.09705640588483
889 329411.61611463275 30890.795973794837 41.27004529748639
890 330075.2518453762 19279.250887887847 44.79387189660751
891 330935.82847501483 4942.612437265252 23.319510476929796
892 332017.90788556787 62746.979979532145 48.27239896569933
893 332570.18545057025 14998.745707528959 42.979506509644615
894 333379.4997015163 37013.78085996427 44.12629987512314
895 334122.42629911157 47656.92689801969 46.74890424524034
896 334898.9103117153 4528.255251901483 21.657732980591913
897 335738.0745687649 8889.384058969377 30.774859445435617
898 336547.33636762353 148779.15122892137 48.043517129761824
899 337264.0226164028 18081.080702798736 41.420249002320375
900 338027.00736905786 5385.608462350705 21.810320871216913
901 338932.08005811425 15688.767222421535 44.89162351403916
902 339699.5470800564 10966.868189828756 36.642340677125055
903 340568.5422697231 10284.90999128139 36.37769605432232
904 341372.3538198635 25970.74249173917 45.49720670495713
905 342124.3427076503 48831.41258146085 47.218588846070425
906 343029.68480970117 38456.92375089445 44.27650357995712
907 343828.3703603908 344216.50150205346 56.23319532190054
908 344741.408614175 65220.451144235514 45.81907178674424
909 345577.0108976528 22509.999064462558 52.706984536988415
910 346309.39939405175 6417.085913675176 22.91419889245714
911 347152.29967023584 347449.60525418964 56.23972017942747
912 347814.87443830224 5624.35844327722 28.02589322839461
913 348724.7393407986 20714.14211179532 49.347666757447385
914 349533.80563642236 154672.7249899077 47.93622876916612
915 350406.4152517483 13615.0667944125 41.97099592004499
916 351306.0210027858 66651.01507093228 45.23971463952744
917 352116.5273466274 33556.0772695712 50.56836988244739
918 352841.51294614526 5603.4682073763415 28.42405225549422
919 353951.40388395044 354076.70715238305 55.999421163812876
920 354470.7796850368 6786.994723337043 29.799727456910233
921 355508.15084363666 96320.36664869092 53.33640958581655
922 356245.68441297265 157687.73773099654 47.986296670777456
923 357103.89116193505 18530.587939279452 44.96791745935166
924 358100.3711500332 5943.1550779512945 23.262290017945418
925 358698.4584608242 9452.998427408098 35.073546426636774
926 359524.4334020778 159232.9237737822 48.27239896569933
927 360395.1595106289 23778.660086648833 53.15521146569936
928 361249.66361905786 7054.619578378548 31.39713193689069
929 362045.3117170498 362410.31387235376 56.345778335998595
930 362833.67135907855 8222.718028085585 33.05175687585553
931 363787.0595731899 7837.319163339488 30.97765944597923
932 364515.898016946 69220.2995100192 46.94440748010362
933 365705.02021695825 99556.05008985302 53.98967649255483
934 366680.9199133083 162211.1938276457 48.06259061608995
935 367130.0766744778 8224.990157144422 30.157355325562573
936 367940.6712331936 5146.686820047235 23.36957837854112
937 368941.1256590053 369209.1725149318 58.320642775529414
938 369683.6827078029 15751.68826963223 46.29829313073838
939 370487.41796399804 100448.54858304758 53.98729230676381
940 371569.64996244165 10930.075434701803 37.94410611901958
941 372418.56315519067 372790.93959714624 50.9355344942638
942 373091.9406690761 41755.26121045865 45.19203092370713
943 374150.4428663418 17015.692976968658 45.084742563111426
944 374795.5272474453 13023.812560098537 42.18080426965437
945 375619.30396939965 5642.590312021118 24.084834115845805
946 376622.27371122094 12037.24124814785 39.243487375123095
947 377452.6331701443 377751.92954923364 50.927249108042034
948 378200.50933744165 17712.898043649566 45.07759000573838
949 379185.726431863 19713.833121316802 49.76489927087513
950 379966.94066907617 6832.654265420783 29.706744211060624
951 380904.7816076443 103491.4586820771 46.31259824548447
952 381790.1871481106 6680.824545877325 29.194144265992264
953 382659.04882337304 383053.70548154565 51.03396526404788
954 383606.0045042202 12070.60077573574 41.85893918786726
955 384378.46162702295 55478.77767469205 45.723704355103614
956 385282.80475522723 73439.95073224821 48.117426889283315
957 386091.17010022845 9703.237799661518 35.934237497193415
958 386993.6249532864 171614.12456418746 48.72062589441027
959 387953.51245786395 37078.22063352384 50.48969175134388
960 388823.4780111477 5132.92053128991 22.482661264283312
961 389516.126898782 21638.586310403716 44.927386300904395
962 390406.6274442837 11904.012946145896 37.810591714722705
963 391408.4933080837 25743.307856576812 52.549628274781384
964 392374.43902875634 74707.63662244596 55.181769388062655
965 393111.3407888576 56610.91545011319 47.34733487878526
966 393949.6801176235 7425.236491220347 31.957415597779363
967 394908.6783209011 395252.940444009 59.0012350252697
968 395700.33052350726 7708.573130624645 25.51057721887314
969 396609.21314145776 11003.863600747945 37.01904203210552
970 397361.8982114956 23897.81453992642 47.37356092248643
971 398515.74638272973 398859.56266309466 59.18924500802897
972 399324.70777417865 6382.844237344608 24.12059690271104
973 400205.1208295986 38504.45487882413 51.00944425378528
974 401033.9901724025 177957.44159604775 52.50432874475209
975 401976.2275495693 6580.805567758429 24.297026651246195
976 402930.7911672756 14129.023341195947 44.989375131470794
977 403719.62049390527 404158.3774366543 53.00023938928334
978 404601.5951910183 45536.35337735929 52.5830068758556
979 405332.4768819973 23885.17835523404 49.586085336548955
980 406295.10143186303 6718.122748391974 24.19212247644151
981 407312.0258131191 28459.152964609042 50.78294660363879
982 408183.21206952777 181200.6805219816 52.89771940026967
983 409085.2735319301 409574.0292349025 53.56350656421411
984 410081.42211820337 9883.341578500627 38.196829812867236
985 410959.98504544946 59188.97130872525 46.75367261682237
986 411859.4525137111 12766.3061895541 40.919569986207094
987 412822.7732458278 12195.961264627342 41.339186685425844
988 413596.6227331325 9324.00682355678 32.12192441735944
989 414489.3405714199 18720.276144998446 47.85039808068956
990 415468.7402525112 6035.222796457155 24.87638379846299
991 416390.97192670556 416835.6440344021 53.76258607776393
992 417380.4233350918 8041.064528482312 34.367827432496156
993 418093.6119833156 113869.48564435732 54.88374616418569
994 419048.92661954614 17789.065627115142 48.3439245394298
995 419898.4525480434 60748.34802533902 46.97778608117784
996 421063.1296911403 20228.63128568448 50.47300245080677
997 421924.7625150844 422234.575537698 53.63284663430283
998 422664.91630460473 187740.94798948037 53.076533334595844
999 423584.69226743426 9550.928858774065 38.125304239136774
1000 424514.75837613794 6680.755404489386 24.037150400025492
1001 425488.9915266201 9480.523852365373 26.936320321900475
1002 426356.034068124 48303.661135690585 53.23627378259389
1003 427392.9617681667 18972.646979349032 52.19200040612904
1004 428585.35507108417 81937.92083646571 47.611979501587996
1005 429180.0210752651 16347.183970468412 49.48594953332629
1006 431181.3400068447 191240.99710370766 49.13547422204699
1007 431125.64542676654 18691.68975736417 50.68996335778919
1008 431979.1600980923 5563.459185617307 24.34471036706651
1009 432868.92393018457 433356.80940534326 59.51383497033806
1010 433880.870131509 26189.183978097808 58.41949369226189
1011 434724.50950528827 118303.3178129364 55.45595075402945
1012 435786.3042631313 9370.310095804094 34.6944608858653
1013 436634.9671163723 437204.97587110254 59.59217240671062
1014 437629.53260328027 9053.072718637344 26.685980813843837
1015 438737.2134008571 9487.144736307024 35.80549146447857
1016 439586.4103117153 34649.49348356046 46.207694070679786
1017 440539.076117532 29765.193251626868 52.130011575562634
1018 441376.48322965356 196335.1557531522 49.19269468103137
1019 442385.8592786953 442767.2193327114 51.50297071252552
1020 443380.644110696 6750.678805368292 30.698565500123117
1021 444187.60278608056 444657.68077756604 51.19389644690924
1022 445066.27061750134 18698.66588498868 53.76079465661733
1023 446164.7627630397 10896.703986184957 38.40902234826763
1024 446871.37582685193 7305.726794259896 23.33381559167589
This plot shows results (as time for a single transform for a given input vector length) for input vector lengths in the range $[8, 1024]$. Note that the plot is on a log-log scale. The thin lines show $C N \log N$ (black) and $C N^2$ (grey) for a few choices of constant $C$ to give some idea of the scaling of the different results. Let’s look at the DFT results first (the red line). After a slightly faster than $O(N^2)$ rise for small values of $N$, the scaling seems to settle down to something like an $O(N^2)$ increase with input vector length, which is what we expect. Next, the results for FFTW are show in blue. The times here scale more or less as $O(N \log N)$ (and perhaps even a little better than that!) with relatively little variability. It’s definitely the case that some input vector lengths do better and some worse in terms of scaling, but there are no gross discrepancies in performance as $N$ varies.
The results for our mixed-radix Haskell FFT code are shown in green. There are two main things we can draw from this:
The timing results for our FFT code give a sort of “wedge” shape. The bottom edge of the wedge seems to scale as $O(N \log N)$ while the top edge scales as $O(N^2)$, but there are results for different input vector lengths lying all over the space in between these two extremes. The reason for this is fairly obvious: we fall back on the simple $O(N^2)$ DFT algorithm for the prime factors at the “bottom” of our Fourier matrix decomposition. For prime input vector lengths, we just do a normal DFT, which gives us the $O(N^2)$ top edge of our wedge. For cases where we have a “good” prime factorisation, i.e. the last prime factor is small, we get close to $O(N \log N)$ scaling, which gives us the bottom edge of the wedge.
Even in the best cases, our code is something like 100 times slower than FFTW. That sounds bad, I know, but we’re not really comparing like with like–FFTW is probably one of the best optimised pieces of code in existence; our code is totally unoptimised. Of course, I use GHC’s -O2 flag to enable optimisation in the compiler, but we’ve not made any effort to optimise the algorithm itself (apart from the basic Cooley-Tukey divide and conquer approach to the FFT) and, in particular, we’ve not made any effort to look at allocation, unnecessary data copying, inefficiencies due to laziness, and so on.
Most of the rest of this series of articles is going to be about how we can optimise our code. We’re going to take an empirical measurement-driven approach, making modifications to the code based on some obvious first things to try, then on profiling information, and measuring performance at each step along the way to make sure that we’re actually making things better.
What’s a reasonable goal? I don’t yet know. I’d be very happy if we can get within a factor of ten of the performance of FFTW with a pure Haskell implementation.
What should we do first? It seems pretty obvious that those prime factors are something we need to deal with. No matter what other kinds of optimisation we do, as long as we have $O(N^2)$ behaviour in our code, we’re not going to get very far. There are a number of FFT algorithms for prime-length vectors that have $O(N \log N)$ scaling behaviour, and in the next article we’ll implement one of these, after spending a little bit of time thinking about how an efficient prime-length FFT might work.
After that, we’ll take a closer look at our code and do some profiling to get an idea of what we should look at next. Before doing any profiling at all, I can say that there is too much allocation and copying going on, and that we’ll probably end up rewriting things to use a mutable vector to do the Danielson-Lanczos steps in place, but there are probably other things that we can do as well.