Hykilpikonna
213 lines
15 KiB
HTML
213 lines
15 KiB
HTML
<!DOCTYPE html>
|
||
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
|
||
<head>
|
||
<meta charset="utf-8" />
|
||
<meta name="generator" content="pandoc" />
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
|
||
<title>8.8 Testing Functions IV: Efficiency</title>
|
||
<style>
|
||
code{white-space: pre-wrap;}
|
||
span.smallcaps{font-variant: small-caps;}
|
||
span.underline{text-decoration: underline;}
|
||
div.column{display: inline-block; vertical-align: top; width: 50%;}
|
||
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
|
||
ul.task-list{list-style: none;}
|
||
pre > code.sourceCode { white-space: pre; position: relative; }
|
||
pre > code.sourceCode > span { display: inline-block; line-height: 1.25; }
|
||
pre > code.sourceCode > span:empty { height: 1.2em; }
|
||
code.sourceCode > span { color: inherit; text-decoration: inherit; }
|
||
div.sourceCode { margin: 1em 0; }
|
||
pre.sourceCode { margin: 0; }
|
||
@media screen {
|
||
div.sourceCode { overflow: auto; }
|
||
}
|
||
@media print {
|
||
pre > code.sourceCode { white-space: pre-wrap; }
|
||
pre > code.sourceCode > span { text-indent: -5em; padding-left: 5em; }
|
||
}
|
||
pre.numberSource code
|
||
{ counter-reset: source-line 0; }
|
||
pre.numberSource code > span
|
||
{ position: relative; left: -4em; counter-increment: source-line; }
|
||
pre.numberSource code > span > a:first-child::before
|
||
{ content: counter(source-line);
|
||
position: relative; left: -1em; text-align: right; vertical-align: baseline;
|
||
border: none; display: inline-block;
|
||
-webkit-touch-callout: none; -webkit-user-select: none;
|
||
-khtml-user-select: none; -moz-user-select: none;
|
||
-ms-user-select: none; user-select: none;
|
||
padding: 0 4px; width: 4em;
|
||
color: #aaaaaa;
|
||
}
|
||
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa; padding-left: 4px; }
|
||
div.sourceCode
|
||
{ }
|
||
@media screen {
|
||
pre > code.sourceCode > span > a:first-child::before { text-decoration: underline; }
|
||
}
|
||
code span.al { color: #ff0000; font-weight: bold; } /* Alert */
|
||
code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
|
||
code span.at { color: #7d9029; } /* Attribute */
|
||
code span.bn { color: #40a070; } /* BaseN */
|
||
code span.bu { } /* BuiltIn */
|
||
code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
|
||
code span.ch { color: #4070a0; } /* Char */
|
||
code span.cn { color: #880000; } /* Constant */
|
||
code span.co { color: #60a0b0; font-style: italic; } /* Comment */
|
||
code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
|
||
code span.do { color: #ba2121; font-style: italic; } /* Documentation */
|
||
code span.dt { color: #902000; } /* DataType */
|
||
code span.dv { color: #40a070; } /* DecVal */
|
||
code span.er { color: #ff0000; font-weight: bold; } /* Error */
|
||
code span.ex { } /* Extension */
|
||
code span.fl { color: #40a070; } /* Float */
|
||
code span.fu { color: #06287e; } /* Function */
|
||
code span.im { } /* Import */
|
||
code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
|
||
code span.kw { color: #007020; font-weight: bold; } /* Keyword */
|
||
code span.op { color: #666666; } /* Operator */
|
||
code span.ot { color: #007020; } /* Other */
|
||
code span.pp { color: #bc7a00; } /* Preprocessor */
|
||
code span.sc { color: #4070a0; } /* SpecialChar */
|
||
code span.ss { color: #bb6688; } /* SpecialString */
|
||
code span.st { color: #4070a0; } /* String */
|
||
code span.va { color: #19177c; } /* Variable */
|
||
code span.vs { color: #4070a0; } /* VerbatimString */
|
||
code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
|
||
</style>
|
||
<link rel="stylesheet" href="../tufte.css" />
|
||
<!--[if lt IE 9]>
|
||
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
|
||
<![endif]-->
|
||
</head>
|
||
<body>
|
||
<div style="display:none">
|
||
\(
|
||
\newcommand{\NOT}{\neg}
|
||
\newcommand{\AND}{\wedge}
|
||
\newcommand{\OR}{\vee}
|
||
\newcommand{\XOR}{\oplus}
|
||
\newcommand{\IMP}{\Rightarrow}
|
||
\newcommand{\IFF}{\Leftrightarrow}
|
||
\newcommand{\TRUE}{\text{True}\xspace}
|
||
\newcommand{\FALSE}{\text{False}\xspace}
|
||
\newcommand{\IN}{\,{\in}\,}
|
||
\newcommand{\NOTIN}{\,{\notin}\,}
|
||
\newcommand{\TO}{\rightarrow}
|
||
\newcommand{\DIV}{\mid}
|
||
\newcommand{\NDIV}{\nmid}
|
||
\newcommand{\MOD}[1]{\pmod{#1}}
|
||
\newcommand{\MODS}[1]{\ (\text{mod}\ #1)}
|
||
\newcommand{\N}{\mathbb N}
|
||
\newcommand{\Z}{\mathbb Z}
|
||
\newcommand{\Q}{\mathbb Q}
|
||
\newcommand{\R}{\mathbb R}
|
||
\newcommand{\C}{\mathbb C}
|
||
\newcommand{\cA}{\mathcal A}
|
||
\newcommand{\cB}{\mathcal B}
|
||
\newcommand{\cC}{\mathcal C}
|
||
\newcommand{\cD}{\mathcal D}
|
||
\newcommand{\cE}{\mathcal E}
|
||
\newcommand{\cF}{\mathcal F}
|
||
\newcommand{\cG}{\mathcal G}
|
||
\newcommand{\cH}{\mathcal H}
|
||
\newcommand{\cI}{\mathcal I}
|
||
\newcommand{\cJ}{\mathcal J}
|
||
\newcommand{\cL}{\mathcal L}
|
||
\newcommand{\cK}{\mathcal K}
|
||
\newcommand{\cN}{\mathcal N}
|
||
\newcommand{\cO}{\mathcal O}
|
||
\newcommand{\cP}{\mathcal P}
|
||
\newcommand{\cQ}{\mathcal Q}
|
||
\newcommand{\cS}{\mathcal S}
|
||
\newcommand{\cT}{\mathcal T}
|
||
\newcommand{\cV}{\mathcal V}
|
||
\newcommand{\cW}{\mathcal W}
|
||
\newcommand{\cZ}{\mathcal Z}
|
||
\newcommand{\emp}{\emptyset}
|
||
\newcommand{\bs}{\backslash}
|
||
\newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor}
|
||
\newcommand{\ceil}[1]{\left \lceil #1 \right \rceil}
|
||
\newcommand{\abs}[1]{\left | #1 \right |}
|
||
\newcommand{\xspace}{}
|
||
\newcommand{\proofheader}[1]{\underline{\textbf{#1}}}
|
||
\)
|
||
</div>
|
||
<header id="title-block-header">
|
||
<h1 class="title">8.8 Testing Functions IV: Efficiency</h1>
|
||
</header>
|
||
<section>
|
||
<p>We hope that the number of sections of these notes dedicated to testing demonstrates its importance in the process of software development. What is perhaps surprising is that testing is not limited to correctness. In fact, strict efficiency constraints are the norm in several domains. For example, a Playstation controller must send wireless signals at the touch of a button or the move of a joystick—if the function for doing so were correct, but took 10 seconds, players would not be happy. Similarly, a search on Google that sifts through terabytes of data must also be fast.<label for="sn-0" class="margin-toggle sidenote-number"></label><input type="checkbox" id="sn-0" class="margin-toggle"/><span class="sidenote"> Check it out: each search you do on Google reports how many results were found in how many fractions of a second.</span> In this section, we will discuss how to write tests for efficiency of functions.</p>
|
||
<!-- Even more surprising than performance constraints, the performance of the tests themselves are incredibly important in well-designed software projects.
|
||
The test suite itself can be quite large, and each time a developer fixes a bug (hopefully) or adds a new feature the tests must be re-run.
|
||
The faster the test suite runs, the better software can reach its internal (e.g., alpha, beta) and external release deadlines.
|
||
In this section, we will discuss how to setup tests for performance constraints for both functions and tests (which, coincidentally, are also functions). -->
|
||
<h2 id="an-efficiency-test">An efficiency test</h2>
|
||
<p>Earlier we saw how to use the <code>timeit</code> module to measure the time taken to execute a piece of Python code. Let’s see how we might setup a performance constraint using <code>timeit</code> and our implementation of <code>is_prime</code>:</p>
|
||
<div class="sourceCode" id="cb1"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb1-1"><a href="#cb1-1"></a><span class="im">from</span> math <span class="im">import</span> floor, sqrt</span>
|
||
<span id="cb1-2"><a href="#cb1-2"></a><span class="im">from</span> timeit <span class="im">import</span> timeit</span>
|
||
<span id="cb1-3"><a href="#cb1-3"></a></span>
|
||
<span id="cb1-4"><a href="#cb1-4"></a></span>
|
||
<span id="cb1-5"><a href="#cb1-5"></a><span class="kw">def</span> is_prime(p: <span class="bu">int</span>) <span class="op">-></span> <span class="bu">bool</span>:</span>
|
||
<span id="cb1-6"><a href="#cb1-6"></a> <span class="co">"""Return whether p is prime."""</span></span>
|
||
<span id="cb1-7"><a href="#cb1-7"></a> possible_divisors <span class="op">=</span> <span class="bu">range</span>(<span class="dv">2</span>, floor(sqrt(p)) <span class="op">+</span> <span class="dv">1</span>)</span>
|
||
<span id="cb1-8"><a href="#cb1-8"></a> <span class="cf">return</span> (</span>
|
||
<span id="cb1-9"><a href="#cb1-9"></a> p <span class="op">></span> <span class="dv">1</span> <span class="kw">and</span></span>
|
||
<span id="cb1-10"><a href="#cb1-10"></a> <span class="bu">all</span>(<span class="kw">not</span> p <span class="op">%</span> d <span class="op">==</span> <span class="dv">0</span> <span class="cf">for</span> d <span class="kw">in</span> possible_divisors)</span>
|
||
<span id="cb1-11"><a href="#cb1-11"></a> )</span>
|
||
<span id="cb1-12"><a href="#cb1-12"></a></span>
|
||
<span id="cb1-13"><a href="#cb1-13"></a></span>
|
||
<span id="cb1-14"><a href="#cb1-14"></a><span class="kw">def</span> test_is_prime_performance() <span class="op">-></span> <span class="va">None</span>:</span>
|
||
<span id="cb1-15"><a href="#cb1-15"></a> <span class="co">"""Test the efficiency of is_prime."""</span></span>
|
||
<span id="cb1-16"><a href="#cb1-16"></a> numbers_to_test <span class="op">=</span> <span class="bu">range</span>(<span class="dv">2</span>, <span class="dv">1000</span>)</span>
|
||
<span id="cb1-17"><a href="#cb1-17"></a> <span class="cf">for</span> number <span class="kw">in</span> numbers_to_test:</span>
|
||
<span id="cb1-18"><a href="#cb1-18"></a> time <span class="op">=</span> timeit(<span class="ss">f'is_prime(</span><span class="sc">{</span>number<span class="sc">}</span><span class="ss">)'</span>, number<span class="op">=</span><span class="dv">100</span>, <span class="bu">globals</span><span class="op">=</span><span class="bu">globals</span>())</span>
|
||
<span id="cb1-19"><a href="#cb1-19"></a> <span class="cf">assert</span> time <span class="op"><</span> <span class="fl">0.001</span>, <span class="st">'Failed performance constraint of 0.001s.'</span></span></code></pre></div>
|
||
<p>There are several issues here that we need to keep in mind. The performance constraint of 0.001 seconds is for the total runtime of 100 calls to <code>is_prime</code> for only one number in <code>numbers_to_test</code> (there will be as many assertions as there are elements in <code>numbers_to_test</code>). Where did the argument <code>number=100</code> come from? Should it be more or less? An important thing to remember is a computer system is not at all like a science experiment you would setup in a chemistry or biology lab. There are too many external factors (i.e., background processes being run) that can impact the results. To avoid this issue, several samples of an experiment (i.e., measurements of time) need to be taken. The field of statistics can help inform us on whether or not 100 samples is sufficient for this test.</p>
|
||
<p>Next, where did <code>0.001</code> seconds come from? The number is most certainly arbitrary in this example. Computer systems are very different from one another, in terms of both hardware and software. While the assertions may hold for all <code>numbers_to_test</code> on one computer, they may not hold on another. The <code>0.001</code> seconds may be tuned over time in the testing suite. Or it can help identify the minimum hardware requirements for running a piece of software.</p>
|
||
<p>While it is easy to write the Python code that checks for performance, coming up with the actual parameters (number of function calls, inputs to the function, total acceptable runtime) is quite challenging, and often domain-dependent. For example, in user interfaces, a great deal of research has gone into how fast actions should be; a so-called “instantaneous” action in a user interface should complete in <a href="https://www.nngroup.com/articles/response-times-3-important-limits/">0.1 seconds</a>. Other domains, such as embedded systems, have a series of functions that must meet hard deadlines in order for the computer system to function properly (e.g., in a spaceship).</p>
|
||
<p>But what about domains where there are no guidelines or standards? Runtime constraints that are tuned over time can still be useful in discovering changes in program efficiency due to bug fixes or new features. When a code change causes an efficiency test to fail, the programmers can decide whether to the efficiency constraint or explore alternative code changes. Without efficiency tests in place, the change in performance might not have been found until it impacted a real user of the software!</p>
|
||
<!-- ## Timing Out on Tests
|
||
|
||
The result of a test can be unpredictable.
|
||
So far, we have assumed that a test can either pass or fail.
|
||
But what if a test never ends?
|
||
For example, a specific set of inputs could cause the function being tested to enter an infinite loop.
|
||
In this scenario, the test does not know that the function is in an infinite loop, and so cannot raise an assertion error.
|
||
In a less extreme example, a recent change in the code has increased the complexity of the function from logarithmic to quadratic.
|
||
An large input that was tested earlier in seconds could now be taking minutes.
|
||
|
||
Both of the examples above motivate the need for a maximum time that each test should take.
|
||
When the maximum time is exceeded, the test is said to have *timed out*.
|
||
You may have seen this type of error before while browsing the internet.
|
||
Sometimes, a server is unable to process a request within a reasonable amount of time, and your browser displays an error such as "connection timed out".
|
||
Setting up timeouts for our tests is useful to ensure that all tests will complete.
|
||
|
||
We can add timeouts to our functions in pytest through the `timeout_decorator` Python module.
|
||
The module provides access to a decorator: `@timeout`.
|
||
We have seen decorators before when we introduced `@dataclass` before defining a new `class`.
|
||
In this scenario, we place the `@timeout` decorator before defining a new test function:
|
||
|
||
```python
|
||
import timeout_decorator
|
||
|
||
@timeout_decorator.timeout(1)
|
||
def test_is_prime_large_number() -> None:
|
||
assert is_prime(32443) is True
|
||
```
|
||
|
||
Much like with performance constraints, we must specify how long (in seconds) a test should take.
|
||
In this scenario, we timeout after `1` second.
|
||
The decision on how many seconds is, similarly, a tuning exercise.
|
||
To give you a very relevant example, your undergraduate programming classes choose timeouts based on a few parameters.
|
||
How generous do the professors want to be with inefficient implementations?
|
||
How much of a load will the test suite put on the servers?
|
||
How long can the professors wait before getting the grades back?
|
||
You can imagine that some submissions may timeout on several tests---if a 30 minute timeout is used, then a single submission could take several hours to test! -->
|
||
</section>
|
||
<footer>
|
||
<a href="https://www.teach.cs.toronto.edu/~csc110y/fall/notes/">CSC110 Course Notes Home</a>
|
||
</footer>
|
||
</body>
|
||
</html>
|