A faster (but incomplete) implementation of SCons on top of doit

19 07 2011

Motivation

doit is an automation tool. It is kind of build-tool but more generic…

My motivation was to demonstrate how to create a specialized interface for defining tasks. doit can be used for many different purposes, so its default interface can be quite verbose if compared to tools created to solve one specific problem.

Instead of creating an interface myself I decided to use an existing interface. I picked SCons. So the goal was to be able to build C/C++ project using an existing SConstruct file without any modification. And of course it should be as good as SCons on dependency tracking, ensuring always a correct result.

A secondary goal was to make it fast.

Note that this implementation is very far from complete. I only implemented the bare minimum to get some benchmarks running.

Implementation

I wont go into the gory details… Just a few notes. You can check the code here.

In docons.py there is an implementation of the API available in SConstrcut files. When a “Builder Method” (like Program or Object) is executed a reference to the builder is saved in a global variable. These “Builder Methods” are actually implemented as class that can generate dictionaries representing doit tasks.

In doit the configuration file that define your tasks is called dodo.py. In this case the end user wont edit this file directly. dodo.py will import the SCons API namespace from docons, than it will execfile the SConstruct file and collect the tasks from the “Builder Methods”.

Creating tasks for compile/link is straightforward. The hard part is automatically finding out the dependencies in the source code and mapping it into account on your tasks. To find out the dependencies (the #include for C code) in the source I am using the same C preprocessor as used by SCons.

SCons uses the concept of a “Scanner” function associated with a Builder. In doit the implicit dependencies are “calculated” in a separate task. The dependencies are than put into the build (compile/link) tasks through calc_dep (calculated dependencies).

A faster implementation

It seems SCons creates the whole dependency graph before starting to execute the tasks/builders. Because of this it doesn’t scale so well when the number of files increase.

doit creates the dependency graph dynamically during task execution. But even on a no-op build it will end-up with a complete graph built because it will check all tasks dependencies.

tup is a build-tool that saves the dependency graph in a SQLite database. I decided to give it a try to its approach.  So I created “dup” – sorry for the name :) . It will still read the build configuration from SConstrcut files but it will keep a SQLite database mapping the targets to all of its dependencies. This enables a much faster no-op and incremental builds. The  underlying graph dependency of a target will only be built if required.

Benchmarks

I did some very basic benchmarks from SCons and my two SCons implementations. The benchmarks were created using the gen-bench from wonderbuild benchmarks.

I used gen-bench script was run with the arguments “50 100 15 5″.  This generates 10000 tiny interdependent C++ source and header files, to be built into 50 static libs.

All benchmarks were run on a intel i3 550 quad-core (3.20GHz), running Ubuntu 10.10, python2.6.6, doit 0.13.0, SCons 2.0.0. All benchmarks were run using a single process.

The graph doesn’t include full build time. It was SCons=266 seconds, docons=249 seconds, dup=253 seconds.

  • no-op 1 lib -> no-operation build when all files are up-to-date and only one of the 50 libraries were selected to be built (scons build-scons/lib_0/lib0.a)
  • no-op -> no-operation build
  • partial build – cpp file -> only the file lib_1/class_0.cpp was modified. rebuilt 1 object file and 1 lib.
  • partial build – hpp file -> only the file lib_0/class_0.hpp was modified. rebuild 30 object files and 14 libs.

Analysis

  1. comparing SCons and docons on no-op build you can see how doit is considerably faster than SCons on creating the dependency graph and checking what to build.
  2. comparing “no-op 1 lib” with “no-op” you can see how both SCons and docons have a performance degradation from creating the dependency graph (5.2 and 3.6 times slower respectivelly). And how dup shows little influence on no-op build relative to the size of the dependency graph.
  3. all 3 solutions have almost no difference between a no-op build and a partial/incremental build where a single source file is modified.
  4. as the number of built objects increase the advantage of dup over docons is reduced because it requires the dependency graph from the affected tasks to be built.

Should you stop using SCons?

Probably not. The implementation is very incomplete and probably buggy in many ways. This code was written just as proof-of-concept (and for fun) to check how powerful, flexible and fast doit can be.

I have personally no interest in developing a C/C++ build tool and if I would build one I would create a different interface from the one used by SCons.

About these ads

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Follow

Get every new post delivered to your Inbox.

%d bloggers like this: