Hasty Impressions: NCover

This post is part of a continuing series chronicling my search for a .NET coverage tool.

Today I’m looking at my fourth candidate: NCover.

I tried NCover 3.4.18.6937.

The Cost

NCover Complete is $479 plus $179 for a 1-year subscription (which gives free version updates). I thought this was a little steep. NCover Classic is $199/$99. I looked at NCover Complete, because that’s the kind of trial version they give out. Also, the feature set for Classic was too similar to that offered by other tools that cost less. Check out the feature comparison, if you like.

Support

I haven’t had enough problems to really stress the support network, but I will say this – the NCover chaps are really keen on keeping in touch with people who have trial copies of the program. I’ve received 3 separate e-mails from my assigned NCover rep in the 2 weeks since I first installed my trial copy. I replied to one of these, asking for a clarification on the VS integration (see below), and got a speedy response.
It’s nice to see such a high level of customer support, but I do feel just a little bit smothered…

VS integration

The best advice from the NCover folks is to create an external tool to launch NCover. That’s an okay solution if you want to run all the unit tests in a project and profile them, but it lacks flexibility. Then to actually look at the report, you have to launch the NCover Explorer and load the report.

There’s additional advice at the end of the Running NCover from Visual Studio video – if you want a more integrated Visual Studio experience, you should obtain TestDriven.Net. That probably works well enough, but I’m not wild about paying an additional $189 per head (roughly) for a test runner that (in my opinion, and excepting the NCover integration of course) is a less robust solution than the one that comes bundled with ReSharper.

Oh. There’s one more feature that I found – once you are examining a coverage report, you can Edit in VS.NET, which opens the appropriate file in Visual Studio. This is somewhat convenient, but doesn’t warp you to the correct line, which is a bit of a letdown.

Command Line Execution

The command line offers many and varied options for configuring the coverage run. Here’s a sample invocation:

NCover.Console.exe //exclude-assemblies BookFinder.Tests //xml ..\..\coverage.nccover nunit-console.exe bin\debug\BookFinder.Tests.dll

Upon execution, NCover tells me this:

Adding the '/noshadow' argument to the NUnit command line to ensure NCover can gather coverage data.
To prevent this behavior, use the //literal argument.

I really like that it defaults to passing the recommended /noshadow to NUnit. The // switches are also a good touch – it makes providing arguments to the executable being covered a lot easier. These features make the command line invocation the best I’ve seen among coverage tools.

GUI Runner

NCover options

The GUI runner looks just like a GUI wrapper on top of the command line options – they appear to support the same level of configuration. After the tests have been run, the NCoverExplorer allows one to browse the results and to save a report as XML or HTML.

XML Report

Reports are generated either from the GUI runner or by using the NCover.Reporting executable, which has a plethora of options for choosing XML or HTML reports of various flavours.
XML reports contain all the information you might want to summarize for inclusion in build output, but they’re hard to understand. Witness:

<stats acp="95" afp="80" abp="95" acc="20" ccavg="1.5" ccmax="5" ex="0" ei="1" ubp="12" ul="40" um="10" usp="39" vbp="63" vl="89" vsp="105" mvc="18" vc="2" vm="22" svc="120">

If you stare at this long enough (and correlate with a matching HTML report), you figure out that this means that there are

  • 39 unvisited sequence points, and
  • 105 visited sequence points

along with various other stats, so using attribute extraction and Math, we could see that 105/144 or 72.9% of the sequence points are covered.

It’s odd that there are many more reports available for HTML than XML. Notably absent from the XML offering: “Summary”. What is it about summaries that make them unsuitable for rendering as XML when HTML is fine?

Reports of Auto-Deploy

My Support Guy explained that you can xcopy deploy NCover using the //reg flag, but I did not find any documentation on how to do this. Support Guy claims there is an “honour system” kind of licensing model that supports this, but the trial copy I had did not work this way. I eventually abandoned this line of investigation.

Mature Isolator Support

From Visual Studio, under the Typemock menu, configure Typemock Isolator to Link with NCover&nsbsp;3.0.
When using the TypeMockStart MSBuild task, use

<TypeMockStart Link="NCover3.0" ProfilerLaunchedFirst="true"/>

and it just works, assuming you have TypeMock Isolator installed or set to auto-deploy.

IIS

IIS coverage is available, simply by selecting it from the GUI runner options or from the command line using the //iis switch. Other Windows Services can be covered in the same manner. Note though, that these features are only available in the Complete flavour of NCover 3.0.

Sequence Point coverage

Supported, as well as branch point coverage and other metrics, including cyclomatic complexity. Nice options to have, although probably a little advanced for my team’s current needs and experience.

Conclusion

Pros:

  • sequence point and branch coverage
  • large feature set, including trends, cyclomatic complexity analysis, and much much more
  • commercial product with strong support
  • report merging
  • easy IIS profiling
  • supports Isolator

Cons:

  • costly
  • weak IDE integration
  • inconsistent (comparing XML to HTML) report offerings
  • confusing auto-deploy

