[ch26 done. Don Stewart **20080822103140] { hunk ./en/ch26-profiling.xml 4 - Performance and efficiency: profiling + Profiling and optimisation + + +Haskell is a high level language. A really high level language. We can spend +our days programming entirely in abstractions, in monoids, functors and +hylomorphisms, far removed from any particular hardware model of computation. +The language specification goes to great lengths to avoid prescribing any +particular evaluation model. These layers of abstraction let us treat Haskell +as a notation for computation itself, letting the programmer concentrate on the +essence of their problem without getting bogged down in low level +implementation decisions. We get to program in pure thought. + + + +However, this is a book about real world programming, and in the real world, +code runs on stock hardware with limited resources. Our programs will have +time and space requirements that we may need to enforce. As such, we need a +good knowledge of how our program data is represented, the precise consequences +of using lazy or strict evaluation strategies, and techniques for analysing and +controlling space and time behaviour. + + + +In this chapter we'll look at typical space and time problems a Haskell +programmer might encounter, and how to methodically analyse, understand and +address them. To do this we'll use time and space profiling, and collect +runtime statistics, as well as reasoning about how strict or lazy evaluation +strategies affect behaviour. We'll also look at the impact of compiler +optimisations on performance, and the use of advanced optimisation techniques +that become feasible in a purely functional language. So let's begin with a +classic challenge: squashing excessive memory usage in some inoccuous looking +code. + + + + Profiling Haskell programs + + + + +Let's consider the following list manipulating program, which naively computes +the mean of some large list of values. While only a program fragment (and +we'll stress that the particular algorithm we're implementing is irrelevant +here), it is representative of real code we might find in any Haskell +program: typically concise list manipulation code, and heavy use of standard +library functions. It also illustrates several common performance trouble +spots that can catch out the unwary: + +&A.hs:naive; + + +This program is very simple: we import functions for accessing the +system's environment (in particular, getArgs), and the +Haskell version of printf, for formatted text output. +The program then reads a numeric literal from the command line, using that to +build a list of floating point values, whose mean value we compute by +dividing the list sum by its length. The result is printed as a string. Let's +compile this source to native code (with optimisations on) and run it with +the standard time command to see how it performs: + + + + + +$ ghc --make -O2 A.hs +[1 of 1] Compiling Main ( A.hs, A.o ) +Linking A ... +$ time ./A 1e5 +50000.5 +./A 1e5 0.05s user 0.01s system 102% cpu 0.059 total +$ time ./A 1e6 +500000.5 +./A 1e6 0.26s user 0.04s system 99% cpu 0.298 total +$ time ./A 1e7 +5000000.5 +./A 1e7 63.80s user 0.62s system 99% cpu 1:04.53 total + + + +It worked well for small numbers, but the program really started to struggle +with input size of ten million. From this alone we know something's not quite +right, but it's unclear what resources are being used. Let's investigate, and +see what we can find out about this program's behaviour. + + + + Collecting runtime statistics + + +To get access to that kind of information, GHC lets us pass flags directly to +the Haskell runtime, using the special +RTS and +-RTS flags to delimit arguments reserved for the runtime system. +The application itself won't see those flags as they're immediately consumed +by the Haskell runtime system. + + + +In particular, we can ask the runtime system to gather memory and garbage +collector performance numbers with the -s flag (as well as +controlling the number of OS threads with -N, or tweaking the +stack and heaps sizes). We'll also use runtime flags to enabling different +varieties of profiling. The complete set of runtime flags the Haskell +runtime accepts is documented in the +GHC User's Guide: + + + +So let's run the program with statistic reporting enabled, via +RTS -sstderr, +yielding this result: + + + +$ ./A 1e7 +RTS -sstderr +./A 1e7 +RTS -sstderr +5000000.5 +1,689,133,824 bytes allocated in the heap +697,882,192 bytes copied during GC (scavenged) +465,051,008 bytes copied during GC (not scavenged) +382,705,664 bytes maximum residency (10 sample(s)) + + 3222 collections in generation 0 ( 0.91s) + 10 collections in generation 1 ( 18.69s) + + 742 Mb total memory in use + + INIT time 0.00s ( 0.00s elapsed) + MUT time 0.63s ( 0.71s elapsed) + GC time 19.60s ( 20.73s elapsed) + EXIT time 0.00s ( 0.00s elapsed) + Total time 20.23s ( 21.44s elapsed) + + %GC time 96.9% (96.7% elapsed) + + Alloc rate 2,681,318,018 bytes per MUT second + + Productivity 3.1% of total user, 2.9% of total elapsed + + + +When using -sstderr, our program's performance numbers are +printed to the standard error stream, giving us a lot of information about +what our program was doing. In particular, it tells us how much time was +spent in garbage collection, and what the maximum live memory in use was. It +turns out that to compute the mean of a list of 10 million elements our +program used a maximum of 742 megabytes to the heap, and spent 96.9% of its time +doing garbage collection! In total, only 3.1% of the program's runtime was +spent doing productive work. + + + +So why is our program behaving so badly, and what can we do to improve it? +After all, Haskell is a lazy language: shouldn't it be able to process the +list in constant space? + + + + + + Time profiling + + +GHC, thankfully, comes with several tools to analysing a program's time and +space usage. In particular, we can compile a program with profiling enabled, +which when run, yields useful information about what resources each function +was using. Profiling proceeds in three steps: compiling the program for +profiling; running it with particular profiling modes enabled; and inspecting +the resulting statistics. + + + +To compile our program for basic time and allocation profiling, we use the +-prof flag. We also need to tell the profiling code which +functions we're interested in profiling, by adding "cost centres" to them. A +cost center is a location in the program we'd like to collect statistics about, +and GHC will generate code to compute the cost of evaluation the expression +at each location. Cost centres can be added manually to any expression, using +the SCC pragma: + +&SCC.hs:scc; + + +Alternatively, we can have the compiler insert the cost centres on all top +level functions for us by compiling with the -auto-all flag. +Manual cost centres are a useful addition to automated cost centre profiling, +as once a hot spot has been identified, we can precisely pin down the +expensive sub-expressions of a function. + + + +One complication to be aware of: in a lazy, pure language like Haskell, values +with no arguments need only be computed once (for example, the large list in +our example program), and the result shared for later uses. Such values are not +really part of the call graph of a program, as they're not evaluated on each +call, but we would of course still like to know how expensive their one-off +cost of evaluation was. To get accurate numbers for these values, known as +"constant applicative forms", or CAFs, we use the -caf-all flag. + + + +Compiling our example program for profiling then (using the +-no-recomp flag to to force full recompilation): + + + +$ ghc -O2 --make A.hs -prof -auto-all -caf-all -no-recomp +[1 of 1] Compiling Main ( A.hs, A.o ) +Linking A ... + + + +We can now run this annotated program with time profiling enabled (and we'll +use a smaller input size for the time being, as the program now has +additional profiling overheads): + + + +$ time ./A 1e6 +RTS -p +Stack space overflow: current size 8388608 bytes. +Use `+RTS -Ksize' to increase it. +./A 1e6 +RTS -p 1.11s user 0.15s system 95% cpu 1.319 total + + + +The program ran out of stack space! This is the main complication to be aware +of when using profiling: adding cost centres to a program modifies how it is +optimised, possibly changing its runtime behaviour, as each expression now +has additional code associated with it to track the evaluation steps. In a +sense, observing the program executing modifies how it executes. In this +case, it is simple to proceed, we use the GHC runtime flag, -K, +to set an arbitrarily large stack limit for our program: + + +$ time ./A 1e6 +RTS -p -K100M +500000.5 +./A 1e6 +RTS -p -K100M 4.27s user 0.20s system 99% cpu 4.489 total + + + +The runtime will dump its profiling information into a file, +A.prof, named after the binary that was executed, which +contains the following information: + + + +Time and Allocation Profiling Report (Final) + + A +RTS -p -K100M -RTS 1e6 + + total time = 0.28 secs (14 ticks @ 20 ms) + total alloc = 224,041,656 bytes (excludes profiling overheads) + +COST CENTRE MODULE %time %alloc + +CAF:sum Main 78.6 25.0 +CAF GHC.Float 21.4 75.0 + + individual inherited +COST CENTRE MODULE no. entries %time %alloc %time %alloc + +MAIN MAIN 1 0 0.0 0.0 100.0 100.0 + main Main 166 2 0.0 0.0 0.0 0.0 + mean Main 168 1 0.0 0.0 0.0 0.0 + CAF:sum Main 160 1 78.6 25.0 78.6 25.0 + CAF:lvl Main 158 1 0.0 0.0 0.0 0.0 + main Main 167 0 0.0 0.0 0.0 0.0 + CAF Numeric 136 1 0.0 0.0 0.0 0.0 + CAF Text.Read.Lex 135 9 0.0 0.0 0.0 0.0 + CAF GHC.Read 130 1 0.0 0.0 0.0 0.0 + CAF GHC.Float 129 1 21.4 75.0 21.4 75.0 + CAF GHC.Handle 110 4 0.0 0.0 0.0 0.0 + + + +This gives us a view into the program's runtime behaviour. We can see the +program's name and the flags we ran it with. The "total time" is time actually +spent executing code from the runtime system's point of view, and the total +allocation is the number of bytes allocated during the entire program run (not +the maximum live memory, which was around 700M). + hunk ./en/ch26-profiling.xml 285 - FIXME - + +The second section of the profiling report is the proportion of time and space +each function was responsible for. The third section is the cost centre report, +structured as a call graph (for example, we can see that +mean was called from main. The +"individual" and "inherited" columns give us the resources a cost centre was +responsible for on its own, and what it and its children were responsible for. +Additionally, we see the one-off costs of evaluating constants, (such as the +floating point values in the large list, and the list itself), assigned to top +level CAFs. + + + +What conclusions can we draw from this information? We can see that the +majority of time is spent in two CAFs, one related to computing the sum, and +another for floating point numbers. These alone accounts for nearly all +allocations that occured during the program run. Combined with our earlier +observation about garbage collector stress, it begins to look like the list +node allocations, containing floating point values, are causing a problem. + + + +For simple performance hot spot identification, particularly in large programs +where we might have little idea where time is being spent, the initial time +profile can narrow down to a particular problematic module and top level +function, which is often enough to reveal the trouble spot. Once we've narrowed +down the code to a problematic section, such as our example here, we can use +more sophisticated profiling tools to extract more information. + hunk ./en/ch26-profiling.xml 315 - hunk ./en/ch26-profiling.xml 389 - Cautions: - - inhibits optimisation + + + + + +What does this graph tell us? For one, the program runs in two phases: spending +its first half allocating increasingly large amounts of memory, while summing +values, and the second half cleaning up those values. The initial allocation +also coincides with sum, doing some work, allocating a lot of +data. We get a slightly different presentation if we break down the allocation +by type, using -hy profiling: + + + +$ time ./A 1e6 +RTS -hy -p -K100M +500000.5 +./A 1e6 +RTS -i0.001 -hy -p -K100M 34.96s user 0.22s system 99% cpu 35.237 total +$ hp2ps -e8in -c A.hp + + + +Which yields the following graph: + + + + + + + +The most interesting things to notice here are large parts of the heap devoted +to values of list type (the [] band), and heap-allocated +Double values. There's also some heap allocated data of unknown +type. Finally, let's break it down by what constructors are being allocated, +using the -hd flag: + + + +$ time ./A 1e6 +RTS -hd -p -K100M +$ time ./A 1e6 +RTS -i0.001 -hd -p -K100M +500000.5 +./A 1e6 +RTS -i0.001 -hd -p -K100M 27.85s user 0.31s system 99% cpu 28.222 total + + + +Our final graphic reveals the full story of what is going on: + + + + + + + +A lot of work is going into allocating list nodes containing double precision +floating point values. Haskell lists are lazy, so the full million element +list is built up over time. Crucially, though, it is not being deallocated as it is +traversed, leading to increasingly large resident memory use. Finally, a bit +over half our way through the program run, the program finally finishes +summing the list, and starts calculating the length. If we look at the +original fragment for mean, we can see exactly why that memory +is being retained. + + +&Fragment.hs:fragment; + + +At first we sum our list, which triggers the allocation of list nodes, but +we're unable to release the list nodes once we're done, as the entire list is +still needed by length. As soon as +sum is done though, and length +starts consuming the list, the garbage collector can chase it along, +deallocating the list nodes, until we're done. These two phases of evaluation +give two strikingly different phases of allocation and deallocation, and +point at exactly what we need to do: traverse the list only once, summing and +averaging it as we go. + + + + + + + + Controlling evaluation + + +We have a number of options if we want to write our loop to traverse the list +only once. For example, we can write the loop as a fold over the list, or via +explicit recursion on the list structure. Sticking to the high level +approaches, we'll try a fold first: + + +&B.hs:fold; + + +Now, instead of taking the sum of the list, and retaining the list till we can +take its length, we left-fold over the list accumulating the intermediate sum +and length values in a pair (and we must left fold, since a right fold would +take us to the end of the list and work backwards, which is exactly not what +we need in this case). + + + +The body of our loop is the k function, which takes the +intermediate loop state, and the current element, and returns a new state with +the length increased by one, and the sum increased by the current element. When +we run this, however, we get surprising results: + + +$ ghc -O2 --make B.hs -no-recomp +$ time ./B 1e6 +Stack space overflow: current size 8388608 bytes. +Use `+RTS -Ksize' to increase it. +./B 1e6 0.44s user 0.10s system 96% cpu 0.565 total + + + +We traded wasted heap for wasted stack! In fact, if we increase the stack size +to the size of the heap in our previous implementation, with the +-K runtime flag, the program runs to completion, and has similar +allocation figures: + + + +$ ghc -O2 --make B.hs -prof -auto-all -caf-all -no-recomp +[1 of 1] Compiling Main ( B.hs, B.o ) +Linking B ... +$ time ./B 1e6 +RTS -i0.001 -hc -p -K100M +500000.5 +./B 1e6 +RTS -i0.001 -hc -p -K100M 38.70s user 0.27s system 99% cpu 39.241 total + + + +Generating the heap profile, we see all the allocation is now in mean: + + + + + + + +The question is: why are we building up more and more allocated state, when all +we are doing is folding over the list? This, it turns out, is a classic space +leak due to excessive laziness. + + + + Strictness and tail recursion + + +The problem is that our left fold, foldl is too lazy. +What we want is a tail recursive loop, which can be implemented effectively +as a goto, where no state is left on the stack. In this case +though, rather than fully reducing the tuple state at each step, a long chain +of thunks is being created, that only towards the end of the program is +evaluated. At no point do we demand reduction of the loop state, so the +compiler is unable to infer any strictness, and must reduce the value purely +lazily. + + + +What we need to do is to tune the evaluation strategy slightly: lazily +unfolding the list, but strictly accumulating the fold state. The standard +approach here is to replace foldl with +foldl', from the Data.List module: + + +&C.hs:fold; + + +However, if we run this implementation, we see we still haven't quite got it +right: + + + +$ ghc -O2 --make C.hs +[1 of 1] Compiling Main ( C.hs, C.o ) +Linking C ... +$ time ./C 1e6 +Stack space overflow: current size 8388608 bytes. +Use `+RTS -Ksize' to increase it. +./C 1e6 0.44s user 0.13s system 94% cpu 0.601 total + + + +Still not strict enough! Our loop is continuing to accumulate unevaluated +state on the stack. The problem here is that foldl' is +only outermost strict: + + +&Foldl.hs:fold; + + +This loop uses `seq` to reduce the accumulated state at +each step, but only to the outermost constructor on the loop state. That is, +seq reduces an expression to "weak head normal form". Evaluation +stops on the loop state once the first constructor is reached. In this case, +the outermost constructor is the tuple wrapper, (,), which +isn't deep enough. The problem is still the unevaluated numeric state inside +the tuple. + + + + + Adding strictness + + +There are a number of ways to make this function fully strict. We can, for +example, add our own strictness hints to the internal state of the tuple, +yielding a truly tail recursive loop: + + +&D.hs:fold; + + +In this variant, we step inside the tuple state, and explicitly tell the +compiler that each state component should be reduced, on each step. This +gives us a version that does, at last, run in constant space: + + + +$ ghc -O2 D.hs --make +[1 of 1] Compiling Main ( D.hs, D.o ) +Linking D ... + + + +If we run this, with allocation statistics enabled, we get the satisifying +result: + + + +$ time ./D 1e6 +RTS -sstderr +./D 1e6 +RTS -sstderr +500000.5 +256,060,848 bytes allocated in the heap + 43,928 bytes copied during GC (scavenged) + 23,456 bytes copied during GC (not scavenged) + 45,056 bytes maximum residency (1 sample(s)) + + 489 collections in generation 0 ( 0.00s) + 1 collections in generation 1 ( 0.00s) + + 1 Mb total memory in use + + INIT time 0.00s ( 0.00s elapsed) + MUT time 0.12s ( 0.13s elapsed) + GC time 0.00s ( 0.00s elapsed) + EXIT time 0.00s ( 0.00s elapsed) + Total time 0.13s ( 0.13s elapsed) + + %GC time 2.6% (2.6% elapsed) + + Alloc rate 2,076,309,329 bytes per MUT second + + Productivity 97.4% of total user, 94.8% of total elapsed + +./D 1e6 +RTS -sstderr 0.13s user 0.00s system 95% cpu 0.133 total + + + +Unlike our first version, this program is 97.4% efficient, spending only 2.6% +of its time doing garbage collection, and it runs in a constant 1 megabyte of +space. It illustrates a nice balance between mixed strict and lazy +evaluation, with the large list unfolded lazily, while we walk over it, +strictly. The result is a program that runs in constant space, and does so quickly. + + + + Normal form reduction + + +There are a number of other ways we could have addressed the strictness issue +here. For deep strictness, we can use the rnf function, part of +the parallel strategies library, which unlike seq reduces to +normal form (hence its name). Such a "deep seq" fold we can write as: + + +&E.hs:fold; + + +We change the implementation of foldl' to reduce the state to +normal form, using the rnf strategy. This also raises an issue +we avoided earlier: the type inferred for the loop accumulator state. +Previously, we relied on type defaulting to infer a numeric, integral type +for the length of the list in the accumulator, but switching to +rnf introduces the NFData class constraint, and we +can no longer rely on defaulting to set the length type. + + + + + + Bang patterns + + +Perhaps the cheapest way, syntactically to add required strictness to code +that's excessively lazy is via "bang patterns", a language extension +introduced with the following pragma: + + +&F.hs:pragma; + + +With bang patterns, we can hint at strictness on any binding form, making the +function strict in that variable. Much as explicit type annotations can +guide type inference, bang patterns can help guide strictness inference. +We can now rewrite the loop state to be simply: + + +&F.hs:fold; + + +The intermediate values in the loop state are now made strict, and the loop +runs in constant space: + + + +$ ghc -O2 F.hs --make +$ time ./F 1e6 +RTS -sstderr +./F 1e6 +RTS -sstderr +500000.5 +256,060,848 bytes allocated in the heap + 43,928 bytes copied during GC (scavenged) + 23,456 bytes copied during GC (not scavenged) + 45,056 bytes maximum residency (1 sample(s)) + + 489 collections in generation 0 ( 0.00s) + 1 collections in generation 1 ( 0.00s) + + 1 Mb total memory in use + + INIT time 0.00s ( 0.00s elapsed) + MUT time 0.14s ( 0.15s elapsed) + GC time 0.00s ( 0.00s elapsed) + EXIT time 0.00s ( 0.00s elapsed) + Total time 0.14s ( 0.15s elapsed) + + %GC time 0.0% (2.3% elapsed) + + Alloc rate 1,786,599,833 bytes per MUT second + + Productivity 100.0% of total user, 94.6% of total elapsed + +./F 1e6 +RTS -sstderr 0.14s user 0.01s system 96% cpu 0.155 total + + + +In large projects, when we investigating memory allocation hot spots, bang +patterns are the cheapest way to speculatively modify the strictness +properties of some code, as they're syntactically less invasive than other +methods. + + + + + +Strict data types + + +Strict data types are another effective way to provide strictness information +to the compiler. By default, Haskell data types are fully lazy, but it is +easy enough to to add strictness information to the fields of a data type +that then propagate through the program. We can declare a new strict pair +type, for example: + + +&G.hs:pair; + + +This creates a pair type whose fields will always be kept in weak head normal +form. We can now rewrite our loop as: + + +&G.hs:fold; + + +This implementation again has the same efficient, constant space behaviour. +At this point, to squeeze the last drops of performance out of this code, +though, we have to dive a bit deeper. + + + + + + + + + + Understanding Core + + +Besides looking at runtime profiling data, one sure way of determining +exactly what your program is doing is to look at the final program source after +the compiler is done optimising it, particularly in the case of Haskell +compilers, which can perform very aggressive transformations on the code. GHC +uses "a simple functional language", known as Core, as the compiler +intermediate representation. It is essentially a subset of Haskell, augmented +with unboxed data types (these are raw machine types, directly corresponding +to primitive data types in languages like C), suitable for code generation. +GHC optimises Haskell by transformation, repeatedly rewriting the source into +more and more efficient forms. The Core representation is the final version +of your program, and the one that will be executed on the machine. In other +words, Core has the final say, and if all out performance is your goal, it is +worth understanding. + + + +To view the Core our Haskell program we compile with the +-ddump-simpl flag, or use the ghc-core core tool, a +third party utility that lets us view Core in a pager. So let's look at the +representation of our final fold using strict data types, in +Core form: + + + +$ ghc -O2 -ddump-simpl G.hs + + + +A screenful of text is generated, which if we look carefully at, we'll see a +loop (here, cleaned up slightly for clarity): + + + +lgo :: Integer -> [Double] -> Double# -> (# Integer, Double #) + +lgo = \ n xs s -> + case xs of + [] -> (# n, D# s #); + (:) x ys -> + case plusInteger n 1 of + n' -> case x of + D# y -> lgo n' ys (+## s y) + + + +This is the final version of our foldl', and tells us a lot +about the next steps for optimisation. The fold itself has been entirely +inlined, yielding an explicit recursive loop over the list. The loop state, +our strict pair, has disappeared entirely, and the function now takes its +length and sum accumulators as direct arguments along with the list. + + + +The sum of the list elements is represented with an unboxed +Double# value, a raw machine double kept in a +floating point register. This is ideal, as there will be no memory traffic +involved keeping the sum on the heap. However, the length of the list, since +we gave no explicit type annotation, has been inferred to be a heap-allocated +Integer, with requires a non-primitive plusInteger +to perform addition. If it is algorithmically sound to use a Int +instead, we can replace Integer with it, and GHC will then be +able to use a raw machine int for the length. We can hope for an +improvement in time and space by ensuring both loop components are unboxed, +and kept in registers. + + + +The base case of the loop, its end, yields an unboxed pair (a pair allocated +only in registers), storing the final length of the list, and the accumulated +sum. Notice that the return type is a a heap-allocated Double +value, indicated by the D# constructor, which lifts a raw double +value onto the heap, and again this has implications for performance, as GHC +will need to check there is sufficient heap space available before it can +allocate and return from the loop. + + + +We can avoid this final heap check by having GHC return an unboxed +Double# value, which can be achieved by using a custom pair type +in the loop. In addition, can can enable an optimisation GHC provides, that +unboxes the strict fields of a data type, which will ensure the new pair data +type is stored entirely in registers. This optimisation is turned on with +-funbox-strict-fields. + + + +We can make both representation changes by replacing the polymorphic strict +pair type with one whose fields are fixed as Int and +Double: + + +&H.hs:fold; + + +Compiling this with optimisations on, and -funbox-strict-fields -ddump-simpl, +we get a tighter inner loop in Core: + + + +lgo :: Int# -> Double# -> [Double] -> (# Int#, Double# #) +lgo = \ n s xs -> + case xs of + [] -> (# n, s #) + (:) x ys -> + case x of + D# y -> lgo (+# n 1) (+## s y) ys + + + +Now the pair we use to represent the loop state is represented and returned as +unboxed primitive types, and will be kept in registers. The final version now +only allocates heap memory for the list nodes, as the list is lazily demanded. +If we compile and run this tuned version, we can compare the allocation and time +performance against our original program, with the full input size: + + + +$ time ./H 1e7 +RTS -sstderr +./H 1e7 +RTS -sstderr +5000000.5 +1,689,133,824 bytes allocated in the heap + 284,432 bytes copied during GC (scavenged) + 32 bytes copied during GC (not scavenged) + 45,056 bytes maximum residency (1 sample(s)) + + 3222 collections in generation 0 ( 0.01s) + 1 collections in generation 1 ( 0.00s) + + 1 Mb total memory in use + + INIT time 0.00s ( 0.00s elapsed) + MUT time 0.63s ( 0.63s elapsed) + GC time 0.01s ( 0.02s elapsed) + EXIT time 0.00s ( 0.00s elapsed) + Total time 0.64s ( 0.64s elapsed) + + %GC time 1.0% (2.4% elapsed) + + Alloc rate 2,667,227,478 bytes per MUT second + + Productivity 98.4% of total user, 98.2% of total elapsed + +./H 1e7 +RTS -sstderr 0.64s user 0.00s system 99% cpu 0.644 total + + + +While our original program, when operating on a list of 10 million elements, +took more than a minute to run, and allocated more than 700 megabytes of memory, +the final version, using a simple higher order fold, and a strict data type, +runs in around half a second, and allocates a total of 1 megabyte. Something of +an improvement! + + + +The general rules we can learn from the profiling and optimisation process are: + + + + + Compile to native code, with optimisations on + + + When in doubt, use runtime statistics, and time profiling + + + If allocation problems are suspected, use heap profiling + + + A careful mixture of strict and lazy evaluation can yield the best results + + + Prefer strict fields for atomic data types (Int, + Double and similar types) + + + Use data types closer to the machine representation (prefer + Int over Integer) + + + + + +These simple strategies are enough to identify and squash untoward memory use +issues, and when used wisely, can avoid them occuring in the first place. + + + + + + Advanced techniques: fusion + + +The final bottleneck in our program is the lazy list itself. While we can +avoid allocating it all at once, there is still memory traffic each time +around the loop, as we demand the next cons cell in the list, allocate it to +the heap, operate on it, and continue. The list type is also polymorphic, so +the elements of the list must be represented as heap allocated +Double values. + + + +What we'd like to do is eliminate the list entirely, keeping just the next +element we need in a register. Perhaps surprisingly, GHC is able to transform +the list program into a listless version, using an optimisation known as +deforestation, which refers to a general class of optimisations that involve +eliminating intermediate data structures. Due to the absence of side effects, +a Haskell compiler can be extremely aggressive when rearranging code, +reordering and transforming code wholesale at times. The specific +deforestation optimisation we can use here is stream fusion. + + + +This optimisation transforms recursive list generation and transformation +functions into non-recursive unfolds. When an +unfold appears next to a fold, the structure between +them is then eliminated entirely, yielding a single, tight loop, with no heap +allocation. The optimisation isn't enabled by default, but is enabled by a +number of data structure libraries, which provide "rewrite rules", custom +optimisations the compiler applies to functions the library exports. + + + +We'll use the uvector library, which provides a suite of +list-like operations that use stream fusion to remove intermediate data +structures. Rewriting our program to use streams is straight forward: + + +&I.hs:fold; + + +After installing the uvector library, from Hackage, we can build +our program, with -O2 -funbox-strict-fields, and inspect the Core +that results: + + + +fold :: Int# -> Double# -> Double# -> (# Int#, Double# #) +fold = \ n s t -> + case >## t limit of { + False -> fold (+# n 1) (+## s t) (+## t 1.0) + True -> (# n, s #) + + + +This is really the optimal result! Our lists have been entirely fused away, +yielding a tight loop where list generation is interleaved with acumulation, +and all input and output variables are kept in registers. Running this, +we see another improvement bump in performance, with runtime falling by +another order of magnitude: + + + +$ time ./I 1e7 +5000000.5 +./I 1e7 0.06s user 0.00s system 72% cpu 0.083 total + + + + Tuning the generated assembly + + +Given that our Core is now optimal, the only step left to take, to optimise this +program further, is by looking directly at the assembly. Of course, there +are only small gains left to make at this point. To view the generated +assembly, we can use a tool like ghc-core, or generate assembly +to standard output with the -ddump-asm flag to GHC. We have few +levers available to adjust the generated assembly, but we may choose between +the C and native code backends to GHC, and, if we choose the C backend, which +optimisation flags to pass to GCC. Particularly with floating point code, it +is sometimes useful to compile via C, and enable specific high performance C +compiler optimisations. + + + +For example, we can squeeze our the last drops of performance +from our final fused loop code by using -funbox-strict-fields -fvia-C -optc-O2, which +cuts the running time in half again (as the C compiler is able to optimise +away some redundant move instructions in the program's inner loop): + + + +$ ghc -no-recomp --make -O2 -funbox-strict-fields -fvia-C -optc-O2 I.hs +[1 of 1] Compiling Main ( I.hs, I.o ) +Linking I ... +$ time ./I 1e7 +5000000.5 +./I 1e7 0.04s user 0.00s system 98% cpu 0.047 total + + + +Inspecting the final assembly (via -keep-tmp-files), we +see the generated loop contains only six instructions: + + + +go: + ucomisd 5(%rbx), %xmm6 + ja .L31 + addsd %xmm6, %xmm5 + addq $1, %rsi + addsd .LC0(%rip), %xmm6 + jmp go + + + +We've effectively massaged the program through multiple source level +optimisations, all the way to the final assembly. There's no where else to go from +here. Optimising code to this level is very rarely necessarily, of course, +and typically makes sense when writing low level libraries, or optimising +particularly important code, where all algorithm choices have already +determined. For day to day code, choosing better algorithms is always a more +effective strategy, but it's useful to know we can optimise down to the metal +if necessary. + + + + + + Conclusions hunk ./en/ch26-profiling.xml 1099 - --> + +In this chapter we've looked at a suite of tools and techniques you can use to +track down and identify problematic areas of your code, along with a variety of +conventions that can go a long way towards keeping code lean and efficient. +The goal is really to program in such a way that you have good knowledge of +what your code is doing, at all levels from source, through the compiler, to +the metal, and be able to focus in on particular levels when requirements demand. + + + +By sticking to simple rules, choosing the right data structures, and avoiding +the traps of the unwary, it is perfectly possible to reliably achieve high +performance from your Haskell code, while being able to develop at a very +high level. A balance of productivity and ruthless efficiency. + + + + + + + addfile ./en/figs/ch26-heap-hc.png binary ./en/figs/ch26-heap-hc.png oldhex * newhex *89504e470d0a1a0a0000000d4948445200000320000002150802000000a6d20c95000000017352 *474200aece1ce9000000097048597300000f6100000f6101a83fa7690000000774494d4507d808 *1604313679554d9700001b314944415478daedddd976a438024041a8e3ffff65fa21db14c5a214 *20819688330f3d7639170ce222483c0ec3304dd3000040227f2c02000081050020b00000041600 *0097fd6cbf348ea3e502001069fb79c19fc87f0700c0d6eecc945384000089092c000081050020 *b0000004160000d7fd5cfbb1cf05f3457dd8707b0dfffcf202379ed8fd3791ef6b1cc7d23e6ef9 *ee4bda3e7ba6f5e4e8610b5c2da96e35b67c7860f7b4dcdd24f9851afdda09ac4c63c1bc165e5b *4bb67bf7cf57965f8f89800bab7b4c9f05fe4df8c72b1d4f031914f9f62f546f033bc8d5581cbf *40e21ff6d4ea17b9061efd9bc0cfa65ab1050785bbb97f29240d138e39a71645609791706f9b63 *37f4e7ce12ff7a4bd253f72cfd2cc48f876f76ba5a6a912f60fb535f977ee0df1c7dabd2fbbe86 *2799e2df7e6089ad1eaa960515b96acdb68bf4f3c5536f3ff0b3e1878d7cc147ff26f0b36e680c *c94795b49b55a631e7d44bddfdc1702a7c7deaf8ddcdf2b92e94c9c56bb06262223cb67e1c25ea *eb811f99d5db171ff8951ffd9bf0b7ae6d15abc51bfe7ae0dd9dfa916b7575f4f6c34bf568f368 *a0ae6256cbc031d9d99f0d7febe6dcd59d39a7d5bab75d0fe75574fbddddf5765cf8fadb39fa67 *810789fffaee8384b7b8af5f17ac0d44d2ee2a11b999efee94038fb07cba98ab68d28e39918764 *bb735731a91078d917763797653c4518e8d6f95bd7264b934fb1167bf6fa6819462e9cddff8e5f *ec470f7579615e783b8d895c02bb93d281e5fff561bffeece51cfcfaa497a7c456ebded1b1c7f6 *1296dd557df58031cf1bcecda33dc16afb3afafad19440608bdb9d7d8c79535451571706dbdcc3 *51a63127f0e347e7e692cf8f3ce3cf85f5e0ce11f9d7f1ebcea1d8f8afc8a5bc9c486ce058f0eb *a9eef8956f75a0706a77fbcc327cf8e91efe3d0686b03bef37f2b45dcc51c7852393c81f8959f7 *2eafea5fbf1e337a1c5d55f3f5eb8163e5988bd5cebe29ea1db7f3ed942fec11328d39d7068af8 *3df5fd930617a2e2d60c56f2d9a3d521e6e599adf05c62e4cfce53a68159cd72c6b26b2f297c42 *e7e687121e9ba68adc39553dd4eeb6c59d09d7c0cf6ebf15f314f7b7d3cb476817469898e3f298 *2b4b62d233702af6f511007d96307732fdecd7e38dafa970ffdcd4f2112e94c9cf8527bbb9ef0c *5ce61c1ee38e4e10e45853e38f989bd9ae926c00f57e58a60a8fa5d5764bbff66fbe0e20a7ded1 *3c329cfa18e6f608eafe88bf7d9057e65093bc291a1813f2ad7eafa45578a088b9582ae1e670e7 *daacbb3358179aeef27bce748abac30e78e02dcf33abcf1c5af5f0db79acae86b8c9e00b13c677 *e698538d30e119d6cf4bfaba526d1fe4daa7cd1f382ca4073777ca45d5d5fd81a29c838d3f37df *f9d9f710be52f5955de6763cbd908cbb1f4688fc37313f9ef03dc62fdec0c73c130efa311fe508 *2cd59bd55eda916878979ce3f66c371ff681a5b1bd86fdc20873ea728d9849f4cbc3da85edfd68 *fb5554bdcd54ddd929af4683c84de3ced0fae2be2c70a9e2d9ddcd9d32f949f20b3e7bb5d3d109 *bee427fe2e8c5f37833dfc02debd2dd0d9c51bf84d5d8ed7b36fbfc35d48cc0672e1971279ffd2 *426af568211cddf67a750661f76763b6f1afe7b88f1ee4ecb076f9b2df6b0d4d0343c1a90fe46e *3f7bbb3b95f07594ce34e6dcdc659fbad1e8107d8f89dd4f352eafa63f7d2c3a3c356f4f75074c *5683da1778a65f62697f9109b04d15b80cfdb167a0a651cc428084db916d2a9f1f8b004af0fce5 *dea53d6ce45ec1a136dcdf849d5c165834b5bf07eb24d89a3ae114210080c00200105800005dd9 *bf06cbc70a00002ef3a91c0080c49c22040010580000020b0040600100d07a60f95423e4dfca2c *038016036b1c4721052f1ec3d80001da09acd59f9c34c4c31b0736eed502d0566001af1ede4c8b *ba728403d056608de3e87ea7f0465dad682c8026026b795ad0c80eafd695c6026825b03e8d354f *5f99c78257eb4a6301b41258cbd2f22b81ac69157d49bbc602a83cb0e61b3418d021eb86f6ef25 *ed1a0ba0ddc05a5edeee360d90b9aeceb24902d4195840a975a5b1009a082ce3381456577f1bcb *e6097062ec1d0ab8b47c7533f7dd7fe0fa77b8ba6525dc768a183100caf753c28b305e439eba4a *be654d0e78006294f5b708076709a1dcbafa9b59ce180284bd3983e506ee50615dfddf58f3966b *360ba0acc0fa8ccb4e37c0b5239370fd3cb311db84018a0b2ce0525a95563393a92c80e2026b79 *735103345495567fb7e3c119438085b2fed8b32b67e1a0aea682eb6a9959ee4a0a300c659e2234 *a105ff6e0b756d08ce1802141058477719751c4cf75d555d5a0dcb97ede2774060bd3d18ef8dc2 *86663a4e2b2b3f80c0ca505720adea3799c402045609bb16bd85b46a8cc60204d67b7b97d5a557 *86633aab2b2b3c406bfe5804a0ae7272e306406001682c80db5e3b45b81c700dbe74c8c9410081 *95e190d68556d01157bb037d718a105ed0e5f495138580c002004060412d3abefaca241620b000 *341680c082f2f9f02080c00248ce241620b080744c5f692c4060010020b0a060a6affe65120b10 *580000082c288ae9ab3d26b1008105a0b100041614c2f41580c00200406041c14c5f7de32c2120 *b000001058f022d35700020be015ce1202020b8863fa0a406001ea0a0081050020b0a013a6afce *73191620b000001058f018d35700082c0000810505337d7583cbb08076fc580490a8ab00406041 *caa2326b0580c082bb69a5a87298c6719c26cb161058d05d5dd9fd0320b020595a0dea0a008105 *d20a00810545b4d48ab47a92cbb0008105add595fd3a0009b8d1280080c0820c4c5f95c42ddd01 *81050080c08215d35700082c505700082c80735c8605082ca896e92b000416a82b0004160080c0 *824e98be2a9ecbb0008105ea0a0004160080c082344c5fd5c35942406081ba0280611886e1c722 *a09baefa505700082cd05500d4c62942daaeabe9f77f54ca65584095cc60d16a5a0dba0a008105 *09eb4a5a01f026a708515714ce5942a03e66b06829ad06750580c082847525ad0028855384a82b *00105840775c8605082c7890e92b000416a82b0004160000028b4e98beea8ccbb0008105ea0a00 *810500402a6e344a65dcb11d008105d28a54a6711ca7c90a00082c485957f6ac00082c48965683 *ba024060c1cd9c5a925600082cb85557728a0097610175709b06d41500082c000081055f99be02 *406081bae22dfe282120b0405d0120b0405d01c04d6ed3c0c339b5a2ae00105870ababe41449b8 *1b1620b0405a01d099d7aec11ac77175c268fb151ae02a2b003a947e066b8ea4e504feee170100 *9a947806eb1352d3344dd3df7bd5cc5f1cf62f730638cbddb0809e026b58cc512d27ab3effbd9a *be5a4598c9adf6383f08409f1e3a450800d08f2c3358ab5384f4c9f4159919648072bd7c9b86b9 *c34c770100cd78e8360d9f8a72b80900f420f10cd6f2cce0f26af7f91e5791335552ac76ce0f02 *d0f57e70a8e1f49ccf180a2c385ad70c0e4081fe58040000028bd299be024060010090d28f4540 *123e97c04b26d76802028b86bbca1e0e00041669ea4a5701c09a6bb050570020b05057f00f7f94 *10288e53849cedaaff7769960600082c741500082c0a4a2b5d050027b8068b705d4dea8a1ab80c *0b1058d454570080c0425d0180c0425d0180c0022890cbb0008145a94c5f0180c0020010580000 *020ba0122ec3020416e571011600082c0000810590d9388e4e1402aff3c79ef9bb5b727e90fa4d *8bf5f9f74b93151b105800e94a4b6c01020be0b9d8d25b80c002481c5b7a0b1058e4e5022cf496 *de02041680de0204164043bd25b600810590b8b74c6eb172edee6bd61c8145f3e3828d1c2ec6d6 *60728bbdb52266f4b5c8041600517b56935b80c002c8185bc3de9923c905028bf6393f084ff6d6 *608a0b041600b9936bee2da505028b4698be82727a4b69b11a9fefaf09db0739fa40c6eebf9cbf *f2f5631cbba7c293bc85afaf7cfed6eaed6c5f8fc002505a324b5d4d81ff7b1449e198083f6ccc *8b19c7f1e8a792acb1470f1ef91ade2daa953fd6e39e3760d357506a694de32f8bc358bd5b0f1f *f3773fcdb1fae2d776f9ba82ad7eea956a89790d47effa4566b0008acdaca86909da2baa554f5c *fe6044f83cddb535eac24fed4eb96ddfd4e72b6767a7d29e881458243924325883d2a2db5dc097 *e2b9f398db87fdfcdfe5d9bdedc9cdb4976dbdfe715d81a5ae00a545ad9134af03a7ce91c55cbd *7eb6b7026b63e04526a9bad579d242b60e8105a0b4a838adc2d994e3d9535dcf3e2c66b62ebf86 *f087075fe422f73eb74c633134535aae88eff2177f7cb97ae0537e17668f563f756d1d5bbeb6f0 *bbb8ff1acad90acc60a92ba08dd2fa67ef624eabe961fce24554ab52893cabb8fda970c9edfef8 *ee9ab9caa679366b7b31d6ee6b38baf95629bfa92ab6c3623f2320b0806237779955fce83a46de *b0cadeb3464e11dafe8126fd7fead08280573845a8ae809633cb1cc693036db25f5b8a1b16f8d5 *0b2c003456e54b39f512beff807ee9ef728ab08fa32ad3570020b00048c7c55820b048cdf415a0 *b1406001a0b140605130d35780c60281050020b02898e92b60c32416082c6ea495ba023416bcc5 *8d461b4cabcf006a5100e1c672234a1058c4d7951113005ee614a1ba02fae44421082c00341608 *2c1e66fa0ad05820b0505780c6028185ba0200041600714c6281c062c1f415a0b14060a1ae008d *05028b52d34a5d011a0b8ae54eee9575d53c085a1a0020b0d0554015fc99421058bda495910ed0 *5820b0905640fd8d350c83cc0281d5585d19d480971b6b3ed8935970964f11aa2b807066f96821 *082c75059021b37eef0e0344718ab09cae9a0f16014a6cacc119431058b5a595d10aa829b33416 *08acc2ebca2005d49759a6b240600190beb1867f2e6f18f41608ac2298be02dac8ac7f87b54172 *81c00220576f0daed6a2636ed3f00ed3574027c9e5fe0ef4c90c1600791b6b707f07041600c82c *1058f5717e109059320b810500320b0456c14c5f01c82c041600c82c38c76d1a1e65fa0ae020b3 *26777340600140facc72d32c9ae114e1734c5f017c6dacc119439a60060b800233cb1943041600 *64c82c670ca99753840f717e10e042630dce185227335800949f59ce1822b0d8307d05703fb39c *3144600140fac6329585c002802c99a5b11058383f0890a5b16416020b00123796a92c0456bf4c *5f0164cd2c5359082c0048df58a6b21058009025b34c6551147772cfc8f94180271b6b70db7704 *1600c82c0416e798be02905974cb355800349c59ae7fe71d66b0d2fbdd981d3301149159cbc632 *a145e381b59db9ad7d2e77b101db7a01ca6aacbdb17a505dd41758e3386ee3a9d595d89415408d *b1d5c94e8a5764b9066b757cb09c9a6aef5cf8efc5ecb64980aaabcb055b941d58abb9abe531c1 *eaebd3f47755defda97aea0a80464a4b6351626055da4900a0b12837b0ba62fa0a406341f6c0fa *ac8ef35f838a593b3f6709cd7b01a0b1105887b5341bf66ec1d0d2ca6afa0a4063c113811508af *c19f2c004063d18d42a367bb4297f622cd60d1dc50607d86fdadc3d4001714faa772566b736907 *10ea8ac68eb216ff61c5066837b080a7ba6afb758d057097db349cdf2f99bea2fab4724d09c473 *19165798c13a9b5683baa2daae8aff9756720081f55c5dd9ebd0765a692c80349c225457b49d56 *e38d9f05e0223358ea8a26bb2ad5e358f3010496ba423ca57f3aeb3f80c04a5f57d05b54692c00 *8195b7abec57e833aa341680c0cac2ee84cea34a6301082c10550fbd549905f09ddb3480ba3afb *9a5d9b0820b0405dc92c0081f5f27ec37d1950577dbd0b008105baa4b8f722b3000416a82b9905 *20b0405d797700020be8b63f4c6501082c5057320b406081baf2ae010416a033000416a0aebc7d *008195726fe02ea3c80b000416a82bcb01406081aab034000416a0270038e3c7220021f5c8b272 *752320b00051a5b1000416e82a00041608a90e17af492ca00b2e725f8cfd6e8265f78f850c9082 *192cb0d70720313358a0ae2c7000810576f6163b40d99c22fc1def5d80651f0f008998c15257ea *0abf0200810576ed7e110065738ad0f4955d3840d8348ee334d9537082192c1a4e2b75a58001de *d1fb0c96e92b3b6c0af895d906018105ba0a0082ba3e4568fa4a5d0180c00275e597085001a708 *b1570680c4fa9dc1727e505d01402666b0d0550020b0d055b4f92b36a30c08acdac772e707b514 *00082ca41500d4c26d1a2824add415d6014060553d8a3b3f68b70a0039394588840280c49c2204 *00105854c6f415d6164060353f7ebb00cbfe12000416ea0a000416802e070416d84d0280c0bab8 *cf770196ba0280fcdc070b390500020b5d45fbab9699664060a1ab00803e03cb05588a0a000416 *d20a00aae4360d1ca595ba42dc03082cecdb004060a1ae004060d55c0dae705757581b019ee222 *77004872187fda3439f26f965384fc1d1f2c020010580000028b7299bec26a0920b00000041605 *334f0010365dbb8c9d6e75f12942f768f83a70682c0aae7f1b2f5daefae378ff3386db075966e2 *eeb7965fdc36a58f3d0a2c4eedc00028b7ae029db4db434719b47c9c711c631a4e515de61461e7 *69a5ae004a8fadddaf4cd3344d7f4f5c2ee79f76cf66ae726ab79c960fc84d66b07aae2b004a2c *aa5509054ed56d9b69f9ef3fff7d340b159e248b7c85ab69b3d5b702c137b43e3d26b0d41594bf *ba3a4901ebc479a651566d3437dcd92c8baf2e8185ba02e01d1712e76b452dcf36eece90057ed6 *a55a024b5a014028a4e2e79656270a65d6d29f1e5620e717d415401ffbbbd0054fcb6f852b2aa6 *b13e9f43dcf6191f66b0d41554b1021bbe61279596535073f104ae6adfde076bf70afaaff9357f *8671fb4a7c0ef1ef7eb7fcf0bc738ed90c96baa28d7d8a45c0eb6369604f74ad2a626e58f5d6de *939bdc074b5d0100028bd8ae721f511c2a409592dcf0d3f4d5bb5c836527044082242aed01d5d5 *bb1a9fc1eaec022c75050045308325ad0080c45c83a5aec0aa0e9098192cfb1b004060292a0040 *60bd16232d5ce1aea8004060a1ab20efa6e193e780c0425a0180c04251010037357b9b864a2ec0 *52570020b0505760c301105876120080c052570080c02ab05f8abe004b5d0180c00270940220b0 *ec18000081953461ca3d3fa8ae004060a1ae00008155eaf495ba02db1420b00000a82eb0c6711c *c731fc1587da00408d12ffb1e765214dd3b4fdfaf28b7d505700d09df43358d3af39aa3efff149 *ab46e7a8d415d8be68ded4d92e8c9202eb6882eaf3f5d5775711d6dce496ed10003af5d3d29b29 *e02384a20a00c81358cb73821d10550040cec03a9b56f359c2fb35f6d2f495ba82770f6f264b01 *2850968bdc8fc22bdfe581ea0a002847ca19ac6d45cdd7b6cff7b86ae8bca1ba02008e2ba1c0e8 *d9ce75055ee41bd357ea0a0ae114218f0efefdddcd918b0afd14e16a0d2eecd623ea0a8ada1eed *f0008155f7380e00f09d3ff6acae000081f5425aa92b70fc0370825384c66b0020313358000002 *0b004060d5c6f941b0d902082c000081050020b0caf5d29f7906006837b092079b4500365e0081 *050020b000000416000002eb1ad770804d1840600100082cc7be0040f37e2c02690500a465064b *5d812d1a40602d87d2bbb77137160300020b00406015ccf415d8b401b270913bd07663f963f080 *c03a3582deba00cb312e882d0081956bc005baddf6f51620b000f41620b02a195201f4169058ad *9f22bc7d072c80afbdb5fc1f0cc3308da3958128bdcd60d93080fba387a33b406001e43d54d35b *40d78165fa0ac83db6882da0bbc00278f8404e6f81c002406f0102ebc6300750c24024b9406001 *902bb99416082c009416d058609dbfcba8f38380d202041680d2525a20b000505ac0c79f0edea3 *f3834033a399010dea60060ba0d28346135a20b000505a20b000505a80c00a8f3b004a0b105800 *282da853db9f22347d05282d406001a0b14060bd3054c4fe9d1c630a0020b000c873646a1180c0 *329a00181541601947008c8d40bd81157d0116001a0b0496e10300105800380a050416001a0b04 *d6e921c3a801a0b14060192c000c9b20b00c1300003d0416008e4e416001a0b1406001a0b10081 *050020b0007887492ce838b00efe10a1710140633d661a47cb8ab6020b008d05020b008d05020b *00008105405226b140601908000cad20b000d05820b06cff00dd369661167a0c2c001cca82c0b2 *cd035439de1a72a197c002406681c002a085cc02041600e91b4b66419b8165db06905950ae1f8b *0080db87bb936501020b804ca5b5a4bae8976bb000c8575d4e2322b000406681c002406681c04a *b5950220b340600180cc426015bc590220b3406025d910c7d1277e016416082c0088cc2c105800 *90beb16416020b006416082c00eac92c1058363900d20ff8c67c041600c82c105800d4935920b0 *00207d63c92c04160064c92c10580090beb16416020b00b26416082c00d058082c00a8a1b16416 *020b00b264d6c3a6711476082c00da6f2cc583c002009985c002807a320b041600a46f2c9985c0 *02009985c002009905020b009905cff9796d651fc76118a6690a7c05009266d6969d0e3507d67c *4f36fd0440a9d5650f45324f9c225c4e4db9fb2d0035c416141f58735dada6afa6e9ef5f1b18c7 *d1e41600053496cca29ec00280aa320b041600682c4af2f3eed3cf67099d1f04a0bcc6b26fe2a2 *8766b03e15e50a77006a6b2c2835b0969f1f34530580c6a28bf5a6c0e831d70540c9cc17506560 *6d7bebad17e9a93db5b7eca93d75a54f0d2ff22942000081050020b0000004160000d7b9750200 *406266b0000004160080c00200105800803f2bc2753f25afd0bb57df87bf9b6a437af8a9974ff1 *fc53bfb5c05f79eaed127eec35ac9efac9f52db05e3dffd4af2ff0a3474ef2d4bbbfd6079e3afc *bccf3ff5bb631a94a0b819ace5df84de1e3a84bf7bdff4ebf9a70e3c6cd6a79e1ffcf977fd1979 *9f7ceab3cf92f035ecfef8336f3fbc5e655ddf02efebe1771d5ed9d23ef5ea89be3e72aaa7de7d *83cfbceba36779654c038115da56038735e1efde7fdecb2f2cd31cc3034f3d3feceee3677dea87 *17f8853798ea356c1fe1b1f5edd4dcd5034ffdccfa76e111923cf5b53775ffa9c38b3aebbb0ecc *8de57bcbe3af98afcc5fdc7e65f5c5b989b7ff6cf72920e0c72228c1bb7f0cf5adb9fae5f1aed3 *04d6372b9b75ecf2832fbff2f9efe524d976adfb74d2b6f5e77edaceaef993d508ac34a37f571b *d26a607a6508ee76f0b2be35b9b2bdf56bdd7dde675eccc36f79fb74db89a5e5773fc9b52caac0 *44d4d13feb706b4560b530262e27b16dc0d637eb9b5f6bbd69957b1d5bcd4b3d7319c3ee934240 *89d760ad36ce53df4db5093df9d4d3c210fc68d52be7fe9b7f6aeb9bf52ded53ef7e922efcc849 *9efada6558399e3aeb3ab6bc0a6a77066bf73fb6cdf77599ec3e82b4e2c4ba5ae0eab25d8f57d3 *fb39d6f2a3e9e5079e7af5329e7cd72f2ef0dd073ffbb9fa9b4bf8e1b7bffbb0cfac6f31b76978 *eca91ffba57f7de4e44f1df8b5667deadde78d59c7323d75ee752cf25e18db7f76f483bbd76fc5 *fc2c541658000055732777000081050020b0000004160000020b00a018ff0178175c804c260502 *0000000049454e44ae426082 addfile ./en/figs/ch26-heap-hd.png binary ./en/figs/ch26-heap-hd.png oldhex * newhex *89504e470d0a1a0a0000000d4948445200000320000002150802000000a6d20c95000000017352 *474200aece1ce9000000097048597300000f6100000f6101a83fa7690000000774494d4507d808 *16051413db602300000020004944415478daeddddb72ab3aa2405191caffff32fde01d37cb802c *84005dc6a853a77667e5e2602126023b5308619ee7000040213f36010080c0020010580000020b *00806cbfeb0f4dd364bb0000245abf5ef037f1f3000058db5c9972891000a03081050020b00000 *04160080c0020020df6fde97bd6e98afeac586eb7bf8df0f2ff2c6139b9f93f87b4dd354dbcb2d *131fd2758f7cfd9daf182a7bdfb3c261c975c3d8f6a1a1a72c720c2af2849afdfa09ac8be682f7 *28cc1b25eb43fbeb23cb8fa71440c6704fe9b3c8e7c4bfbcddf9345242895b20237c3b38407efd *ad231b70eff3e37b4ae269c95ed47efdd74b9f53c141e54e1e5f2a49c3a3c7a6ec435ee447c4a7 *b2333ffa8a63d0ef992d7ee838716896bc79087efcacc4538af5577dfd95239fb3f74fedbeef6b *7c9d297d0b44b64c64c76bf15c76bddda6698ac768fabe139f89d63f6eef7425fda1461e55cace *02143f2867cfe19b3b78ded77e9de2e23fe2eb2ff8f5fba71f6b22735a8acc7bb0e6794efc25f7 *fee965ef713f1ef88917dad60ffe1567f17cfcf89cf83fe5ed151f9b77ef8329bf60c6171eadab *bd2d10d932871aa2a1bafaf8451217ff4eee3b911ff7f561ef7deddea34ad9593647ece690fe18 *a589bbc0de0f5d7f87c8a3daccdcc48f6f7e93f8eef6f5e36ab58348da1c1289b3c7e64139f21d *963f2e6f073f33b1a47cdb33433a655e4a3cd69c71e125c2af0b0ff1744d5f33bc6eade5711927 *fa65970df2961523db73f0a58bf465ce337df6f56b3382ece6a25d0fbcbd738ff57af3e60cb33e *81fefa73e375bb3e74ed9dac6f7e7c7324c477b7f8e9b5c06abdaeeebf80f3753a8a3c8cf35ffb *f59f52aeea547ea6fd93310ececcf85fe7af33a762d3bfd28f1ccb19b0f573c1afb7ec1c1a7c1f *c33d65cb2ccf096e5b10eaf5e8b24e8ac822d3d7a1bb1ceae90197feca89bc47953df0b287fad7 *8f1fbd4360ef876e7efce8baecc95f8a76e7edeb0eca19478452677745beedd7a9acc8c37eefa1 *47a3e2d40a56f1d5a38f53ccec95ad94bb46be7eed7bc934f18edd4a0ec0a56e163efadd36bfe4 *9e65aac48353eb7595b2daf475df49e99533ebb89b5f7b7e8fceaebdbd879172029d7267493878 *67ee7543b4c24989b6fa2c7b073fffb519dff6d039fff96b53e9b78b1508acafd76bcfc46cca6d *4c374c2b5fef43ef78bf3a1fb5a1e5d7cbd49c56eb5d6ff93927ef1e88cf80292f64892fd497ba *a7e1fd7dd25fbbb47906953ded46bec9236ba8457e293a982bae1b7ef5a4d56d0fbbe03c767605 *2ba3e9b27fe78b2e518b80eb66ff824b17477bbda7ba0ae75667e39f7fd1045aed59c7d78ba429 *d3e8fa9b3cfbfe735e9569b23d73506ea8ae527eb57ae6a59f334f64c6ef10bf53f59143e67a3e *cd48c6afaf928d7c4eca9717fc1d335e4898fdd812e7fd945773c4afb97490c8d9973b234f6ee2 *3d55475f3c98f250f71e55e2688fbf523a63863974fb60ca227af6b496b1bfef6d4c45358ef4db *c913df1a2a71d73833b5e6dde75e24b612e7a59463cd9932f92df2041fbddb69ef025ff10b7f19 *f3d7c9608f3f80e2f7fa5dbdd81379b2b2fbf5e8c31bf02892f8667ae9fb4efc79ccf871895ffb *754f3f3af0f6dea3eee38269f61b9c7ebdc01d7931e6a1692dfb4a6ea92ea78975a978f47f3d28 *c7bfc37baf493f30959a1cf6fee9eb213bf19094fed6caf18fbfafc3e4ed62b15b5371ce642434 *bdb52f7a069f1d188625d8a79ad886fed833d0d22c662340c1fdc83e759d5f9b006a70d1bd77ad *3cd4f4a382536d38bf0bbbb82cb0e8ed900f0624d89b46e012210080c002001058000043d9be07 *cbcb0a0000b279550e0040612e110200082c000081050020b00000e83db0bcaa11001058991525 *a4c0de0720b0cacceceffffef80b940000020b68cf344d619e83d31b80fe026b9a26ef770a8fd5 *15009d05d6f2b2a0136878766fb40f0214f15bc7ac3e6ffe377029cb570017a9eb1e2c75050fd7 *95452c806e02ebfd1271333b0020b0cad4d57be1cadb34c06dfbddeec541bb21400781050020b0 *2e3eab066ed8d1e2f73b5ac402683db0de97055fffdf7deef0705d01705a756fd300843a764b6f *ff0b90adaebf45185c2584ab7737cd0470bd2757b0bc813ba82b008155d8ebea83cb1070dbc9cc *d15dd4ee09d05e6001e55b2a84b0ce299104305a602ddf5cd4b9329c2eaca2d7012d620164a9e2 *7db0e6797e5f2e743f169c882b77590108acfd8384d2825aeaca9b8e021cf7fc25c2e5dcbdbc12 *614e87e7eb0a8046032becdc7ae5b60fa8a5aedc89057050157f2ac7d300b573a110e0882a56b0 *f6ae120249bb8fbd064060ad0f0f1fb75e692ca8b1ae5c280448f6631380ba3ad458b63c80c002 *75a5b100eef6d825c2e51c6dbe0600045691d3607772c089f39307f7203763017ce31221a8abcc *c6f25c00082c50571a0b40600100082ce052d5bda7a8452c008105ea4a6301082c000081055ca3 *ea3f3868110b406081bad25800020b6881c6021058d08a0696af001058a0aeae62110b406041e5 *69d5e4da95c60208213cf8c79e81bdb47a958a4d0120b00069155e8f7f9aa6592002020b78beab *82552b00810594aa2b5d05d01d37b903a5b9d51d105836013cc5f21580c002d41500020bd41500 *020be884dbb0008105dcc9f21580c002d41500020ba881ab8480c0026e60f90a406001ea0a0081 *05ea0a008105f4cc6d5880c0022e62f90a406001ea0a00810554cb55424060016559be02105880 *ba02406081ba02406001c3711b1620b080f32c5f01082c405d0120b080b6b84a08082c209be52b *000416a82b000416a82b000416a82b42701b1630965f9b00cea65508ea0a008105e5ea4a5a01b0 *e21221a8abbbb84a080cc30a1664a555705910008105d20a008105d2aa43f33c4dd36c3302020b *70bb1500020b8aa655b0700580c002690580c002693510b76101020ba41500082c385157d20a00 *8105678b6a495dddc65542406041b751e5000f80c082026925aa80f3a767c9acd40a2c9056005f *72e9e8ec639b092c9056dc7aa0721b1620b0405a0180c062e4ae925600082c289656ba0a800afc *d804745257f3acae1a33cf935b80e1e32cf19aefbc74e903b653bf59c1a297ba0260f774665ece *99f1d7979c79014ae40bcf7cdb8caf5da6de23afa7b18285ba02182bb60659679aff3cf2fb5ac1 *425df1e4fce7cd1ae0bd17bc3be0bd537c94c1fae3f18f7cddb9d6dffff591d7d7eefdf494dfe5 *e3212dbfedde63f8d808295fbbf74dd68ff6f509eb8d93f13b0a2cd41540dd93d84e13bc0fff1f *97f6f6cae9236bd65fbb7f8e33af1324fed38f56e3b29336ebeae383f18794f2b3f67ed3bd0db8 *2ec2f55323b05057006da455fac17b1d37ebef70e62a58fc6bb3bf73e2afb9f969193db7f9b38e *6eeacde4cacb2c8185ba026820c5f62e0ba6af57257effc47f2dd228eb4fcbf8a19b3fab48b7bd *bf2a63f3bac91d75c5a3bc5903238efaffeebc4e19fceb44d8bc80b5bebc95980bf174c8eeb694 *ab6c7b9f76e887467ed6deff4cbc99ecb5a15e323682152cd415c0339915bead517d04d3fbdef3 *8fcf5c7e70f326f7c87b16acbf7fd8b907fcfdd3bfde83bff920d7df3ff2699187b4de8ceb6ff2 *be2f3e3bdacedfed9e7f71f1e6c3aad719a1ae3a7e6aede0f4390519db03e784152cd41500ed1c *0b56eaac588185bae269de0d8b762623dbe0e9d9623ef1ecddfaf4092cd415c0b58776067c06bd *8a10750500020b75458fa796deac0110580000082c5a63f90a00819573f8fcb82290f89eb6a82b *00a85cf95711c6df88d6ab30806ddeac01e848e115acf7fbf4cf8b5b56cffcb5480664f90a0081 *b53e0bddf8638a9b7febfb23c29cb9a2ae00e8c34d970801000456becdbfe30da9696ecc8ccc6d *5880c02a5563cb3bb418b7aba41500022be3203a7ba76636d34a570120b0e29615b5bcdbfdfd1e *5756aa46cfa97f878bcdc27a54b84a08f470d4ab337ad60763136ef375e5192479b8d8df81d6fd *d6f9b03ea657d716d5150034c4df220400105834c5f2158779410c20b000001058dcc7f2150002 *0b00008145c52c5f91cf6d5880c0020040607139cb5700082c80cab84a08082c58b27c0580c002 *750500020b750500020b750587b90d0b68d6af4d4099b40a415d0180c0e2444b7d90560020b0c8 *af2b2d0500dfb8070ba898dbb0008145df2c5f0180c0425d0180c00258739510105874c9f21500 *082c00008145c52c5f51cb38041058a82b28690ed334c92ca015de6814a83df3c3fc5f6385bfa5 *ac59f70375b382053465fe6f35cb960004164d727d901a466198b733cb15434060019466290b10 *5834c7f215ad6496a52ca0426e7207eacdfc9012f98b9bdffffb807303406051e571cdf215ad99 *ff1dc07b9f656003020b1839f343760bcdd19307b105082c8092560b5d320b1058dcc1f5416a18 *85e18631e89d4b018105707566292d40607109cb578c9c59c1821620b0805e333f3c9837ae1b02 *028bd2c735cb5720b30081057497f9a19e9e717b1620b000aecbac60410b105864707d10524acb *821620b0505734361043fdc3d0821620b0002e2d2d9905082cb659bea29281185a1c86ae1b0202 *0b7505d76556f0c7a4018105705d69892d10588ccbf215f58cc5d0df48145b20b0505780d80204 *16b951b598da6d102a199761a8c1b8155b4a0b04162d7795491caa8c2dcb5a20b0d055c055a525 *b64060a1aba0c0780dc6e9b7d8925920b0d05540e1d89aa6496381c0425741eaf0b57c95985996 *b24060716f5d9970618cc60a96b2a01d3f3601f0d4f981e5ab8cccfae7cd5600810580c6028145 *fde7ffae0fc2b88d25b34060017c9e1fb83e78b2b12c6581c0e28ac393e52b90591a0b2ae55584 *c003e70796afca36969716de745a9bf1fc786a041600ed369663f93d9bfa6094d964e37289b0d9 *13293329b03cf0bb5c08020b18f9fcc0f5c1eb32cbab0ba1122e110274d5586175b7904b8720b0 *4839ff777d908687afe5abdb32eb9f49436f81c002406f81c0e2cef37fcb57343c7c2d5fd5dc5b *4a0b0496ba0228dc5bcb952db105020b8092a5152c6b81c01a87e52b5a1fc1ae0fb6185b4aeba2 *f9dcf6145800282d6f165f74a3da8c028b7a4e772c5fd1f408b67cd5476959d00281a5ae002ec9 *2ca505020b78fe14c1f255f7a525b340600150b8b42c681d3ce970937bfffcb167e0da2389e5ab *51326bfeefaf4ddb18dfb796ba1a8015ac064e74dc800534545a3d2fcfa8470416001aabe4afe5 *5c97235c2204ae3bdd777d70e8c6b2191058547b78727d10d05820b000fece0f2c5f692c8d85c0 *02008d0502abfff37fd7076978f85abe426321b00000105800b4c22216028b4ab83e48d3c3d7f5 *413416020b00341694e49ddceb3cffb77c45c3c3d7f215b1c67a0d92d7ff32d121b05057a0ae28 *324ade83646f414b7821b000d415b9e6ddf34c8d45ebdc8355db11caf215ea0ae115a66972c316 *4db38255535a85a0ae5057f06aac60290b8145fe8129fcddef6912415dc12ab334168d7289b086 *83d3acae505710692c9b0181c5a163933bae505790d458320b8185ba425d41e1c6b29485c0027a *4f2b75c54399a5b11058c48f5096af68b6aee6a0aed05810e75584b777d57f73840314cdd61554 *d0585e5a88c06251576604d415146aace08fea50319708d515a82b9a6c2c970b11588e4dea0a75 *05976496c6426001ea0a3416028b328727cb57001a0b8185ba82bf116cf90a8d05024b5d81ba42 *63c1c081b5fec3529dfda9297505a0b1105817e4c52a9ec619f7ea8a0e06b1e52b3416d41558eb *ba0a7f6f0737c2b85757a82bd05808acf279b17e6bddd7473e3e3ecff37b1fe8e6ef1ea82b804a *1a4b66d14f60f9fb50d0c15982e52bfa682c4b59f4135880ba82aa32cb52168f28f9c79e5f23f8 *d055bff75542d70701b8a8b142f0c7a16939b09603f7a3ae5effd33904547e8a60f98aee334b63 *718f3b2e112e5f3f686483ba820733cb15436e9a53eb8c9ef5e8afbfcc5c1f44604143473f27fc *5ceab7ce87f531ee9d6dc0b5691582ba02e83fb01a3c4259bea2d9ba3272014af3360d85ea0ad4 *15007fac6095482b6b57a82b000456b1ba9256349a56c14d5700020b285857d20ae062eec1ca3e *4859be425d01b0cd0a1674975011ea0a4060557c08b37c45c575656c02082c7505c5eacac00410 *58ed75d58bbaa2c2b40a16aee088d91f7e4660555257f643a41500024b5dd17f5d199800024b5d *41b1b40a16ae000496ba828275655402082ca0585a050b5700020b285857d20aa011fe544ee470 *e6fa20ea0a801c56b0a0fab40a2e0b02082c405a01082ca0a2a27a93560002abbb239d1bb0b8bd *ab8c3800810594492b5d0520b080627525ad000416502cad82852b008135dce1cf0d585c595706 *1740efbcd128a82b000ab3820577a55570591040600105eb4a5a0108acb10f856ec0a2685a050b *5700020b285857d20a406061f98a6269152c5c018ccbab08e182ba9ad515546f0ed3c71f000581 *0555d71500637389707964747d90135df5774e0c00020b74150002eb92a3e4eb966407490ea695 *210380c0daad2b69457a54bd183200082c1055c0d9b3f1e36627f0020bd8e82a7323907f9ae56d *20041660b10a0081050542eacca9290008ac9d43ad3bdcc78b2a4f3800020bce1695a802406041 *81a8525440bd73d53f67805e6928b0a0eeae3247018d5846d5344d9bfff3e3e3082cb837adcc3f *40e3b1a5a5045667476777b84b2b9a78badf0722db82010e4c8b6b88c24b6081b4e2baba9a3dfb *0ce2bd9a25ad0416482bee3bfafc37120c03406081b4a270661912f439d54dcbffb088d5b41f9b *8006ea6a76281df6d9dfcba83984d9df79a39bae7a85d4fbff2fff278db28245dd6915a4151196 *b26838aafe3f8e8594c0ea6d701bd395d795e767f43190924eb316a7bd3383fda3cffb9f5497c0 *820bd2cac1928307acff8f9cad7f0110580c5f578e889cc9accd5e175eec0c83833792bbef0f81 *455b51e5b0c7c681acc8689863a3ce78237d24b96687c0a28d9612553c7ab8945980c02a7e9477 *87fb435d65ab9334606e1b2b320b1058b45b570e5d546d761a00082cd4155c9659c18216508077 *72475d51dbb079bc6efede26de2bc6008175e4a0ef062c7505320bb8904b84a82baa1a39a1b28b *736ecf020416357495e3101d727b1620b07830ad1c7838358aea1f4316b40081b59d016ec02a11 *52fb67f830000b5a80c0a26c5a3996c04769d9350081457e5d397e70ed186b3752febd6e28b600 *8185ba829299f5de65c416082c50573c3dcc3a2b91add8b21f81c00275058563cbb21608ac7e6b *c14b08d5153c5d5a620b0416ea0aae1f6c035686d8028185ba02c41620b05057b433dea4c4b7d8 *b2794060015038b6bc912934e8c726e01f96afa0c6d29ac3643b80c0425d41d2900b56660e6496 *c6ba68bb4eb62c02eb543c788f0675051a0bb8837bb07087074f0d3cc32eafb1ecb0d00097081d *e4a6d70d1e40338d65290b04160dd4153c30f682ae3f9b591a0b2a36ca2542376085cdbb381de0 *a0edc6728e04028b6773ca2c0cbd36961d1c0416720a5c1f2cdc58c1e57e10585c915626569059 *1a0b6a32c44dee9ddf80654aa5b11dd2a8bdaeb16c04a88515acb6cbd1710af8b7b126675f20b0 *505740e9c65ace123bff02082cd4153d0d5dc7f987624b6f81c0425d01b7f69629050496ba0af3 *1cdccb4a93a3d791bcd6de125b20b08e0749472f21fc6fed4a5d01d7c796d2028135c6d9bf2b83 *343d801db15b8b2da505024b5d01282d1058a82b861ac30ece1d959667120496ba02285c5a16b4 *406001704966292d1839b09a7f09a1e52b7ad80f1d8195160ce7c72600e07469cd0dffb5e9394c *93b7bf41600d74de6ff98a0e8671b0ac3156694db3b7ea83ce03abedeb83ea0a6838b36c040416 *ea0aae1ac9c1f21520b0a823add415d03c8b588ccedb34d411558b4909a097c672ba88c0ea305a *5ab801cbdb22d3f39983c18dc6625c2e113e5a57b30310d07d63d9088ce8b115acd79b8ecc8b45 *a6f547baedaabf6907fa1de78638cbc6b28e85c02a914dffed52ab78baad9f6abc3ea8ab008d05 *c3287f8970fef38eaae5d2d4a0ef96fbbe1a687e618801ef4c82cdc6b211105827ea2af2f18f7f *fd88b0528b5bd52d5f396f03d058082c4aa695ba02d0588ce7929bdc47b95d3d9e56c14512c61c *fc863e5f1b6bdafc3008ac6269f5be4ad84f8d492bd4157c6dacbdc9536cd18b4b6e72df0baf51 *ee703735a0ae2067eafcfbbf29b89248eb4aae60ad2bea7d6ffb344df7ac543d7c87bb3bae5057 *50ea3cd58c4af393627d97e7d66b5d890ff2c9c0321730ee2ca2aeb86c78cd77fd9cd918a6a44a *ff16e1c7406fe0daa2ba62e073349b81eb8e066e6c45608d7974f1feeca82bb8b8b19cc422b09e *ae9d1baf0f3aa9425dd901b833b334164de9e78d46efae2b7ff70675057737965717d28c4e56b0 *eeab2b0b57a0ae78b0b182cb8508ac7e0e27defe0ed415356556f1c69a4bfe495c10586975658f *037545f78d0545f963cfea0ad4158d36968d80c0bab682aeb9014b5d81ba4263c1b08105a82b34 *1608ac268e2896af405da1b1406001ea0a8d0502abe2838ae52b008d05020b287fa6112c5fa1b1 *208ff7c15a1f542c5f81baa2ddc6ba6a0e9fa69c7cf3e6a5c3b282a5ae003a6b2c1b018105d478 *a6112c5fd17c63c92c04d6a90341a97719f5579c415dd1536359cae251eec15aa6957d11a0afcc *72f2cc435c220cf63d589c6fd81fe86f7e77c5900758c102d415639c4657f332a68f1724be5f69 *384dd3deab0e5f5fb2fed7e5b7dafb3eefaf5d7fffcdcffcf86e9b0f6cfd9a4aaf9714589f63d3 *01056094ccaae68a613c5fd2436d19559bdf67afcce2df2de55129aa38970881d76c1a2c5f3144 *63357bc5f0b504b517409bb9935d57eb1fc75163af6059be826979e0a9fc51da5d2998592da543 *e212d7e6553ceb4c020bd055328b714ef0a7abbfffe61254c19fbb7727193d0456b137c1025dd5 *c283965974237eb3f9ba63de357374352b7e25f14c6f29aa9e03eb649d99a2e9349e62536247bf *ad1d98116b2c9244eea3aa8a9bdca1f1cc78ffdfebeedd2fffd753367a6b234e45cbe7f099432b *2db27cdb85afe195d858eb4fcb7e6d232feec182a693c3f467298b3607eefe5b61a597d0471545 *7a28a596e2df2de5762e41f63955d7bf45f64646fe3d58ae0fd27057cd63fedadf1724e0e8e89a *571f88364ac6cfd01cc36a7805cb1dee0c5617f3e0bfff914f36330002eb893433fdd24e4518ac *65b7a9ed09082c1822001cf273c2b3c4b7b5e539c0c53e04567c76b57c85a862f994782e008105 *0d77950379668dca2c40600116ab9a7ece3c5f80c03a3c85ba3ec83d5d659cb5fe2c7a0647303b *2820b0a0da96fa77bee6b28d2bb3008105dd1fe51d7ac719049e6b4060c5a64a4bc1a49493846a *e3e979e221191240ef81e56ddc39718036723833b68c1fa0dfc0ca2832b3e2302de599e69e6167 *a401028b3e8bca116e8864aefbd11a84c0b08165f94a51c1e563d4e004460b2c1aee2a07ad716b *5a6901020bca1e581da2505adcc07b8d22b0f2e73a3b4f85fd24a7186de81be420b0a0f0f1c5a1 *8502192eb600818563a50309882d10586d4d4ee9ef32eafae0a587865d363ae54755efbfbbbd06 *0416431f011d06e0eacab4973d640ed334cdfe4c0802ebdb7c65f94a5781d8020496baaa6e86b7 *11b93326d8db3ef6441058482ba0fc6e6997048175e934937287bbe5abfcae92563c33ec48db56 *76cfe2bcd728022b39c1ec2aba0afadd63edaa20b0686081c0644dbda3138d05020bfd04682ca0 *cbc01ae7faa05bd1c1d99519006af5d35b5d0d34b5cee6563a3845c066842e75b48235c2da951b *d2818d79c18400024b5de92ab0eea2b14060a9ab0a8e44a64e20a559cd15508b1f9ba0ea09535d *0187338ba3665b8ee2bc4d43cd33a4b4420490b779cd1e20b0cc84eb73298092938b5905049696 *82f1f604f41608acdae68deaef7077c90fd05b20b0287d7e6ef282dddd839a9e1793158c1a58d3 *3485b9e229c09faf013a2960f3188c1458d59f939b9280cea636d31a0c18584fdd8025aae0dc6e *83d20281657a597fc844038c3915f63afbcd43fc415b04566569659f83f2a72934fe54763a31ce *619aa67936ed3372605d7ab621ad00462e2d1837b0ae9d374c1950fc488cd2028135f444619a00 *c89b40cd9f20b036ceae4d0d70e10ec618cfb88914da0dacc23760990e00341614f3631e301100 *5c31b782c0525780a32c9e7d1058ea0a406395346b420496ba0207570c0310588577d81377b84f *ea0a406381c02a4f5d81632ac60308acd70e3a4de1e4df87b276050008accdceca6c247505f0dc *dc6d1320b07addb5d5153894626080c05257001a0b1af43bc6eeacaec011943a0789f91981f5ec *ee987187fb64ef057545e5836473cc3c356fcf61328629e3a7f75d585d81bac25882bbfdf6bb6f *4a2b7044a4f51165264760ddb4c77d7b8f066905ea8aae8696291d81657a0775051a0b3aba076b *5efc1fa0aee86c98dd38d2e630b9d51d81658607fb1ec61b08ac2bf638ab5670ff8ee76887c682 *8e030b7090c3f00381557a47b37c050e6f1884a5ccc638c30796ba0275c5b843d168446015dba1 *264105ea0a8c4904d6a5bb95da0247328c4c1058806318189f08acbacccbbdc9f215387a81518a *c02ab91fa92b003416020b70d002c3158105385cd90418b4d058604dd3f4f1d734d71fd9d9775c *1f04406351b5dfdb72eaf51ff32c8fc0510aae1ebd678e35b3f1cf7977ac60bdeaea9556dfd7a8 *007505c630022be974609ec36af96a9ee7776f4dd3f47d71cbf541000e3496cca2f7c02ad5699e *3070ea0fc633020b703482c747b581cddd7e9ffdf1efab846e7e07e0fa9307c71a6e72d30ad6ab *a2cedde16eaf807b8e406090430b81b57cfda0952a70e081a787bad1ce2d536a85d1e3dd1c0078 *90e500fa0cac756fd5f320ab7a30368e8de399b27146de38502daf22040010580000020b004060 *010090cf5b2700001466050b0040600100082c000081050043f08743b8c86fcdc37df3eefbf8bf *5eb7e3edfdb83b1fcff2873ebe71aa7aa6aa7a3c1fcfced79f7be903db7b308f6ca5c8b87de429 *5bffdc078750250f666f843c3b8ca145d5ad602dff26f4fac422feaf5798ff6cfeb8fb1f4fe407 *ddfc60de3f6e73e3dcbf655ec7a7c71fcfc737fffa732f7d609bdff0a9ad141fb7f78fe7c8af5f *c3c679703caf7feeb3c3180456c9dd3b721a14ffd72b1ec999477bdb1ac0230fe6fd83367fe2cd *0fa692676afdfdbffedceb1ed8de8379642b1d5abbbae1298b0cdafb8774c6f7bce8c1644fbc65 *1fcff427e523cb108c7f5afc33377f0a64fbb5091a52e1dfa0cd3e3c5c71887291c278ee66488f *3c9e37af96be3ff2faefe59ad9fa897b45d2f41888de00000110494441543a975f9fb6b7dee6ef *5823b09e9973ed789193dd1a26a6f514ec0932a4db1dd2cf8ee7c747c8fa01ac579596fffa4aae *6551c557a1f63ed3ae81c01af138b43cf7d210b43ea48d6723242573c38d371b6cfe5cc8f653ed *1e1ebff5f5b66be45ff7b1db1ecfbc10a22f2caae40682aa1ecc838fe7ebcfad6a481bcfad0ce9 *eb1e4cde7351eaf12c6f81da5cc1dafc8f75afa76cbdcd6f22ad28b693563898d6a3fc63b5fc9e *7d606f45fae88bf02f7a6ccf6e9caa9ea9bdc7f3d433f5f5e7def9c0369f91c8907efc6d1aee1c *425fdf19e1a967eaa9fd2b7219eece61bcf956119b0f603d9237bf70fddf1fbf69e4cba1abc002 *00689a7772070010580000020b004060010020b00000aaf13f5c33a1ba37b558b7000000004945 *4e44ae426082 addfile ./en/figs/ch26-heap-hy.png binary ./en/figs/ch26-heap-hy.png oldhex * newhex *89504e470d0a1a0a0000000d4948445200000320000002150802000000a6d20c95000000017352 *474200aece1ce9000000097048597300000f6100000f6101a83fa7690000000774494d4507d808 *16050036beca201200001f544944415478daedddd992a3b8a24051e1c8ffff65fac1956e92c942 *08d0b05654dcdb27ab72c2486c04b68710c2388e0100804c5e36010080c0020010580000020b00 *80643fcb0f0dc360bb0000445a3e5ff027f2df0100b0b4ba32e51221004066020b004060010008 *2c000081050040ba9fb44f7bdf305fd4930d97f7f07f7ebc9d179e58fd3791bfd7300ca53dddf2 *d91f69f9dd2fda4fb6be6c81bb25d5edc6b60f371c9ea6879b2c0fa8d9af9dc0ba682ef8ec8569 *7bc9f2e8fefec8f4e3311190b0bbc7f4d9cebfd9fff44ae7d39d0c8afcf513aab79903e4fe5898 *7d8593bbdffe0fb6ffd3a6edd52747bae0a02e278f2f85a461c6c9e1eba7cf92f4e80492302f5d *7118fa39b3c5bfee28875eb374fad56ede0567df2bf29462f9595f7fe59d7fb3f55795beeeebfe *2253fcafbfb3c57622a3d273d9c8b17068ff597d38b642eae84f3bfdb2c330cc7eec9dbf7a6aa4 *4393e20fcac9d3f86c149f991c2267c298f3c09da96ce75bc71f6e96bff2a1cd9b780fd6388ef1 *a7e0ab7ff5b6f5733f3ee7c6fc00abfbf43bcef6f789d9bfd9ffabb45131ddbcb34d1d7f8c5f7d *a4b2d7d5d6afbfbf55571fa0f20fd547eb2a6cafcbc6ec3ff11b273eb9b6beecf2d357ff2a7ea4 *47eec6d31d756786997e703f43b7beddd72f12fff1d52fb23fe2be7edc3b70341049abbb44e478 *5c3d28ef7c85e9b78bb98be6681eed4f0e316330617a8cf9b1130e37c92ebc44b8b324b3939647 *d7ba2e5d6e795cccaad8d7ba4f8eb6b495869d8d99f0eb34e6e41648fec4b495e6af3fedce973d *399ae277e3e57af3ea0cb35c5dfbfa7df72f882c0f5dfbcb75b38faf6edbfd11b77f7a2db06aaf *abfb9775cf0ff0b4cffdba86b4dca50f6d90720ee5af84fde0cc8cff75fe3a732a36fc15b9953f *e1dfc6b960cc6f1dbf65a6ff1dbfee75db747ff3b72be174f6ccdcb13a34729d5dec57cbd1911e *b3ef7dbdabe3ebd9edd6c78fde21b0f54d573fbe73ae1c734de4e82f4533f376c68372cc1e95eb *eceee499e1d6a948e491fae4a1e13d428f46457a60651fc9b335ba33a7f8e35f87bec8e7b3761e *9502f32be37e96f0dbad7e4acce5e32ba6a4f6ee825f8e8593bfe3d6f8baf4194c5b4f22491be9 *09a36f7691f1eb7596af7796c40c93f822bc6d06409f5d31c02ffadce97164f5325fcc0492e5a4 *7467e6fcea27e19b9d1ccc5fef11d9b98d69f9dfd977acaff7a1d738ae3e9b74a7c1137ebb9ddb *6e82fb97733cacd3076e7508a43d6ab395bf335ff6505a458ef433bbf1d7c1fbc991333bfcf28b *3c9238597e296a3f19bb74f7bb3fad12a6c74bbff5997bb37ece7cbf90741f55f2ef7cd1256a1d *70d1d49f7c8fddd54b1a0d9ca11eddb05bfffefc973d5a578f9f757c7dba65cc349ab6b878dd70 *7077a3f9f6cc41b9c0ba3af32b9473b2f13af34086a475bf9d3b551f39642ee7d38464fcfa2cd9 *9d7f13f3e98fb4c8ced33c334efa314fe5f8da070d2472f258d8d95009afbc7074c7387a9f7be4 *6fb7ff4ce98419e6d065f49845f4e4692d61bc6f6d3445d58ff8dbc9235f1a2a72689c995a734d *cb3bc785a3df3ae17073a64c7eb23cc0878ebed3dfe4d2971f4c9bbf4e06fbfe0f70e846e02b3a *32391c935ffa35f2f74a7ed66ef3f369965b50b3ece131df77676f5ffdab9879707936b2ffca37 *5b9f1bb305be5ee3defa2247a7b533379325c42e95ae4bed47ffd783f2fe57f88c9af80353c20a *f7a1cf9dbe3cf8ce2c71e8854643f46b4cac3eab717a8fe3e157200fa72f1350d131fbd0bd3576 *83621f9d671fc4d2de910930a60adc86deecb9bb1511b01b8371644c5dedc726e86738394729d9 *158fcea5b754db8da1ded9c6c56581c5634744438e1e1a148c262ee212210080c0020010580000 *5d59bf07cbd30a00009279560e0040662e110200082c000081050020b00000683db03cab11fa64 *ec03952ae8ad72bcd118304fabdf374d33330002ebf034fa993adfef4069260569153ef3c0383a *0103041640a6b49a925980c04a9b584d9a20adbefc3b990508ac48e3ef3d16c10dadd06d5d1daa *a5dfccd25840b18a7816e1388ed3dbb03c2aa0ae62260ea76480c08a2d2d0f09a8ab438d25b300 *81b539c9bea7481325a8aba38d65290b1058eb93ecec651a3c2aa0ae8e6696a903105880baca7d *3f80cb8580c0da9b76017595da5896b28052e6ba50c0ade5d30971f587f17c6ca83eaaa61974fd *f70b9e34033caa88171a350f82a8ca3ba73831039e55c44dee3bff13a8b5aec6f1ff3f0f9dba99 *4f80a73cb982e505dca1e5ba2ac1bbb12c64015d05d668191fd4d5f5134d28ed47023ae0651a80 *76ebeab7b12c9303372bebcd9e2d6581ba026840596ff6ec7502415d5d34cb985b803bfd14f833 *59d002750520b0f2e4d4aca89c6e82baca691c3da506e828b0c2c64a9579102a48ab10ac5d012c *3d7f0f9690825aebeac117114d9d6e2c8d03f7286205ebeb7b110225d61500c506d6ecae083749 *80baba903bb1805b78a151a09bba021058406969d5485db9130bb8de639708a7139cc90e0a4fab *7797d81400a507967b20a08eae6a32addc8905b41a5840e969a53f00041690a7ab3a492b8b5880 *c002ee482bb50120b00069758a452c40600199a3ea37326c1000810588aa7c2c6201020b484f2b *0d017023afe40eadd7d538aaab3d5ed81d1058c0e1ba02406001ea0a406001eaaa72ae1202020b *505700020b505700020b505700082c405d9de2362c406001ea0a406001ea0a40600195a495baca *c65542201fef450815d795b4022893152c5057006466050b6aebaa37750520b0005d5581711c86 *61b491018105ba0a00810544a795ae021058409eae925600020bd055ed701b1620b0a0faa2d255 *00020bc893568a0a406001d20a008105d28a546ec30204165450570ed500020bc89656c1c21580 *c002a41500a7bd6c02c85f57e3a8aeea368ef397d2001058f0705d01d0379708215f5a05970501 *08c10a1664ab2b97051be32a2120b0e0f9ba02805f2e11c2b9b40a2e0b0220b020635d492b00d6 *b844082969a5aebae0362c2095152c389656efe3ae4d0180c0824c7525ad001058902dad82852b *000416482bce1bc76118463b0020b0205b57492b000416644b2b5d0580c002690580c002694525 *dc8605082c3850549323a86d0280c0827351a5a80010589021ad441500020bb2d595b402e05ede *ec9996d34a5d9187777d060eb282459b69f53e28da1400082c486da925750580c082c4ba125280 *93cc83bcae9bc082dd39c51c017074267443a1c082cdba92560014ccb308515710c113098123ac *6051555a05970501105890b1aea41500957089107505c0ef648bc0a293d1aeae006eab2b8d958b *4b84943ddaa515c08dbc4496c0a2fd1329754569479e61181c7e9056082caaad2be31c809ab907 *0b750500020b750500020bd41500020b00008145e52c5f5107ef4808082cd415003cc2cb340040 *dd27a9b681c082e5cc60f90a209157072dd6639708ffbdc7dcee4750570050a3fc2b589f489a66 *f5ea07e93dad00a0519957b0de47cd711cc7c9736d3e1f7458257c962ac7f1df1fa88b271202f7 *075698ac514d17abdeff3d5bbe9a4598c5adbed20a00da75d32542a4d57b9fb029001058293e5d *65510a690580c07ac0e72aa114935600d08c9b5ea6e17dac7567685f75e55e2b00045616ef15a9 *b7d9ddee56aabaab2b68952712025f0f856546cf72f25266ea0a8adad14d4ac08e42df2a673673 *395904002af2b209c87a566ff90a0004160080c0a25896af00406001a4f2444240607103cb5700 *20b00000041605b37c0500020b750500020b004060d109cb570020b00032f14a0d80c0e20a96af *00406091ff0cde360080a51f9b8004ffae8c082c00105864ab2b690500028b6c69152c5c01c017 *eec1e2485d8da3ba82ff79222120b0c850570080c0425d0180c0425d0180c0425d0100020b7505 *00020b7505450f16cf250466bc0e16ea0ace197f474d08a38103082cd6d32a7829513895594a0b *1058fc392a482b389f59c18216082c9b4057e92a481e4261dc2b2d0b5a20b0e832ad4cfa70a971 *7132f3f91ba30f0416ad7595b482874a6b39189516082ceaaf2b533914965c4a0b041635a755b0 *6a0599c755c832a4dc170f028b5aebca940de5735f3c082cd415705d66050b5a20b05057c045a5 *25b34060017474fa12ee691e9905020b00990508acb64fb05d1f049905082c006416082c801edd *760396cc02814561f3bfeb83d0019905020b009905028b5a59be82ce334b6981c002a8ec0c2694 *9c2ede431a0416004a0b0416559c5dbb3e086c9696cc02810540e6d29259708f974dd012cb5770 *f5180bb58fb03184f1ffeb8680c002205b660dc320b3e03a2e110274da58c1154310587ce5fa20 *20b340600120b3406001f4ac813bdc6516082c0ecefcae0f02320b041600356496d20281d529cb *57c07599152c6881c002b8e83c26f45c1716b4406001705d664d4b6bfd5fc92f10584d9c57bb3e *083c535a9b9392cc4260d9040064cf2f9985c0026057e73760c92c1058fd4dfbae0f02320b0416 *001d67d6ff1fd35b082cca64f90aee1969ae0f66ccac3f3398d4a25d2f9b0080677aebfd67f745 *1fa05256b0ea3da9b67c0534525ac33058c64a3f16246c725b5b60013c7bf8727d506395bff50e *eed536d91d5c22acf694c54c0434d7583603020ba0fd5319cb571a0b04563f73bee52b001058a8 *2b801816b11058006d9fcdb83ea8b120996711d635e15bbe027a692c4f2a7ce010337d106cff73 *ac60a92b6065bc59be2aa1b16c86bbb7fa2f9b42600100082c124fa72d5f019db18885c00268e9 *84c6f5418d0502ab87d9def215a0b1a0269e45587c5a85a0aee0ce5167f9aad8c672f335028b1c *5d25ad007e1beb3337ca2c0416a96965fa009059082cb2ce20660d78ec14c7f541990502abbdb9 *ddcdec0032ebe8c1c3de20b0000a3ec5b17c557566f5595a797f654fd8145800f027b38205ad92 *5a0d8155cec9b3eb8300194aabe7052d04164059a738ae0f3696594a0b8105004a0b8145fe9367 *d707e1c91168f9aaabd29259082c00c85c5a320b810500328bfabc6c82c7b93e08cf8e40d707fb *cdacd12b3f21b000d4151764d6300c328bec5c227c7c7ab77c05ea8a871b2bb86288c0525780ba *426621b0505700320b8185ba82d647a0e52b6416024b5d01ea0a9985c0025057c82c04160020b3 *1058000759be225f66292d041680ba227366292d04566993bc3bdc415da1b4105800407469c92c *0416d0baf79ab1e31d379696052d0416d0745afd3be0791f5f1ec8ac60414b6071e384ef062cb8 *33ade0f9d29259020b405ac15599a5b1041680b482cc9965294b60dd3319cef7337b1e20ad68bb *b182a52c8175be9f96f1d4793fb9010ba41558caeac4ebaa9258fccff79e34fb2b80c4b47abf76 *a823147536d63bb31c1305d6b1ba5a56f9fb23b38f8fe3f8d9b72c990207ea4a5ad15066d91202 *2bb1ae08ae0f02b0915996b29ae45984ea0a2a1b4ed6ae68afb182677a09ac2f1931b9cb2a6635 *eb7395d02e05a82b64960b41026bbd96a6b1b5fc9f7d2e815abe027505f19965dda10daf3bf696 *c9f3077bdb63d415a82b38da586ecc6a61d22a337a967b558d65a6ae405dc19943b475ac7a157a *93fb6c97aab1e2d515a82ba05b2f9b405d0100797999067505850ea47fff61300102abf7aefa77 *3c7040807351a5ab008145b06a0559baca18020416409eb4d2554073dce40e3c9456deb319f679 *2be89a59c1ca72a4707d108ea455d05580c00238d3528b937200810590da555a0a1058a41e4a5c *1f84bf6965400002cb2600a41580c002a41580c06af9c8e2fa20d2ca860010584096ae92560002 *0bc89656ba0a40605d79ac717d903e8aeac3fe0e20b000450520b0ea3a0c59bea2c5a8b2530308 *2c2031a4a6441580c00212a34a480108acb28f59ae0f52495ad94f010456357505d20a00819533 *adac5d21ad00105839a92ba41500022bdff1cb7d57482b000496baa2f9ae925600020bc85054ba *0a406035715cb37c85a202406041ed39a5a8000456d3473dcb575c1c52720a406001a7ba4a4801 *082c204354e92a0081c5e4f8e8fa2027bacabe0320b0803c69a5ab0004964d0079ba4a5a0120b0 *220e9aae0fa2ab001058a0ab001058051f432d5fa1ab001058ea8a8b8a4a570120b0d41579a2ca *5e0080c082b34525aa801a17058e1bad23082cb824a41415d08ea313d9609309ac274e05747d93 *51e5510540604162489d39a903008185ae125200082cd0550008acee0edc6ec0aa21ad3c4494b5 *5b06c54f3b07c189b4671a0ec330fbc4e547041694d4550e60946b74024023bbf2a484ba0da35c *5e3601e576d5fbcf18fefd81d2336b0c83a7c09379b74a7ba5ab2cb1f5d4b76e8315acff53ddf5 *c152ba6ab22800156696d52c5a3c444ec2ebf3c1adff9efdcbe5d7e9616d4c6051585d392651d3 *1ebb9551328bd6eaea9d44c3307cbd74b85a5d3b4126b0e0e2b47228a23593cc5a7c186ada957f *63e8e475c3aeae390aacdf87dcf5c167ebcae6a7edcc5a9e4e882d3a0eb51eb8c91d7505f727d7 *f8e7a678771253e2dcbc725bd5c925a85c5fa70a56b07828aa9cc153fd6e9c65f71de783c288e0 *d1a8fa7fd7fc7b5970f5fef4d54edaba937dfa75dce4decdfee4fae09d45e510025f4bcb18e1fe *5d70fb50b8fa57911f9c7ea4ab4b84028b5bbacad1020e9596cc028105ba0a64160fceb93681c0 *2a2d03de9397d92b775dd9a220b3b8671771081358d24a5d415b4b06b7edeb7f5f4fcb10038155 *6e5d492b75059571173cd4a4bbd7c15257ea0aea2f2def2a0d024b5da92b406681c0027505bbfb *7c28e6129dcc0281f57c0658be5257d0249905c5f13a589c48abe04e5b282ab30c4c105854dd55 *6670283fb38c531058e82aa8642c54310cbc873408ac9bf2c00d58e7d2cac6832a79f52c105848 *2be0d2d232a8416021ad009905028b26a26a3209038b61d2c6f0905920b0b821a74415f4486681 *c0227b54994f01990502eb5c57f4fd1442cfd3066416082c32d795e912f28ca6e6eb43664136de *ec595d01cc32cb3b1b82c0425d01320b0ad3fe25c24e6fc05257409ecc721f27082c80ab4e5a7a *ee0befb703026b36255abe02c85b5ac310f3af4060a1ae000e66d6fe2c24b3e89e9bdcd51540f6 *021bdd1d8fc00260ffd425589049c92c4f424460b53925f6760396e52ba0b4c69259f4ca3d58ea *0ae0eaccf25ea8082cd415f0677c29827c99f599b236fe060416009c8e2da78834aad97bb03aba *01cbdc04d4de5b6ed24260a1aea0a721165cc1d25820b0d41580c6028175557874707d505dc1e5 *a32c58bea288f21cb4a7c05257ea0a203d256c040496ba5257001a0b7a08acf6a92bb869ac05d7 *07351608ac3ed24a5d011a0b6ae08546eba92b69050095686a05abcd1bb02c5cc103e32eb83ef8 *348b58d4cd0a569145f5779201e8b5b19c5e22b0c8555766137878183ab3d15870969bdcd51540 *e18d652320b09e8c93ca6fc05257001a0b8105d020d7074b6e2c9985c0ba7b4ab47c05d07c63c9 *2c0416ea0a2a1c8cc1f295cc822c3c8bf0e9b4329f03a464d6e4456dcca2082ca41540cecc32a3 *22b02e6b95da6ec0724d104a1c980ed1959796052d0416005c9259c182167d07d6300c218471b2 *f2b4fc08c05d5392037273a565418b96026b98bc8fde329ef4d3bf316fb403dc93594a8b87e47f *9986f1d727aaa64b53c390f999b5d5bf0216009797d6e4c51dbcbe033506d6d602d5fbe3b3bf9d *4558178b5b96afa0c481192c6ef4585a50516001401da5a5b1b8d22537b9bb5d7d6bbb384986f2 *0666b07cd56f6679be21b504d6d1b4fa5c256cbfc6d415a82b0a6c2cf333d7b8e426f7adf0ca7e *877b356965f482baa2e4cc725716b9e55cc15a56d4e7def661180ead54b59362d20aa08ac60a5e *a194ec6770c55f9edb798e61b92fd360a042f1939fcdc0d6ce51d6de31b8adb93ede2ae782a89a *9c0e01ea8ada58cd42609596568622a82b6416781dacec831180b66676b7c093a2ee15ac526ec0 *72273b54336b381922f504da7b1ad24f60155279061ba82b7ac9ace0ba21020b405d71516959d0 *42605d39655bbe02e838b39416024b5d41c7a3d5d10fa585c0525780baa2f6d2b2d3092c8076d3 *ca818e874acb8296c0e2c87cfd3e2f190d189056f03db3822b1e028ba8b4fa337903d20abe9796 *8b86028bcdba3230a082ae7210a3d4c672281158a82ba830ad8c526ac82c4b59020b7505d20af2 *3796238bc00228bbae1ca3a836b3322d650d43ca3dc1e368ec5cee6513ecefb926705057704963 *85310c714f9a1a13430a81a5ae80e8b45257b4975934c725c28db432814399756564d2646639ee *08ac2eeaca2e0eea0a6e6e2ca7f76d7189105057504e6645df9845d9ac60cd2671cb57a0aee0f1 *cc7ae07834bb8ffef34cc36118b69e75f8fe94e5df4ebfd4d6d7f97ceef2ebaffecbd957dbfac1 *96cf0678ea29931507d6300cc1134d415d41ab99757b637dcd97c8a3f334aa763228e6eb2f63eb *eb6715f222142e11fe79184de3a0ae8eff889f3fd05f068ee374d1681640abad935c57cb6f5732 *9708d515945051db27f1f5fd26a6123a396c462d712d2fff853e5ee95460018f17d5d8e2af27b3 *38efeeab84572f0ebd9b6cf95df27edfad9bc904d6331d6e3284cbfa69edb0d1cb5630b35055d0 *edde6cbe8c984fca1c5dcddabf9278b2b70a591e1358ea0ab217d5d8ed6fbefb0f4c34345b633b *4954f57d5467747f93bb77778284a898fd79bf78cfff7f88d970d0d8e174086bf7bc6fc5594c63 *2dff59f2731beff7d3e75ee09412be94c0eea4670b65ddcab6276545d2b46ff63b69b5846655b4 *d34391afb9b0f3d5567fe0425e0aab8e9bf9375f4523e12777411007f428c649fe6d6a9b93b28f *8dbfff7ffb250f0eef6a5e45f27a9dad60a92bba3eeedbfb4baeab604d0b0496ba82c28ff5f6f5 *061e4e0f2208ac0762c9fbe4a0a51495cca2772ef609aca7ebcaf21555669396426681c002d2cb *c911b4d922965920b080ecc75c0745641608ac362725d707b921a41cf9905940578105392bcab1 *0d9905082ccb577c0f2615c5b53b93cc0281a5ae68f5486757a0ed61600f078105d972ca410566 *c3c3a0008175ed6c63f9aab19672e400a5d59bd1b14c6041dea232a35053fb2b2da0eec08a7d19 *77c95fdfd1ca0306970e33430c04d6e90a3393d473b6efa102990502abfcb432819455541e0c90 *5920b01a60de78b8ab3c0074740221b3800e02cb95c1278f38363dc82ca0c9c0e2997378b333c8 *2ca0d5c0b27c75534e99884166019d0496ba9253f0c4f0905940d38145b6a3838915905920b082 *e5abf8a2b299009905028bb373a39911905920b052c6bee5ab8df9d07601724f2b2616e826b090 *56706b61d80e26191058d20ae081dc341721b0905600f9272693125d7b55366487218c06ed6406 *fb7727bb6d02143a4391c71886c1f6ac8915ac3a67adcf8003ee1d75246d3a93d5d9b6b20905d6 *cd23b79b7d6ef83bd8006416082c4e9f279b9880f62638331b028b9b261fd30d5473de43be6d6b *eaa3352f9ba09449465d014a0b5a6105ab90f9445a0180c022435a892aa8ec4c888b37b5599176 *b844f8c874ed95ab00e42c028bcc750538de639bd33297086f9e31d415c0d719d35489c07a720c *16fc2aa3f37330930500082c141518d53cb9f1cda2082cf380a202d05830e126f7f375e52981d0 *ec99131e05683fb0866108e358d0c0f79440008d056baabd44380c4f0f73690500b41458773e7f *d02b2c4077ac9a94f670987ea98f7bb0be4eb3a3bbac0024efa346dba03a9e45b83f9075153896 *53cee3624e4660553c840d60009905022be759ab710b20b3a0c3c0bae20e770b57c0e44c0b9905 *fd05d62553a8210a50f5846e1a47603d3f128d4320eadc8bda1e3ed33b02eb81a167e0017452c9 *267c1ee675b00068b2b42c49f2a49f2e4699b319206ea6a0d187d5210081957f701957004a4b69 *21b0728e266309883ffaa2b4a0cfc0fafa2258de9b1980a8d2729840601d3833316080c313071d *3ff48e1a08acef33a4710280cce279af5646c7687800c92767d8136c0204d66a5d0138a672727f *b04bd05f600dc310462105a82b641602eb8e19527501d07c6639d809ac0b77f8c10e06e43a3983 *0a330b8105a0ae9059082c007505328b2c7eeadedb5d3204d4150fec428e3e7c61050b00124a4b *afb3e7a7d61d1bc0c441293b95052dda082c7b33a0ae505a14ec55e76e6c0f06d41565ee6c175e *3d1c063bb3c00228e580e7948cd64a8bf2fdd80440bb47b8d97fc053fba1caef4e552b58a37912 *883ca4992c2833f7115845771680b44263512e970801472fb8732fb54c20b02eddcb862184308e *e3ce47cc9f80aea2c59d566309acac39f5a59fa2d8290169451b7baf235acbeeb8076bba34e535 *3c007505bfbbb13d59609df3aeabd9f2d5388e9fde1a86e1f4e216a0aea0e1cc7294145897759a *070c1c8d6c02ecd894cfb30801472028670fb79420b072f85c25747d10505720b39a71d325c277 *45b9c31d5057609f1758794c9f3f7862a54ace83230d74b5e77bc7e8ca67ae022fcf59eb028039 *f7d308acecbd65a7b2c56c315bcc46b3c5a0162f9b000040600100082c000081050040322ff209 *009099152c000081050020b00000041600f0186f67d2809f9277acd5bbeff7ffd6385c6e165b6c *b63566dbc1fe76688bd9df2207e3ea46b38fc56c31fb186d789539dea6ef0f1dffb7dd1a276cb1 *432785f6b784d368fb5bcc60fcfcfaf6b1a35bcc3e461b7eca1c6fefffbb35b9effc6de7ddb07a *3e678b4d37c57223d8df8e6e31fbdbfedc654e3bbfc5cadcc7567faad907bfaec9ada6e17e2f5a *b113583c3c490dc3e08d51b1bf611fbba8ae5697d3961535fdc8a70297bfd1ec13b756e68cb27a *b9c9bd9d53408310fb5b21476207c5335bacd87decfd73ae7e707591e9e86fb4f5cf56bf2fe5b3 *820590ed002c3d5bdd62b305a7d518ba2283b6be2fe57b153be4f6af46cbf9e590b6c5ec6ff6b7 *720ec3f6b1e42d56e03eb6b546b5fc69a7ff73f98becffccabffde0d5815cf96a1c865d865b9ef *5ce776c05b3dd7b1c5b636d7d79769b0f576b698fd2d6624aeae3dd862915baccc7d2cf23538e2 *6f725ffe6a5fef7c37870b2c0080aeb9c91d0040600100082c000081050080c0020028c67fde72 *d9b9ff957b800000000049454e44ae426082 addfile ./en/figs/ch26-heap.png binary ./en/figs/ch26-heap.png oldhex * newhex *89504e470d0a1a0a0000000d4948445200000320000002150802000000a6d20c95000000017352 *474200aece1ce9000000097048597300000f6100000f6101a83fa7690000000774494d4507d808 *1601051566d30df900001efb4944415478daedddd992a33a160550a8f0ffff32fde02e2ec5200b *9040c35ad1d151d799e9b441c3e64826c76118a6691a000048e48f430000206001000858000002 *160000977db60f8de3e8b8000044da7e5ef013f97d00006ced56a62c1102002426600100085800 *0002160080800500c0759f6b3ff6dd305fd4870db77bf8e79717b8f1c4eef7e47b5fe338a67af2 *ed53e5382947cf596003a052093b85e343b1273130072539c5c6e4760256a6d1616e85d75ac936 *707c1f593e1e934b6a1cd1024968f7fd6e8fd8331193b389f9c2995a8de6091bc0b59fbdd9af05 *0e6a57effcf2b36bff7c2fbbdf7367b489f9d5819f3d3b88dd99193f778ef8cf837bea9ea5cb67 *7bb809ae7e57aa4b8a12d255e0fd1ed5fcb68faf8e865bd13e7681bb3d23ab737dd4500363d6ee *58bf7cda711c8fc6c4a39f0dcc1f2ff66be86d0049dbc5c2c342cc44b0fb3de11123724abafcb2 *4fcd80f12f75d7c53d58d334c5e4d6c097be8e5ef7eba370cc0bf8befeed7b89f9c1dd1fb9f054 *67d3d5f2387f7364f8f1a343619acc9daece9e91846d3eed001dd9af578d7fdb11e6eeb6fdea6e *c71917c2c73cd0e98e9e24fccc472f6f1b94cf0e05e13745ede3c06e23894c15bb9372e01996bf *2e66174da00e94a4c212488aab0130e669032ffbec0c7847c625c29fe590a30be5b3a376be0ad0 *a95712f9aa8e7ee4da6109bcf2a3e34f694e9da9530d23fe47de4dccdb8e7034a46eabcbbb1d67 *f5843f7fe9d14aebee9304baead197764f7178f4085f4cebd7eda5abe70bbd3f479ec0cb8819b5 *2ecc41f183d5b597fdb0cf85767027eb8473e2cdbd1ae1ad273fcfd68522c1eaea3ce668fc1cca *e3e373a6b270f8c419d98b2a7ac58c80678b6181f5cadd9ffdf99c3f5f6d4c3fbadc718e2e3fe6 *6bf75301347c61bdfdd2f6c19f95c2cb6f8adaafb26e8e06f1d3c1851927e1c8ff4c493ec9cbbe *f952ff3cdc147ea6843bb3f8f4afb3c17959628d2cfec7bcbb0bf5fca3b964fb54316bb5c93bbf *c1bd84e138d05396ade2e8231de1cd0d81e0b5fdd9f073dee9d7379718c25d2f668888e9bfe1fd *73c9670beb833c1fb8d37e44f1e72854cecbbef9523f177ed9cdc3f1733c3a1af88e960c72b4d4 *54578d095f5ef89adef6e13e47d50b9d31bcb321dc8a7e56adb62fe9f2ce86c82253b8abce71e4 *4ee75d3dc95bf926c99ba2314926e5c7a2d5fd61e1f9977de7a57eeefcbee1d23eaacbef39d312 *7581d1e4c221bdbca12d6b398157dac6859650ef841d9308031f2388df307bf6a22e5f7fb4584f *da49b9b161a19c97fde7ce89bcf01ec27b575f99c877b7825dd84a7ca74ddf7ffb91636ecce726 *c23b605c343fdf2c8f9a56cc878c02b7d78adcb3b8db618f7ef5f639631a76f873d117c69398b5 *bf9f57a547b5b1a30f34edbed998f318391a48549d5f59dd9c947fb6d5b40591c8b713b3e3f3c2 *dc1ad8ee797606bc33357f929ce053ef7ff94e8e86fe7cb73b8f19a693bc973b6deef27d56cfee *8e8f3fc51432aa46de44e3a82dcdc5cedd0bdff00875f4b381e78c6cd8472ff868c3fbf20af5e8 *674fdd6a2426c2ee8ec5916ff6ce66b29faf871eaeb27687f79f9372f819e67e1479f133a45b74 *0b8c4249eeb9187fb3e598f1f6f2d43c0ec11b45703fbd41d50df2dd76ae97815e56e931f4c79e *8172c72c0701b2f62cbd2c9f8f43006dc87d87f757e60017d690a3535b6e16b07a9ccf00fd0bf4 *afda5922040010b00000042c0080aeecefc1f2b1020080cb7c4e070020314b8400000216008080 *050020600100d07ac0f2a94634090004ac8b53a65993e874356930000858e1c9f2ff567f811282 *a6396669360014c51f7ba68198f55f527753370004acff8ce3686a24b2a9cca16a9bb4c42c0004 *ac61f87759d0420ff71bd4b221495a00741ab056b3a0199180e3f2d54ecc1a14b400e839604957 *e46b53838216008f2be2360df3a7c02c11126e2771e5abdd9835b9b303001d05ace5f676b76920 *33310b8027b84d0375b851beda8d59d60d01e82660a92bf0201be101683760cdcb82e6395e4c5a *9a1f004d052cb31a3f255d1ffc1db3b449006e2aeb6f110e5609793beddb080fc07d6f56b0dcc0 *9de876f27c3dc9ba21007506acefbce5af105230eb8600d416b0e0a797ca573b316b50d002a0a2 *80b5bcb9a8a98bb229680110572028679e08cc5b96113b6d9d4594afeae83e0014a5c425421502 *2a61233c00a506ace5470897b3948f16525dcc92b4002825601dcd4926aace15bf3eb813b30605 *2d000a0958a622da62dd1080322a5847ab8474abb6f255286669d50002d63b53e96aeb95d98856 *58370410b0a00cf597aff693969805206001196396a405206065b1dc77e58e0cfcdb18da4e1ed6 *0d0104ac7c938c7985de296801085840b698352868010858904907eb833f929698052060011963 *96a4052060c15d7d97af7662d6a0a00520600199929698052060c115ca5791314bd20210b080c4 *316b50d00210b02086f2d585a4256601085840c698256901085840e298352868010858b0647d30 *61d212b300042c2063cc92b400042c3aa57c952f660d0a5a00021690296929680108587444f9ea *c99835286801085840a6a42566010858344bf9aa8498256901085840e29835286801085840a6a4 *2566013412b0b603ba21be1fd6074b8e59ba214071016b1ea097c3f4ee83409931ebdb67f55380 *8202d6517e3258f36f0ad71e4a4f5a3216c01d7f724c9f5f3f1f9ca6697ec4680e000858c757be *d3b45d19dc7d900e295fd563d25b014a095873156a598eda7d1090b1005af5f26d1ae65542d9ab *07ca5700742271056bb9a72afc205003452c802bd257b0766fa573f6fe3ac674282a63a931039c *8b43430dcb73c6f7169a9af5c19acf9e0e0870ca1f8700f8c542218080457994af0010b0005614 *b100042c4aa27c256301085800000858144cf9aa2d8a5800021620630108580000021684581f6c *942216808005002060d106e5aba62962010858808c052060513be52b00042c800b14b100042c9e *a27c256301085800000858404114b100042c32b33e286301206001000858144cf9aa638a580002 *1600808045f994afbaa788052060013216808045c994af0040c0023251c40210b04841f90a190b *40c002006831608de3b8bac6dd3e02544b110be8da27796cfa67889da6d5e3f32334c3fa20818c *a5cb030256a23175339e7ed3d5344ddf1a95011700685bfa25c2f1af6dea5a45ab6fe49a7f4af0 *aa91f215e10b2e0b8580809568409da66f5432b0020002569a74b5fa070d53be22665470ad0508 *588f0fbd3666818c052060852df7546d1f37c8b644f90a001e0a58c3e27656abe5c2d583404f14 *b180be141a7ab663b16456e439725238d76a7464a0139f325fd66a1476ed2b5d014045fc2d42e0 *b94b27174b808005fb94af90b100042c0000018b82295f719b2216206001002060918ff2158928 *62010216808c0520600100085854c0fa20a92962010216808c0520609190f215000858402d14b1 *00018b2e295f2163010858000002160553bee2118a5880800500808005144f110b10b0e883f541 *642c00010b0040c0a260ca57bc41110b10b000642c00018b48ca57002060012d51c402042c9aa3 *7c858c0520600100085800bf2962010216adb03e0800b506ac711c57d7a6db4780ee29620155fa *e4cb4fd334cdfffe67bc9c5447caa57c459919cbb8010858c3f68ad3e00800f423fd12e1eeb5e6 *f8d72a75cd8fb8422d81f215a5b25008f41db08e72d2344ddfc78d92808c05085829c6c5bf914b *8daa64ca57005062c0fa5e5fce4b8131979bdf5542eb8340ccc59a2216d063c09a168645bd6ab9 *d1ca1107642ca0799f677ecd3c26aa5495c9fa2000a49c58cb0c3d6ef4206041a0c11a1080c27d *ca7c59abd1d3a28074050015f1b70881ead889050858944df90a190b40c0020010b02898f21535 *53c402042c00190b10b0000010b038c7fa204d50c402042c0000018b56295fd110452c40c00290 *b100018bf6285f01808005f09322162060f11ee52b642c00010b00a0321f870068c8348ee334a9 *d1f2b46bd5536d55c0a2a521407f46c6822c6defec90ec9035cc1221008080c555ca5774c36e77 *40c0020010b0a891f2159d51c402de64933bd072c6b2db9d7aaf8aefb7deed932c2f3c965fdafd *cef991a39fda7ddaf9dbd276c0c06bf87e69f576b6af47c0224b4755be02a8345d6dfff3282485 *c344f869635ecc388e473f9524c11c3d79e46b783751ad5822041a66a19036ae9077d2c3d7fcd5 *6fe6583df833bbfcec20ab9f7a25b5c4bc86a377fd22152ca0fd8c65a190ba12d52a4faca2437c *7b0eafd35deb17177e6ab7e4b67d53df47ce56a78aede0025627573f6617004e249e3bcfb97dda *ef7f2e57f7b68b9b69b76d5d4ea5021640ec25b72216ad86a4b9619f5a238bd9bd7e366f05ba58 *e045264975ab75d2b7129580d5610f34af808c45b3d12a1c9b72fcf654fbd9874565ebf26b087f *78f0457f5e6c1fdb186b3b2a00fcbe6238deae1ef894df85ead1eaa7ae4dd3cbd7167e17f75f43 *3941225705ebe833a5ae201fbfca71c0e1ffc38f2216ad0cec173751ad924ae4aae2f6a7c2496e *f7c77763c02a36cdd5aced66acddd77074f3ad52ce548ed0b3aa5e2e37afad8ecbee1eb79f710d *010baef5092309258db763e40dab52153b78d29f1c8dec686178f5f8f6061ece87740539b92d16 *f090c44b847212507ec6324c91e9c23659334d71c3024dbda98005003d26f7d451e6fe134a57ef *4ab94438efbcdb6ec10b8774293bfd6594f541381e782c14023505ac6961d8dbc06e5003642ca0 *074f2c112e3fa21959a932f6dda17c05002fcfc5430dcbb4d610052cc8d1570c2c40267f1c02e9 *0a7a65a11010b00000042c9ea77c0527296201021600808005503c452c40c0e298f54190b10001 *0b0040c0a260ca57708f2216206001c85880804556ca57002060019449110b10b0188641f90a64 *2c40c0020010b0007aa3880508587db33e08000216401514b10001ab57ca572063010216008080 *45c194af203f452c40c00290b100018bcb94af0040c002a8972216206001c8588080c559d60701 *40c002688022162060b54bf90a00042c806628620102568b94af40c60204ac1f5961354e6d1f01 *00a8d1274772faff85de34ad1e593dcef903ebd0c1eba6711c8d63c0a3016b39ee2cff6d300264 *2ca01f8997088f469cf1afd537cf8f18ad0000012be49ba59681699aa6ef7fda6575f9905a1f84 *92d8ed0e3c1eb0be716abb194b8d0a90b10001eb9c0b63cd3787591f8c38b08e0f007419b09655 *abdde0e56a0f688b2216b0ef89db341c3d18f324285f01407dd3f750c3d6a89ed710052c28bf9b *dae400acf85339d2157093854240c0020010b0008aa78805085895b03e08321620600100206015 *4cf90a2aa488050858000002563f94afa05a8a5880800520630102560f94af0040c0026045110b *042c00642c40c06a98f5410010b00038a2880502160550be02190b10b0000010b00aa67c058d52 *c402010b000001ab0dca57d034452c10b00090b100010b0040c0e21fd607a10f8a582060012063 *010256a594af0040c002e00e452c10b0c84cf90a642c40c08282d2a943008080b5991ec771750d *b77da4f180a07c75375dc958d44b110b1af7c9931b866118a6690a3f0837d2d5fc6f2d0a80e224 *ae608de338fd3587aaef3fbed1ca451be9d2d5d1235005452c10b0e2078c8302d5f7f1d5575721 *acabe296f5c144e94ac642c6024af4c9f1a4cb9215644e57f357b537004a916593fb6a8990bd00 *2a0d244c57f1df03a53154828015951b4e47b1ef870795bb782a87818c055415b00255abefe306 *9141f92a7b6cd2c600682b60cd016255945a7e7e50a58a9ce94ac6a2528a58d0e2ec5560e8d98e *356d2433e5ab07a392e34c7d0dde252834e353e6cb5a8d32aeeda4ab4b3f6eae02e01dfe16214d *a6ab844f02cf5d5aba9804018bf3b3bdf5c1178291e90a00010bd24722198b8a28628180c5a949 *5ef9eacd3064c642c602042c90b10010b0f831b72b5f159181642c6aa188050216d4947e4c5ac8 *588080d5467050be2a2bf798b40010b090ae642c3aa588050216549675cc5bc8588080556f7cb0 *3e586eca316f012060215dc958f448110b042c56b3b7f25505c9c6d4058080053216dd51c40201 *8b79d256beaa29d098bd90b100010be94ac60240c0ea2e44285f551962642c4aa688050216d41a *5f4c60c858808085742563012060751125ac0f561f59642c8aa588050216541c56cc61c8588080 *55ceb4ac7cd54e4c3187012060818c452f14b140c0423af12e0010b0402e91b1289e22160858fd *640a1bb09a4d246632642c40c04216f1be00e830608de3b8baf6da3e8214e2dd4190221614ea93 *3c36fdd7efa769fbe0f2f1d6e65eeb835de40f6799123356abe32a0858c36eae9affadf34b5732 *1600fd48bc447814a4c6bf56df3c3fe20a4cbaf27ee1f2d06ba1101a0f5881e0f5cd4f4601642c *90b140c0ba34f38ce3eefa60c335aabe37608d1dbf71531a003bb26c728f0f52f32aa1f541e9aa *e623a0f55202bbdda120e92b58dbeebddc68e5884b578e0300cd4b59c1fae6a7f09d1a22afaeea *8a62bdae0f4a15aba3a172c0eb14b1a0a439b2fcde58f890d165c092aef6a737878012baa78c05 *aff3a77290ae1c1900042c6408c70742dcb20104ac06a6d3bed6078dda8e1232162060818c0580 *8085d0e070410a8a582060d53b8576b43e68a476d00010b010141c3a7aa7880502162282030832 *1608580807388c000858a9e7ccf6376089050e260d50c402010b81c02105190b042c44011c5800 *04ac44f3648f7fe019198b7a296281808504e008838c050216e67e1c6700042cccfa8e361d52c4 *0201abe489b1cd0d58865dc71c00010b33bd230fa7296281808539def107190b04ac2e26c3d6d6 *078db3ce02000216e675e702ee52c482bc3e0e019494b1dcbd964733d6346972897aefa5c0eaf8 *374c05abf3e91c27050001ab886b94362e384ce44e0d582804010b53b813043216085898bc719a *00042c4cdb38597448110bd2f329c233d35df51bb08ca1359e321f32824e679cfb9f31dc3ec932 *4cef7e69f9e03679fbd8630501ebe8443a79d21532168f73cb86a2d3552027ede6a1a353b97c9e *711c634eba5671d99fe46d62b6fbb8232e5de1f4516cc67214ca0c5bbb8f4cd3344dff9db56591 *62f754aee2d46e725a3e216505acf9949f3aebf53471411e190bc83eddc424a1ed57bfff5e3d12 *9876c345b2c8ccb72aa0acbeb4fa9e95b6cf63e225c2a3d3339ff5d5eaef7c46bfff109ccdcd04 *cfa3884f56160aebbae60f4dbbc97fd16e868b6f30db1f11b090ae90b190b128ec3c9d8f383f53 *d4b2e0b45b210bfcac36f350c072b8a52b642ca0f4d1e42048c5d7969639cfbcbf926593fb770f *56e4b989fc20c3ebadb0c2594dba929be102bb352a0e4c8178b4da87133ecb316d60b98f4ab4da *4a5fc1da3dcab6589983497d7e0d67e4cd58a6cc724fcf623e5d96a0e6c413d80fbdbd0fd6eecd *ae7ec6aff9d36cdb5762aeff6f1a4ed58b027724db3d01cb53bbdcea3e947773b3da2a581a772f *c3ac4340be6144c0ba39035e2e490c897656257c1e2e4859c10a9cc5ed97021f311d0e6e2f2b5d *49576cceb5a1935cf1dddc0c77f85b84edcdb838e340e5f136c5a61a11f9fdd1b9fc13f06e2ba9 *a78265aeed77347608c834aa98a1e11a152c68e44a097264771b9641c0ca3371295f2163012060 *995cd10c201d452c10b04cab680c2063818055fa6455c1faa0510f4d0240c0c2548a86417d14b1 *40c0328982e6818c050216a64f34120001ab8fd9a9dc0d58264e34155ea1880502162063010858 *982fd166289e221608587766a442d7078d6b6839c8582060618e44fb0110b0303ba215c12f8a58 *20609917415b42c60201ebfd29a8ac0d58863092b7288d0a40c0ea7d2e044d8b3229628180650a *040d0c190b04acd7e69c726fe00e3216808085990f2d8df62962818065ce03ed0d40c032db8156 *47f114b140c00a4f32ef6fc03248a1ed2163818085190e2d100001cbdc06da211928624101016b *1cc75557dc3ef2fc4b7a6f7dd0a8848c858c05edf8644a2ad334fd1b5c16fd6f729729f319e5b7 *49fd14a0a480b57bf92254419db95fcfe5ac69758d0d7d4abf44b8dbafc6bf56df393fd2718754 *bea2f0f6a989722563390a08588ff4b669fae6a7627bdd4b1bb08c415414b33457809202d65c9a *523496ae682269c1ef815f118bce7d5eee827f5709fbcb5e861e6a6fbdae97000e3d51c15a6eb4 *72c4a52b1a6ac65a32a12b68633e3d7ba8823577b3322b55cf6ec032e2d0e4d5828216fb19cbe6 *10fa1d1c0b6cfddbeb9eac2ff2c180255dd1f884ea10b01af4042cfaf429f365ad3a642b7566e9 *8a2eaed9c42c96c3b922167df2b708dffd0b39d06acc7239c13f19cb5140c022eb953d88590002 *16d215248859ba40e714b110b090ae2063d20210b07a18f2b36fc032a38098c5a0888580857405 *62163216dcf27108a42b78bb8ff8182fd09aae2b5839d707a52b38d55f74994e28622160215d81 *98858c0502162066010858ad4e0f8098458022160256c3e377960d58860c481eb3742b190b042c *805c490b40c0ea740e00c42c2229622160b5374e67bf813b206601021609067de0e198a5dfd54e *110b010ba0dca4858c0502569b433c206601741cb06cc002318b9228622160b13fa60362163216 *fce7e3104857d074df54ae065ed05d05cbfa20f497b45c085541110b018bf52532206621638180 *058859000256912335506fccd285cba488858055e3b06a0316b04e5a00025641e3322066918322 *1602d69d216d1c575d68fb887405885932160858ff45a5dd38f56e87b13e08885940ad016b375d *0dc3304dd3ee572b1c7f811e6296cefe2e452c04ac559f98a6a307575f9aa6fffacf388ebb3f08 *f076d242c682020256eba32d2066010858df01d2062c40ccaa8f2216b57af98f3dcfab8435ac0f *eae480bf21fd4ec6b28784ea3c54c1faa6a89a2f44a42b603526181680434f54b0be65aa5395aa *b451ccfa2090f3d2cbf0927d1a51c4a2cad1a1fc567bb36bdd0e58ae5381df21c021c83a0f0858 *d4c5a70801525dafba18cb985fed7647c06a6fd0043815b38c1b32160256f3a39d0d58c06b490b *10b0d81f2201c4ac4228622160012066c958f4eae31004c74480e4438a4d0bd0bec62b58373660 *495740bea46584b943110b010b00314bc642c0e2efc00720660102d676dc728306a0a69825699d *a288858055df4807f062d202042c00c4ac7728622160d534ae01885932160858bb23d3950d587a *2920660102164047314bd2daa588858055faf8055045d242c642c07a650472830640cc0204ac02 *462b0031ab5e8a58085800248e59b2858c858055e2f004d046d20204ac4c63ccb90d58c62340cc *6a862216021600621608588d8e410062564b14b110b0720c276ed000b013b3baca1c321602d6cb *830e406f490b10b00010b3ae50c442c07a6d880110b3642cc8e2d3d480610316c0954b4d232724 *f65a056b1cc7d5b5c5f691fc630a0043bb052d452c5ef344056bd5bea7e9dd4b259d0d20303c36 *56cd9ac6717c7bde41c0cad7c0f3376eeb8300621614e2a125c2f1af55ea9a1f79ea0a43f90a20 *72b46c66c0b45048bb016b9aa66f7ed2ca016a8b59c66d283260cda529bbaf006a4e5af552c4a2 *c58015ce5edfa5c39bd9cb062c00314bc6a2af80b5dc68f5eab80040e7310b1ef2d0a708e76815 *59a94a1dc58c050099ae5a2b5a3d70cb069eed21e5b7b6709788581f14b000f266978a263e198b *07f4f0b708a52b8007465a832df415b00010b36676bb2360a5e9ed00885920609deac76ed00050 *6ecc2a336929622160ddedde009490b4642c042ce90a802e62160858bbfdd5fa20809875912216 *02d6953e0c40c931ab84815ac642c002a0cda4050256353d1600312b86221602d6aa47da800520 *66c95808584f755100c42c10b000601db39e4c5a8a5808583ffa24008d252d10b01eeb733b1bb0 *74420031eb32452c042c00c42c198b827d1aea7800f410b3fe1f861c0b4a566505cb0d1a0024ad *3c97d68a58741cb08e2f680010b3642c042c0028316641ef014ba702206dcc52c4a2bf80f5ef06 *2c1d00806dccba3f3bc8587416b000203a69818075a5f30040a698a588453701cb0d1a00783666 *410701ebdfde02006763d6a9e943118bee021600dc495a32162d06ac711c574d76fb48b06f00c0 *63310b8a0c58e35f379f641826fd018067639622164506ac6fbb9ca669fe37005415b3642cca0b *5873bafafefff2c1b9bd8ee3b8faea711f00807c31cb44433d012b41ab778306001e4d5aeb5a81 *22160d06acbf2d1e00de8a593216b13eeffefa7995306e7d10005eb9b6374971ce739f221cec70 *07a0e298f5fd9f2216c504ace5e70755aa00a83c69415c432930f46cae0fdcfe0a807228175067 *c0dae62d6dd98172ac1c2807ca81825af85b8400000216008080050020600100709d5b27000024 *a68205002060010008580000021600e04fe872dda7e406bdbbfb3efcd53e7b7ef840395cf30139 *3a081a55cc81d2a2760f85612ac98172b810b01eea90d3348de3b81de8c35fed70e40a1f0aa355 *cc65a846157fbdae456d0f8561eaf281d2a810b0dee990dfe1e9ec573b1cb90287c265f4f25805 *1a8c461579a0b4a8c8b7af45c5b7936b8d6afb538147e607772b6adb2a9a119566031669473797 *d16851b4d4a876ab86ab52d95c47dccd46ab5fb7fcb6e50f2e939636cf5936b9b77fed6850408b *ca41d0bc7fa02e37aa3909ad1e39daf535d714637eddd1b76d7f2904a860019c4e0c82e68b076a *55975a85a7dc1718ce3e91fe14db27c3abe02e23220f946375ff48a24505a65b2deafe813a75ac *9665a4e5936f9f6af98fd51909ffbac03388569c18330b6c2ebb7b15033b194d78e103e558ed1e *9cdda1d981da3d38810dc23df7bbd5d1304cdd3950a78e5578affa854deebbfbb7627e162a0b58 *000055b3c91d0040c0020010b00000042c0000042c008062fc0f6aaaa95fb64b65f70000000049 *454e44ae426082 addfile ./en/figs/ch26-stack.png binary ./en/figs/ch26-stack.png oldhex * newhex *89504e470d0a1a0a0000000d4948445200000320000002150802000000a6d20c95000000017352 *474200aece1ce9000000097048597300000f6100000f6101a83fa7690000000774494d4507d808 *1605382d233055050000193e4944415478daedddeb72a3b8a28051d395f77f65e6877b68c24508 *214097b5ead4a9d94ec7b109c81f427686cfe7338ee30700804cfed8040000020b004060010008 *2c000092fdac6f1a86c176010088b47ebfe04fe4bf0300606d7366ca25420080cc04160080c002 *0010580000020b0080743fa7fef5e63af942de72b87e6cd3030b7cf0c4e6bf897c46c33094f676 *cb771fd2faa77fb76af687b477b737fd38bada8d6d1f1e78799abfdc64f9851afdaa0facf5ef6f *1886f0ce716ad799f6c2b4bd64fdd8beb7cc6f8f898084dd3da6cf02ff26fced958ea7810c8a7c *fa09d5dbcc0be4e6b170654325ef7ee1079c70b7d97fad8283c25d7c7d29240dcfbe365d1973f6 *7e4ae42c4fc671e9ca78f5737dbf09b4f9a9cf2c5d6cc42777c1c5cf8a3ca5587fd7e1530efc9b *bd2f55fab9afe149a6f8a71fd8628bdf512d1b2ae6716e1e0bebe73bdf38e1dd6ff1eb580f5881 *43eff000dffcd18b2f6d3e5a6d04794795bc07d4de511c339405be377cb7e101736f1a25fe619f *7ab9d91b7523fd79e057bef9a5afbdc7fdfa981bf30036f7e9bde20cfc9bf097d2b6fc62f3866f *0f3cbb53df9256577b4f3fbc55377f41e5bf549fadabc82775b8fb85efe7ca0c74ccef6873743b *bb1baff7c369175d7f7573bf1d660e7f3b7bff2c7027f1b76fde49f8883bbcdd5fe06820923677 *89c8d1631cc7c32177ef18895945137fde75f8bdf1777baabd22ef3fe1e526d9cff57d62eff907 *a66422d33579d0cf35ddf2ba9859b1c889c084cd9e36a718d898094fa7316f6d81e4bacafe1313 *16387eff7befdc633ddfbcb9ab1f5e65d81c67c38f2a6658dbbb7d6fda2f70c4854faf0556ed75 *f5fcb4eee17074386e5cf9dec32f9d6ab832cfb47f12f6835cbbd1ba132faec18a99e408ec286d *acf8395c43139fe78b7994532b879e192316179e1a1b70c3534481cb85f1f719f852e45947cc8f *0e5cf88ee9b0bd7d2f79570ffcd0e984fed40a8153a7c5eb1b034977fd4951efb89df6c2173950 *9f7d45b832c626ac233a1c7fe2a7092efe5eae84c19f849f379725b916e7a9c9f7b9786ca7ee64 *fe8c3efb17b34a9b8a4f7b487baf4c67ef6af35b3667aa1f1892da5b05bf3816a61167717bfcc4 *64e0f8dafc526464847ff4e640997ca4271c7d8b8b8c87d7590e2335e63079ac815c1fe481d1ef *ca459ec0f786efb6847756ee8dba77cd609d1d8fe287c898654cb9e6ba625e33aa3847ccf89012 *ee2a3ca960fdf2f5dfc5def9d395f3aaf03aadc5c2a6c3a1eaf00a63f872c0d9b3a09819a6f0c1 *3be5c8951d7e7d27af244e962745ed2763b7ee7eafa4d5e1f873f8e292f170b8b236ebe7c541e1 *ca6892f78d12bd8d4a0f3ce5efbef8c00f72ee7ef1371e73f52df9834b5ef9cc919855f9810b13 *31c368c26cdfadcfddea46a764f3dd2cd79ef64a5d5d1f7fca39d9f893e517907cf6bc58a9faca *4be6e652b0e42981bdef0dfc9b986fcff81ce3376fe06d9e1907fd98b77204b6eac56a2fed4c34 *fccbdabc7df156bbc355a2d73f5765f39d7d7b8bb2d3468ff03ba513469853ab4c6226d19387b5 *84e37d6f975054bdcd54c5e448e447d6451e1a5786d6b475ee59aae3709d65fccbcd9532c9b0c8 *3de17577ef025ff60b7f09e3d727d312fbb3af0d0f8c9567376fe037951caf679f7eb72f217b8b *dcc3b7c70c2b9fad25e4693b7ff8476fbee924f2c7eded7b7b0bdee78f61ef7b237f6e78f488d9 *8c31c3da95c564318f8736e6a5c2d17ff87ed8f03d4c474dfc0b53c24cd2dec1b5f9a5bc736f81 *29b1f8bcd91c75631fc627c7e5009a7c81b71bd4bec16ffa2596f6179900c75481dbd01f7b066a *1ac56c04c8781c39a6eef3631340096e5a7b57cb438d7f5570aa0dd70f61179705164dbdde837d *121c4d9d7089100040600100082c0080ae6cafc1f2b602008064de95030090994b840000020b00 *40600100082c00005a0f2cef6a045e1c7fbe6c0a205e417f2ac71f1a038a3c971b37bf6ab0028a *0eac6118a671eafb17280d5bc04b69151e7cc6bd1a336a01c50516400175955048a3d8024a0f2c *1357405575751c5bc63410586ffa5e165c9f0502dc9f569f1c75b51d5bd69582c07abfb136ff1b *e0cebaba7bb419651674abac8f69300601add4d53cb346d3f320b0de19ecbea38f310868abaefe *65960fd30281f5f460b7f89806bf15a0adbafa3bc2c92ce8878f6900fa49abcf7b7535cf2c0bb3 *4060bd330202641f5b8aaa1999058d7bff12e17459d05803f45157f3ccb22e02da54dcc73400f4 *515740cb8a58e41ef89f00add795492c68d09b33583ec01de8beaefe3596b97c1058994694f1ef *324fc30ad0715d010dfa6313008da5559d75e5422134a5ac3ff66c2a0bb8585726ae8012143183 *358ee374b9d0391cd06b5d99c4028175f328a9b480ceea4a634153debf44381f4de697088d3240 *67750508acbca76c5b4bafacc702a2cfb55a1a2e7c640308acdbea0ad0552dc61320b05e3a43d5 *5b20adbaef2a935820b0720ca68ba5578615e8bbae8c001a0baae7834601750520b08016d34a5d *adf8c806a8d86b9708e7038741043aaf2b690508ac4ca766d61680b4b29efd68a4b4120b0416c0 *d9ba920e409bacc102d455c9acc4028105a0ae000416a0ae000416a0ae7ae32a21d4c72277e0b1 *b4faa82ba01366b08067ea6a54571798c4028105b0515700020b405d95c52416082c007505082c *007505908b771102d7436a93bacace9f26048105f452545eef010416a0a82a66120b0416d04854 *793907105880a86a99492c105880a802105840eb15b520aa0004169052542aaa31ae1282c0025e *482b2fbd00020b90569c63120b041620ad00041620ad289e492c1058c02d75e5c515406001d9d2 *eaa3ae00041620adc8ce554210584086baf2520a50813f3601549156ea8a1d63f093fa817798c1 *82d2d3eafb226a530054c40c16944f5d01082c20139705894c70570941600100082ce00da6af00 *04160000020b0a66fa8a932cc30281050020b0802799be021058e92f218b09edf52d000035caff *49ee5324cdfffee8e68dc0ce11e43021813ffc0c05c93c83f50da9711cc7f1df8acbe9c6796901 *0008ace873a8ffcf9fe62752dfff5e9c5a2d22cc891700d086872e1102d1878f03074060ad4c5d *65520a0010582f98ae124a31fab45a95e840e0d298eacc16fa0aacef316f853b426afd8a68e300 *08aca3b3a75945cd57bb4f9f7115796a25c568aeae8414404f23ffa786cb7326bda939ad3eea8a *27773aa32594e0c726006945432cc3028105d20a8016f963cf7007750520b0804cac6707406081 *ba02406081ba82033e741004160080c002d64c5f0120b0405d0120b0405dc109966181c0020010 *58c097e92b000416a82b0004160080c0824e98bea278d6b983c002750580c0027505007b7e6c02 *88eeaa2f750580c0025d45a7c66118c6d1ae0b020b8a4b2b2f4e00082cc8d355d20a008105d9d2 *4a570120b0204f57492b9a641916082c78a7aebcf6009099cfc1425d0180c002750527f89b3920 *b0405d81c6028105ea0a6a692c99058fb1c81d7505bd34d6ff87c0c7fb0a416041aeaefaf71a03 *324b6381c0025d059933cb5416082c488b2a5d05a1c6fab86208020ba2d3ca4b059cce2c8d0502 *0b36bb4a5a0120b0205b5ae92a0004165ccaa939690559f89bd020b0e831a4e41400020b2e7595 *90024060419eb4d255f02257094160d15457492b000416644b2b5d0580c0824b393527ada040ae *1282c0a2e87e925300082cb85457fa09007ef96313909c56ea0a9a3346cc4903c7cc60919256df *81d8a600804d66b048a8ab515d41bb4c6281c0e29dba02000416ea0a000416ea0a788fab8420b0 *5057005018ef22e430ad3eea0a004e318345b8aebc6110fae42a21082c6eac2b004060a1ae0040 *60515a5aa92be0f3f9b84a085758e4ceafba925600709d192cd41500082cd415f01057094160a1 *ae0040600100082c1a64fa0a0872951004160080c0e25da6af800826b140600100082cde62fa0a *000416006f7195100416114c5f0149e30620b050574036a3792c105800dc92591a0b04161b4c5f *01d71b4b6681c00220736399ca82b01f9ba02ba6af808c99f56dac7134aa24be03c0a6135800b0 *5108dfb6100ad3d63855653659c35c22eced04cb2008e40f0b970b4160a92b805b1a4b66c1c425 *4200f234d6ffe77296168119ac3e98be021ecc2c570c41600170436669ac1c27c645dcc9dd3fae *d55d45607572949abe0234564de3f6fc32eb7a4b0eff3bbcf1adc77c624769f482b2c002406315 *7e92bc71cb388ee3f86f0b6fdec88b2c72efe1c8347d05bcdc5896bd9f1ab7e79b6b3398a67fb0 *f897ebff98ee6dafbaa67f3cfd83f52df3db376f0ce4e0e1f7ee3dc2daf71981d5fc198f410d78 *b9b13e3e8cf4b6417ef34ae2dea69e97d3a269e6bfa0e9bff72e53ae0b6cfeed819f12beee1968 *3b8185ae02d87e71d75839b7e62a62f66e4c7a0589ba3dc74b55cb0456636965f002e052b42d5e *59c25718135eaa32de61c92c726fa6ae46750514fe0a6ef1750d27eadb5703c3df183f61d6cf2c *a6192c00a82a5467cbde17ebd99323e6fbedeb7724cc632bcb45deec77586eb0569193aedc1fed *ac360e50cda0d5e4789e3414ef6e8a5caf7a5e3d5fe412210040662e117678ce04c02d4372ae3b *9a7f7ed5951708d3572fef0d2e11aa2b8027472f433acd738910004060f13d01347d05d4cae735 *d03e6bb0aa082900406091fb6ccf2600808ab8445834d7018156cf1b4dcf23b050570080c002a0 *7426b110583ccef41500082cd41500f097771196d0520080c022675d99a902ba35fa4b68b4ca25 *42750500082c000081c59ae92b80cfe7e3c31a1058a82b004060010008ac1e98be02f8cd554204 *16000002ab28a6af004060a1ae001ee02a21020b0000815502d3570020b000e049ae1222b038c9 *f41500082cd4150020b000a89eab84082ce298be020081050080c002a01dae1222b00000105800 *002d07d6300c8b79e0f52db5b3c21de03c57091158076db18c27c70c0020b0b2d5d5e7f319c771 *fd250058318985c0daaaab6f4bfd3a56c671fafff31ba74368f3bb000004964efab5292cc00200 *81050085709590bafd64bcafefc170eaaadf7495d0bc170020b0b66b691e5bebffd9cfe988eb83 *00d0b3272e11cedf3f68a60a00685ea1d1b39eebaaa8cc4c5f01e41a509d9653a99f321fd6e288 *b2d41100a8887711e63edb327d050002cb2600a0543eac018185e92b004060010008aca299be02 *00041600e5b30c0b81d531d3570080c0020010580000020b0072b00c0b81d5250bb00000810500 *20b00000041600e4631916020b004060718515ee0080c00200105800601916020b00406091c802 *2c0040600100082c00f8cb322c0456075c1f040004160080c002805f5c25446035cdf541004060 *0100082c00d8e02a2102ab51ae0f0200020b004060010008ac7eb83e0800082c001a639d3b020b *00406011e0fa200020b0d4150020b000000456274c5f0194c43a770496ba02007af2631344a4d5 *475d0100022b635d492b00e01c9708d5150020b000e0f3b1ce1d81551fd3570080c002a04326b1 *1058f5307d0500082c00ba65120b81050020b03ae4fa200020b0000004160080c0ea87eb830080 *c002006f244460010008ac7eb83e0800082c0000810500b7b00c0b815524d70701008105007326 *b110580000020b000081050020b000e012cbb01058000002ab613ea3010010580000020b009e60 *1916020b00406035c9022c004060a92b004060010008ac4e98be02689175ee082c750500082c75 *050020b0000004160080c0aa8beb830080c00200105805337d05d0019fd480c002001058f5327d *0500082c000081050020b06c0200008195c8022c0040600100082c0028858fc242600100082c00 *007a0f2c2bdc010081050020b0000010580000020b00406095c10a77004060010054ecc72600a0 *51e3300ce3f8c4158cb44f8d7fe6b1f10a33580000022be5acc229020020b00000041600005d04 *96eb8300c0f35a7e17a1ba02a0de97b0ebef315cdfc9fcdd8ef32f6dfecbe996bdefdabcdbe99f *e57d0b67e0317cbfb4783aebc723b000405d8d81ffb91749e19808df6dcc83198661efbbb214cc *de9d473e86778b6ac11a2c00283ab636ebe16bfaeab73916371eb6cbe1c7772dbeeb956a89790c *7bcffa4566b000a0aca25af4c4221de22b277c9d2ead9612be6b73ca6dfda4beb79c9d9d7aecb3 *640516007467de6187c111533c572a6a7db7dfff39bfbab7beb89977d95672950a2c00e8d76265 *f7629552b8276256af9fedadc04f9cbeb49e8dcb52758beba46f15552f81e52d8400f49056cfff *f45cebd93fb399ade4c7107ef3e08b2c720780ca24244edaecd1e2bbd20a663ec394f02c4e3d86 *721acb254200a8c6e2a2d89429316bb016a512f9cebbf5774d8f24a690bedfbef9d816d934cd66 *ad17636d3e86bd0fdf2ae537f529e03a65ccfe74f641ba4408c0e7f3d05bccd25ed7233fb0eac9 *574f72718910004060c59e49687600aa94e55297e9ab7735b5066bb63bdaa5007834894abb4375 *25b032ef937ea900c0bbacc102a061c5fd893a04160000020b0040600100082c00004a0dacf907 *e7efdd020050a3cc1fd3b0f9e78ae6b7fb580e00a079f967b0c6ff2dfe7af6de9f660400105807 *7515b87df1d5458499dc0200041600001b6ef95339f36b828ff1079e01803603eb6c5a4d57095d *1f04009a71cb22f7bdf0b2c21d00e841ce19ac75454d6bdba7cfb83253050034afd0e859cf7585 *1fa4055800ecbd4438b7e7793f653eacc5c1e0da220050111fd3000020b0000004160080c0aa8c *15ee0080c0020010580050abd15bd11158a7b93e0800082c000081050080c0020010580000020b *000081050020b0000004160000020b004060fde263dc010081050020b0000010580000020b0040 *600100d06460790b210020b00000baf06313005c33d4f020cdf783c0021049773dc13e4b6b1c86 *611c5526020b4051292d10580072aada6dd2436c99c442600128aaa73797f2809c6a7d17a1cf68 *00568930ff3f24e9da380cf60d1e62060bf04a0f20b0002dc55dbf8ee6af0c588985c00214151a *0b041680a2a27826b11058805ae285dfb2f8008105082334d63926b1105880780210588096a289 *9dcd24167416583e651445051a0b4af6c72680525fdbd41512ff563ed89d1bb944085ed2001058 *a09ce0d1fdb6e10b85566221b0404881c6824a588305195f842c9c82ea5889c52dcc60c1f5ae82 *1ef673935820b04054c12dbbbdcc028105120aee3a345a2a2d4bdd1158a0a2a0a0c3479480c002 *4505771d534a0b0416ca09505abfb84a88c04221014a0b0416da08e87564a828b34c6221b09053 *4065238670416081a2026e1949641602abd86374f081c2720aa877842979007795908e030b5105 *0085f3c79ea595ba029cd1416666b00c7000cf0f412ec3d13833581d8e6bea0a709ab7671c0683 *241998c1329601bc352e99c7426021a700008125a7008a1fbe0a9cc4f2610d64600d56ed6393ba *029c224271cc601977000081a5a2005a1b065d8fa3352e11be38a0b8c00750e6a9a60f6be02a33 *589d0f220080c0d25500cd8e932e14d20e9708d515006bae1222b08a4e2bc72780d3510416460a *00232708ac220708630480c6426021ad00f8c5322c0496b32e00c32908ace6c602c30180c60281 *651400e080ab84082c75056080058155ff91efe007d058507f600d43217f4bc1310f00b4125865 *a495ba02e8e784d6322c52f863cfe51fdb0080c0d25500641e90475b018125ad0080ae5983a5ae *000cce20b01cc0003cca3a779a0eac9b3fa3c1c103e01c18fa0b2cc72d005085ce17b9eb2a80ba *066d6f27a40e7f3a3e4ad51500912cc34260492b8096c77010588e4c004060a92b000ce6d04b60 *5dfe8c06072480c60281e55004a020d6b923b07ea595e301c09933082c871f0020b0d41500c0a4 *b14f72175500fdf0c1ee94cbdf220400105800f0970b17082c871900750ffe3ea981ee02cb1e0f *0008ac9c69a5ae007ae6550081050020b000a07826b110588e28004060a92b00801e024b5d01f0 *fceb824f6aa0f1c00200e7de082c00d058082cc70f00403f81050020b000e021ae7220b01c3900 *80c07acfe8b70580537104160080c002004060010008ac8b5c5607c0eb05020b004060391d0180 *7dfede330507d6300c8b1d747d0b00382da7463f8fe5d4dfec1f47c70900d0b62766b0be75f54d *2b73540080c0cae35b578be9ab71fc77197b18860b935b0000fd05160080c00280065897c23b7e *defdf1d35542d70701b8adb1bcc4f0b48766b0be1565853b0020b0f298bf7fd04c15008f737acf *1bfb5c81d163ae0b8092992fa0cac05af756e7bbb22d600bd802b6802d0015f12e420000810500 *20b0000004160000e97c740200406666b0000004160080c00200105800803f2b42ba9f9277e8cd *d5f7e1afb6773caf9f66c35b60fd41d5874fb6b1adb1d802873b434b5b60fe64373742f303c2e6 *16e8794080aa15378335ff9bd0eb5387f0579b31cef4b305127edd8d6d8dcda710d819dadb02d3 *339d9e4b6f03c27a0b743b2040ed4a9cc1fa0e168b2126f2ab8da5c6e66b6aab5b60f3191d3ed9 *96b6c6e6b3389c9f68660ba43dc1c676000342f22019b865b3410373847b5bd26421d50716d358 *e06fbb6267c03eb00e9df55a8279304d91b4975f8b8d39ff677b9382363e6759e45eee59ac8399 *0e770619b1f7da6f40586fa5f52d7b2bf9a679be988db9f7cfd63f1402cc6001a5bc64769e11b6 *c0d9138ff916bb7bbb6dfe5008287106ebbbfb86af82f7b000abdb2d70eac9b6bd350e7786c6b6 *4060217f278743e04d820684e9f96eae855a6fa8f97f2cb652787305ee415a71625f2d7077d95c *ab1858c9d8ea6b6a875b20e6631af63ec8a0f98f69687b0becbdbfa19f01616f0bf43c209c1d24 *f76e39b531d78bdc03df0b9505160040d52c72070010580000020b004060010020b000008af11f *3643e61f52b02ee60000000049454e44ae426082 adddir ./examples/ch26 addfile ./examples/ch26/A.hs hunk ./examples/ch26/A.hs 1 +{-- snippet naive --} +import System.Environment +import Text.Printf + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean [1..d]) + +mean :: [Double] -> Double +mean xs = sum xs / fromIntegral (length xs) +{-- /snippet naive --} addfile ./examples/ch26/A.ps hunk ./examples/ch26/A.ps 1 +%!PS-Adobe-2.0 +%%Title: A 1e6 +RTS -i0.001 -hc -p -K100M +%%Creator: hp2ps (version 0.25) +%%CreationDate: Thu Aug 21 22:43 2008 +%%BoundingBox: 0 0 576 384 +%%EndComments +0.888889 0.888889 scale +/HE10 /Helvetica findfont 10 scalefont def +/HE12 /Helvetica findfont 12 scalefont def +newpath +0 0 moveto +0 432.000000 rlineto +648.000000 0 rlineto +0 -432.000000 rlineto +closepath +0.500000 setlinewidth +stroke +newpath +5.000000 407.000000 moveto +0 20.000000 rlineto +638.000000 0 rlineto +0 -20.000000 rlineto +closepath +0.500000 setlinewidth +stroke +HE12 setfont +11.000000 413.000000 moveto +(A 1e6 +RTS -i0.001 -hc -p -K100M) show +HE12 setfont +(1,751,755,873 bytes x seconds) +dup stringwidth pop +2 div +319.000000 +exch sub +413.000000 moveto +show +HE12 setfont +(Thu Aug 21 22:43 2008) +dup stringwidth pop +637.000000 +exch sub +413.000000 moveto +show +45.000000 20.000000 moveto +455.149594 0 rlineto +0.500000 setlinewidth +stroke +HE10 setfont +(seconds) +dup stringwidth pop +500.149594 +exch sub +5.000000 moveto +show +45.000000 20.000000 moveto +0 -4 rlineto +stroke +HE10 setfont +(0.0) +dup stringwidth pop +2 div +45.000000 exch sub +5.000000 moveto +show +119.322272 20.000000 moveto +0 -4 rlineto +stroke +HE10 setfont +(5.0) +dup stringwidth pop +2 div +119.322272 exch sub +5.000000 moveto +show +193.644544 20.000000 moveto +0 -4 rlineto +stroke +HE10 setfont +(10.0) +dup stringwidth pop +2 div +193.644544 exch sub +5.000000 moveto +show +267.966816 20.000000 moveto +0 -4 rlineto +stroke +HE10 setfont +(15.0) +dup stringwidth pop +2 div +267.966816 exch sub +5.000000 moveto +show +342.289088 20.000000 moveto +0 -4 rlineto +stroke +HE10 setfont +(20.0) +dup stringwidth pop +2 div +342.289088 exch sub +5.000000 moveto +show +416.611360 20.000000 moveto +0 -4 rlineto +stroke +HE10 setfont +(25.0) +dup stringwidth pop +2 div +416.611360 exch sub +5.000000 moveto +show +45.000000 20.000000 moveto +0 382.000000 rlineto +0.500000 setlinewidth +stroke +gsave +HE10 setfont +(bytes) +dup stringwidth pop +402.000000 +exch sub +40.000000 exch +translate +90 rotate +0 0 moveto +show +grestore +45.000000 20.000000 moveto +-4 0 rlineto +stroke +HE10 setfont +(0M) +dup stringwidth +2 div +20.000000 exch sub +exch +40.000000 exch sub +exch +moveto +show +45.000000 116.240222 moveto +-4 0 rlineto +stroke +HE10 setfont +(20M) +dup stringwidth +2 div +116.240222 exch sub +exch +40.000000 exch sub +exch +moveto +show +45.000000 212.480444 moveto +-4 0 rlineto +stroke +HE10 setfont +(40M) +dup stringwidth +2 div +212.480444 exch sub +exch +40.000000 exch sub +exch +moveto +show +45.000000 308.720666 moveto +-4 0 rlineto +stroke +HE10 setfont +(60M) +dup stringwidth +2 div +308.720666 exch sub +exch +40.000000 exch sub +exch +moveto +show +505.149594 140.333333 moveto +0 14 rlineto +14 0 rlineto +0 -14 rlineto +closepath +gsave +0.000000 0.000000 0.000000 setrgbcolor +fill +grestore +stroke +HE10 setfont +524.149594 142.333333 moveto +((160)CAF:sum) show +505.149594 267.666667 moveto +0 14 rlineto +14 0 rlineto +0 -14 rlineto +closepath +gsave +0.000000 0.000000 1.000000 setrgbcolor +fill +grestore +stroke +HE10 setfont +524.149594 269.666667 moveto +((129)GHC.Float.CAF) show +45.000000 20.000000 moveto +45.000000 20.000000 lineto +45.000000 20.000000 lineto +45.000000 20.000000 lineto +45.000000 20.000000 lineto +45.148645 20.000000 lineto +45.148645 20.000000 lineto +45.891867 20.000000 lineto +46.189156 20.000000 lineto +46.486445 20.000000 lineto +46.932379 20.000000 lineto +47.378313 20.000000 lineto +47.675602 20.000000 lineto +48.121535 20.000000 lineto +48.567469 20.000000 lineto +49.310692 20.000000 lineto +50.053914 20.000000 lineto +50.945782 20.000000 lineto +51.837649 20.000000 lineto +52.878161 20.000000 lineto +54.067317 20.000000 lineto +55.107829 20.000000 lineto +56.148341 20.000000 lineto +57.486142 20.000000 lineto +58.526654 20.000000 lineto +59.715810 20.000000 lineto +60.904966 20.000000 lineto +62.242767 20.000000 lineto +63.729213 20.000000 lineto +65.067013 20.000000 lineto +66.553459 20.000000 lineto +68.039904 20.000000 lineto +69.674994 20.000000 lineto +71.458729 20.000000 lineto +73.539752 20.000000 lineto +75.472132 20.000000 lineto +77.850444 20.000000 lineto +80.526046 20.000000 lineto +83.201648 20.000000 lineto +86.323183 20.000000 lineto +90.931164 20.000000 lineto +94.498633 20.000000 lineto +99.552548 20.000000 lineto +103.417306 20.000000 lineto +109.809021 20.000000 lineto +114.119713 20.000000 lineto +120.362784 20.000000 lineto +124.970765 20.000000 lineto +131.659769 20.000000 lineto +136.862328 20.000000 lineto +143.997266 20.000000 lineto +149.497114 20.000000 lineto +157.821209 20.000000 lineto +163.766991 20.000000 lineto +172.685663 20.000000 lineto +178.780090 20.000000 lineto +188.144696 20.000000 lineto +194.685056 20.000000 lineto +204.644240 20.000000 lineto +211.779178 20.000000 lineto +222.184296 20.000000 lineto +229.467879 20.000000 lineto +238.981130 20.000000 lineto +245.670134 20.000000 lineto +255.629319 20.000000 lineto +262.021034 20.000000 lineto +272.426152 20.000000 lineto +278.817868 20.000000 lineto +289.817564 20.000000 lineto +297.398436 20.000000 lineto +308.992710 20.000000 lineto +317.019515 20.000000 lineto +331.735325 20.000000 lineto +341.248576 20.000000 lineto +355.221163 20.000000 lineto +363.099324 20.000000 lineto +376.328688 20.000000 lineto +384.801427 20.000000 lineto +399.071304 20.000000 lineto +405.908953 20.000000 lineto +411.260156 20.000000 lineto +417.057294 20.000000 lineto +423.746298 20.000000 lineto +430.583947 20.000000 lineto +436.083795 20.000000 lineto +442.624155 20.000000 lineto +447.826714 20.000000 lineto +452.880629 20.000000 lineto +458.380477 20.000000 lineto +463.285747 20.000000 lineto +468.042372 20.000000 lineto +472.947642 20.000000 lineto +477.704267 20.000000 lineto +482.906827 20.000000 lineto +487.663452 20.000000 lineto +492.271433 20.000000 lineto +496.730769 20.000000 lineto +500.149594 20.000000 lineto +500.149594 20.000000 lineto +500.149594 20.000000 lineto +500.149594 20.000000 lineto +500.149594 20.000000 lineto +496.730769 22.508174 lineto +492.271433 23.769614 lineto +487.663452 30.076813 lineto +482.906827 32.599693 lineto +477.704267 38.906892 lineto +472.947642 40.168332 lineto +468.042372 42.691212 lineto +463.285747 43.952651 lineto +458.380477 45.214091 lineto +452.880629 50.259851 lineto +447.826714 52.782730 lineto +442.624155 55.305610 lineto +436.083795 59.089929 lineto +430.583947 61.612809 lineto +423.746298 65.397129 lineto +417.057294 71.704328 lineto +411.260156 72.965768 lineto +405.908953 73.438808 lineto +399.071304 75.961687 lineto +384.801427 85.629441 lineto +376.328688 90.675200 lineto +363.099324 96.982400 lineto +355.221163 144.364425 lineto +341.248576 178.423301 lineto +331.735325 195.452739 lineto +317.019515 208.224817 lineto +308.992710 210.999692 lineto +297.398436 204.758129 lineto +289.817564 200.701218 lineto +278.817868 197.268330 lineto +272.426152 196.956319 lineto +262.021034 195.708083 lineto +255.629319 194.459655 lineto +245.670134 193.523430 lineto +238.981130 191.026959 lineto +229.467879 189.154509 lineto +222.184296 187.594070 lineto +211.779178 183.849171 lineto +204.644240 180.416282 lineto +194.685056 175.818116 lineto +188.144696 173.321453 lineto +178.780090 171.761206 lineto +172.685663 168.952532 lineto +163.766991 166.767878 lineto +157.821209 163.022979 lineto +149.497114 158.341855 lineto +143.997266 153.660730 lineto +136.862328 152.724505 lineto +131.659769 150.852055 lineto +124.970765 149.915831 lineto +120.362784 148.667595 lineto +114.119713 147.107156 lineto +109.809021 142.114021 lineto +103.417306 138.369121 lineto +99.552548 136.184661 lineto +94.498633 133.063783 lineto +90.931164 127.758637 lineto +86.323183 121.517073 lineto +83.201648 119.020410 lineto +80.526046 117.772174 lineto +77.850444 114.963499 lineto +75.472132 112.779039 lineto +73.539752 110.282375 lineto +71.458729 106.849486 lineto +69.674994 102.480565 lineto +68.039904 101.232137 lineto +66.553459 97.799441 lineto +65.067013 95.302777 lineto +63.729213 92.806113 lineto +62.242767 91.869888 lineto +60.904966 88.437192 lineto +59.715810 86.876753 lineto +58.526654 85.316314 lineto +57.486142 83.756067 lineto +56.148341 80.323179 lineto +55.107829 78.616455 lineto +54.067317 78.304444 lineto +52.878161 72.999105 lineto +51.837649 67.381756 lineto +50.945782 66.133520 lineto +50.053914 60.204160 lineto +49.310692 56.459261 lineto +48.567469 46.160787 lineto +48.121535 45.536573 lineto +47.675602 44.912359 lineto +47.378313 42.415888 lineto +46.932379 39.919224 lineto +46.486445 37.110549 lineto +46.189156 36.174324 lineto +45.891867 30.868986 lineto +45.148645 21.818940 lineto +45.148645 21.194726 lineto +45.000000 20.882715 lineto +45.000000 20.570512 lineto +45.000000 20.258501 lineto +45.000000 20.000000 lineto +closepath +gsave +0.000000 0.000000 0.000000 setrgbcolor +fill +grestore +stroke +45.000000 20.000000 moveto +45.000000 20.000000 lineto +45.000000 20.258501 lineto +45.000000 20.570512 lineto +45.000000 20.882715 lineto +45.148645 21.194726 lineto +45.148645 21.818940 lineto +45.891867 30.868986 lineto +46.189156 36.174324 lineto +46.486445 37.110549 lineto +46.932379 39.919224 lineto +47.378313 42.415888 lineto +47.675602 44.912359 lineto +48.121535 45.536573 lineto +48.567469 46.160787 lineto +49.310692 56.459261 lineto +50.053914 60.204160 lineto +50.945782 66.133520 lineto +51.837649 67.381756 lineto +52.878161 72.999105 lineto +54.067317 78.304444 lineto +55.107829 78.616455 lineto +56.148341 80.323179 lineto +57.486142 83.756067 lineto +58.526654 85.316314 lineto +59.715810 86.876753 lineto +60.904966 88.437192 lineto +62.242767 91.869888 lineto +63.729213 92.806113 lineto +65.067013 95.302777 lineto +66.553459 97.799441 lineto +68.039904 101.232137 lineto +69.674994 102.480565 lineto +71.458729 106.849486 lineto +73.539752 110.282375 lineto +75.472132 112.779039 lineto +77.850444 114.963499 lineto +80.526046 117.772174 lineto +83.201648 119.020410 lineto +86.323183 121.517073 lineto +90.931164 127.758637 lineto +94.498633 133.063783 lineto +99.552548 136.184661 lineto +103.417306 138.369121 lineto +109.809021 142.114021 lineto +114.119713 147.107156 lineto +120.362784 148.667595 lineto +124.970765 149.915831 lineto +131.659769 150.852055 lineto +136.862328 152.724505 lineto +143.997266 153.660730 lineto +149.497114 158.341855 lineto +157.821209 163.022979 lineto +163.766991 166.767878 lineto +172.685663 168.952532 lineto +178.780090 171.761206 lineto +188.144696 173.321453 lineto +194.685056 175.818116 lineto +204.644240 180.416282 lineto +211.779178 183.849171 lineto +222.184296 187.594070 lineto +229.467879 189.154509 lineto +238.981130 191.026959 lineto +245.670134 193.523430 lineto +255.629319 194.459655 lineto +262.021034 195.708083 lineto +272.426152 196.956319 lineto +278.817868 197.268330 lineto +289.817564 200.701218 lineto +297.398436 204.758129 lineto +308.992710 210.999692 lineto +317.019515 208.224817 lineto +331.735325 195.452739 lineto +341.248576 178.423301 lineto +355.221163 144.364425 lineto +363.099324 96.982400 lineto +376.328688 90.675200 lineto +384.801427 85.629441 lineto +399.071304 75.961687 lineto +405.908953 73.438808 lineto +411.260156 72.965768 lineto +417.057294 71.704328 lineto +423.746298 65.397129 lineto +430.583947 61.612809 lineto +436.083795 59.089929 lineto +442.624155 55.305610 lineto +447.826714 52.782730 lineto +452.880629 50.259851 lineto +458.380477 45.214091 lineto +463.285747 43.952651 lineto +468.042372 42.691212 lineto +472.947642 40.168332 lineto +477.704267 38.906892 lineto +482.906827 32.599693 lineto +487.663452 30.076813 lineto +492.271433 23.769614 lineto +496.730769 22.508174 lineto +500.149594 20.000000 lineto +500.149594 20.000000 lineto +500.149594 20.000000 lineto +500.149594 20.000000 lineto +500.149594 20.000000 lineto +496.730769 214.988541 lineto +492.271433 216.249981 lineto +487.663452 222.557180 lineto +482.906827 225.080060 lineto +477.704267 231.387259 lineto +472.947642 232.648699 lineto +468.042372 235.171579 lineto +463.285747 236.433019 lineto +458.380477 237.694458 lineto +452.880629 242.740218 lineto +447.826714 245.263097 lineto +442.624155 247.785977 lineto +436.083795 251.570297 lineto +430.583947 254.093176 lineto +423.746298 257.877496 lineto +417.057294 264.184695 lineto +411.260156 265.446135 lineto +405.908953 265.919175 lineto +399.071304 268.442054 lineto +384.801427 278.109808 lineto +376.328688 283.155568 lineto +363.099324 289.462767 lineto +355.221163 336.844792 lineto +341.248576 370.903668 lineto +331.735325 387.933106 lineto +317.019515 400.705184 lineto +308.992710 402.000000 lineto +297.398436 389.516719 lineto +289.817564 381.403053 lineto +278.817868 374.537121 lineto +272.426152 373.913254 lineto +262.021034 371.416551 lineto +255.629319 368.919772 lineto +245.670134 367.047322 lineto +238.981130 362.054302 lineto +229.467879 358.309403 lineto +222.184296 355.188756 lineto +211.779178 347.698957 lineto +204.644240 340.833026 lineto +194.685056 331.636849 lineto +188.144696 326.643367 lineto +178.780090 323.522797 lineto +172.685663 317.905448 lineto +163.766991 313.536219 lineto +157.821209 306.046420 lineto +149.497114 296.684171 lineto +143.997266 287.321922 lineto +136.862328 285.449472 lineto +131.659769 281.704573 lineto +124.970765 279.832123 lineto +120.362784 277.335806 lineto +114.119713 274.214774 lineto +109.809021 264.228657 lineto +103.417306 256.738858 lineto +99.552548 252.369706 lineto +94.498633 246.128028 lineto +90.931164 235.517659 lineto +86.323183 223.034763 lineto +83.201648 218.041281 lineto +80.526046 215.544964 lineto +77.850444 209.927614 lineto +75.472132 205.558462 lineto +73.539752 200.565366 lineto +71.458729 193.699434 lineto +69.674994 184.961515 lineto +68.039904 182.464736 lineto +66.553459 175.599266 lineto +65.067013 170.606169 lineto +63.729213 165.612688 lineto +62.242767 163.740238 lineto +60.904966 156.874769 lineto +59.715810 153.754122 lineto +58.526654 150.633090 lineto +57.486142 147.512520 lineto +56.148341 140.646973 lineto +55.107829 137.233371 lineto +54.067317 136.609504 lineto +52.878161 125.998673 lineto +51.837649 114.763974 lineto +50.945782 112.267657 lineto +50.053914 100.408706 lineto +49.310692 92.918906 lineto +48.567469 72.321959 lineto +48.121535 71.073762 lineto +47.675602 69.825180 lineto +47.378313 64.832160 lineto +46.932379 59.839063 lineto +46.486445 54.221714 lineto +46.189156 52.349264 lineto +45.891867 41.738433 lineto +45.148645 23.638265 lineto +45.148645 22.390068 lineto +45.000000 21.765816 lineto +45.000000 21.141486 lineto +45.000000 20.517618 lineto +45.000000 20.000000 lineto +closepath +gsave +0.000000 0.000000 1.000000 setrgbcolor +fill +grestore +stroke +showpage addfile ./examples/ch26/B.hs hunk ./examples/ch26/B.hs 1 +import System.Environment +import Text.Printf + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean [1..d]) + +{-- snippet fold --} +mean :: [Double] -> Double +mean xs = s / fromIntegral n + where + (n, s) = foldl k (0, 0) xs + k (n, s) x = (n+1, s+x) +{-- /snippet fold --} addfile ./examples/ch26/C.hs hunk ./examples/ch26/C.hs 1 +import System.Environment +import Text.Printf +import Data.List + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean [1..d]) + +{-- snippet fold --} +mean :: [Double] -> Double +mean xs = s / fromIntegral n + where + (n, s) = foldl' k (0, 0) xs + k (n, s) x = (n+1, s+x) +{-- /snippet fold --} addfile ./examples/ch26/D.hs hunk ./examples/ch26/D.hs 1 +import System.Environment +import Text.Printf +import Data.List + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean [1..d]) + +{-- snippet fold --} +mean :: [Double] -> Double +mean xs = s / fromIntegral n + where + (n, s) = foldl' k (0, 0) xs + k (n, s) x = n `seq` s `seq` (n+1, s+x) +{-- /snippet fold --} addfile ./examples/ch26/E.hs hunk ./examples/ch26/E.hs 1 +{-- snippet fold --} +import System.Environment +import Text.Printf +import Control.Parallel.Strategies + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean [1..d]) + +foldl'rnf :: NFData a => (a -> b -> a) -> a -> [b] -> a +foldl'rnf f z xs = lgo z xs + where + lgo z [] = z + lgo z (x:xs) = lgo z' xs + where + z' = f z x `using` rnf + +mean :: [Double] -> Double +mean xs = s / fromIntegral n + where + (n, s) = foldl'rnf k (0, 0) xs + k (n, s) x = (n+1, s+x) :: (Int, Double) +{-- /snippet fold --} addfile ./examples/ch26/F.hs hunk ./examples/ch26/F.hs 1 +{-- snippet pragma --} +{-# LANGUAGE BangPatterns #-} +{-- /snippet pragma --} + +import System.Environment +import Text.Printf +import Data.List + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean [1..d]) + +{-- snippet fold --} +mean :: [Double] -> Double +mean xs = s / fromIntegral n + where + (n, s) = foldl' k (0, 0) xs + k (!n, !s) x = (n+1, s+x) +{-- /snippet fold --} addfile ./examples/ch26/Foldl.hs hunk ./examples/ch26/Foldl.hs 1 +{-- snippet fold --} +foldl' :: (a -> b -> a) -> a -> [b] -> a +foldl' f z xs = lgo z xs + where lgo z [] = z + lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs +{-- /snippet fold --} addfile ./examples/ch26/Fragment.hs hunk ./examples/ch26/Fragment.hs 1 +{-- snippet fragment --} +mean :: [Double] -> Double +mean xs = sum xs / fromIntegral (length xs) +{-- /snippet fragment --} addfile ./examples/ch26/G.hs hunk ./examples/ch26/G.hs 1 + +import System.Environment +import Text.Printf +import Data.List + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean [1..d]) + +{-- snippet pair --} +data Pair a b = Pair !a !b +{-- /snippet pair --} + +{-- snippet fold --} +mean :: [Double] -> Double +mean xs = s / fromIntegral n + where + Pair n s = foldl' k (Pair 0 0) xs + k (Pair n s) x = Pair (n+1) (s+x) +{-- /snippet fold --} addfile ./examples/ch26/H.hs hunk ./examples/ch26/H.hs 1 + +import System.Environment +import Text.Printf +import Data.List + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean [1..d]) + +{-- snippet fold --} +data Pair = Pair !Int !Double + +mean :: [Double] -> Double +mean xs = s / fromIntegral n + where + Pair n s = foldl' k (Pair 0 0) xs + k (Pair n s) x = Pair (n+1) (s+x) +{-- /snippet fold --} addfile ./examples/ch26/I.hs hunk ./examples/ch26/I.hs 1 +{-- snippet fold --} +import System.Environment +import Text.Printf +import Data.Array.Vector + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean (enumFromToFracU 1 d)) + +data Pair = Pair !Int !Double + +mean :: UArr Double -> Double +mean xs = s / fromIntegral n + where + Pair n s = foldlU k (Pair 0 0) xs + k (Pair n s) x = Pair (n+1) (s+x) +{-- /snippet fold --} addfile ./examples/ch26/SCC.hs hunk ./examples/ch26/SCC.hs 1 +import System.Environment +import Text.Printf + +main = do + [d] <- map read `fmap` getArgs + printf "%f\n" (mean [1 .. d]) + +{-- snippet scc --} +mean :: [Double] -> Double +mean xs = {-# SCC "mean" #-} sum xs / fromIntegral (length xs) +{-- /snippet scc --} }