Based on what we saw concerning the performance of our FFT code in the last article, we have a number of avenues of optimisation to explore. Now that we’ve got reasonable looking $O(N \log N)$ scaling for all input sizes, we’re going to try to make the basic Danielson-Lanczos step part of the algorithm faster, since this will provide benefits for all input sizes. We can do this by looking at the performance for a single input length (we’ll use $N=256$). We’ll follow the usual approach of profiling to find parts of the code to concentrate on, modifying the code, then looking at benchmarks to see if we’ve made a positive difference.
Once we’ve got some way with this “normal” kind of optimisation, there are some algorithm-specific things we can do: we can include more hard-coded base transforms for one thing, but we can also try to determine empirically what the best decomposition of our input vector length is–for example, for $N=256$, we could decompose as $2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$, using length-2 base transforms and seven Danielson-Lanczos steps to form the final transform, or as $16 \times 16$, using a length-16 base transform and a single Danielson-Lanczos step to form the final result.
Basic optimisation The first thing we need to do is set up some basic benchmarking code to run our $N=256$ test case, which we’re going to use to look at optimisations of the basic Danielson-Lanczos steps in our algorithm. The code to do this benchmarking is more or less identical to the earlier benchmarking code, but we’re also going to use this program:
module Main where
import Criterion.Main
import Data.Complex
import Data.Vector
import qualified Numeric.FFT as FFT
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 ))
main :: IO ()
main = run ( nf ( FFT . fftWith $ FFT . plan 256 ) $ tstvec 256 ) 1000
This does nothing but run the $N=256$ FFT calculation 1000 times–we use the run
and nf
functions from the Criterion package to make sure our test function really does get invoked 1000 times. This allows us to get memory usage information without any of the overhead associated with benchmarking. We’ll also use this code for profiling.
The first issue we want to look at is allocation. By running our benchmarking program as ./profile-256 +RTS -s
, we can get a report on total memory allocation and garbage collection statistics:
5,945,672,488 bytes allocated in the heap
7,590,713,336 bytes copied during GC
2,011,440 bytes maximum residency (2002 sample(s))
97,272 bytes maximum slop
6 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 9232 colls, 0 par 2.94s 2.95s 0.0003s 0.0010s
Gen 1 2002 colls, 0 par 1.98s 1.98s 0.0010s 0.0026s
INIT time 0.00s ( 0.00s elapsed)
MUT time 2.14s ( 2.14s elapsed)
GC time 4.92s ( 4.92s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 7.07s ( 7.07s elapsed)
%GC time 69.7% (69.7% elapsed)
Alloc rate 2,774,120,352 bytes per MUT second
Productivity 30.3% of total user, 30.3% of total elapsed For 1000 $N=256$ FFTs, this seems like a lot of allocation. The ideal would be to allocate only the amount of space needed for the output vector. In this case, for a Vector (Complex Double)
of length 256, this is 16,448 bytes, as reported by the recursiveSize
function from the ghc-datasize
package. So for 1000 samples, we’d hope to have only about 16,448,000 bytes of allocation–that’s actually pretty unrealistic since we’re almost certainly going to have to do some copying somewhere and there will be other overhead, but the numbers here give us a baseline to work from.
Profiling To get some sort of idea where to focus our optimisation efforts, we need a bit more information, which we can obtain from building a profiling version of our library and test program. This can end up being a bit inconvenient because of the way that GHC and Cabal manage profiled libraries, since you need to have installed profiling versions of all the libraries in the transitive dependencies of your code in order to profile. The easiest way to deal with this issue is to use sandboxes. I use hsenv
for this, but you could use the built-in sandboxes recently added to Cabal instead. Basically, you do something like this:
hsenv --name=profiling
source .hsenv_profiling/bin/activate
cabal install --only-dependencies -p --enable-executable-profiling This will give you a hsenv
sandbox with profiling versions of all dependent libraries installed.
To build our own library with profiling enabled, we add a ghc-prof-options
line to the Cabal file, setting a couple of profiling options (prof-all
and caf-all
). Then, if we build our library with the -p
option to Cabal, we’ll get a profiling version of the library built with the appropriate options as well as the “vanilla” library.
A second minor problem is that we really want to profile our library code, not just the code in the test program that we’re going to use. The simplest way to do this is to add the test program into our Cabal project. We add an Executable
section for the test program and this then gets built when we build the library. This isn’t very pretty, but it saves some messing around.
Once we have all this set up, we can build a profiling version of the library and test program (in the sandbox with the profiling versions of the dependencies installed) by doing:
cabal install -p --enable-executable-profiling and we can then run our profiling test program as:
./dist_profiling/build/profile-256/profile-256 +RTS -p The result of this is a file called profile-256.prof
that contains information about the amount of run time and memory allocation ascribed to different “cost centres” in our code (based on the profiling options we put in the Cabal file, there’s one cost centre for each top level function or constant definition, plus some others).
Aside from some header information, the contents of the profile file come in two parts–a kind of flat “Top Ten” of cost centres ordered by time spent in them, and a hierarchical call graph breakdown of runtime and allocation for each cost centre. For our profile-256
test program, the flat part of the profiling report looks like this:
COST CENTRE MODULE %time %alloc
dl.doone.mult Numeric.FFT.Execute 26.2 23.8
dl.ds Numeric.FFT.Execute 21.6 21.6
dl.d Numeric.FFT.Execute 19.7 24.7
dl.doone.single Numeric.FFT.Execute 14.0 13.9
dl.doone Numeric.FFT.Execute 5.7 5.7
slicevecs Numeric.FFT.Utils 2.7 3.3
dl Numeric.FFT.Execute 2.1 1.9
special2.\ Numeric.FFT.Special 1.5 0.8
special2 Numeric.FFT.Special 1.4 2.4
slicevecs.\ Numeric.FFT.Utils 1.2 0.9
execute.multBase Numeric.FFT.Execute 1.1 0.6 and the first half or so of the hierarchical report like this:
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 235 0 0.3 0.0 100.0 100.0
fftWith Numeric.FFT 471 0 0.0 0.0 99.7 100.0
execute Numeric.FFT.Execute 473 1000 0.0 0.0 99.7 100.0
execute.sign Numeric.FFT.Execute 528 1000 0.0 0.0 0.0 0.0
execute.bsize Numeric.FFT.Execute 503 1000 0.0 0.0 0.0 0.0
baseSize Numeric.FFT.Types 504 1000 0.0 0.0 0.0 0.0
execute.fullfft Numeric.FFT.Execute 489 1000 0.4 0.1 99.7 99.9
execute.recomb Numeric.FFT.Execute 490 0 0.0 0.0 99.4 99.8
dl Numeric.FFT.Execute 514 7000 2.1 1.9 93.5 95.3
dl.ws Numeric.FFT.Execute 527 7000 0.1 0.0 0.1 0.0
dl.ns Numeric.FFT.Execute 522 7000 0.0 0.0 0.0 0.0
dl.doone Numeric.FFT.Execute 516 127000 5.7 5.7 90.8 92.6
dl.doone.vs Numeric.FFT.Execute 523 127000 0.8 0.2 3.6 2.9
slicevecs Numeric.FFT.Utils 525 127000 1.9 2.3 2.8 2.7
slicevecs.\ Numeric.FFT.Utils 526 254000 0.8 0.4 0.8 0.4
dl.doone.single Numeric.FFT.Execute 517 254000 14.0 13.9 81.5 84.0
dl.doone.mult Numeric.FFT.Execute 518 508000 26.2 23.8 67.5 70.1
dl.d Numeric.FFT.Execute 520 508000 19.7 24.7 41.3 46.3
dl.ds Numeric.FFT.Execute 521 0 21.6 21.6 21.6 21.6
dl.ds Numeric.FFT.Execute 519 508000 0.0 0.0 0.0 0.0
slicevecs Numeric.FFT.Utils 515 7000 0.4 0.6 0.5 0.8
slicevecs.\ Numeric.FFT.Utils 524 127000 0.1 0.2 0.1 0.2
execute.multBase Numeric.FFT.Execute 502 1000 1.1 0.6 5.8 4.5
applyBase Numeric.FFT.Execute 512 128000 0.6 0.1 4.1 3.2
special2 Numeric.FFT.Special 513 128000 1.4 2.4 3.5 3.1
special2.b Numeric.FFT.Special 536 128000 0.4 0.0 0.4 0.0
special2.a Numeric.FFT.Special 534 128000 0.3 0.0 0.3 0.0
special2.\ Numeric.FFT.Special 533 256000 1.5 0.8 1.5 0.8
slicevecs Numeric.FFT.Utils 511 1000 0.4 0.5 0.6 0.7
slicevecs.\ Numeric.FFT.Utils 535 128000 0.3 0.2 0.3 0.2
execute.recomb Numeric.FFT.Execute 488 1000 0.0 0.0 0.0 0.0
execute.rescale Numeric.FFT.Execute 476 1000 0.0 0.0 0.0 0.0
execute.(...) Numeric.FFT.Execute 475 1000 0.0 0.0 0.0 0.0
execute.n Numeric.FFT.Execute 474 1000 0.0 0.0 0.0 0.0 It’s clear from this that the vast majority of the allocation (89.7%) and time (87.2%) is spent in the Danielson-Lanczos step function dl
in Numeric.FFT.Execute
. Here’s the code for this function from version pre-release-1
of the repository:
-- | Single Danielson-Lanczos step: process all duplicates and
-- concatenate into a single vector.
dl :: WMap -> Int -> ( Int , Int ) -> VCD -> VCD
dl wmap sign ( wfac , split ) h = concatMap doone $ slicevecs wfac h
where
-- Size of each diagonal sub-matrix.
ns = wfac ` div ` split
-- Roots of unity for the size of diagonal matrix we need.
ws = wmap IM .! ( sign * wfac )
-- Basic diagonal entries for a given column.
ds c = map (( ws ! ) . (` mod ` wfac ) . ( c * )) $ enumFromN 0 ns
-- Twiddled diagonal entries in row r, column c (both
-- zero-indexed), where each row and column if a wfac x wfac
-- matrix.
d r c = map (( ws ! (( ns * r * c ) ` mod ` wfac )) * ) ( ds c )
-- Process one duplicate by processing all rows and concatenating
-- the results into a single vector.
doone v = concatMap single $ enumFromN 0 split
where vs :: VVCD
vs = slicevecs ns v
-- Multiply a single block by its appropriate diagonal
-- elements.
mult :: Int -> Int -> VCD
mult r c = zipWith ( * ) ( d r c ) ( vs ! c )
-- Multiply all blocks by the corresponding diagonal
-- elements in a single row.
single :: Int -> VCD
single r = foldl1' ( zipWith ( + )) $ map ( mult r ) $ enumFromN 0 split
In particular, the mult
, ds
, d
and single
local functions defined within dl
take most of the time, and are responsible for a most of the allocation. It’s pretty clear what’s happening here: although the vector
package has rewrite rules to perform fusion to eliminate many intermediate vectors in chains of calls to vector transformation functions, we’re still ending up allocating a lot of temporary intermediate values. Starting from the top of the dl
function:
We generate a list of slices of the input vector by calling the slicevecs
utility function–this doesn’t do much allocation and doesn’t take much time because slices of vectors are handled just by recording an offset into the immutable array defining the vector to be sliced.
We do a concatMap
of the local doone
function across this list of slices–besides any allocation that doone
does, this will do more allocation for the final output vector. Moreover, concatMap
cannot be fused.
The doone
function also calls concatMap
(so again preventing fusion), evaluating the local function single
once for each of the sub-vectors to be processed here.
Finally, both single
and the function mult
that it calls allocate new vectors based on combinations of input vector elements and powers of the appropriate $\omega_N$.
So, what can we do about this? There’s no reason why we need to perform all this allocation. It seems as though it ought to be possible to either perform the Danielson-Lanczos steps in place on a single mutable vector or (more simply) to use two mutable vectors in a “ping-pong” fashion. We’ll start with the latter approach, since it means we don’t need to worry about the exact order in which the Danielson-Lanczos steps access input vector elements. If we do things this way, we should be able to get away with just two vector allocations, one for the initial permutation of the input vector elements, and one for the other “working” vector. Once we’ve finished the composition of the Danielson-Lanczos steps, we can freeze the final result as a return value (if we use unsafeFreeze
, this is an $O(1)$ operation). Another thing we can do is to use unboxed vectors, which both reduces the amount of allocation needed and speeds up access to vector elements. Below, I’ll describe a little how mutable and unboxed vectors work, then I’ll show the changes to our FFT algorithm needed to exploit these things. The code changes I’m going to describe here are included in the pre-release-2
version of the arb-fft
package on GitHub.
Mutable vectors A “normal” Vector
, as implemented by the Data.Vector
class, is immutable . This means that you allocate it once, setting its values somehow, and thereafter it always has the same value. Calculations on immmutable vectors are done by functions with types that are something like ... -> Vector a -> Vector a
that create new vectors from old, allocating new storage each time. This sounds like it would be horribly inefficient, but the vector
package uses GHC rewrite rules to implement vector fusion . This is a mechanism that allows intermediate vectors generated by chains of calls to vector transformation functions to be elided and for very efficient code to be produced.
In our case, the pattern of access to the input vectors to the execute
and dl
functions is not simple, and it’s hard to see how we might structure things so that creation of intermediate vectors could be avoided. Instead, we can fall back on mutable vectors. A mutable vector , as defined in Data.Vector.Mutable
, is a linear collection of elements providing a much reduced API compared to Data.Vector
‘s immutable vectors: you can create and initialise mutable vectors, read and write individual values, and that’s about it. There are functions to convert between immutable and mutable vectors (thaw
turns an immutable vector into a mutable vector, and freeze
goes the other way).
Now, the bad news. As soon as we introduce mutability, our code is going to become less readable and harder to reason about. This is pretty much unavoidable, since we’re going to be explicitly controlling the order of evaluation to control the sequence of mutations we perform on our working vectors. The vector
package provides a clean monadic interface for doing this, but it’s still going to be messier than pure functional code. This is something that often happens when we come to optimise Haskell code: in order to control allocation in the guts of an algorithm, we quite often need to switch over to writing mutating code that’s harder to understandNote that this is advice aimed at mortals. There are some people–I’m not one of them–who are skilled enough Haskell programmers that they can rewrite this sort of code to be more efficient without needing to drop into the kind of stateful computation using mutation that we’re going to use. For the moment, let’s mutate! . However, this is often less of a problem than you might think, because you almost never sit down to write that mutating code from nothing. It’s almost invariably a good idea to write pure code to start with, code that’s easier to understand and easier to reason about. Then you profile, figure out where in the code the slowdowns are, and attack those. You can use your pure code both as a template to guide the development of the mutating code, and as a comparison for testing the mutating code.
I worked this way for all of the changes I’m going to describe in this section: start from a known working code (tested using the QuickCheck tests I described above), make some changes, get the changes to compile, and retest. Writing code with mutation means that the compiler has fewer opportunities to protect you from yourself: the (slightly silly) Haskell adage that “if it compiles, it works” doesn’t apply so much here, so it’s important to test as you go.
Since we have to sequence modifications to mutable vectors explicitly, we need a monadic interface to control this sequencing. The vector
package provides two options–you can either do everything in the IO
monad, or you can use an ST
monad instance. We’ll take the second option, since this allows us to write functions that still have pure interfaces–the ST monad encapsulates the mutation and doesn’t allow any of that impurity to escape into the surrounding code. If you use the IO
monad, of course, all bets are off and you can do whatever you like, which makes things even harder to reason about.
Given these imports and type synonyms:
import Data.Vector
import qualified Data.Vector.Mutable as MV
import Data.Complex
type VCD = Vector ( Complex Double )
type MVCD s = MV . MVector s ( Complex Double )
type VVCD = Vector VCD
type VVVCD = Vector VVCD
a version of the dl
function using mutable vectors will have a type signature something like
dl :: WMap -> Int -> ( Int , Int , VVVCD , VVVCD ) -> MVCD s -> MVCD s -> ST s ()
dl wmap sign ( wfac , split , dmatp , dmatm ) mhin mhout = ...
Here, the first two arguments are the collected powers of $\omega_N$ and the direction of the transform and the four-element tuple gives the sizing information for the Danielson-Lanczos step and the entries in the diagonal matrices in the “$I+D$” matrixI moved the calculation of these out into the FFT planning stage on the basis of profiling information I collected, after I’d switched over to using mutable vectors, that indicated that a lot of time was being spent recalculating these diagonal matrix entries on each call to dl
. . The interesting types are those of mhin
, mhout
and the return type. Both mhin
and mhout
have type MVCD s
, or MV.Vector s (Complex Double)
showing them to be mutable vectors of complex values. The return type of dl
is ST s ()
, showing that it is a monadic computation in the ST
monad that doesn’t return a value. The type variable s
that appears in both the types for mhin
, mhout
and the return type is a kind of tag that prevents internal state from leaking from instances of the ST
monad. This type variable is never instantiated, but it serves to distinguish different invocations of runST
(which is used to evaluate ST s a
computations). This is the mechanism that allows the ST
monad to cleanly encapsulate stateful computation while maintaining a pure interface.
When I made the changes need to use mutable vectors in the FFT algorithm, I started by just trying to rewrite the dl
function to use mutable vectors. This allowed me to get some of the types right, to figure out that I needed to be able to slice up mutable vectors (the slicemvecs
function) and to get some sort of feeling for how the execute
driver function would need to interface with dl
if everything was rewritten to use mutable vectors from the top. Once a mutable vector-based version of dl
was working, I moved the allocation of vectors into execute
function and set things up to bounce back and forth between just two vector buffers.
Here’s part of the new dl
function to give an impression of what code using mutable vectors looks like (if you’re really interested in how this works, I’d recommend browsing through the pre-release-2
version of the code on GitHub, although what you’ll see there is a little different to the examples I’m showing here as it’s a bit further along in the optimisation process):
-- Multiply a single block by its appropriate diagonal
-- elements and accumulate the result.
mult :: VMVCD s -> MVCD s -> Int -> Bool -> Int -> ST s ()
mult vins vo r first c = do
let vi = vins V .! c
dvals = d r c
forM_ ( enumFromN 0 ns ) $ \ i -> do
xi <- MV . read vi i
xo <- if first then return 0 else MV . read vo i
MV . write vo i ( xo + xi * dvals ! i )
This code performs a single multiplication of blocks of the current input vector by the appropriate diagonal matrix elements in the Danielson-Lanczos $I+D$ matrix. The return type of this function is ST s ()
, i.e. a computation in the ST
monad tagged by a type s
with no return value. Take a look at lines 7-10 in this listing–these are the lines that do the actual computation. We loop over the number of entries we need to process (using the call to forM_
in line 7). Values are read from an input vector vi
(line 8) and accumulated into the output vector vo
(lines 9 and 10) using the read
and write
functions from Data.Vector.Mutable
. This looks (apart from syntax) exactly like code you might write in C to perform a similar task!
We certainly wouldn’t want to write code like this all the time, but here, since we’re using it down in the depths of our algorithm and we have clean pure code that we’ve already written that we can test it against if we need to, it’s not such a problem.
Here is the most important part of the new execute
function:
-- Apply Danielson-Lanczos steps and base transform to digit
-- reversal ordered input vector.
fullfft = runST $ do
mhin <- thaw $ case perm of
Nothing -> h
Just p -> backpermute h p
mhtmp <- MV . replicate n 0
multBase mhin mhtmp
mhr <- newSTRef ( mhtmp , mhin )
V . forM_ dlinfo $ \ dlstep -> do
( mh0 , mh1 ) <- readSTRef mhr
dl wmap sign dlstep mh0 mh1
writeSTRef mhr ( mh1 , mh0 )
mhs <- readSTRef mhr
unsafeFreeze $ fst mhs
-- Multiple base transform application for "bottom" of algorithm.
multBase :: MVCD s -> MVCD s -> ST s ()
multBase xmin xmout =
V . zipWithM_ ( applyBase wmap base sign )
( slicemvecs bsize xmin ) ( slicemvecs bsize xmout )
These illustrate a couple more features of working with mutable vectors in the ST
monad. First, in the multBase
function (lines 18-21), which applies the “base transform” at the “bottom” of the FFT algorithm to subvectors of the permuted input vector, we see how we can use monadic versions of common list and vector manipulation functions (here zipWithM_
, a monadic, void return value version of zipWith
) to compose simpler functions. The code here splits each of the xmin
and xmout
mutable vectors into subvectors (using the slicemvecs
function in Numeric.FFT.Utils
), then uses a partial application of applyBase
to zip the vectors of input and output subvectors together. The result is that applyBase
is applied to each of the input and output subvector pairs in turn.
The calculation of fullfft
(lines 3-15) demonstrates a couple more techniques:
We see (line 3) how the overall ST
monad computation is evaluated by calling runST
: fullfft
is a pure value, and the ST
monad allows us to strictly bound the part of our code where order-dependent stateful computations occur.
We see (lines 4-6) how the thaw
function is used to convert an immutable input vector h
into a mutable vector mhin
for further processing.
The final result of the computation is converted back to an immutable vector using the unsafeFreeze
function (line 15). Using unsafeFreeze
means that we promise that no further access will be made to the mutable version of our vector–this means that the already allocated storage for the mutable vector can be reused for its immutable counterpart, making unsafeFreeze
an $O(1)$ operation. Here, we can see immediately that no further use is made of the mutable version of the vector since the result of the call to unsafeFreeze
is returned as the overall result of the monadic computation we are in.
The “ping pong” between two mutable vectors used to evaluate the Danielson-Lanczos steps is handled by using a mutable reference (created by a call to newSTRef
at line 9). At each Danielson-Lanczos step, we read this references (line 11), call dl
(line 12), passing one of the vectors as input (penultimate argument) and one as output (last argument), then write the pair of vectors back to the mutable reference in the opposite order (line 13), achieving the desired alternation between vector buffers. After each Danielson-Lanczos step, the result so far is held in the first vector of the pair, so this is what’s extracted for the final return value in line 15.
We apply similar speedups to the Rader’s algorithm code for prime-length FFTs, although I won’t show that here since it’s not all that interesting. (We also fold the index permutation involved in the first step of Rader’s algorithm into the main input vector index permutation, since there’s little point in permuting the input then permuting it again!) In fact, a more important issue for speeding up Rader’s algorithm is to get transforms of lengths that are powers of two as fast as possible (recall that we pad the input to a power of two length to make the convolution in the Rader transform efficient). We’ll address this more directly in the next section.
Unboxing Until now, all the vectors we’ve been dealing with have been boxed . This means that there’s an extra level of indirection in each element in the vector allowing values of composite data types to be stored. However, all of our vectors are just plain Vector (Complex Double)
, so we might hope to be able to get away without that extra level of indirection.
In fact, apart from one small issue, getting this to work is very easy: just replace imports of Data.Vector
with Data.Vector.Unboxed
(and the equivalent for mutable vectors). This simplicity is the result of some very clever stuff: Data.Vector.Unboxed
is one of those pieces of the Haskell ecosystem that make you sit back and say “Wow!”. There’s some very smart type system stuff going on that allows the unboxed vector implementation to select an efficient specialised representation for every different element type. For our purposes, in particular, although Complex Double
is a composite type (and so not, on the face of it, a good candidate for unboxing), Data.Vector.Unboxed
has an instance of its Unbox
type class for Complex a
that leads to efficient memory layout and access of vectors of complex values. It’s really very neat, and is one of those things where the Haskell type system (and the implementor’s clever use of it!) allows you to write code at a high level while still maintaining an efficient low-level representation internally.
The “small issue” mentioned above is just that we sometimes want to have Vector
s of Vector
s, and a Vector
is not itself unboxable (because you can’t tell how much memory it occupies in advance without knowing the length of the vector). This just means that you need to use the “normal” boxed vectors in this case, by importing Data.Vector
qualified, as shown here (compare with the other listing of type synonyms above, which is without unboxing):
import Data.Vector.Unboxed
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed.Mutable as MV
import Data.Complex
type VCD = Vector ( Complex Double )
type MVCD s = MV . MVector s ( Complex Double )
type VVCD = V . Vector VCD
type VVVCD = V . Vector VVCD
type VMVCD a = V . Vector ( MVCD a )
type VI = Vector Int
More hard-coded base transforms for prime lengths Although they’re very tedious to write, the specialised transforms for small prime input lengths make a big difference to performance. I’ve converted “codelets” for all prime lengths up to 13 from the FFTW code.
The more I think about it, the more attractive is the idea of writing something comparable to FFTW’s genfft
in order to generate these “straight line” transforms programmatically. There are a number of reasons for this:
Copying the FFTW codelets by hand is not a very classy thing to do. It’s also very tedious involving boring editing (Emacs keyboard macros help, but it’s still dull).
If we have a programmatic way of generating straight line codelets, we can use it for other input length sizes. Most of FFTW is implemented in C, which isn’t an ideal language for the kind of algebraic metaprogramming that’s needed for this task, so the FFTW folks wrote genfft
in OCaml. In Haskell, we can do metaprogramming with Template Haskell, i.e. in Haskell itself, which is much nicer and means that, if we know our input length at compile time, we could provide a Template Haskell function to generate the optimum FFT decomposition with any necessary straight line code at the bottom generated automatically, allowing us to handle awkward prime input length factors efficiently (within reason, of course–if the straight line code gets too big, it won’t fit in the machine’s cache any more and a lot of the benefit of doing this would be lost).
We’ve only been specialising the primitive transforms at the bottom of the FFT decomposition. Let’s call those specialised bits of straight line code “bottomlets”. It’s also possible to write specialised “twiddlets” to do the Danielson-Lanczos $I+D$ matrix multiplication–there are often algebraic optimisations that could be done here to make things quicker. If we had a Template Haskell genfft
equivalent, we could extend it to generate these “twiddlets” as well as the “bottomlets”, giving us the capability to produce optimal code for all steps in the FFT decomposition.
This seems like it would be an interesting task, although probably quite a big piece of work. I’m going to leave it to one side for the moment, but will probably have a go at it at some point in the future.
Strictness/laziness One topic we’ve not looked at which usually turns up in discussions of Haskell optimisation is strictness (or, if you prefer, laziness). We can tell just from thinking about the basic DFT algorithm that any FFT computation is strict in its input vector, and strict in all of the elements of that input vector. There shouldn’t be any laziness going on anywhere once we get into executing the FFT. (It matters less at the planning stage, since we’ll only do that once.)
To some extent, the behaviour of the Vector
types helps us here. The data structures used to implement the various flavours of Vector
are all strict in the arrays that are used to implement them, and since we’re now using unboxed vectors, the arrays inside the vectors are necessarily strict in their contents.
I’m actually going to sidestep this issue for a little while, since we’ll be coming back to this kind of question when we do a final “kicking the tyres” examination of the whole FFT code after we’ve done the empirical optimisation described in the next section.
Profiling and benchmarking check Let’s see where we’ve got to in terms of performance. Here’s a view of the performance of the current optimised code (which is tagged pre-release-2
in the GitHub repository) in the same format as we’ve used previously:
Size FFT FFTW
8 5.007572446252795 0.8791249777589538
9 2.848346464806221 0.26211304761789656
10 2.318941285587859 0.275921030728833
11 0.5166611553175923 0.3138257236224645
12 5.322221410285708 0.3141506774669159
13 0.5888924282121375 0.3510386123549407
14 2.563849876613535 0.3777006394857711
15 3.0438069762633075 0.3816526948722123
16 9.392476663975932 0.41541233774600855
17 21.155691629486714 0.5541921443663212
18 6.660291168091356 0.475717090003201
19 69.64984625459664 0.5992282098758172
20 5.735583257462298 0.4875075175163472
21 3.476634118381854 0.5480598431411812
22 3.062660448813208 0.577231142491509
23 69.4821585206285 0.7666534556866154
24 10.021138029822978 0.5950064602800773
25 4.987665615828751 0.6291999565326564
26 3.3758259864973916 0.650288244927084
27 9.120353623515076 0.6753972970984096
28 6.360569742086915 0.6788467108220844
29 70.02336869518908 1.7255109335694967
30 7.38796655685355 0.7153962686285501
31 70.92432601466068 1.8518727804933244
32 17.56736270728564 0.717217976832759
33 4.1475860066875345 0.817646725900118
34 43.56262783843034 1.0278785504497494
35 5.647980092217851 0.8373959659570412
36 12.708588524972566 1.6897481467042625
37 135.14617595171174 2.157048561743323
38 140.64543293345537 1.1652593997710574
39 4.699784967096109 0.9358255431627627
40 10.98316492778914 1.8375676657472308
41 133.99785321738037 2.3787778403077753
42 8.245879439744938 0.9818458475635512
43 134.00309842612054 2.3382466818605097
44 7.487816777566775 1.0240262466845378
45 10.167156293810837 1.0351243551775837
46 141.47565940779356 1.4864354080079007
47 134.1392548193061 2.7745526816163717
48 18.876249303857072 1.9043248678956681
49 8.466387316951609 1.1412712608343452
50 11.249107652652619 1.1280293249408644
51 64.9399169797736 1.5164419431576106
52 8.103938607232914 1.195918598968394
53 135.0253772049669 2.9128354574952784
54 17.452912049330017 2.118901589087073
55 7.109444248691153 1.284627973451782
56 12.287259874077995 1.242910637404444
57 210.16785770299882 1.7004197261222642
58 142.79464396929 2.8270047690187154
59 128.6071103598392 3.4111302878175462
60 14.302251830796076 2.1522801901612922
61 128.43068061130407 3.420667030981609
62 143.11518450341538 2.950982430151529
63 11.580231768704168 1.4576101978555545
64 33.38998921762102 1.3428978791692916
65 7.922832198253197 1.4822704150090722
66 9.927279226975156 1.5272036559292157
67 269.0642636801512 4.00956092136247
68 88.31973275815955 1.9296214310041204
69 211.84552977127677 2.156026967851017
70 13.092977740436702 1.5443457416007287
71 268.6041158224852 4.486398079565597
72 24.357169586350548 2.493218758276526
73 269.1334050680907 5.025224068335129
74 273.16176020673333 3.5422605063234074
75 15.931497490439648 1.6474132840024291
76 283.1791552262646 2.1992644463557625
77 10.869750549119573 1.7786885550038518
78 10.907090811667087 1.754865563618682
79 269.1977780844481 4.929856636694504
80 21.0595020648147 2.700642922094887
81 25.291429546528622 1.8358364786356332
82 275.1191767411572 3.8927358176027043
83 269.93687567966293 5.394772865942552
84 16.157148127213016 2.7650159384523088
85 109.06770462613727 2.4105187315492764
86 274.6270807938916 4.131154396704269
87 216.54317050817465 3.752068855932783
88 14.93591089538986 1.9380788011170014
89 269.3122190024169 4.300545580636925
90 20.18132733269817 2.967671730688639
91 12.138709732590842 2.0705304654320535
92 285.6038721757274 2.790388624096958
93 215.9296400312866 4.083470680883956
94 267.77203498142075 4.638985970190597
95 354.0985177404116 2.7764444157611123
96 36.49260939858038 3.024892189673013
97 271.4556020285399 5.823926308325365
98 19.055833513592642 2.1706924186332626
99 14.315531191190221 2.277401440830796
100 22.401752640214575 3.070191719702311
101 270.2348989035399 6.56779227512224
102 130.85430425192627 2.8677027743904526
103 269.8367398764403 5.220844518843587
104 16.179720509408977 2.2562288873331227
105 18.97619463245332 2.3190693213852915
106 268.4491437460692 5.268411019018723
107 270.74749884860825 5.303928313707692
108 34.12642291791384 3.368214943579265
109 270.8476346518309 6.551102974585132
110 16.176002017481444 2.4390303217938967
111 403.44412741916466 4.894093849829269
112 23.998687395445106 3.477887489965984
113 270.0227063681395 5.246505530004047
114 427.98100450918787 3.310748808007613
115 362.841327036066 3.5560147181271238
116 290.52244746259265 4.77965293186052
117 15.885821619314692 2.6768902505754957
118 269.2502301718505 6.07188163059099
119 154.02845494183038 3.438418408174781
120 28.198138599676938 3.9261144186769243
121 20.658272070038983 2.8955864778687674
122 269.01657996433096 6.305531838110522
123 403.9734166647701 5.478219368628099
124 290.91440760663573 5.010918953589036
125 26.868205057075304 2.904834402785722
126 23.278188333919424 3.849820473364423
127 270.24920401828604 7.056550362280444
128 65.85682464161312 4.474477150610519
129 404.4645589377194 5.845383980444506
130 17.984780554949253 2.9115274683164323
131 530.7954114462641 8.382157662085133
132 19.90977786568624 4.004792549780439
133 498.98603100861806 3.955491676430136
134 545.0051587607172 7.650212624243336
135 29.490773549594813 3.971413948706221
136 176.90172595333073 4.653291084936692
137 526.6040128256586 8.23672232883318
138 431.4531737495034 4.229535273244939
139 527.7007382895258 6.720073036323162
140 26.11290808642526 4.011945107153487
141 405.4420751120358 6.357983925512866
142 545.8563130881098 7.764653542212087
143 23.499806649000433 3.4104094940928205
144 48.070571215434384 4.002408363989424
145 361.1402104741763 5.573586800268724
146 545.3246396567133 8.546666481665213
147 27.988050836924614 3.439149044330478
148 544.0729421164301 6.1648648764406
149 527.7150434042719 8.420304634741383
150 32.6235502482133 4.181222298315596
151 527.2882741476801 8.29155860202654
152 568.7957856981526 5.206422188452318
153 198.31852631605386 4.389369803999055
154 24.216443031024525 3.6226974480284895
155 360.1740191823672 6.002740242651537
156 22.421738526650827 4.557923653296066
157 528.9285939718989 6.9999109978110114
158 546.9816487814693 8.711175301245289
159 410.2533620383052 7.478551247290211
160 41.98175523607503 4.271821358374191
161 501.78585985586733 4.904873368594212
162 49.91805379305568 4.736737587622239
163 528.2443326498775 9.950951912573416
164 541.7936605002193 6.9659513022218515
165 23.951751659480802 3.6524842638340704
166 548.4073918844965 9.87704215305193
167 528.3158582236078 8.710141381895054
168 32.536025532990465 4.70812735813005
169 30.583663686577736 3.9929522632068037
170 221.58413399897856 4.7653225843969915
171 636.155285526599 5.037414153148122
172 552.1696370627193 7.230595925024585
173 529.0668767477778 8.974813581222579
174 434.93170081859523 6.539182045630054
175 31.654329284097702 4.0473246792971205
176 29.55071879234039 4.865483620337082
177 414.2444890524654 8.61819205539568
178 546.3212293173578 8.42462295895727
179 528.6949437643793 8.941270529190794
180 40.55092587002685 4.8392575766359105
181 530.003861763647 10.277585365942555
182 27.44521508114293 4.368563622374085
183 412.8306668783932 9.018735268286306
184 574.5543891120521 6.405667641333179
185 674.974278786352 7.483319618872242
186 437.7617293525309 7.051781990698413
187 250.63501917890133 5.612457911258127
188 551.2970250632076 8.174733498266773
189 34.77088158270195 5.456761696508958
190 710.4536673320196 5.535442890788748
191 530.2017491843013 10.034398415258961
192 71.54110343892043 4.93700919406755
193 530.0515454794673 10.27520118015154
194 548.1141370322017 10.458783486059742
195 26.939678800679893 4.387765751820426
196 38.50778428771132 5.5449765707765355
197 530.1588338400629 8.940446582630663
198 29.31031339174628 5.735711434057787
199 530.8168691183834 9.039114700265653
200 45.3035682873436 5.230264046362473
201 822.3193448569085 10.24182257907732
202 549.1584104086664 11.908368446997246
203 511.68897290314925 7.542924263647633
204 269.9426325517041 6.696538307837085
205 678.331212380102 8.498982765844898
206 549.5208066489008 12.041882851294119
207 650.4854342234985 6.4457248978018304
208 32.85356143531494 5.611733772924975
209 784.4441693808344 6.360656665527215
210 37.888864557524855 5.52113471286638
211 531.0028356100825 11.824921944311699
212 551.0180753256587 9.46934638278826
213 827.2665303732659 11.0929769064699
214 549.0606587912349 12.285069801977713
215 683.20925650852 9.049729683569508
216 69.18678439207494 5.72855887668474
217 509.56784227774216 8.208112099340992
218 550.5412381674556 11.820153572729666
219 822.240666725805 12.299374916723808
220 33.39952596078508 5.909756996801928
221 300.5574534780211 6.579027639019376
222 815.5864041830804 8.67779670017107
223 530.7501119162348 12.862042763403496
224 47.987583210016375 5.802468636206225
225 48.81675069246978 5.9359830405031
226 550.0238698508052 11.989430763891775
227 529.6748441244869 12.208775856665213
228 851.0535520102288 7.504777290991383
229 530.7548802878168 10.755879303861965
230 715.8082288290765 7.736043312719898
231 36.113523857808936 5.556013953150647
232 584.1412001777258 8.363084175757008
233 530.3829473044184 10.76132284310163
234 32.967666145342186 6.41043601291521
235 684.6493047262934 10.170297005346852
236 554.9639028097895 11.231259682348806
237 825.3544133688714 11.956052162817556
238 316.92846521202995 7.098368873999165
239 531.6394132162836 10.94512535088924
240 56.74814438181268 5.947903969458178
241 531.4248364950923 14.819459297827324
242 45.05385090121811 6.942109444311694
243 74.30661871027539 6.658391335180835
244 553.2520574118403 11.443452217749197
245 48.449565056752384 5.917062295704896
246 819.7706502463129 9.87704215305193
247 930.4993909384515 7.561014489495774
248 582.7241990892655 8.949593880346853
249 827.5526326681878 12.306421559836183
250 55.57284915892338 6.977872231176929
251 544.957475044897 12.437657692602714
252 47.653247002553144 6.484345772436695
253 790.0374692465571 8.260786243137863
254 551.966981270483 12.628392555883963
255 338.5667394048402 7.136254725275984
256 133.9713021758057 6.443814613989428
257 265.4593747641356 14.743165352514824
258 824.1909307028559 10.647134163549977
259 960.8429235007073 10.110692360571461
260 38.17705301501386 6.882504799536304
261 646.6501515890865 9.335831978491385
262 1070.8730977560783 15.837506630590996
263 1113.7312215353752 13.556709177967509
264 41.761869540795914 7.001714089087085
265 692.0760434653071 12.013272621801931
266 994.8867124106196 8.062480809517144
267 820.3142446066644 12.858033985307138
268 1084.7681325461176 13.748959877661308
269 1115.044907906225 13.410933246745412
270 60.258335356606906 7.168607094458179
271 1113.5547917868403 14.523820259741386
272 366.8318580037784 8.417920448950367
273 41.70407706428141 6.555238484580947
274 1070.7038205649164 14.88144812839373
275 41.269916831737454 6.543594202364736
276 850.8890431906489 9.199933388403494
277 1112.889603951147 13.438281898848711
278 1071.4095395590568 15.141324379614431
279 649.8497289206293 10.253743508032398
280 53.87676609506519 6.899194100073413
281 1116.1368649985102 13.489557153412289
282 824.229077675512 11.808232643774588
283 1115.3023999716547 13.816724513114734
284 1100.8923810507563 13.977841713598808
285 1053.394631722143 8.262890927551107
286 52.18165434808245 8.041219093969898
287 961.9158071066644 11.762933113745293
288 95.92198073700237 7.314042427710132
289 411.0854428793697 10.202976237738975
290 721.9665807272698 10.18221793430193
291 823.7474721457269 15.248612740210135
292 1084.055260994604 16.064004280737482
293 1114.3582623984125 16.29288611667498
294 58.436703879614264 7.798032143286306
295 695.7786839987544 13.565377571753103
296 1102.3300450827387 11.057214119604668
297 44.69494579017772 7.414842533366714
298 1076.280431130102 15.663461067846855
299 948.6978810812737 10.358647682837086
300 67.64232883215847 7.304505684546069
301 960.6140416647698 12.323216774633963
302 1074.1442006613518 15.386895516089043
303 822.5076955343989 17.494515755346857
304 1133.0192845846918 9.574250557592947
305 695.1683324362544 14.921979286840996
306 409.3875342536538 9.93664679782732
307 1115.4764455343989 18.35282264011248
308 50.97071950350483 8.203343727758961
309 823.0536740805414 17.422990181616388
310 721.1631101156976 11.011914589575367
311 1115.4454511191157 16.977744429583993
312 46.156345123609356 8.00784049289568
313 1118.7332433249262 17.167505470499897
314 1087.9033368613032 15.529946663549982
315 57.8432442644587 8.23195395725115
316 1087.1976178671623 15.50372061984881
317 1115.7625478293207 15.479878761938652
318 832.7143949057368 13.853864052465994
319 799.8007100607659 11.538819649389822
320 81.35918485976399 7.728890755346852
321 825.0444692160395 17.53027854221209
322 1002.897576668432 10.27248131503638
323 1231.9677632834223 11.683594198251258
324 105.00087971311237 8.286790230444508
325 48.09578856514707 7.920354514980184
326 1074.5423596884516 18.677071907690603
327 824.5485585715082 17.380074837378107
328 1096.715287544897 12.657002785376152
329 965.3061193014886 13.717965462378103
330 50.34720723543843 8.718327858618336
331 1117.321805336645 18.698529579809748
332 1087.5457089926508 17.60657248752459
333 1220.475987770727 12.709454872778496
334 1078.6813062216545 18.956021645239435
335 1353.0200284506598 17.25848136203631
336 66.04843788913321 8.246259071997242
337 1118.9239781882075 17.722495342699858
338 67.49890123430949 9.192780831030447
339 825.1660626913812 17.420605995825373
340 461.2920536526611 10.246590950659352
341 798.7588208700922 12.766675331762869
342 1263.8490956808835 10.964230873755056
343 71.1036697680515 8.366432382995864
344 1099.654988625219 13.44855246799334
345 1077.6203435446525 11.44822058933123
346 1072.1891683127192 19.44954810397967
347 1118.993119576147 18.681840279272638
348 868.2196897055413 12.051419594458181
349 1118.7713902975825 17.8035917193914
350 65.64325178812321 9.078339913061695
351 50.606034444911096 8.710575978655704
352 60.7733406711902 8.799390175512867
353 1118.428067543676 17.620816843788567
354 835.9974187399653 16.545609810522638
355 1354.3480199362552 17.380074837378107
356 1090.1158612753654 18.395737984350763
357 484.08328035757637 10.692962117766314
358 1074.342088082006 19.41140113132342
359 1118.6760228659416 17.74925189574807
360 83.49779951430504 9.056882240942556
361 1375.8867543722909 13.45337699379426
362 1078.1758588339592 19.79763922946795
363 68.72915317496609 9.948567726782398
364 58.400032831495274 9.488419869116385
365 1353.7138265158453 19.84532294528826
366 836.3669675375726 17.017678597143732
367 1119.7250646139887 20.38414893405778
368 1142.8635877157953 11.903600075415213
369 1238.2405560995844 14.514283516577324
370 1358.7301534201422 13.989762642553885
371 975.3435414816645 16.176061012915216
372 866.9679921652581 13.171986916235525
373 1119.7965901877192 19.38644786641983
374 518.3678720323811 12.311295845678885
375 84.1197541143213 9.55040869968279
376 1101.91042838352 15.456036904028498
377 953.0680936362054 13.553456642798027
378 71.51759091232505 9.824590065649586
379 1133.8942807699946 18.977479317358576
380 1410.6219571615977 11.67710242526873
381 829.3526929404046 18.19069800632342
382 1075.052575447729 18.882111885717947
383 1140.4150289084223 18.01647620134745
384 146.94074305986604 9.044961311987478
385 63.93059870494262 9.560106893211536
386 1079.782800057104 19.409016945532404
387 1230.735139229467 15.39404807346209
388 1092.9411214377192 19.480542519262873
389 1121.8398374106196 20.40799079196794
390 57.26432060556753 9.93664679782732
391 1253.5684865500239 15.221428922402168
392 79.21580183364098 9.905652382544117
393 1615.0110524679956 21.862344124487457
394 1076.4807027365473 19.3327230002199
395 1356.8490308310306 19.075230934790216
396 61.27759596598995 10.430173256567555
397 1125.9024899985102 19.426903336429284
398 1076.7715734030512 19.473389961889826
399 1486.4986699606702 12.315300540275565
400 93.1771707093837 9.390668251684742
401 1121.2771695639399 23.118810036352684
402 1630.3675931479272 19.456700661352716
403 953.4543317343499 14.986352303198416
404 1092.4523633505607 22.768334725073387
405 90.61417098404193 10.430173256567555
406 1015.1928227926994 14.46183142917498
407 1505.047635414772 15.804128029516777
408 541.8060078152588 12.707070686987478
409 1129.7910970236567 22.413091042212063
410 1354.111985542945 15.928105690649593
411 1632.8137677695092 21.82896552341324
412 1101.1093419577387 23.593263008764787
413 971.9961446310786 18.925027229956232
414 1269.9740689780026 13.86816916721209
415 1349.3459981467047 21.93625388400894
416 67.10601251264264 10.518388130835133
417 1630.930260994607 21.93625388400894
418 1560.4918759848406 13.882474281958183
419 1122.6170819784907 21.040553868489166
420 80.33763345197904 10.513619759253103
421 1124.4338315512446 22.150053796643498
422 1088.4230893637446 22.58952079074722
423 1220.03729758518 17.685250618628107
424 1112.0432179953364 18.11917243259295
425 569.471305005607 13.484315254858574
426 1636.6093915488061 20.491437294653483
427 974.0274709250239 19.895390846899588
428 1103.3528607870844 23.357228615454243
429 78.09769090131985 11.782006600073418
430 1357.6954167868412 16.781644203833185
431 1123.580293038061 21.88396163246766
432 142.05051309296064 10.544614174536305
433 1124.6197980429438 24.43249640720228
434 1017.4935620810297 15.649155953100763
435 1082.9513829733637 14.86475882785662
436 1106.480912544897 22.243813851049953
437 1385.7930463339608 17.413453438452326
438 1628.2647412802514 22.951917030981587
439 1123.129681923559 23.1349803732483
440 70.1049608311483 10.935620644262867
441 87.36742083363383 11.545972206762869
442 603.560761788061 14.244870522192556
443 1124.0022939230705 23.466382198199472
444 1635.9847348715602 16.428784706762873
445 1363.5462087179935 22.711114266089012
446 1089.088277199438 24.12493644016127
447 1630.8325093771753 23.044900276831196
448 98.74008834198281 10.606603005102713
449 1123.3299535300043 23.379313567100652
450 100.88299348772988 11.071519234350758
451 1500.1982015158462 18.138245918921076
452 1150.3237050558832 22.503690102270657
453 1637.2721951987085 22.651509621313625
454 1115.9342092062736 23.226098396948384
455 72.6968725626709 11.71035618654319
456 1756.383733132059 14.333085396460135
457 1161.1431401755121 24.079636910131974
458 1117.6245969321037 24.198846199682755
459 621.0288187755001 14.936284401587088
460 1461.0260289694593 14.800385811499197
461 1190.3446477438715 23.263813466543247
462 76.35276492552028 11.967973091772636
463 1133.660630562475 22.556904655180855
464 1159.6387189413813 15.720681526831228
465 1083.5688870932365 16.850785591772638
466 1089.6032613302973 23.717240669897603
467 1125.8142751242426 23.531271904867616
468 68.93631242925214 11.786774971655447
469 1892.2322553183387 23.4883588339601
470 1380.5526059653084 19.113377907446466
471 1637.813405373269 22.975758888891747
472 1113.962487557104 21.13039908664567
473 1508.6835187460708 19.4853108908449
474 1662.7043050314724 23.145036080053853
475 1791.1618512656041 15.475110390356619
476 650.3027242209223 15.377358772924978
477 1267.279939034155 21.30206046359879
478 1137.2726720358635 23.79830298679213
479 1135.9089177634028 23.52875276516391
480 115.25798531902302 11.72478614108904
481 1853.9446157004188 18.78436026828631
482 1099.645451882055 28.764561989477645
483 1605.5291455771262 17.518409517355806
484 103.96514966906534 14.47852072971209
485 1480.1805776144788 26.645020821264765
486 166.08736864956364 13.470010140112478
487 1256.191090920141 29.677705147436622
488 1154.915646889379 22.656277992895657
489 1636.6332334067163 27.61061606662609
490 100.14620776196102 12.919263222387869
491 1127.2996228720451 26.521046873853077
492 1641.4039891745385 18.896417000464044
493 1279.1484159018307 20.276860573462084
494 1850.2729695822547 16.295270302465998
495 78.35008957404266 13.222054817846853
496 1159.896211006811 17.06297812717303
497 1892.3896115805458 23.8245290304933
498 1632.000760414773 27.808503487280387
499 1148.9647191550043 25.81635595590872
500 119.90454668154965 13.214902260473806
501 1783.4466260458776 31.129674294165135
502 1191.8276113058832 26.954964974096796
503 1223.3370107199457 26.928738930395625
504 102.97964523945538 13.05993018405779
505 1457.0921224142835 31.26557288425302
506 1570.5674451376728 17.554120400122248
507 101.82196532509147 13.37225852268084
508 1122.3238271261955 24.19169364230971
509 1176.0681432272697 24.440649992862006
510 686.5351956869869 15.589551308325369
511 1911.0792439963175 28.313950874975692
512 278.93816554120605 12.282685616186699
513 1895.276860573466 16.416863777807794
514 576.1354726340082 28.397397377661243
515 1376.532868721656 28.483228066137805
516 1632.3703092123803 21.583394386938632
517 1556.1145108725361 21.826581337622223
518 1924.554662087138 20.2792447592531
519 1634.1989797140893 28.36640296237804
520 82.57766274469242 13.86101660983904
521 2712.079839089092 30.73151526706553
522 1384.5794957663338 18.7676709677492
523 2643.8086789633594 28.854052139470326
524 2181.040601113018 28.88138709323741
525 101.33554967386384 13.079003670385916
526 2318.0764478232236 28.414086678198352
527 1262.4448102499748 22.010163643530426
528 85.36350436863442 13.048009255102714
529 1688.7443822409452 22.96622214572768
530 1372.010068276099 22.730187752417137
531 1238.9510434653068 24.272755959204236
532 2004.188851692851 17.613725044897638
533 1797.3511975790807 21.673993446997223
534 1636.893109657937 26.437596657446406
535 1379.6346944357674 28.797940590551864
536 2170.812444069561 25.669888832739385
537 1632.8185361410913 28.516606667212024
538 2337.5647824789853 28.609589913061633
539 94.9255744752648 13.513767633885383
540 124.71454900290287 14.917210915258963
541 2560.891465523419 31.065301277807716
542 2323.1094640280576 28.54044852512218
543 1638.4499829794702 28.368787148169055
544 713.2738393332269 16.72442374484881
545 1383.5161489035409 27.30544028537609
546 87.24906303900842 13.996915199926931
547 2541.0002034689755 32.04758115448898
548 2169.6561139609184 28.216199257544055
549 1237.9377645041252 25.445775368383917
550 90.7633528949655 13.80141196506365
551 1419.4172185446544 22.804097511938622
552 1693.9991277243437 18.033341744116388
553 1898.3619969870401 27.238683083227656
554 2335.2640431906552 28.91953406589366
555 2042.438344338115 20.496205666235518
556 2223.853425362285 29.918507912329204
557 2543.234185555157 30.50122213020974
558 1292.3925679709228 21.490411141089023
559 1842.8939145590614 22.60621009128433
560 111.87417544908337 13.620213844946464
561 760.9289449240472 18.021420815161306
562 2308.556393959698 28.945760109594833
563 2553.0308049704404 30.409498914544074
564 1662.4372762228786 22.789792397192528
565 1381.3203137900155 27.927712776831164
566 2307.5741094137993 29.11026892917491
567 106.65292178413692 14.681176521948416
568 2168.263749458965 26.56634269016125
569 2544.5478719260063 30.81257758396006
570 2111.951665260967 17.718629219702326
571 2590.1454251791797 28.938948071631422
572 110.60093477190951 15.734986641577326
573 1632.3560040976342 27.620152809790156
574 1928.0498784567667 22.44646964328628
575 1785.6877606894323 18.889264443090994
576 194.61282040087545 14.201955177954275
577 2563.063458779034 31.430081703833107
578 820.4763692404534 21.600083687475742
579 1633.3597463156518 28.27341971652843
580 1438.1855290915294 19.29696021335467
581 1902.2196095969034 30.55508551853037
582 1636.7071431662378 29.248551705053817
583 1546.012715676003 26.335076668432734
584 2173.6400884177056 30.69098410861826
585 87.45631690384174 15.849427559546074
586 2523.0830472494936 35.45220313327645
587 2756.2468808676554 30.913038953606563
588 124.6432618477515 16.14029822604998
589 1554.5194905783467 26.07758460300305
590 1495.2319425131607 28.08983741062023
591 1721.0953992392365 31.134442665747166
592 2213.9089864279595 21.435574867895664
593 2551.0924619223447 30.65536807424255
594 94.19234564507397 15.284375527075369
595 790.6883519675043 18.43865332858904
596 2179.5743268515434 30.083016731909282
597 1651.9707006003202 30.199841835669044
598 1970.903233864482 20.38414893405778
599 2543.8636106039853 32.169206842247924
600 142.106938823348 14.426068642309744
601 2544.86020026463 36.81118903415535
602 1916.7035382773233 24.24891410129408
603 2518.7557500388 30.669526436499115
604 2179.838971474346 29.76115165012217
605 127.3269013741186 16.95330558078631
606 1774.839715340311 34.73694739597176
607 2570.8764356161923 35.49042645461703
608 2356.2162679221005 18.421964028051935
609 1525.294141152077 21.557168343237464
610 1386.6084378744881 27.808503487280387
611 1810.380772926981 25.677041390112432
612 805.0649922873284 18.72475562351092
613 2538.196400978741 37.27372107761238
614 2311.8990224387016 36.060170509985426
615 2043.3419507529097 23.595647194555806
616 105.85302745125121 15.49179969089373
617 2537.2165006186333 36.15447575492522
618 1666.8504041220488 33.71890006320809
619 2541.243390419659 39.038265626212294
620 1480.640725472145 21.28060279147965
621 1899.5087903525186 21.64538321750504
622 2313.0672734762998 36.21514258640144
623 1912.3309415366007 33.50432334201669
624 98.45838762082896 15.336827614477713
625 148.40198404022624 17.11066184299334
626 2321.7647832419243 36.25567374484871
627 2345.0368207480283 20.603494026831218
628 2205.6859296347466 30.18315253513194
629 2337.4121945883603 27.460412361792105
630 129.48816579367434 15.429810860327322
631 2539.69605384129 31.942681648901463
632 2164.737538674053 30.309514382055767
633 1633.3406728293237 33.74989447849129
634 2327.219800331768 30.574159004858497
635 1381.587342598609 29.682473519018654
636 1653.1461041952907 26.978806832006956
637 109.66136688810013 16.246868803032807
638 1607.4269574667749 23.79115042941908
639 2466.885403969464 30.676678993872162
640 185.20704857738974 15.799359657934748
641 2720.0430196310836 35.840825417211995
642 1681.3462537314238 34.05745444553231
643 2572.9959767844052 37.855606878898556
644 2090.0505345846973 21.175698616674968
645 2074.467496254619 25.028542854956182
646 2468.3039945151186 24.53024802463392
647 2548.145608284649 35.022444843637736
648 207.59055286291093 16.044930794409357
649 1537.6704495932393 30.133084633520607
650 101.51599481524453 16.078309395483576
651 1525.6970685507588 23.431138374975728
652 2206.7778867270317 35.33537802951668
653 2574.0903180624814 37.0329183127198
654 1657.3565763022243 36.07447562473152
655 2718.633965828594 36.61330161350105
656 2169.7014134909477 24.747208931616342
657 2482.4660581137514 35.64293799655769
658 1931.8526547934366 27.30544028537609
659 2540.6902593161435 36.15693006382772
660 107.17068746508582 16.514615395239435
661 2552.7303975607724 36.32319196119529
662 2314.8649495627255 36.88986716525886
663 902.8142255331782 21.273450234106605
664 2186.3263410116997 35.595254280737386
665 2524.2703717734194 20.908669808081218
666 2452.081994393048 25.20258841770032
667 1747.4883359457797 29.482201912573345
668 2221.8411725546684 35.63816962497567
669 1639.6873754050073 36.517934181860426
670 2693.9290326620894 32.221631386450284
671 1533.219174721413 32.61740622775888
672 139.02021295257978 16.621903755835138
673 2539.6388333823056 38.20330675739745
674 2329.5181554343076 37.01622901218269
675 153.01905028255914 16.829327919653494
676 142.26191089976405 17.632798531225763
677 2544.786290505108 37.204579689672926
678 1703.4142774130644 33.26352057712411
679 1919.1973966147257 34.87761435764168
680 901.5696805502679 20.613030769995284
681 1651.7942708517849 34.1480535055909
682 1603.7600797201928 25.083379128149538
683 2585.9468740012016 36.354326622701485
684 2542.2423642660947 22.243813851049953
685 2783.1238072897745 35.476044991186605
686 150.32231324012324 17.23702368991717
687 1637.3294156576928 34.43415580051278
688 2170.037583687481 26.497201302221796
689 1864.3706601645301 31.580285408667084
690 2129.8878949667774 22.358254769018703
691 2540.2968686606255 36.902338739077535
692 2212.2185987021294 36.10308585422371
693 116.56278517919708 18.09294638889178
694 2324.330167153057 36.67767462985847
695 2698.5400479819136 35.54518637912605
696 1745.9862988974396 23.826913216284318
697 2397.8703778769345 32.71515784519052
698 2368.1395810629692 36.74920020358894
699 1737.1648114706818 34.663037636450284
700 140.43165094086103 17.222718575171076
701 2547.8761952902646 36.70047498046061
702 107.14871921129041 17.766312935522638
703 2638.196305611309 31.22504172580576
704 124.44775861288822 17.506436684301935
705 2057.9212468649707 28.487996437719836
706 2313.9875691916313 37.51929221408698
707 1923.7201970602825 39.23352179782721
708 1663.9512342001738 31.678037026098725
709 2545.337037422833 36.681545990241055
710 2701.5107434775196 33.38272986667489
711 2426.242188790021 34.57959113376473
712 2177.368954994854 35.154179909399495
713 1739.2199796225373 31.072453835180763
714 953.1276982809808 23.564652779272603
715 140.2387968013211 18.965558388403498
716 2213.1102841879692 37.35001502292488
717 1638.9935773398217 34.99205527561043
718 2319.2041677023735 37.20934806125496
719 2528.7764829184384 37.58219023481076
720 170.27429692181096 17.079667427710138
721 1937.9585546042279 39.00940833347175
722 2746.6243070151168 27.851418831518668
723 1641.6590970541772 42.37349448459479
724 2235.5883878256645 37.6885694052491
725 1811.0435765768834 25.233582832983526
726 144.0730973723389 19.192056038549982
727 2528.9791387106748 46.51005683200689
728 120.83261769797117 17.980889656714044
729 240.32979478083894 19.79525504367693
730 2710.3679936911426 37.84830985324714
731 2353.5984319235654 33.64022193210458
732 1661.9056027914824 34.66780600803231
733 2562.9561704184384 40.237264015844794
734 2325.0025075461235 40.49237189548346
735 152.40184418590997 18.35282264011248
736 2304.4222157980766 23.407296517065568
737 2989.3868726279084 37.44299826877449
738 2442.161397316632 30.085400917700294
739 2527.582005837139 39.79634713673376
740 2715.9016889120894 26.90012870090344
741 2782.7971738364054 24.334744789770642
742 1938.0253118063763 32.417134621313565
743 2543.7515538718076 39.629377222143596
744 1735.712842323953 26.220635750463988
745 2702.557401039775 38.12487540500495
746 2325.6414693381157 40.65688071506354
747 2427.019433357892 39.27882132785651
748 1010.4554456259515 25.209740975073366
749 1944.7749417807413 40.18719611423346
750 173.4981304376709 18.007115700415216
751 2552.437142708477 41.04073462741706
752 2182.0205014731255 30.05679068820811
753 1645.6478398825466 38.787679054907294
754 1904.875592568095 27.181462624243277
755 2708.808736183818 36.8040364767823
756 150.61503827335338 18.59839377658709
757 2533.9358609701962 38.98611156203383
758 2314.9460118796196 37.199811318090894
759 2371.9375890280576 26.087121346167116
760 2823.3402532126256 23.36199698703627
761 2538.6756223227353 39.29143811357187
762 1661.6624158407985 35.49273429172371
763 1941.3226407553507 38.5587972189698
764 2212.1995252158013 36.66098532932136
765 1014.0221875693109 23.722009041479634
766 2320.758656838116 37.254647591284254
767 1829.294518807108 35.619096138647535
768 306.4088414556212 18.16685614841326
769 2530.993775704083 41.152791359594794
770 133.83072179343017 19.375638344458185
771 856.7732137228753 42.55230841892096
772 2217.418507912334 37.4906819845948
773 2530.977086403546 39.51055247868811
774 2444.326238014874 30.91986594455576
775 1808.54733405369 27.503327706030387
776 2183.610753395733 38.32753119724128
777 2858.4283154990026 31.663731911352627
778 2319.788293221173 40.34216819064948
779 2637.945966103252 35.52611289279793
780 119.92519658591064 19.327954628637873
781 3005.9188169028107 37.84830985324714
782 2494.8685925986147 31.029538490942482
783 1953.071908333476 27.78943000095226
784 166.02269760998234 19.0728467489992
785 2736.0957425619918 37.86976752536628
786 3257.223920204811 42.92900977390142
787 2573.863820412335 41.46367166368733
788 2217.499570229229 38.563565590551825
789 3455.5810254599373 42.251901009253
790 2712.261037209209 38.64462790744635
791 1954.2449277426556 39.21921668308112
792 127.4806813576392 19.563989021948416
793 1831.5261167074987 37.40008292453621
794 2321.2807935263486 40.351704933813544
795 2071.6517728354297 35.290078499487386
796 2212.6978200461235 38.217858650854566
797 2527.8847974325986 41.23534613776774
798 2968.0627149130646 25.195435860327272
799 2377.6095670248837 37.903146126440504
800 192.05322665523508 18.719987251928888
801 2437.2905057455873 40.54959235446784
802 2325.224236824688 45.91401038425299
803 3033.186749794656 41.903809883764715
804 3248.3094495322034 39.11431250827643
805 2503.7282269980287 26.58303199069836
806 1910.9028142477823 29.432134010962017
807 3436.848477699927 42.69297538059087
808 2184.1448110129204 44.161633827856505
809 2536.80880484837 47.14186606662604
810 189.90030688594808 20.064668038061694
811 2592.2148984457817 45.05808768527838
812 2026.6478818442185 28.466538765600692
813 3444.8593419577396 42.559460976294005
814 3007.02031073826 31.937913277319428
815 2741.9608396078906 44.14494452731939
816 1069.9027341391352 24.587468483618295
817 2643.2603162314263 37.98182425754401
818 2326.3042729880185 44.47634635227057
819 134.43303949066575 21.247224190405433
820 2722.1649449850875 31.05814872043467
821 2545.859174111065 44.82558318783366
822 3246.6119092490003 42.00632987277839
823 2609.3571942831836 44.48394534767284
824 2241.2532132651177 43.95182547824712
825 141.13816466359867 22.30103431003433
826 1953.067139961894 38.04619727390144
827 2550.381974556622 44.59343413433069
828 2571.6274541403623 26.79522452609875
829 2560.1261418845024 44.560408745966264
830 2711.1786168600875 42.17322287814948
831 3441.6001599814213 42.72873816745611
832 138.69543386593705 20.348386147192553
833 1142.9661077048088 26.27801541354715
834 3268.5797971274187 42.20183310764167
835 2747.4230092551074 47.32306418674322
836 3148.545579292946 27.18623099582531
837 1948.830441811259 30.57654319064951
838 2352.334813454327 44.504956581762755
839 2543.5798924948544 43.95067530570838
840 169.37992922695622 20.379380562475752
841 2250.880555489239 37.707642891577215
842 2328.545407631573 44.38336310642095
843 3446.3828366781986 43.2604115988526
844 2211.4437383200493 44.34044776218268
845 175.04151282565945 22.193745949438625
846 2463.063554146466 35.030202248266676
847 171.2387364889896 22.68727240817886
848 2207.938985207256 35.82175193088386
849 3443.3263104941166 43.02676139133306
850 1126.7035764242912 25.66750464694837
851 3234.528855660133 39.250211098364325
852 3257.4480336691663 39.79142127292487
853 2547.456578591046 46.194547347763866
854 1946.1386960532022 39.82241568820807
855 3178.5553258444597 26.73561988132336
856 2204.2458814169727 44.907883980444396
857 2543.7753957297177 45.86605952766838
858 165.97739807995302 22.470311501196438
859 2554.373101570782 45.804688819344086
860 2734.603242256816 33.28259406345224
861 2877.4779599692174 34.21957907932137
862 2343.012647011456 45.15822348850103
863 2545.5802243735166 45.8216430294135
864 293.38343843285503 20.460442879370284
865 2744.7002690817676 45.949773171118224
866 2324.578122475323 47.86904273288579
867 1216.2249845053461 32.574490883520596
868 2059.9406522299605 31.103448250463966
869 3007.5805943991486 42.33057914035651
870 2169.0910619284477 30.249909737280376
871 3543.7434476401127 44.21885428684087
872 2204.0336888815727 43.22703299777837
873 2440.175370552716 43.78254828708502
874 2773.846940376933 34.88476691501473
875 168.96422324436065 22.923306801489403
876 3260.769204476051 44.729070046118224
877 2543.556050636944 48.236207344702194
878 2322.3679822470517 48.42455802219243
879 3450.581387856177 46.93444190280766
880 155.8287227792399 21.414117195776523
881 2551.924542763409 47.521658286779804
882 185.50080290558384 22.215203621557766
883 2547.196702339825 47.329181133882045
884 1208.4120076681877 28.020696022680774
885 2083.274678566631 39.7651952292237
886 2338.764027931866 48.579530098608444
887 2545.484856941876 48.37125372346287
888 3248.681382515602 34.00261817233895
889 1954.0518086935836 40.76893744724128
890 2715.870694496806 44.06388221042486
891 138.85252521861167 22.980527260473778
892 2222.7519315268364 48.02401480930181
893 2689.461068489726 42.75496421115729
894 3261.958913185768 43.7038701559815
895 2747.699574806865 46.77231726901861
896 204.77363735082602 21.309213020971836
897 2819.1726964499303 30.80304084079599
898 2321.16635260838 48.74165473239751
899 2238.9548581625786 40.988282540014715
900 210.14918158096918 21.96486411350113
901 2405.797795632062 44.92218909519049
902 3019.0461438681423 36.577538826635816
903 2865.2828496481725 36.19845328586433
904 2211.6201680685845 43.906525948217826
905 2735.2565091635543 46.96782050388188
906 3250.4289907004163 43.80639014499518
907 2543.842152931866 56.48549018161625
908 2221.4477818991504 46.31932196872564
909 2443.5132306601377 51.764802315405326
910 153.552213830075 22.81125006931167
911 2540.5305188681455 56.10939933398328
912 3388.578252175025 27.70598349826672
913 3010.0291532065216 48.93477378146977
914 2321.502522804913 47.14901862399907
915 2078.8663190390425 41.70115409152839
916 2222.1678060080376 48.17183432834478
917 3807.226971962621 50.61800894992681
918 1207.4130338217524 28.92191825168468
919 2547.0512670065727 56.18274004585073
920 2856.358842232401 29.827908852270607
921 3448.6621182944095 53.65307746188969
922 2341.2435811545224 47.21100745456548
923 3561.333970406226 44.26415381687017
924 160.70387713345028 23.33100257175307
925 3396.5915006186287 34.772710182836995
926 2322.5134175803037 47.66638694064947
927 2462.8823560263486 50.61800894992681
928 2320.5226224448056 31.08675894992685
929 2546.874837258038 55.46393521710652
930 2179.6959203268852 32.755689003637784
931 3514.634923317603 29.78499350803233
932 2228.319005348858 45.91401038425299
933 3444.7425168539794 53.97255835788578
934 2330.514745094952 48.016862251928764
935 1270.81330237644 29.78260932224131
936 146.30125144880918 23.073510506323387
937 2547.5519460226865 58.551564188553165
938 3794.414357521703 47.27776465671392
939 3438.109711983374 54.16329322116703
940 2752.355889656718 37.72433219211433
941 2534.2934888388486 50.813512184790085
942 3280.2170079733655 44.521645882299865
943 3295.108632424049 44.65754447238775
944 2252.6996892477837 42.03494010227057
945 183.93950181043877 25.462464668921022
946 3027.6077550436794 38.86158881442878
947 2541.150407173809 51.180623220545876
948 3286.1893933798597 45.15583930271002
949 3567.404107430151 51.09246192233892
950 3563.7729924704345 29.403523781469833
951 3459.801034310035 45.613602974585014
952 1274.5946210409907 29.24139914768077
953 2530.512170174298 51.180097633706644
954 2481.40747962254 41.57002387302253
955 2760.469273903544 46.05706153171393
956 2221.8173306967583 46.32170615451666
957 2407.57878241795 34.62727484958505
958 2379.1092198874326 48.26243338840337
959 3798.0001729513906 49.95282111423345
960 235.2467106743936 22.708730080298
961 2398.7572949911923 44.41435752170416
962 3579.7470372702387 37.38100943820808
963 2477.9217999960756 51.39286933200689
964 2245.301560738262 56.084946968725625
965 2769.7318357016397 47.036961891821335
966 3009.726361611062 31.945065834692475
967 2529.1221898581357 58.941201546362336
968 196.87064434496725 24.902181008032358
969 3668.27423987644 37.20696387546394
970 2725.4956525351367 47.745065071752975
971 2533.0060285116997 58.97405394384643
972 312.4802869345457 24.23222480075697
973 3799.6881764914297 49.92182669895024
974 2379.030541756329 55.38876471774906
975 152.54195151584514 24.365739205053845
976 2254.094437935528 44.08295569675299
977 2532.1644109274716 53.14047751682133
978 3278.0497830893323 53.99878440158695
979 3011.121110298807 50.74913916843266
980 210.0975242221639 23.919896462133927
981 2468.6902326132627 49.27332816379399
982 2381.4051908041806 53.3192914511475
983 2531.120137551007 53.50690631670242
984 3286.9356435324476 38.017587044409254
985 2760.3929799582315 47.427968361547904
986 2527.009801247296 40.95490393894049
987 2894.2459386374303 44.13779196994634
988 3703.948811867407 31.983212807348725
989 3246.0444730307386 47.64969764011235
990 161.93560711773375 24.91648612277845
991 2545.618371346173 53.308604255040954
992 2319.821671822247 34.052686073950284
993 3451.906995155982 54.63059363620609
994 3804.170445778539 47.385053017309616
995 2762.8677648093058 48.033551552465866
996 3271.5290349509046 50.911263802221725
997 2532.150105812725 53.19543001463724
998 2379.171208717999 53.703145363501015
999 3662.54504142063 38.06765494602058
1000 238.7574824052196 24.027184822729627
1001 199.32682929294447 26.802377083471796
1002 3284.5037740256116 54.41363272922367
1003 2413.4128850485654 52.084283211401406
1004 2216.8534558798638 46.996430733374076
1005 4055.8713239218487 48.22667060153813
1006 2369.1600125815244 49.18034491794438
1007 2697.820023873027 50.49879966037603
1008 206.45091205480554 24.12493644016127
1009 2533.6473744894834 58.893517830542024
1010 2726.0678571249805 55.21471915500493
1011 3434.821919777564 55.479363777807656
1012 3165.931062081032 34.44846091525888
1013 2561.139420845684 59.057273381218614
1014 211.23345313327644 26.29216132419446
1015 2539.526776650128 35.75737891452645
1016 2223.0308812643852 46.402768471411186
1017 2472.471551277814 49.945668556860404
1018 2367.8224843527646 51.49777350681157
1019 2551.6956609274716 51.87447486179203
1020 1345.3191083456793 30.9413236166749
1021 2531.5039914633603 51.37560086856995
1022 3798.2028287436274 52.5396626974854
1023 2404.4554990317197 38.081960060766676
1024 549.2323201681879 23.652867653540177
The overall performance and scaling behaviour of our code isn’t all that different to what we saw before (last article ), but everything is faster! We can get some idea of how much faster from the plot stack below. Each of the three panels in this plot is a histogram of execution time ratios for all problem sizes in the range $8 \leq N \leq 1024$. The tab labelled “pre-release-1” shows the execution time ratios between the pre-release-1
version of our code and FFTW–larger values represent slower execution relative to FFTW. The tab labelled “pre-release-2” shows the same ratios for the pre-release-2
version of our code–much better!–and finally, the tab labelled “Speed-up” shows execution time ratios between the pre-release-1
and pre-release-2
versions of our code, which gives a measure of the speed-up we’ve achieved with our optimisations.
rel2,rel3,speedup
31.0035623439637,21.1433970940118,1.4663472575438
23.0236843367442,10.9284704465462,2.10676182448025
20.8464275202564,8.43711760729872,2.47079968426927
280.324183098903,1.67440325644213,167.417366169337
31.3217344925748,16.997410745701,1.84273563551417
238.564872414651,1.63349471368707,146.045696025652
220.196265658982,6.80582459796996,32.3540906012569
24.4004823296537,8.05938108991602,3.0275876096967
41.613223688593,22.845840851164,1.82147919000638
75.6522121597436,38.3947173570711,1.97038075462771
31.659967533097,13.6679428291178,2.31636669313905
428.745816685474,117.821087628618,3.63895653413859
31.1467155085507,11.7470316558796,2.65145412228128
243.187456369924,6.3462483275987,38.3198771646463
297.173923636788,5.33583647241035,55.6939713526389
338.913321074374,91.1426420009795,3.71849349145191
39.9146205525711,17.0613062579703,2.3394820976222
30.844757712075,8.00933754987466,3.85109973452895
254.636204069331,5.17769308272402,49.1794704709235
35.8707950145261,13.4528482806725,2.66640894672551
256.327406474509,9.2896462837598,27.592805866314
136.255087213481,36.4046594898679,3.74279251949612
34.4694643926202,10.3983137298377,3.3149090600826
140.631775111143,37.3827650533443,3.76194149658179
55.796267061807,24.8742425738626,2.24313431438659
365.283997243452,5.1307018977268,71.1957163999908
99.4332853296993,42.8177133412736,2.32224650898982
296.647448889548,6.73751616465583,44.0292003224754
22.1364583157872,7.19578180143054,3.07631038942653
312.918980821529,62.034049688856,5.0443100586055
531.142250661184,122.788477860653,4.32566849850482
357.94137972657,5.04889819775385,70.8949488991104
20.4687655988403,6.01579563844752,3.40250348067385
279.270424648104,54.1054863143249,5.161591618005
318.924524672781,8.48163644377719,37.6017678648286
281.747643338043,54.2643223327939,5.19213419104605
424.1869719843,7.39256837178648,57.3801892185667
40.0534922145836,9.92223498086788,4.03674094514139
427.682735934799,97.7607931881241,4.37478790819338
256.424329809441,48.9762335847427,5.2356890483576
30.1298650675711,9.83801882374295,3.06259477719803
371.29467467343,7.46464578926852,49.7404277651349
45.9285788055788,10.1380076754654,4.5303357696926
108.93295754923,43.7222057457359,2.49147900228831
418.450271063551,6.84958007768998,61.0913758679164
233.262880194168,44.0468043597988,5.29579576962603
30.8789814952158,8.36830377726286,3.68999289666273
519.369414156701,5.59410641161449,92.8422478840204
338.902214071608,9.98240210504665,33.9499662010483
481.308370331345,125.049713257737,3.84893621738526
228.591352563704,50.1711130647591,4.55623442654434
211.712173908992,37.4137320631106,5.65867563149993
26.415368131313,6.39692512049681,4.12938523333246
217.957897546566,38.7325048772451,5.62726057189796
217.582717709118,47.0886452274134,4.6207045596302
399.561169721661,8.02274355230238,49.8035574883849
77.1386234280048,25.301599237488,3.04876473237758
481.857605313242,5.39551211417611,89.30711211772
524.756015432184,6.6090888477682,79.3991467688299
493.973069731807,64.4965841864878,7.65890280799236
129.768483217381,46.2463934891008,2.80602385238893
451.222572680023,99.8304279468651,4.51989019740742
412.985101384841,8.51042365714818,48.5269732768194
446.168666714429,58.1996536549202,7.66617391505232
43.3313245255458,10.5238232000538,4.11745082579154
422.209119515195,55.1787943807507,7.65165539141399
438.762564712467,77.6886538679287,5.64770456002967
56.3774648955331,9.7944617910825,5.75605542173463
546.277651021967,130.339618231458,4.19118652052427
555.351526550351,6.14181768791621,90.4213629855838
483.562604732599,6.27519830788696,77.0593343838769
421.277925273441,54.7106115834114,7.70011361746823
32.5702339374315,7.49344519937004,4.34649658079432
60.8374213913291,13.8272629245088,4.3998166320751
391.400568530886,68.7371305925086,5.69416507725947
376.43862980617,48.597104267363,7.7461123554841
258.660069203734,5.6156838816292,46.0602973130127
147.352980120585,45.658942380548,3.22725346751266
371.070479141964,64.575255372499,5.74632615854886
242.132373957657,55.6264398722664,4.35282887982152
551.401191875935,7.7845570955556,70.8326992926475
502.646686053713,64.8536851941561,7.75047222912485
35.490493816823,6.55787522061015,5.41188915966001
478.318094027619,5.89864068132478,81.0895458579099
460.329737004008,102.458861238314,4.49282503670722
231.280967852096,51.1460083431805,4.52197493693433
349.468105493579,58.8400635419965,5.9392883769432
602.254428424729,128.260463996779,4.69555784890856
48.3820658264393,12.2081371707418,3.9630997874428
361.023447620726,46.5526444197923,7.75516519244679
448.542659597839,8.87771548708946,50.5245589645375
516.505095013952,6.34157191464685,81.4474868322478
39.1023293337295,6.88974300774294,5.67544091119
307.671136213038,38.8597684111634,7.91747220306779
149.505035197283,46.075330596926,3.24479571302864
406.730452669845,51.7136370689051,7.86505215496451
500.501671424073,7.1964546876157,69.5483669598283
425.162572970627,8.26008888378508,51.4719125850135
305.97788291228,50.1146474035824,6.10555793096147
383.150072000661,48.8880148394464,7.83730068113766
49.2275128714945,9.94858775910732,4.94819104615424
326.228891955307,41.6007302348353,7.84190301741704
565.622120091478,6.69114998478339,84.5328712370493
639.112844687001,81.168333235561,7.87391854939552
273.996433022369,6.80229169805695,40.2800181445666
409.337945427271,51.800080694032,7.9022646286038
613.23874996535,131.195368903918,4.67424082944926
500.922741873498,103.062512997025,4.86037771937463
296.500529084055,61.0563233119128,4.85618053955443
451.719074313888,5.90449402102723,76.5042817733773
259.845133913181,42.4912736635492,6.11525876985154
154.671595437838,45.5662127927479,3.3944360515837
46.499174900736,7.77200992661668,5.98290215012349
610.328310244978,7.23088898520026,84.4057088269728
259.930403508287,42.3111221177822,6.14331151002599
573.313354046854,72.5721356937633,7.89991018682564
289.453788865766,57.1845845523218,5.06174506874184
71.0629719495507,9.3338918146885,7.61343428447722
297.680059140862,6.03523526140875,49.3236876852713
307.710885330496,38.5446683960375,7.98322824233014
56.4045482855623,14.5552186478495,3.87521133486346
549.339852550991,69.1365616761042,7.94572132650415
497.35505670896,6.24090340111878,79.6927984207865
695.928907841214,63.5045028887033,10.9587332580319
395.531989644992,4.81100614498461,82.213985541741
617.28480992687,129.310478969256,4.77366424474872
618.695555789857,73.8401929815087,8.37884532540148
49.9844159596429,7.16745433189526,6.97380320056057
188.083940308365,47.0303288477974,3.99920529828857
719.295889668846,65.2745882897077,11.0195392803766
502.525446836379,104.136793894818,4.82562817656885
872.942812789777,78.9107823330417,11.0624022089343
332.551356100159,6.31357018970745,52.6724731186632
491.668951166375,61.4190295096897,8.00515662802533
587.18482651983,69.7214558518479,8.42186697546229
523.972874511054,6.91180732267227,75.8083739968135
67.7299881544339,11.7855365164878,5.74687355638674
312.101861576098,63.3047183275752,4.93015165095756
546.709253613293,64.7808240477973,8.43936861948396
417.177229780238,8.21961300603236,50.7538772779293
662.169036336561,88.94069268714,7.44506273035025
701.786347622189,63.4072655614918,11.0679169241513
65.1752883721421,7.82904165164072,8.32481052881912
700.753969942058,63.1930609406903,11.0890968013046
503.801432706304,106.754162305161,4.71926735058973
181.329392680331,45.6179916730402,3.97495343460056
541.043311835516,6.7733796405604,79.8778956070373
288.826578404247,57.9968071324767,4.98004274174107
386.526618980629,5.1200721854183,75.4924159236342
834.542331338152,74.9788400355254,11.1303713280006
538.769792982785,63.520429375299,8.48183487236147
435.714709146841,54.1319802229049,8.04911823570195
63.7782579786892,9.44778124063422,6.75060697895751
544.872701910037,102.021135670363,5.34078255774918
65.8962179141201,10.438496503251,6.31280739458956
602.396566061772,53.4945470807782,11.2608966508705
578.970676300861,77.511291882606,7.46950105254001
545.964865486633,6.56834209949459,83.1206501148354
481.151118987848,56.1738825920493,8.5653883403806
698.678541154153,61.2400270808084,11.4088542160868
344.667718728519,6.70343193802766,51.4166059885334
517.912065422364,7.51625390368988,68.9056107016436
187.773527222397,46.6720928525767,4.02325063535329
684.342512136198,126.457817886072,5.41162676674314
542.342627134465,74.2115749812465,7.30805979082801
691.446918204287,61.0825018530708,11.3198853555067
323.690545705247,65.8387535287987,4.91641363720018
416.771335598153,7.87146289814131,52.9471257111007
426.574487709098,5.73881034117797,74.3315186160234
396.512956199167,48.6581538550381,8.14895191832502
474.673162247135,55.2052082787555,8.59834021185647
682.272685691075,60.2859089164548,11.3172828933637
65.140155932268,8.45022076585624,7.70869279480504
563.065132198392,50.0589055394726,11.2480511934965
457.635660262831,6.21027567828894,73.6900717407313
372.875240298742,45.5936126612695,8.17823415461635
447.231871511689,85.7367141071047,5.21634023614428
664.294696626511,89.1173620771969,7.45415574634124
299.688065640459,61.577859112325,4.86681528004723
193.714881150811,44.9039662771721,4.31398153016362
478.597326529552,65.9573213439587,7.25616681783862
307.919880322086,6.3085901320171,48.8096189288545
654.515562164685,129.048328581469,5.07186392384372
584.268659113577,51.8524189087388,11.2679151987471
84.3939794660343,14.1689673051948,5.95625479600711
592.160682445265,52.1416729068318,11.3567641664155
505.150491642247,53.2688509039529,9.48303714215771
536.307975198127,6.16478620689093,86.9953891667238
347.849331181805,6.87945754703953,50.5634824843852
674.131604545726,59.6089777987365,11.3092294053735
432.409036710015,5.03267687121908,85.920286117092
672.32728119474,59.6019086890932,11.2802978290823
74.1495001282507,8.40499176873767,8.82207885129042
747.263302135204,75.6245692837878,9.88122390926992
424.436484409191,44.6576810780702,9.50422131563874
351.113850141492,66.947530326227,5.24461243649404
151.827104640608,40.5122543209585,3.74768344012055
588.799652391248,79.3229822436328,7.4228128562137
407.659571435643,42.7477496665414,9.53639839794227
520.313314974387,100.843822193035,5.15959533920088
402.793691683496,5.81729065158884,69.2407713156783
627.466437344979,124.029144933817,5.05902413243115
354.025897583459,6.89517409824912,51.3440114113081
511.040444728673,45.0595618605971,11.3414428287098
422.391924997952,58.1452871916849,7.26442237021672
736.175247364266,75.1404386590854,9.79732432364838
408.079797739854,42.6882024253524,9.55954513318877
542.166398734392,74.1273423556506,7.31398673559843
90.6417415134905,11.7449717126415,7.71749338620628
328.04316595483,62.1165272434896,5.28109314078263
451.260037872095,47.0698921479371,9.58702085940242
670.902993282901,67.8380831068438,9.88976932361488
463.914388694385,5.54635448950323,83.6431190203163
213.42503126647,45.6457095482758,4.67568657336233
632.89136298718,91.4959676997342,6.91715032802498
466.967602378254,41.0894191679232,11.3646678837163
379.99709156789,8.18933796396264,46.4014421239025
75.685162555707,7.49524385478475,10.0977585282154
448.964506679869,46.5794012909795,9.63869208784387
502.185119847148,44.0905307686089,11.3898633355688
569.731831319062,112.471454319951,5.06556827920378
555.812350340781,48.9358046455967,11.3579893978671
457.060724940688,90.656166706744,5.04169480736148
578.855477893771,6.52443242570754,88.7212005772284
357.783442762585,69.6880257673361,5.13407344838693
562.08338002122,49.4548542172989,11.3655856218176
388.464908783067,4.91953315586009,78.9637749102946
492.16793745969,67.035159701543,7.3419372706941
361.390406862752,50.1142330716085,7.21133268359827
662.478082979693,67.040012647546,9.88183111573359
190.842998544489,44.7711243498215,4.26263582422741
546.493120794215,48.0224292774499,11.3799557626885
83.1914014040263,9.15541054786598,9.08658338903406
421.258869670249,36.6920873334053,11.4809186471854
617.866795051413,6.42586811406284,96.1530464186199
89.7270342015239,12.7785993510038,7.02166424792678
343.105586126694,47.4758566125546,7.22694882425697
450.304106696642,8.20005732096406,54.9147510890449
579.070826575427,81.9876416391073,7.06290381084966
677.300422052894,123.677323376185,5.47635090705168
335.336750312789,64.595020569732,5.191371522992
553.810902657188,55.7702367480308,9.93022326871766
78.8365200760403,8.04099643955753,9.80432222158507
523.399742696637,43.514572243887,12.0281486340513
377.449894087009,6.99156277809295,53.9864842907072
576.834639475515,97.0521583821844,5.94355292134752
417.632242312575,43.1059302025623,9.6885101504607
189.178267404063,47.2738410924015,4.00175367671721
110.734191742325,20.9688836107923,5.28088160522443
158.04862300712,18.2146327484694,8.67701398044388
549.7790952933,77.4611462943067,7.09748204867074
771.640801166783,91.2035197775412,8.46064716634762
430.246987615493,5.68475837276371,75.6843051899713
346.359379184053,66.7258427625635,5.19078313355343
975.801001719577,71.3994053121659,13.6667945265548
1315.66173593951,83.0378468836715,15.8441215098295
576.222160143937,5.90215529143509,97.6291086376736
412.358846415636,56.5980015135142,7.28574923828671
660.267723190285,123.70882185127,5.33727274506016
589.265515745625,58.2098683636588,10.1231205689088
836.299919499441,77.8448566090602,10.7431621808923
1319.61240409077,83.4934365050551,15.804983712832
76.9386078845709,8.46206355983584,9.09218033409141
1203.06911393861,75.9597885795692,15.8382367359853
158.813219162244,42.5409229644907,3.73318696669575
531.625846529593,6.32596735144338,84.0386642855962
940.392060345556,71.467644016007,13.1582910461541
675.192450291204,6.14296406181006,109.913136964089
527.43144793996,91.398309878871,5.77069147820083
1319.80680856013,82.6711780290045,15.9645337108548
955.268634472655,71.892301339402,13.287495554814
325.468398428997,63.3027727130591,5.14145565004381
400.933471805248,7.5482107724676,53.1163588154783
1325.77960338102,83.2427383282815,15.9266697613021
489.345546650158,68.3517074502064,7.15922929952616
1293.72834674038,81.2305586752933,15.9266213090059
806.928750634983,77.607753053516,10.3975275521577
695.647937109771,127.695356521486,5.44771521893767
538.657203479221,6.36651585320193,84.6078476673096
727.55331718038,83.139592444711,8.75098488922969
109.277615313159,13.1618302590689,8.30261545409795
223.571813289553,40.4185313122334,5.53141853578151
382.752054496402,71.0705423265311,5.38552319944121
561.479960811569,55.5584343634836,10.1061156104249
753.966911082262,70.474649656163,10.6984130429988
1103.35906346806,69.5140112786083,15.872470070039
391.558967307844,7.42784577153832,52.7150104284882
370.546474356103,50.5880958500717,7.3247760788288
809.916210213678,98.5242040176235,8.22047960995254
661.862949786433,6.08029309373422,108.853790365548
940.101921882978,69.7529772080382,13.4775884773939
558.638305291894,91.1647983315081,6.12778523636375
101.182083440555,8.94212700969071,11.3152143031409
699.758177310983,78.620365021328,8.90046970808586
940.827322153705,69.7006893710145,13.4981064124877
481.038853666049,47.5659738710599,10.1130874555419
652.219475009659,119.289912777021,5.4675157339481
353.135312599842,48.0293392092815,7.35249158979892
169.682263138503,41.2093465297927,4.11756743135516
905.898978825545,59.9460529795139,15.1119036833856
626.613220392914,6.20974192557486,100.908093750596
460.96160034408,45.562166217805,10.1172011475596
384.06120650799,65.2346770132348,5.88737806473805
998.025430316007,65.8651797614039,15.152550010967
516.468589757692,5.69433067242997,90.6987351925765
970.632427693536,64.2821375400282,15.0995667667262
925.845936398627,69.2122160304845,13.3769150808701
421.336899752695,7.02457453283698,59.9804155800638
738.784541906404,68.5126163507761,10.7831897430966
1096.9846367387,71.7794093418145,15.2827203065275
452.321710322474,59.9931217217398,7.53955949184364
409.605786037976,68.6608697458189,5.96563643242983
102.287460999453,10.674709466901,9.58222435154934
472.127167529192,46.6828273457502,10.1135084221109
540.059488113134,97.7255288970729,5.5262887211584
622.636523327125,105.987284629482,5.87463416487915
122.590179913927,12.6561958210767,9.68617913684411
591.747207938315,6.08393748120438,97.2638541678722
779.196514122214,57.5324701688545,13.5435956745003
489.872495455394,48.1889586430916,10.1656584671938
726.483441465791,86.0647587690553,8.44112563442167
613.982257355448,69.9663589213899,8.77539244317805
634.252608881127,5.8744205711112,107.968539399479
901.985690895881,59.6630014513574,15.118007290184
659.708705342733,60.8462260790245,10.8422288094899
752.99016577877,95.4910222645841,7.88545507128831
775.2938758776,57.4460831415089,13.4960267694456
846.09125333199,77.1395976186018,10.968313025371
494.73393126766,7.81731829032949,63.2869115588751
979.880865238625,64.0768000205212,15.2922877691272
589.055704975882,7.28772686965803,80.8284552249587
487.216641835129,47.8119998361131,10.190258585819
198.591406523838,44.5112636595195,4.46159893466349
409.586472040896,62.6591708845998,6.5367362232615
609.139831752487,113.662881318642,5.35917992475334
562.070367675752,8.50226519137423,66.1083082007354
695.329369579615,81.6512815173554,8.51584147435357
523.856265790079,94.7012744878013,5.53167070478612
784.839938486554,56.4056320276743,13.914212291806
933.457314250363,59.6383571229779,15.6519622484824
427.456671139366,72.0852773995592,5.92987481715621
950.074101468039,62.228181366618,15.2675858526327
494.113338108466,7.06192602390629,69.9686369463196
574.903207511164,5.91474290344069,97.1983426662104
638.893719088529,6.88038266124594,92.8572945058894
968.134511027729,62.7420145393862,15.4304020700512
381.673866122807,51.9642933050243,7.34492556037328
881.13644748383,77.6162225271661,11.3524778557141
618.922357178502,58.1510260647968,10.6433609011275
198.607151994154,45.4503059530138,4.3697649076218
781.547601605375,55.564106615445,14.0656918505755
959.608426416626,62.7286731561438,15.2977638157271
109.74304887471,9.28518471443831,11.8191562418851
751.637490270261,102.935646559292,7.30201359193201
783.005691204304,55.4750838501113,14.1145472320495
621.147351103776,6.8623477993499,90.5152827087284
559.608020154014,6.13325067010664,91.2416677964157
796.609802272414,69.729247557988,11.424328100055
374.941868803699,49.0985824816448,7.63651107328544
840.824731314084,54.9181187445168,15.3105159196305
513.812163735259,96.2599503322778,5.33775637699418
674.572209462169,83.9598507270688,8.03446175309463
801.260072138537,97.3383105564402,8.23170309365436
540.62672699841,59.8366121923846,9.03504906427866
390.405340803122,65.794885131574,5.93367311185975
900.6418234615,56.9445552347635,15.8161183233138
216.000750046229,41.0630744058015,5.26021865561318
149.916344129949,8.89898911774579,16.8464465060414
620.918231999434,71.9812796709577,8.62610716060881
476.307825573929,70.0109158741616,6.80333658868355
451.850366440746,7.15780212496362,63.1269708986321
923.209964002848,59.8093449566058,15.4358815444756
611.099378902982,120.090562678799,5.0886544726871
494.253379913041,47.8183936307747,10.3360515145986
816.215954231671,56.7056306940517,14.3939136950167
976.669541180908,63.5312474547884,15.3730578307304
152.641402495647,16.1560274816611,9.44795387782743
675.67591693434,6.71470939529784,100.626233714225
787.938100127915,55.0312002809252,14.3180249768426
682.843173868159,79.81240775184,8.55560173038905
638.418893624038,55.8375115065734,11.4335126404922
851.727837497005,54.5814489835081,15.604712834838
556.42205513466,5.72853684600739,97.1316184380431
523.733161797886,82.8001679059623,6.32526690516739
485.807529115287,7.9835194976977,60.851298635318
1060.21601867565,74.1627232247536,14.2958075509527
831.571970107557,56.3768382232901,14.7502413458161
819.216150348264,70.1751379253456,11.6738801599474
628.65757491269,6.0649184598897,103.654744753835
914.596515194875,58.0091171215156,15.7664270821259
824.264738519433,55.737868177951,14.7882358164086
675.839046197227,120.572777006213,5.60523745888677
156.70936927354,9.91971819988686,15.797764222307
764.497773429644,48.721566606234,15.6911574623265
1022.25299664792,83.2536485481053,12.2787771404066
434.342447179386,65.007012896082,6.68147062646474
545.515295272911,46.2333460349978,11.7991740173849
127.87834857968,8.30238232333056,15.4026089861375
386.998118999461,69.7150064650418,5.55114513535215
848.052117943561,94.0531927124124,9.01672865626858
188.738867582271,42.5261962043961,4.43817892094382
793.507881855528,50.5526687177454,15.6966566154199
694.736328914123,85.0645347448852,8.16716779792764
1087.24836606028,75.9868796625336,14.3083696934112
579.225239637382,48.4729453723631,11.9494541787763
449.896522495776,51.2246357415915,8.78281545554233
481.608974102715,90.6393091945257,5.31346695360519
683.947511404036,58.4680364775852,11.6978019548551
560.362439390747,6.47076683526613,86.5990776142222
1091.42931780311,75.0828155050596,14.5363397797671
647.620097051185,109.896538878635,5.89299812040841
855.774804797403,53.5307318824461,15.9866075934977
492.476568201643,7.66731819570513,64.2306156639626
831.529675540752,52.2616955519248,15.9108820859932
686.189350142989,47.4069543911851,14.4744449196378
608.430142029746,69.4163305316891,8.76494244754111
525.783827437897,61.2366088308765,8.58610294521711
194.488630624881,44.8892086519192,4.33263665067006
987.814650377906,79.4700824475372,12.4300191965954
430.692521759793,48.7818861791395,8.82894359964229
584.783053385078,47.7054985635232,12.258189747381
564.437273863266,6.6730755264118,84.5842777635654
658.774352361513,79.6138132611402,8.27462377917606
832.205734282893,52.2014353943096,15.9422002095676
149.789830487304,13.3685153420455,11.2046720712657
731.316001578312,45.6243880630243,16.0290588570326
390.388355988516,64.6347198356788,6.03991719900701
391.03670022181,72.021532632032,5.42944152854495
599.785054162366,49.5307870113796,12.1093382591431
562.314650063609,78.358359209901,7.17619224972946
892.027263732429,71.275373556032,12.5152239718698
801.909006806316,50.2377551387824,15.9622778643479
623.218920572504,6.31429004280493,98.6997613900641
472.803385486657,7.44995293178745,63.4639426336911
284.931102399285,41.2651205715363,6.90488961265325
783.428649920795,48.9830053696758,15.9938869411593
898.468106781393,98.4794889285075,9.12340342701868
766.860466046303,59.6689491716717,12.8519184046629
663.550758009001,45.4128141986823,14.611531342364
1065.54188317982,72.4616430773098,14.7049092171838
492.35403534789,9.13873815618296,53.8754942896334
809.662746988605,49.0593585086104,16.5037369342386
147.451863291934,9.04178160260736,16.3078328776946
756.091147986454,82.0508780840077,9.21490623430418
595.314067501916,50.7673366427541,11.7263206398062
1058.42510903773,72.0002936962663,14.7002887724695
689.063268549226,48.3791422500689,14.2429823370472
600.91663917742,6.56098015467946,91.5894614844751
674.309731096883,122.703168171923,5.49545493521478
750.736157491946,48.4125456449858,15.5070580877356
661.960722893855,48.287719364983,13.7086764833605
189.440774013471,42.4041053006123,4.4675102250238
551.772203810844,98.9060974810269,5.57874810414687
811.473144674888,53.4224307023717,15.1897458428237
633.814173185857,6.42709099782335,98.6160260373643
810.681501264912,50.5886703071587,16.0249616434412
391.236056774239,73.5306370495092,5.3207217082971
380.206821299068,66.6711952287236,5.70271494300832
652.613015692748,46.9561146515852,13.8983606402519
785.84208906336,49.0524253711958,16.0204532827202
542.084077773696,5.82618705323874,93.0426834600779
1038.32601978614,80.5356493964548,12.8927503232108
608.355664929834,72.112431863044,8.43621063959157
944.885671612098,68.5799131861061,13.7778779195586
460.496214669603,52.6945104701918,8.73897889098137
684.112195487549,74.8173881698008,9.14375938832469
864.527279588159,71.4628213805983,12.0975811322064
771.698207770463,118.258424045733,6.52552419836095
266.473262695194,43.5243418403183,6.1223961449625
508.686673582495,60.9925635808997,8.34014253078213
655.437300677378,48.1739196744184,13.6056460654878
785.891318553757,49.3860125708016,15.913236919605
148.789986940107,10.0929218526121,14.7420131764519
971.222766756003,99.9003617302838,9.72191441486629
554.715783997261,39.3578003692069,14.0941764731157
694.26212830919,101.929976395534,6.81116736076875
646.186870301022,8.03686871721027,80.4028152055374
724.487746474418,60.3878074345335,11.9972520489312
168.409212113894,13.1270404319701,12.8291836219034
687.822122514261,47.5709651200887,14.4588641575363
424.012366373052,50.2196389805953,8.44315839341037
797.536079428995,56.8267552975848,14.0345172842006
490.169254027678,7.87370771253394,62.2539306669196
688.379490586977,42.6957780437089,16.1228936941321
819.768972919284,86.873858351875,9.4363136215141
450.75665922744,62.8180101132078,7.17559595433072
783.673478318083,109.632253553535,7.14820185590189
627.791370972855,6.19138606602416,101.397548832873
430.758887795221,67.6838867499938,6.36427528735648
1002.35062404769,79.3030804865309,12.6394916552823
763.618257042825,61.6856227732873,12.379193444303
728.733682452732,45.9237476785488,15.8683408756975
177.537235352487,9.44130848190336,18.8043040530644
837.000531352696,64.154969239939,13.0465424778293
664.732949242104,49.0868390659143,13.5419791107244
740.496411688008,48.22067133726,15.3564102521283
488.327379387896,8.35004318356584,58.4820184342278
583.733087791724,50.3344312980823,11.5970931375947
600.164605506714,87.8704233293505,6.83010941300708
603.505737174284,7.46139003507929,80.8838211562372
542.214598197208,46.4614830871159,11.6701956582089
773.371742646601,49.7436774840716,15.5471364756706
253.479245875098,43.5780967096335,5.81666628453423
909.571298558846,71.5378573531888,12.7145448887043
191.836498116332,22.5651872729286,8.50143611910007
732.721224371974,113.793831880242,6.43902408649969
203.959819983088,20.4895361468669,9.95434052392036
575.122412159116,46.1306062796217,12.4672632454254
759.434785432332,80.5701144943405,9.4257627682244
634.635289856642,70.9995174605753,8.93858595882773
867.797608652772,96.9890334618263,8.94737866414894
824.111659460536,58.0640827899487,14.1931400594378
565.18307163623,6.34262695477383,89.1086730571219
1498.25459791786,93.8805800580519,15.9591536076087
520.869833196188,75.0132414844064,6.94370517643162
1551.39940316362,95.7644660369917,16.2001571915448
1072.27513227212,75.6981942869734,14.1651348803262
496.446050570955,7.66823526748175,64.7405867522357
1240.86848905617,81.4928381299503,15.22671829244
410.132072917508,57.5129104665659,7.13113055121651
626.510905262879,6.53029308002931,95.9391711191111
653.465571117176,77.2189074983664,8.46250733514975
576.432722269123,60.158581840955,9.58188681696443
448.798779660079,50.9876196699892,8.80211279845717
795.055841530106,118.467561660658,6.71116911992741
896.232103806864,83.7927750347928,10.6958159988701
777.302708365584,60.4860427736473,12.8509433370345
587.686567138934,47.0503200453457,12.4905965904704
1104.59737008177,84.4251040239214,13.0837549192571
804.759193188106,56.5678650878167,14.2264374294272
1261.51856059997,81.6645920745591,15.4475584650961
726.098874970669,7.02983889760617,103.288124457294
170.061347621322,9.29978274282745,18.2865936037574
1385.49522203287,83.0859707164115,16.6754412337774
1260.903377379,81.0717989774694,15.5529221416366
807.992663068268,56.8568884866946,14.2109898127357
234.526631063782,43.810091969211,5.35325584864336
637.435073965456,50.2947352583065,12.6739920329967
573.25506277815,6.2451177435054,91.792514780735
1400.76348486921,83.3852900939191,16.7986881534081
1098.34495754179,77.1284021549183,14.2404733775722
428.21642409432,48.4320691929036,8.84158846050425
681.193482488049,6.47126357142032,105.264369928691
535.035858791042,61.772294714982,8.66142113158824
650.750667048643,94.0361335946807,6.92021930477854
939.947384473715,70.7209785931449,13.2909272916202
1256.47507964087,80.597370150133,15.5895295007811
916.245660731232,99.0844578160283,9.24711787223421
1098.05693562896,78.6683294345548,13.9580558468888
1386.65889150992,83.1122571422379,16.6841683668487
524.108548674871,65.1621805653577,8.04314011789691
799.13154953098,80.5612121795083,9.91955716543015
540.523334755136,8.36460128406366,64.6203347175612
266.762661882614,41.5527383014719,6.41985757827095
1286.22687536678,80.0974208709277,16.0582807958257
1445.42082564087,84.1368107470823,17.1794106860771
726.396844237268,72.801627819168,9.97775552548859
631.584554468889,49.0874666776297,12.8665135362693
1267.22683419539,79.2828905474395,15.9836104037748
475.20381990524,7.2340220985345,65.6901255529078
1010.87332174474,81.0421444376963,12.4734276068161
1457.87210841751,85.7598283108834,16.9994755951779
796.256209167334,117.563981861585,6.77296053228967
1503.79701598318,91.2178741756999,16.4857713422112
606.443552778871,7.27475599514331,83.3627345279674
857.184394886198,59.02359696664,14.5227407162372
823.574399805857,85.3422292450688,9.6502564684698
677.600101062989,93.9648737357186,7.21120642346391
190.063066625296,14.1891008168977,13.3950043119682
1366.23434339652,82.0708595131974,16.6470090785003
268.390001282356,37.6440227774429,7.12968438227546
837.415055509825,57.7213258131206,14.5078971023821
471.591710735791,72.6440214218826,6.49181724118777
814.489698512036,61.5018355309987,13.2433396740087
753.861098194257,57.7034892701785,13.0643936394303
568.744369625575,59.7052652997102,9.52586621582828
918.716211917827,73.6198469987108,12.4791920843562
566.157202838182,5.93292002811226,95.4264005170354
1197.6385242667,81.2309632824858,14.7436208543021
1395.09553251849,90.2192350193165,15.4633935016162
518.813606204685,8.55386143462766,60.6525614390278
559.276920152753,62.2757875672411,8.98064788901922
489.068368362511,56.4398049188461,8.66530933382451
823.379947292871,60.0577346074983,13.7098069494961
929.258609434265,99.8499358875031,9.3065518888387
1388.42007465563,82.9137672686988,16.7453502644039
748.249202000277,6.18772124829936,120.924840013749
259.623375175152,42.4755125078284,6.11230706462463
1064.27412315248,73.553557769447,14.4693765390443
825.71323631448,57.6024929672895,14.3346788268934
671.715852046562,96.3496006886579,6.97165164406991
1373.58178467059,81.9204734464161,16.7672588656246
190.421089625676,9.88988134161305,19.2541328908016
1204.97073943955,71.5421375775616,16.842811526748
790.150694961337,78.8178840746388,10.0250178527132
1083.42056362943,83.6802035881233,12.9471549682415
1039.35736325981,73.5210808794604,14.1368618473369
699.591073980053,7.86896106012619,88.9051386370483
635.103150356197,51.2836793789716,12.3841182623222
1228.3312046364,73.5398233579508,16.7029392858013
787.869923321634,127.98485805045,6.15596200459174
485.792080496192,70.3045493686689,6.90982425545116
469.539917738897,49.8113686892583,9.42636048947099
718.89456610235,69.8120145708156,10.2975765779273
246.301311426979,42.7658143977589,5.75930366100748
1129.94223342683,66.8936594794297,16.8916193585477
1022.32627451459,62.8733474353923,16.2600897870932
809.708663900494,86.7206608437897,9.3369752492895
697.438607682519,6.74048514522901,103.470090454271
1197.24461561026,70.5556171877704,16.9688065008917
687.922357513737,49.5667836108156,13.878696727936
1163.18878738785,67.6548314620544,17.1929892108333
483.72726147557,68.2013947559444,7.09263004380725
691.039050680961,90.8165122702391,7.60917847874033
1060.45527363896,62.2272775529768,17.0416466112654
829.186845320996,59.7960271311761,13.8669220197855
623.082918985416,6.37117422940118,97.7971872296418
185.411126618826,8.91144111877534,20.8059643942647
1067.68237278954,62.7146831453231,17.024440198725
831.675785680329,112.682603513566,7.38069373397292
1021.10184670803,72.2659634634344,14.1297755924155
948.257944091708,84.5903180385032,11.210005661169
520.458170342153,8.37263112734814,62.1618416512036
1350.03416524413,79.6682835367982,16.9456916267132
947.673534642313,72.1473052147697,13.1352589236875
691.70739238333,48.3475083817778,14.3069915190094
1244.82851268428,76.7816357127285,16.2125813175131
588.117229793036,45.8022913658073,12.8403451498953
628.303008148543,61.1350930521817,10.2772888169526
645.333590863415,6.7692682832159,95.3328430583097
535.273235513216,69.4213539817291,7.7104983526264
1059.02619837487,80.4780128441959,13.159199152011
186.796588030041,12.413616081296,15.0477175068669
1201.03553075966,76.1250936922421,15.777130411362
645.032398916213,49.4890852217642,13.0338315211481
1221.92995714235,73.1104301184965,16.7134833588294
646.63197032523,98.4562076970376,6.56771152830707
781.860362175706,80.738041457209,9.68391538937801
750.451534889,100.087534810785,7.49795203076715
1221.86908164988,72.5579274649693,16.8399115622451
214.863474871702,13.1311871077394,16.3628370465503
539.598795341489,50.7441197441833,10.6337206766375
614.168829833405,6.26550613776013,98.0238174426185
458.988628167404,64.7318509106236,7.09061492465491
821.63896723908,59.4250012825059,13.8264863189992
1144.02233995556,68.72051579904,16.6474643947819
673.971344075337,50.2463060302811,13.4133510962809
1124.27020602021,75.5312736560387,14.8848305026606
843.02688487024,87.1871432947804,9.66916512013657
999.578910478347,73.2802522853343,13.6404949397042
713.000242574187,70.2465873873862,10.1499627112451
1200.67169165136,71.0101614236458,16.9084489822262
696.580426121324,6.50349915142131,107.108559546608
1191.60035759226,70.8264267665393,16.8242337216877
1021.86302922336,62.496108912326,16.3508264275606
286.589693627204,42.2867400231959,6.77729457201001
822.662777572089,62.7112493377901,13.1182648449701
771.799655220865,119.21900638368,6.4737970784373
939.315204610539,97.3406027684449,9.649777974408
568.141191887983,61.1109070922075,9.29688690483256
842.787494589472,61.1337067088151,13.7859707837403
635.985171234099,44.4452157574178,14.3094180193726
1116.34581408648,81.7904540199775,13.6488521486115
510.454282219038,48.4583090978803,10.5338855548587
518.090150540254,8.60938204691003,60.1773910969836
1162.49495229153,68.8656583754022,16.8806191607797
1018.37232837763,62.4415602715829,16.3092069440342
184.206884561851,9.2376268690662,19.9409314938558
763.245320149297,8.0267518351911,95.0876937297421
1149.83369661697,68.0985629876674,16.8848452327137
658.714126920765,51.2279254784001,12.8584970164077
749.831736234241,56.3792616546344,13.2997792845803
246.728031639254,43.9563120682323,5.61302848283232
685.366494014556,48.1061058560666,14.2469751358626
475.116569315815,63.4724268280181,7.48540103253289
1184.62454049305,71.3951694742693,16.5925026751283
769.438729510337,118.611996861639,6.48702281277573
1139.44056987355,78.2927761952311,14.55358495696
559.3982097035,8.67168254959612,64.5086125448116
668.919915625723,47.7976798036393,13.9948197982361
795.073583813363,81.3549355590867,9.77289918982131
615.794581609889,61.188438031663,10.0639042508527
661.073178425251,94.4058029251923,7.00246338616588
1164.93615155336,68.9953018857477,16.8842822585577
831.058130277,59.8790608946116,13.8789439557123
736.425280665839,6.45262047955474,114.128094624381
1023.31218976872,62.7233868586514,16.314683262796
1158.03252705707,75.2421438436155,15.3907433773278
514.28870148554,72.6380631298102,7.08015438911778
856.225019097665,75.8489980173457,11.2885475283649
1016.98754809235,63.3836231555183,16.0449576319905
665.588439830414,50.1846979353361,13.2627766473365
526.391986344262,8.18896773719224,64.2806276978625
1165.37448932601,69.1954920400985,16.8417689500738
678.216658066484,5.9534827905057,113.919311087632
912.726735088656,84.5864382469383,10.7904618518642
792.667262489475,7.14661383679676,110.915082386033
721.328206250743,71.8890459649233,10.0339098477214
1006.81905594603,61.3935914151165,16.3994161725833
632.417690190266,47.3436575591716,13.3580234987094
483.788170621505,52.4715563853961,9.22000801859486
1180.0578098656,69.9190697306579,16.8774815570548
1094.1049679917,81.2909824143276,13.459118533163
983.484023434481,71.1299779788995,13.8265756770827
839.796815738163,59.6634792260851,14.0755588951809
498.163250755859,54.2093024789969,9.18962665031283
249.375683499672,42.8030920045317,5.82611376470815
648.673776919271,7.39622382802273,87.7033729646719
810.439719305663,58.4031444393286,13.8766452917202
664.880282833152,46.8516894395951,14.1911698550458
1040.49619508955,61.6255522124732,16.884168299249
1142.49809814831,66.9715190953219,17.0594621949992
183.427577741298,9.8851986172903,18.5557807023182
647.524237020807,48.0777269658202,13.468278928435
767.783152354092,98.6167703646603,7.78552318753718
558.192381813456,39.5889793212036,14.0996911611331
818.244915678415,59.4074895986261,13.7734302729624
513.802585053426,71.7370609943206,7.16230324928009
748.129377662551,7.53120916354137,99.3372194845218
930.797796519286,54.6521556210864,17.03130985304
684.647624065403,6.64426433783528,103.043405447722
219.996001887404,12.9669019934028,16.9659647307686
1011.95963548093,74.4533618991633,13.5918595167198
794.028616515608,69.9240196232087,11.3555916950183
467.282532768426,49.7264603143139,9.39706003232082
1069.25759805572,63.1904956903516,16.9211775659323
931.874988870851,58.0435981476657,16.0547419286467
544.254437821785,8.33319542007282,65.3116134191209
641.717463267959,98.9423880229356,6.48576890138536
1165.98758881702,81.5571137613269,14.2965773927364
817.687504453665,83.8314597069511,9.75394568234942
1072.7956761926,62.9961920574628,17.0295321217835
953.010948098821,100.013647284092,9.5288090573456
849.048333348047,115.121513391523,7.37523602960702
638.561325896524,59.512470950528,10.7298741876699
1101.80914542846,64.3498899688104,17.1221605190388
470.074441260341,66.4803664170669,7.07087620894434
1160.7361991702,74.0351566646166,15.6781757676073
963.431883446816,57.8117962143235,16.6649705861953
866.168298826463,62.0492772235082,13.9593616168393
283.192328350644,41.9546305852878,6.74996596084797
671.166116811921,47.4470090904559,14.1455937830005
243.898551471721,9.57031287995734,25.4849088562722
1039.24436450975,60.5705285178617,17.1575911576087
698.067699980212,71.6922080710728,9.73700934539742
619.866164920823,42.1574987032138,14.7035802404844
579.504392641967,67.2994176895732,8.61083814001188
1154.57758197929,72.4600708084859,15.9339836284576
520.387945916268,8.02724635522299,64.8277034101082
1101.42467261315,64.5415786759302,17.0653506655534
1068.15167862711,62.4580946256031,17.1018934379924
736.558970969195,90.625270250313,8.12752302900471
841.498250114011,120.213504361482,7.00003094147915
1088.83706609367,63.1557588438938,17.2405032577475
614.669904182212,43.5437995080733,14.1161293025945
703.795711843656,48.2382208448075,14.5900014452837
898.560993838497,60.8684178808444,14.7623517272539
250.019721989229,42.7889211230133,5.8430947877945
1076.33731223984,62.1988164588513,17.3047876715131
578.379875701866,50.806103605049,11.3840628322536
261.407844067136,17.0475161812426,15.3340722066458
1058.46047755996,61.5379004633803,17.2001395821073
828.635444204477,6.62741964292048,125.031383079784
258.596043228279,20.391622658073,12.6814843313071
830.785979683635,59.4671886175136,13.9704936284639
1081.6329280676,63.7246998881981,16.9735272188848
737.43211989366,76.9066810037613,9.58866135255004
504.162201253966,65.928677371904,7.64708502204564
750.254809125945,53.629549479705,13.9895788125139
988.268425641431,95.6088036908753,10.3365839492849
953.815990154617,57.6048421325237,16.5579134469339
868.741963483235,71.9830718360616,12.0686981164371
715.504137445214,5.88048483695352,121.674344426316
1148.47685489369,79.3051033506894,14.4817521996674
657.222686080398,80.6444860207,8.14962954704306
494.965452359725,70.4198767812463,7.02877475769087
557.261352455066,8.67534859644307,64.2350386569533
1102.54097434532,72.6617043231293,15.1736184089804
1166.32732004847,77.457596953738,15.0576233438415
1074.62700041157,61.8202585768605,17.3830880871438
854.61724157712,59.2685135332212,14.4194141312164
1351.62926970938,78.8829015443229,17.1346292193616
1047.1671153504,72.7007903467445,14.4037927284691
694.924970297679,49.9805842032134,13.9038985113143
828.658324291027,6.54878453558459,126.536202220166
583.586339299211,48.837209781703,11.949624925498
956.992678411413,57.3228920586925,16.6947731358626
630.877350374125,61.508339625229,10.2567774421821
840.838421331531,58.9485967373145,14.2639259943448
1063.22014224949,61.6054892576995,17.2585293138729
796.297391599454,113.722727017276,7.00209546925907
715.927689486895,62.7876734360521,11.4023605320565
261.285513892916,10.2279566377918,25.5462086070524
840.624134476516,59.7026155341914,14.0801894013353
873.391146435482,51.2820427740642,17.0311301810543
1031.80263140242,71.873214572487,14.3558714820221
1154.10913902807,84.6616418924636,13.6320193328404
694.861207698147,93.8231014863426,7.4060779988103
564.497626576878,62.5589730694249,9.02344777863324
1383.46235940519,79.8237807207021,17.3314562015776
673.43442131044,49.9568423658024,13.4803240040535
948.197174728681,55.4210047776065,17.1089856370091
208.623502843133,9.42517999766412,22.1346969389271
1057.66977184788,57.7013963461834,18.3300550562472
593.651575758216,72.0019313622938,8.24493960823253
1396.12970397736,81.0329169812247,17.2291675529938
977.665387314612,94.236257687239,10.374620250301
944.894761745995,62.4125754739313,15.1394931962175
252.951492564745,43.6877033725035,5.78999290505048
784.156766770674,69.6144817064223,11.2642764486506
869.600167578196,52.337882303881,16.6151194755871
710.005098724058,6.37643505889638,111.348283510464
867.109088620376,86.9595847496019,9.9714032802387
996.9140740984,56.6607993148479,17.5944230606214
1126.36882497793,74.0360617575447,15.2137863392382
1003.32995882055,58.0920699145605,17.2713755990483
651.138598600569,50.5763018326244,12.8743813803434
844.515428048511,6.81704894266282,123.882846544246
576.106357758339,51.5439471193834,11.1769934193047
992.109951666725,56.0834774215358,17.6898793954913
644.278867143651,95.6581598070878,6.73522121315064
995.569189170372,56.5440859269078,17.6069552252963
888.341440629926,62.7021171648371,14.1676466568836
1359.79569761804,79.9695690320788,17.0039142898542
717.403415146655,6.74802007858124,106.313171388412
282.673947745812,43.3047170068405,6.52755559402827
1172.80276287497,77.6088384333847,15.1117164816433
917.107055683623,60.1444149546947,15.2484159397752
816.923640135252,115.570414868327,7.06862254553642
464.807691998318,64.5819738145042,7.19717383264506
871.791737168063,52.7481014191027,16.5274524336215
1022.18824326786,57.4629575852742,17.7886465685471
517.664181967137,7.84160601803337,66.0150715015092
614.596857512926,59.4185800524888,10.3435130386826
866.811056971428,52.103232017142,16.6364162723389
1385.64909866304,80.2630072273835,17.2638572429454
721.138910002951,49.6764411325895,14.516718459726
766.459058456285,7.9201304652722,96.773539503802
704.343411540687,70.31242095699,10.0173397808551
853.05006857076,7.5708365767801,112.675800080942
627.915550526086,61.5629413568015,10.1995703370777
1361.37466659606,78.7703521294047,17.282830783333
264.582605698173,43.3762290224228,6.09971432881822
938.370400044133,82.6336534406288,11.3557898141142
1126.48315768714,81.1192758514413,13.8867506626926
979.827315102371,55.227127045617,17.7417759626179
505.472876614513,48.6171088556024,10.3970163696039
791.750397920969,118.739836310455,6.66794247425838
676.154932193,49.4776550198178,13.6658645589039
980.277431315768,55.2132655266126,17.7543824290428
734.001552531788,7.31432028962465,100.351300389862
976.72574024949,55.3406022216021,17.6493514894969
846.300973131295,82.0689173084518,10.3120767385113
838.113161688194,84.6487445586878,9.90107019374778
854.539016707292,51.5469683862906,16.5778714725455
961.92479533997,54.1016574892609,17.7799505593874
265.61340634876,14.0364161778449,18.9231640743173
894.324214970059,59.0129548026464,15.1547099778497
814.037656409623,48.7749022058312,16.6896830048857
354.813887078032,37.2303720744981,9.53022672908153
537.911300179912,66.8330427169206,8.04858313062746
1027.66604448814,69.6492515403915,14.7548756341218
563.239265660982,72.0976166374446,7.81217593493179
1155.46921480469,80.3054065706974,14.3884361482867
679.536842775566,51.2274673910366,13.2650876059992
796.368567195073,56.06359679384,14.204735563498
677.264357933236,79.1411804780015,8.55767318408262
547.431218112839,7.42565928183948,73.7215642861047
1031.71986009956,73.5590367781098,14.025739124504
930.584545334349,52.1410045020415,17.8474610188592
843.986776560976,48.3968403371198,17.4388817675283
1293.52419141863,74.4264309602821,17.3799035467511
782.904081094442,7.17621923971997,109.097012638788
934.64249263278,52.1322456718868,17.9282990898818
623.226757624836,7.96708629603804,78.2251797542046
970.418087129436,52.8482402625969,18.3623538325503
303.442999442797,40.0263935113363,7.58107270785853
577.747766711815,52.0150641858955,11.1073162314481
846.511407749841,47.2273808778857,17.9241658549441
926.231749745451,51.7643765906155,17.8932271718572
993.086757584895,98.3343468603706,10.0990832734672
658.641755700138,46.2528045804751,14.2400393159764
872.453537277444,60.9129550684073,14.3229553762028
797.358096929358,6.02279193921707,132.390111592168
666.490000569727,45.6473048186752,14.6008620490788
721.157101755568,62.6941919092202,11.502773698715
1122.95075245574,73.0788407740893,15.3662912624347
872.8020371521,57.146937070571,15.2729451811962
540.599731505117,9.32173850477438,57.9934452385931
706.755078699019,87.5836971871925,8.06948212277991
830.819157805731,46.0386176000118,18.046136072633
566.615005602821,53.3184790931194,10.6269911527904
271.187799297243,9.40516272167397,28.8339295472578
640.227831174316,52.0894631889877,12.2909277995721
868.025803785126,79.2030590991386,10.9594984544551
819.601359106328,79.0193612549607,10.3721587480546
643.576442058412,47.7078812039502,13.4899397293947
909.228848969586,57.9923914643411,15.6784161854864
1100.01551637581,68.7828585085853,15.9925821669436
807.99126506455,44.8761511942584,18.0049144938242
711.79127060755,48.7370167440546,14.6047361566172
669.293105264384,46.9639768028139,14.2512016832502
750.572267105405,6.75824435303759,111.060244036315
805.286978853394,44.9236051433011,17.9256979996289
796.653528995929,117.657336544635,6.7709634808341
906.049765633183,61.2038123758745,14.8038125479636
860.082070314086,48.7079325305222,17.6579465731814
528.897388614536,48.6037488583184,10.88182292597
725.916567325999,48.9962859475011,14.8157468119892
1171.23104351,72.407903233399,16.1754586337718
271.115300648325,42.4969209311526,6.37964574157141
818.176466723655,45.1780603639039,18.1100396992111
706.895049202311,96.524864281297,7.32345033029258
1129.85449184923,63.9671382305525,17.66304579356
830.569449354848,47.519961170012,17.4783276102294
1161.48155942179,79.9866503158027,14.5209426177498
799.323463012984,6.90137479443283,115.820903344907
1026.06950758535,97.5591906233855,10.5174048803495
867.636345570733,48.9396801888697,17.728688504345
677.359690770258,47.7387610079239,14.1888829217379
574.472527508353,74.577841724733,7.70299212504342
813.483449106188,45.6055738448501,17.8373689995362
531.893023362667,66.3458970068103,8.01696935845285
817.296013892808,113.71271909021,7.18737552344021
713.33088051632,48.6485667886468,14.6629372169457
1128.85728471138,63.1626101015632,17.8722393342552
865.10116525594,48.7652927321721,17.7400999109599
322.616153216964,42.1966225097395,7.64554445423921
720.972783584823,6.3669539185474,113.236689444944
778.06898147789,43.1555333145594,18.0294141149078
1225.72719274588,81.8174032837245,14.9812526864893
1168.23272198486,63.0740797395287,18.5215975692266
765.901421943323,73.1537339032923,10.4697515912972
873.780025960545,47.9831673991481,18.2101364566454
1112.44187725866,69.3257667645434,16.0465859834907
882.998832097523,73.7073332607817,11.9797962161161
575.434546744269,53.5303055059797,10.7496966681796
561.337326365201,7.73217598042469,72.5975880251977
860.873094722788,77.998232494422,11.0370846516856
916.186682340258,50.284116297159,18.2202005286513
1053.07552206902,73.0791080555573,14.4100762870345
1059.71160884098,70.4403743270742,15.044093944198
885.428522146107,120.956741193437,7.32020814557256
1346.16794720647,75.6208264521117,17.8015503184028
276.925778486357,43.6241594432985,6.34799115949267
906.203977861731,49.9900889756839,18.1276728333596
612.51743960058,56.8148480360228,10.7809395039167
910.89966686315,57.7015056003705,15.7864107250834
697.293608862074,44.1098210401989,15.8081260004797
574.775710556546,69.1378969375409,8.31346824268891
856.841283734152,49.4613361998274,17.3234560480221
1216.39447043105,76.5578086193727,15.8885748216577
265.643639706113,10.4580923495948,25.4007739486452
574.173781708331,53.6685579165926,10.6985133194871
1030.97988591845,93.2652240932573,11.0542798341165
655.361295957022,46.169724910925,14.1946112354234
591.623032423643,40.6332728528505,14.5600634870381
921.532980372998,60.0312093682118,15.3508981423415
679.377025302583,93.9909920884108,7.22810782402999
758.56647143844,42.2713988153294,17.9451471372495
836.087844217789,7.85908406826307,106.384896376681
861.816646050012,98.7807620877275,8.72453935195023
837.305406645717,57.6194249958519,14.5316515516424
773.056494583846,42.737458434722,18.0884994779142
269.738705701556,12.9807674723294,20.7798734763986
1200.69158015954,76.2948355310129,15.7375210497894
780.18977261685,45.262109330312,17.2371501054715
733.226488871681,6.34303911199887,115.595454469872
555.196730673397,50.9950281247519,10.8872717809899
857.108003346016,47.6567365163975,17.9850335125467
952.428525591511,62.3578627278814,15.2735915556911
895.483515207574,58.7400426765796,15.2448563944373
691.721941873944,8.6454761363177,80.0096988259763
726.616137700927,49.6097878988998,14.6466285883283
764.194888551527,43.3168828279521,17.6419640255923
915.523888569179,47.2805325943979,19.3636543061627
892.514888148552,83.6565876639131,10.6687938520059
1005.63589199243,58.8465912502789,17.0891103567136
568.845855194287,61.505211695239,9.24874233443733
745.562092716827,70.1827698666766,10.6231500143574
1041.59114555383,107.216987598629,9.71479584422818
881.607367727917,65.1500228366785,13.5319579232992
794.837361604731,6.21372148853755,127.916476956839
865.27837268516,45.6799651877453,18.9421854664042
557.587178042882,67.0585547696638,8.31492983942334
1162.79627857404,61.3911671517486,18.9407749114755
1185.59999212125,78.620515928558,15.0800332218451
942.413740908592,55.5241193604162,16.9730515632536
934.298073132544,62.1577037431685,15.0310905466039
870.93256880831,45.8056264381727,19.0136591622401
812.641234560375,44.0927529634965,18.4302675596859
1002.54718922372,90.5087014182687,11.0768044786173
291.449573656779,9.40146218628018,31.0004516193343
776.653452684421,7.01681873769525,110.684554029042
951.175605458871,57.9690500654482,16.4083352131004
593.159494315019,44.69377577632,13.2716353454588
728.070226435854,47.3049932140099,15.390980464621
1206.14720083557,76.6329068676918,15.7392855123974
878.910059385352,45.3478977152565,19.3814951445844
682.884348313215,52.4234496213667,13.0263146215179
559.048888273261,7.92329280311353,70.5576459390188
772.817533157271,40.0715773659901,19.2859274317757
730.999061202589,46.8033904091955,15.6185065827832
1131.82282383852,59.0879640748468,19.1548793660386
709.310865376529,84.6610011363411,8.37824802277296
806.677018536328,42.4259980868468,19.0137428678766
812.985332707849,7.71235725583688,105.413339364247
613.07278843776,67.7072707540518,9.05475559138635
668.043216728699,45.6798726894806,14.624454434667
741.805247009802,48.3131230196996,15.3541150032328
846.833273326224,45.6095313277354,18.5670242309914
909.122842257941,48.030791127037,18.9279172989967
295.142025029424,43.3260137664673,6.81212046463072
930.461123973853,48.2419027186448,19.2874051714018
1030.02961536967,68.6798592033116,14.9975498977145
559.605990143784,62.131373927552,9.0068182106565
319.068029697597,22.6341223959371,14.0967705359263
Concentrating on the “Speed-up” tab showing the speed-up between the unoptimised and optimised versions of our code, we can see that for most input vector lengths the optimised code is around 10-20 times faster. For some input vector lengths though, we get speed-up factors of 50-100 times compared to the unoptimised code. This is definitely good news. A lot of this improvement in performance comes from using specialised straight line code for small prime length transforms. In the next article, we’ll think about how to exploit this kind of specialised code for other input sizes (especially powers of two, which will also give us a speed-up for the convolution in Rader’s algorithm).
Looking at the “pre-release-2” tab, we appear to be getting to within a factor of 10 of the performance of FFTW for some input vector lengths, which is really not bad, considering the limited amount of optimisation that we’ve done, and my own relative lack of experience with optimising this kind of Haskell code!