I expected to be blown away by NCover—from all reports, it’s the Cadillac of .NET coverage tools. After demoing it, I figured I’d end up desperately trying to make a case to the Money Guy to shell out hundreds of dollars per developer (and build server), but this did not happen.
While NCover definitely has lots of features, it’s lacking some pretty important ones as well, notably IDE integration. Other features just weren’t as I expected – the cornucopia of report types is impressive, but overkill for a team just starting out, and many of the report types aren’t available in XML and/or are very minor variations on other report types.
Ultimately, I don’t see what NCover offers to justify its price tag, especially across a large team. If ever I felt a need to have one of the specialized report, I’d consider obtaining a single license for tactical use, but I can’t imagine any more than that.

Hasty Impressions: OpenCover

This post is part of a continuing series chronicling my search for a .NET coverage tool.

Today I’m looking at my third candidate: OpenCover.
OpenCover is developed by Shaun Wilde. He was a developer on (and is the only remaining maintainer of) PartCover. He’s used what he learned working on PartCover to develop OpenCover, but OpenCover is a new implementation, not a port.

I tried OpenCover 1.0.514. Since I downloaded a couple weeks ago there have been 3 more releases, with the 1.0.606 release promising a big performance improvement.

The Cost

Free! And you can get the source.

VS integration

None that I can find.

Command Line Execution

Covering an application from the command line is easy, and reminiscent of using PartCover the same way. I used this command to see what code my BookFinder unit tests exercised:

OpenCover.Console.exe -arch:64 -register target:nunit-console.exe -targetargs:bin\debug\BookFinder.Tests.dll -output:..\..\opencover.xml -filter:+[BookFinder.Core]*

Let’s look at that.

  • -arch:64 – I’m running on a 64-bit system. I didn’t get any results without this.
  • -register – I’m auto-deploying OpenCover. More on that later.
  • -target:nunit-console.exe – I like NUnit
  • -targetargs:bin\debug\BookFinder.Tests.dll – arguments to NUnit to tell it what assembly to test, and how.
  • -output:..\..\opencover.xml – where to put the coverage results. This file is not a report – it’s intended for machines to read, not humans.
  • -filter:+[BookFinder.Core]* – BookFinder.Core is the only assembly I was interested in – it holds the business logic.

GUI Runner

There isn’t one, but I have to wonder if there won’t be. Otherwise, why call the command line coverer OpenCover.Console.exe?

XML Report

OpenCover doesn’t generate a human-readable report. Instead, you can postprocess the coverage output. ReportGenerator is the recommended tool, and it works like a charm.

ReportGenerator.exe .\opencover.xml XmlReport Xml

generates an XML report in the Xml directory. The summary looks like this:

<?xml version="1.0" encoding="utf-8"?>
<CoverageReport scope="Summary">
  <Summary>
    <Generatedon>2011-08-05-2011-08-05</Generatedon>
    <Parser>OpenCoverParser</Parser>
    <Assemblies>1</Assemblies>
    <Files>5</Files>
    <Coverage>71.6%</Coverage>
    <Coveredlines>126</Coveredlines>
    <Coverablelines>176</Coverablelines>
    <Totallines>495</Totallines>
  </Summary>
  <Assemblies>
    <Assembly name="BookFinder.Core.DLL" coverage="71.6">
      <Class name="BookFinder.BookDepository" coverage="85.7" />
      <Class name="BookFinder.BookListViewModel" coverage="50" />
      <Class name="BookFinder.BoolProperty" coverage="50" />
      <Class name="BookFinder.BoundPropertyStrategy" coverage="0" />
      <Class name="BookFinder.ListProperty" coverage="75" />
      <Class name="BookFinder.Property" coverage="100" />
      <Class name="BookFinder.StringProperty" coverage="100" />
      <Class name="BookFinder.ViewModelBase" coverage="81" />
    </Assembly>
  </Assemblies>
</CoverageReport>

ReportGenerator also generates Html and LaTeX output, with a “summary” variant for each of the three output types.

The XML report would be most useful for inclusion in build result reports, but I found the HTML version easy to use to examine coverage results down to the method level.
HTML Coverage Summary HTML Coverage Detail
I appreciate the coverage count by each of the lines – not as fancy as dotCover’s “which tests cover this”, but it could be a helpful clue when you’re trying to decide what you need to do to improve your coverage.

Joining Coverage Runs

Perhaps your test are scattered in space or time and you want to get an overview of all the code that’s covered by them. OpenCover doesn’t really do anything special for you, but ReportGenerator has your back. Specify multiple input files on the command line, and the results will be aggregated and added to a comprehensive report:

ReportGenerator.exe output1.xml;output2.xml;output3.xml XmlReport Xml

DIY Auto-Deploy

There’s no built-in auto-deploy for OpenCover. However, I made my own auto-deployable package like so:

  1. install OpenCover
  2. copy the C:\Program Files (x86)\OpenCover directory somewhere – call this your package directory
  3. uninstall OpenCover – you won’t need it any more

Then I just made sure my coverage build step

  • knew where the OpenCover package directory was (for the build system at the Day Job, I added it to our “subscribes”)
  • used the -register flag mentioned above to register OpenCover before running the tests

That’s it. No muss, no fuss. I did a similar (but easier, since there’s no registration needed) trick with ReportGenerator, and all of a sudden I have a no-deploy system.

In less than an hour’s work, I could upgrade a project so the build servers and all the developers could run a coverage target, with no action on their part, other than pulling the updated source tree and building. (Which is pretty much what the build server does all day long anyhow…)

DIY (for now) Coverage with Isoloator

Isoloator and OpenCover don’t work together out of the box, but thanks to advice I got from Igal Tabachnik, Typemock employee, it was not hard to change this.

Isolator’s supported coverage tools are partly configurable. There is a typemockconfig.xml under the Isolator install directory – typically %ProgramFiles (x86)%\Typemock\Isoloator\6.0 (or %ProgramFiles%, I suppose). Mr. Tabachnik had me add

 
<Profiler Name="OpenCover" Clsid="{1542C21D-80C3-45E6-A56C-A9C1E4BEB7B8}" DirectLaunch="false">
  <EnvironmentList />
</Profiler>

to the ProfilerList element, and everything meshed. His StackOverflow answer provides full details and suggests that official support for OpenCover will be added to Isolator.

IIS

I can’t find any special IIS support. I’m not saying OpenCover can’t be used to cover an application running in IIS, only that I didn’t find any help for it. I may investigate this later.

Sequence Point coverage

OpenCover counts sequence points, not statements. Yay!

Conclusion

Pros:

  • free
  • open source
  • active project
  • XML/HTML/LaTeX reports (via ReportGenerator)
  • report merging (via ReportGenerator)
  • Isolator support is easy to add (and may be included in future Isolators)
  • auto-deploy package is easy to make

Cons:

  • no IDE integration
  • no help with IIS profiling

I really like OpenCover. It’s easy to use, relatively full-featured, and free. In a work environment, where there’s a tonne of developers who want the in-IDE profiling experience, it may not be the best bet, but I’d use it for my personal .NET projects in a flash.

Hasty Impressions: PartCover

This post is part of a continuing series chronicling my search for a .NET coverage tool.

Today I’m looking at my second candidate: PartCover.

Technical stuff

PartCover has a GUI runner as well as a command-line mode. It integrates with Isolator, but doesn’t offer any help for those wanting to profile IIS-hosted applications.
There are some XSL files provided that allow one to generate HTML reports, but probably the better way is to use ReportGenerator to make HTML or XML reports.
PartCover claims to be auto-deployable, but I did not try this.

Project Concerns

The hardest thing about working with PartCover is learning about PartCover – finding definitive information about the project’s state is quite difficult. Searching with Google finds the SourceForge project which contains a note to see latest news on the PartCover blog, which hasn’t been updated since 17 June 2009. Back at SourceForge, you can download a readme written by Shaun Wilde, which says that he’s the last active developer and has moved development to a GitHub project.

At last! A project with recent (26 June 2011) updates. Unfortunately, my trials did not end here. I tried a number of versions, each with their own quirks. Unfortunately, I did not keep as careful track of which version had which problem as I should, and can’t say which version (from either GitHub or SourceForge) had which problems, but I can describe the problems.

At first I thought things were working really well, but then noticed that I had abnormally high coverage levels on my projects – one legacy project that I knew had about 5% coverage was registering as over 20%!
I looked at one assembly’s summary and found 6 classes with 0% coverage and one with 80%, and the assembly was registering an 80%. It turns out that completely uncovered classes were not counting against the total.

I tried other versions, with either the same results, or failures to run altogether. Ultimately, I gave up.

A Successor

It turns out that PartCover has a successor of sorts – Shaun Wilde, the last surviving maintainer of PartCover, has started his own coverage tool – OpenCover. It already seems be a viable PartCover replacement, and is in active development, so I’ll be checking it out as a free, non-IDE-integrated coverage tool.

Conclusion

Pros:

  • free!
  • XML/HTML via ReportGenerator
  • report merging via ReportGenerator
  • Isolator support
  • auto-deployable (reported)
  • sequence point coverage

Cons:

  • no IDE integration
  • no special IIS support
  • forked implementations, each with their own warts
  • not quite abandoned, but not a lot of interest behind the project

Until I noticed the high coverage levels, I didn’t mind PartCover. I figured its lack of price and its Isolator support made it a viable candidate. Unfortunately, the high coverage reports and other problems soured me on the deal, as did the lack of maintenance. I’m going to look at OpenCover instead.

Hasty Impressions: dotCover 1.1

This post is part of a continuing series chronicling my search for a .NET coverage tool.

Today I’m looking at the first candidate: JetBrains dotCover.

I tried dotCover 1.1, integrated with ReSharper 5.1 running in VS2008.

The Cost

A lifetime license, with 1 year of free upgrades is $199 $149 – a special introductory price.

This isn’t usurious, but considering that ReSharper C# edition, a tool that changes the way I work every single day, is $249, it’s enough.

VS integration

cover with dotCover

This is where I expected dotCover to shine, and it didn’t disappoint – the integration with Visual Studio (and with ReSharper) was excellent. The first thing I noticed was an extra “Cover with dotCover” item in the ReSharper test menu (triggered from the yellow and green ball things). I clicked it, and it ran my tests, bringing up the familiar Unit Test results window.

Once the tests ran, there was pause while dotCover calculated the coverage info, and then the bottom pane filled in with coverage results: green/red bars by every method in the covered assemblies. Clicking on the methods warps to the source code, which is also highlighted – covered statements have a green background, and uncovered statements have red. In fact, every source file opened in the IDE has the highlighting.

dotCover BookFinder tests

Finding tests that cover code

The most interesting feature that dotCover has is the ability to identify which tests covered which lines of code. I’m not entirely sold on this, thinking it more of a gimmick than anything else. When I first heard about it, I thought “I don’t care which test covered which line, so long as the lines are covered. I’m here to see what isn’t covered.”. Yes, I think in italics sometimes.

Still, I gave it a go. Right-clicking on a line of code (once coverage has been run) brought up a tiny menu full of covered lines of code. I don’t know why, but it made me happy. I suppose one could use this from time to time to make sure a new test case is exercising what it’s supposed to, but normally I can tell that by how a new test fails, or by what I’ve typed just before the test starts working. Worst case, I could always debug through a single test – something made very easy by the ReSharper test runner.


There was one aspect of this feature that I could imagine someone using – the ability to run the tests that cover a line of code. All that’s needed is to hit the “play” button on the “Show Covering Tests” popup. If the full suite of tests takes a very long time to run, this could be useful. Still, it doesn’t do much for me personally – if my tests took that long to run, I’d try speed them up. If nothing else, I would probably just run the test fixture designed to test the class or method in question, instead of my entire bolus of tests.

So, running tests that cover some code is a cool feature, but it’s not that useful. I’d rather see something like the automatic test runs and really cool “what’s covered” information provided by Mighty-Moose.

Command Line Execution

Covering an application from the command line is pretty straightforward. I used this command to see what code my BookFinder unit tests exercised:

dotcover cover /TargetExecutable=nunit-console.exe /TargetArguments=.\BookFinder.Tests.dll /Output=dotCoverOutput /Filters=+:BookFinder.Core

BookFinder.Core is the only assembly I was interested in – it holds the business logic. “cover” takes multiple include and exclude filters, even using wildcards for assemblies, classes, and methods.

One quite cool feature is to use the help subcommand to generate an XML configuration file, which can be used to specify the parameters for the cover command:

dotCover help cover coverSettings.xml

will create a coverSettings.xml file that can be edited to specify the executable, arguments, and filters. Then use it like so:

dotCover cover coverSettings.xml

without having to specify the same batch of parameters all the time.

Joining Coverage Runs

Multiple coverage snapshots – perhaps from running tests on different assemblies, or just from performing different test runs on the same application – can be merged together into a comprehensive snapshot:

dotCover merge /Source snapshot1;snapshot2 /Output mergedsnapshot

Just include all the snapshots, separated by semicolons.

XML Report

After generating snapshots and optionally merging them, they can be turned into an XML report using the report command:

dotcover report /Source=.\dotCoverOutput /Output=coverageReport.xml

There are options to generate HTML and JSON as well.

Note that if there’s only one snapshot, the “merge” step is not needed. In fact, there’s even a separate analyse command that will cover and generate a report in one go.

No Auto-Deploy

There’s no auto-deploy for dotCover – it needs to be installed. And since it’s a plugin, Visual Studio is a requirement. This is a small inconvenience for developers and our build servers. Having to put VS on all our test machines is a bit of a bigger deal – definitely a strike against dotCover.

TypeMock Isolator support in the future

The dotCover 1.1 doesn’t integrate with Isolator 6. Apparently dotCover’s hooks are a little different than many other profiles (nCover, PartCover, …). I’ve been talking to representatives from both TypeMock and JetBrains, though, and they tell me that the problem is solved, and an upcoming release of Isolator will integrate with dotCover. Even better, a pre-release version that supports the latest dotCover EAP is available now.

IIS

dotCover covers IIS, but only by using the plugin – this means that the web server has to have Visual Studio and dotCover installed, and it’s a manual step to invoke the coverage. In the JetBrains developer community there’s a discussion about command-line IIS support, but no word from JetBrains staff on when this might come.

Statement-level coverage

As Kevin Jones notes, dotCover reports coverage of statements coverage, not sequence points. This means that a line like this:

return value > 10
      ? Colors.Red
      : Colors.White;

Will report as completely covered, even if it’s executed only once – in order to ensure an accurate coverage report for this idea, the ?: would have to be replaced by an if-else block.
This isn’t necessarily a major strike against the tool, but it’s worth knowing, as it will skew the results somewhat.

Conclusion

Pros:

  • awesome IDE integration
  • XML/HTML/JSON reports
  • report merging
  • IIS profiling

Cons:

  • moderate price
  • no auto-deploy
  • no Isolator support—yet

Overall, I like the tool. I’m a little disappointed by the lack of auto-deploy and the inability to run IIS coverage from the command line, but those problems can be worked around. I was very impressed with the in-IDE support as well as the automatically generated configuration files using the “help” subcommand.
Ordinarily, the I’d say the current lack of Isolator support is a deal-breaker, but I recently demoed the product to some colleagues, and they went bonkers for the IDE integration. I guess I’ll be writing JetBrains and TypeMock looking for the betas.

Can you cover me? Looking for a .NET coverage tool

Recently at the Day Job, my boss’s boss has been on a “code confidence” kick. We’ve always done various levels of automated and manual unit, integration, issue, system, and regression testing, but he’s looking to improve the process. Part of this push involves getting better at measuring which tests exercise what parts of the code. We want to know this for the usual reasons: we can identify gaps in our testing, or more likely find opportunities to cover some areas earlier in the testing cycle. It’d be nice to know that a particularly critical section of code has been adequately exercised by the per-build unit tests, without having to wait for nightly integration testing or wait even longer for a human to get their grubby mitts on it.

To that end, I’m looking for a .NET coverage tool to dazzle us with tales of test runs. Over the next little while, I’ll look at a few candidates, summarize my findings, and hopefully come up with a winner.

Considerations

Here are some factors that will influence me. Some of these may be negotiable, if a candidate really shines in other areas.

  • We’d like to see coverage information in our build reports, so the tool should run from the command line.
  • It’d be easier to put the coverage info our our build reports if the coverage reports were in XML.
  • I really prefer a product that has an auto-deploy, so it can be bundled with the source tree and new developers or build servers just work. You may remember the pains I went to to auto-deploy TypeMock Isolator.
  • While I’m on the subject, one of our products uses Isolator as its mocking framework, so the coverage tool should be able to link with TypeMock Isolator.
  • We have a web services layer, which will be exercised by unit tests, but if we could gather stats on the layer as it’s being exercised by the client-facing portion, that would be gravy. To that end, it should be possible to cover IIS.
  • When I used TestDriven.NET + NCover a few years ago, I enjoyed being able to quickly see what my tests covered. This isn’t a requirement of our current initiative, but IDE integration would be a bonus.
  • Price is a factor. Money’s available, but why spend if you don’t have to? Or at least, why not pay less for an equivalent product.

The Candidates

Googling has lead me to these candidates, which I’ll be examining in the next little while:

Update: I picked one.

Prime Time Programming, Part 2

Last time I presented a truly horrible prime number generator I was using for Project Euler problems. Then I presented a revamped generator that used trial division. By adding various refinements to the generator, we saw the time required to generate primes less than 107 shrink from hours to 123 seconds. Today I’ll describe a different approach.

Attempt 2: Sieve of Eratosthenes

The Sieve of Eratosthenes is another method for finding prime numbers.
The algorithm is basically this:

  1. make a big array of numbers, from 2 to the highest prime you’re hoping to find
  2. look for the next number that’s not crossed off
  3. this number is your next prime
  4. cross off every multiple of the number you just found
  5. so long as the prime you just found is less than the square root of your limit, go to step 2
  6. the uncrossed numbers are prime

Suppose we want primes less than or equal to 20. We start with this list:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The first uncrossed off number is 2. That’s our first prime. Cross off all the multiples of 2 (believe it or not, the 4 is crossed off):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The next uncrossed off number is 3. Cross off the multiples:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Next, we have 5. Cross off its multiples (actually, they’re already crossed off because they’re all also multiples of either 2 or 3):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

5 is greater than √20, so stop looping. All the uncrossed off numbers are prime:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

A “borrowed” implementation

The wikipedia article even provides a Python implementation, which I reproduce here in slightly altered form:

def eratosthenes_sieve(m):
    # Create a candidate list within which non-primes will be
    # marked as None; only candidates below sqrt(m) need be checked. 
    candidates = range(m+1)
    fin = int(m**0.5)
 
    # Loop over the candidates, marking out each multiple.
    for i in xrange(2, fin+1):
        if not candidates[i]:
            continue
 
        candidates[2*i::i] = [None] * (m//i - 1)
 
    # Filter out non-primes and return the list.
    return [i for i in candidates[2:] if i]

I ran this to find my standard list of primes less than 107, and was surprised at the results. The time to completion varied wildly on successive runs. Sometimes over 50 seconds, and sometimes as low as 13. I noticed that when the run times were high, the laptop’s hard drive was thrashing, and just afterward my other applications were unresponsive.

I reran the test and, with a little help from PerfMon, found out that the memory usage was off the chart. No, seriously. Right off the top. I had to rescale the graph to get everything to fit. the Private Bytes went way up over 200MB. On my 512 MB laptop with Firefox, emacs, and a few background processes, things slow to a crawl. With a smaller set of primes, or on more powerful iron, this implementation may work, but it’s not going to meet my needs.

Attempt 3: The Sieve, but slowly cross out the composites

If allocating a big array of numbers just to cross most of them out right away doesn’t work, how about we start by allocating nothing and just cross out numbers at the last moment?
The idea is pretty simple: start counting at 2, and keep a record of upcoming composite numbers that we’ve discovered by looking at multiples of primes so far. Essentially we maintain a rolling wave of the next multiples of 2, 3, 5, …:

  1. let composites = {}, an empty associative array, where each key is a composite number and its value is the prime that it’s a multiple of
  2. let n = 2
  3. if n is a known composite, remove it and insert the next multiple in the list
  4. otherwise, it’s prime. Yield it and insert a new composite, n2
  5. increment n
  6. go to step 3

Let’s see how it works

n composites
2 {} 2 isn’t in composites, so yield it. Then insert 22 = 4 and increment n.
3 {4:2} 3 isn’t in composites, so yield it. Then insert 32 = 9 and increment n.
4 {4:2, 9:3} 4 is in composites, with value 2. Remove it, insert 4 + 2 = 6 and increment n.
5 {6:2, 9:3} 5 isn’t in composites, so yield it. Then insert 52 = 25 and increment n.
6 {6:2, 9:3, 25:5} 6 is in composites, with value 2. Remove it, insert 6 + 2 = 8 and increment n.
7 {8:2, 9:3, 25:5} 7 isn’t in composites, so yield it. Then insert 72 = 49 and increment n.
8 {8:2, 9:3, 25:5, 49:7} 8 is in composites, with value 2. Remove it, insert 8 + 2 = 10 and increment n.
9 {9:3, 10:2, 25:5, 49:7} 9 is in composites, with value 3. Remove it, insert 9 + 3 = 12 and increment n.
10 {10:2, 12:3, 25:5, 49:7} 10 is in composites, with value 2. Remove it, and… wait.

12 is already in the list, because it’s a multiple of 3. We can’t insert it. We’ll have to amend the algorithm to account for collisions. If a multiple is already accounted for, keep moving until we find one that isn’t in the list.

In this case, add another 2 to 12 to get 14 and insert it. Then increment n.

n composites
11 {12:3, 14:2, 25:5, 49:7} 11 isn’t in composites, so yield it, insert 112 = 121, increment n, and continue…

Show me the code

Here’s an implementation of the naive algorithm presented above

def sieve():
    composites = {}
    n = 2
    while True:
        factor = composites.pop(n, None)
        if factor:
            q = n + factor
            while composites.has_key(q):
                q += factor
            composites[q] = factor
        else:
            # not there - prime
            composites[n*n] = n
            yield n
        n += 1

This implementation takes 26.8 seconds to generate all primes below 107, close to ¼ the time the best trial division algorithm took.

Why is this method so great?

  • Using the associative array values to remember which “stream” of multiples each composite comes from means that the array is no bigger than the number of primes we’ve seen so far
  • The primes can be yielded as soon they’re found instead of waiting until the end
  • Adding p2 when we find a new prime cuts down on collisions but still ensures that we’ll keep find all multiples of p, because 2p, 3p, …, (p-1)p will be weeded out as multiples of lower primes.
  • There’s very little wasted work – finding a new prime number takes O(1) operations – just checking that the number isn’t in the associative array and adding the square to the array. Many composites will take more work, but an amount proportional to the number of distinct prime factors the number has. For example, 12 has prime factors 2, 2, and 3. We tried to add 12 to the array twice, once as a multiple of 2 and once as a multiple of 3. Fortunately, the number of distinct factors is severely limited. For numbers less than 107, 9699690 has the most distinct prime factors: 2, 3, 5, 7, 11, 13, 17, 19. This sure beats the 446 divisions trial division took to find that 9999991 was prime.

The method already incorporates some of the advantages of the souped-up trial division methods from last time. We only worry about multiples of primes, so there’s no need to cut out the composite factors. And when checking to see if n is prime, we never consider prime factors larger than √n. Still, there are some optimizations to make.

That’s Odd

In the sample runthrough above, the algorithm checks 4, 6, 8, 10, … for primality, even though no even number larger than 2 are prime. Here’s an implementation that avoids that:

 def odd_sieve():
    composites = {}
    yield 2
    n = 3
    while True:
        factor = composites.pop(n, None)
        if factor:
            q = n + 2 * factor
            while composites.has_key(q):
                q += 2 * factor
            composites[q] = factor
        else:
            # not there - prime
            composites[n*n] = n
            yield n
        n += 2

This method generates primes less than 107 in 13.4 seconds. This is about half the time it took when we didn’t pre-filter the evens. In the trial division case, when we cut out the even numbers, we were saving almost no work – one division per even number, out of potentially dozens or hundreds of divisions being performed. This time, we cut out an associative array lookup and insertion, and most numbers are checked by using only a small number of these operations. Let’s see what else we can do.

What about 3?

If skipping the numbers that are divisible by 2 paid off, will skipping those divisible by 3 as well? Probably.

def sixish_sieve():
    composites = {}
    yield 2
    yield 3
    step = 2
    n = 5
    while True:
        factor = composites.pop(n, None)
        if factor:
            q = n + 2 * factor
            while q % 6 == 3 or composites.has_key(q):
                q += 2 * factor
            composites[q] = factor
        else:
            # not there - prime
            composites[n*n] = n
            yield n
        n += step
        step = 6 - step

Now the time to generate primes less than 107 is 11.9 seconds. Again, I think we’ve hit diminishing returns. We didn’t get the 1/3 reduction I’d hoped, probably due to the more complicated “next multiple” calculation.

YAGNI

Things are going pretty well. There’s only one thing that bothers me about the latest generator – we’re storing too many composites in the associative array. Every time we find a prime number, its square is inserted in the array. Even 99999912 is put in the array, even though we’ll never check to see if any number greater than 107 is prime. So, modifying the algorithm to omit storing composites that are too large, we get:

def sixish_sieve_max():
    composites = {}
    yield 2
    yield 3
    step = 2
    n = 5
    while True:
        factor = composites.pop(n, None)
        if factor:
            q = n + 2 * factor
            while q % 6 == 3 or composites.has_key(q):
                q += 2 * factor
            composites[q] = factor
        else:
            # not there - prime
            if n*n <= highest:
                composites[n*n] = n
            yield n
        n += step
        step = 6 - step

This generator takes 10.8 seconds to generate primes below 107 – modest improvement, and one I’d keep anyhow, since the code is barely more complicated than the previous version. However, the real boost, if there is any, is in the memory usage. When sixish_sieve generates primes below 107, the private bytes climb up to 52MB, but sixish_sieve_max stays below 25MB. The advantage continues as the problem set grows – when the upper limit is 2*107, sixish_sieve takes 100MB, but sixish_sieve_max remains at a cool 25MB – I guess that’s the difference between storing 1270607 composites and 607.

Conclusion

This was a fun and interesting exercise. Being able to look bad at your old code and say “Boy, that was horrible. I’m glad I’m smarter now,” makes me happy. And embarrassed. I enjoyed seeing how applying incremental changes and even rudimentary profiling yielded provably better results, right up until they showed that I probably needed to abandon my current path (trial division) and jump on a new one.

I’m sticking with sixish_sieve_max for now. It’s fast enough to meet my current needs, and will likely remain so until “CPU inflation” forces the Project Euler team to increase the size of their problem sets. Of course, maybe by then I’ll have a faster processor and I won’t care.

Prime Time Programming, Part 1

From time to time, I find myself caught up in the heady world of Project Euler. It’s almost like playing Professor Layton or some other puzzle-solving game – mathematical or programming brain teasers, served in bite-sized pieces.

If you look at the Project Euler problems for any length of time, you’ll notice common themes. One theme is prime numbers – many problems can’t be solved without generating varying quantities of primes. To that end, I’d written a prime generator to be shared between problem solutions. Over time, I added functionality and “optimized” the generator to improve the running time of my solutions. Everything was great, until I tried Problem 315, whose solution required a list of primes between 107 and 2×107. My solution worked, but it ran really slowly – something like 12 minutes. Now, I’m not doing myself any favours by writing in Python and running on a 7-year-old laptop, but that’s still too long.

My Original Generator

This is the slow-performing generator that I replaced when working on Problem 315. The squeamish reader may want to avert his eyes.

class PrimeGenerator:
    __primes_so_far = [5]
    __increment = 2

    def __init__(self):
        self.__next_index = -1


    def is_prime(self, n):
        if n == 2 or n == 3:
            return True
        elif n % 2 == 0 or n %3 == 0:
            return False
        elif n <= PrimeGenerator.__primes_so_far[-1]:
            # bisecting didn't really help
            return n in PrimeGenerator.__primes_so_far
        else:
            return self.__is_prime(n)

    def __is_prime(self, n):
        limit = math.sqrt(n)
        g = PrimeGenerator()
        g.next() # skip 2
        g.next() # skip 3
        p = g.next()
        while p <= limit:
            if  n % p == 0:
                return False
            p = g.next()
        return True
        
    def next(self):
        self.next = self.__next3
        return 2

    def __next3(self):
        self.next = self.__next5
        return 3

    def __next5(self):
        self.__next_index += 1
        if self.__next_index < len(PrimeGenerator.__primes_so_far):
            return PrimeGenerator.__primes_so_far[self.__next_index]
            
        candidate = PrimeGenerator.__primes_so_far[-1]

        while True:
            candidate += PrimeGenerator.__increment
            PrimeGenerator.__increment = 6 - PrimeGenerator.__increment
        
            if self.__is_prime(candidate):
                PrimeGenerator.__primes_so_far.append(candidate)
                return candidate

    def __iter__(self):
        return self

My eyes!

When I first went back to this code, I exclaimed, “What was I thinking?”. I can think of two things:

  1. The is_prime member was intended to help out for problems where I didn’t have to create too many primes, but just had to check a few number for primality. This doesn’t really belong here, and clutters the class. I’d be better off focusing on prime generation.
  2. I was optimizing at least partly for the case where I’d want to get lists of primes a couple times—hence the indexing into an already-generated list of primes. If the generator were fast enough, this wouldn’t be necessary.

Things I can’t understand, even today. I’ll have to blame them on then-ignorance, foolishness, and hasty modifications to the class:

  • Why the mucking about with __next3 and __next5? What did I have against yield?
  • Why is is_prime fussing with a whole new PrimeGenerator and skipping 2 and 3? Why not just go straight for the saved list of primes starting with 5?

In fact, just about the only defensible things (as we’ll see below) in the whole class are:

  • ending the modulus checks once the candidate divisor is greater than the square root of the candidate number, and
  • the bit where the next__increment is formed by subtracting the current one from 6 – I was exploiting the fact that, past 3, for any prime p, p ≡ 1 (mod 6) or p ≡ 5 (mod 6).

How slow was it?

The generator took 551.763 seconds to generate primes less than 107, as measured by the following:

def run(f):
    global highest
    start = datetime.datetime.now()
    count = 1
    for p in f:
        count += 1
        if p > highest: break
    end = datetime.datetime.now()
    elapsed = end-start
    return highest, count, elapsed.seconds + (elapsed.microseconds/1000000.0)

Where f is an instance of PrimeGenerator passed into the run method, and highest is a global that’s been set to 107.

Moving forward

Based on the extreme slowness and general horribleness of the code, I figured I’d be better off starting over. So, I chucked the generator and started afresh with the simplest generator I could write. I resolved to make incremental changes, ensuring that at each step, the code was:

  1. correct (otherwise, why bother)
  2. faster than the previous version
  3. simple enough for me to understand

Let’s see what happened.

Attempt 1: Trial Division

Trial division is one of the simplest methods for generating primes—you start counting at 2, and if no smaller positive integers (other than 1) divide the current number, it’s prime. The naive implementation is very simple.

def naive_trial():
    n = 2
    while True:
        may_be_prime = True
        for k in xrange(2, n):
            if n % k == 0:
                may_be_prime = False
                break
        if may_be_prime:
            yield n
        n += 1

This method takes 113.804 seconds to generate primes below 100000—I couldn’t wait for the full 107 – it would probably be over 3 hours.

Trial until root

Fortunately, there are some pretty obvious optimizations one can make to the algorithm. The first comes from the observation that if there is a number k, 1 < k < n, that divides n, then there is a number j that divides n with 1 < j ≤ √n, so we can stop our trial once we’ve hit that point.

def trial_until_root():
    n = 2
    while True:
        may_be_prime = True
        for k in xrange(2, int(n**0.5)+1):
            if n % k == 0:
                may_be_prime = False
                break
        if may_be_prime:
            yield n
        n += 1

This method takes 468 seconds to generate primes up to 107. A definite improvement (and already faster my original generator), but there’s still room for more.

Trial by primes

Here’s another observation about divisors of n: if there’s a number k that divides n, then there’s a prime number p ≤ k that divides n, since either k is prime or has prime factors. So if we keep a list of the primes found so far, we only need to check prime divisors that are less than √n.

def trial_by_primes():
    primes_so_far = []
    n = 2
    while True:
        may_be_prime = True
        for p in primes_so_far:
            if n % p == 0:
                may_be_prime = False
                break
            if p * p > n: # it's prime
                break
        if may_be_prime:
            primes_so_far.append(n)
            yield n
        n += 1

Now we’re down to 136 seconds to generate primes below 107. That was a worthwhile change, but we have to balance it against the fact that the generator now requires additional storage – the list of primes encountered so far. In this case, we’re storing over 660,000 prime numbers in a list. Even an older laptop can handle this burden, but it’s something to keep in mind.

That’s odd

And by “that”, I mean “all the prime numbers except for 2”. There’s no point checking the even numbers to see if they’re prime. Let’s see what happens when we skip them. The only tricky part (and it’s not that tricky) is to make sure we still return 2 as our first prime.

def odd_trial_by_primes():
    primes_so_far = []
    yield 2
    n = 3
    while True:
        may_be_prime = True
        for p in primes_so_far:
            if n % p == 0:
                may_be_prime = False
                break
            if p * p > n: # it's prime
                break
        if may_be_prime:
            primes_so_far.append(n)
            yield n
        n += 2

This method takes 127 seconds to generate primes less than 107. Not a huge improvement, but better than nothing, and it doesn’t really complicate the code that much. I’ll keep it. The reason we don’t get a huge improvement here is that checking the even numbers for primeness doesn’t take that much effort – they were eliminated as soon as we modded them by the first prime in primes_so_far. Still, it’s a little quicker to jump right over them than to perform the division.

What about 3?

If skipping the numbers that are divisible by 2 paid off, will skipping those divisible by 3? As I noted above, every prime p greater than 3 satisfies p ≡ 1 (mod 6) or p ≡ 5 (mod 6). Let’s use that. We’ll take advantage of these facts:

  • if p ≡ 1 (mod 6) , then p+4 ≡ 5 (mod 6)
  • if p ≡ 5 (mod 6) , then p+2 ≡ 1 (mod 6)

So we want to alternate our step between 2 and 4. Fortunately 6 – 4 = 2 and 6 – 2 = 4, so we can use 6 – step as our next step.

def sixish_trial_by_primes():
    primes_so_far = []
    yield 2
    yield 3
    step = 2
    n = 5
    while True:
        may_be_prime = True
        for p in primes_so_far:
            if n % p == 0:
                may_be_prime = False
                break
            if p * p > n: # it's prime
                break
        if may_be_prime:
            primes_so_far.append(n)
            yield n
        n += step
        step = 6 - step

Now the time drops to 123 seconds to generate primes less than 107. Clearly we’ve hit diminishing returns – we’re saving two modulus operations on numbers that are divisible by 3 (but not 2), at the cost of a more complicated “step” calculation. We could continue on in this vein, but the gains are not likely to be large, and the complexity increases rapidly. Consider the next step: we’d make sure we don’t test numbers divisible by 2, 3, or 5. That means (after 5) we only consider numbers whose remainders when divided by 30 are one of 1, 7, 11, 13, 17, 19, 23, or 29. The steps between numbers are 6, 4, 2, 4, 2, 4, 6, and 2. Who has the energy?

The problem with Trial Division

Trial division has a few things going for it:

  • it’s simple to understand
  • there are some obvious optimizations that can make its performance tolerable

Ultimately, though, its downfall is that it takes a lot of work to verify that a large number is prime. Consider the largest prime number below 107: 9999991. In order to verify that this is prime, we have to consider all prime factors less than √9999991. There are 446 of these. That’s 446 divisions, just to verify that one number is prime.

We’re unlikely to radically improve performance by continuing to tinker with trial division. It’s time to throw the whole thing away again and try a new approach. Next time we’ll do just that.

Categories