Performance Comparison between KJam, Jam, Make and MSBuild
One of KJam's primary design goals is extremely fast build speeds. To determine how KJam compares with
other popular build tools, and with the original Jam/MR, we conducted a series of performance benchmarks.
The Tools
We compared the performance of 4 build tools:
All of these tools the the same basic job:
The one exception to this is Gnu Make, which generates the dependency graph using a separate "make depend" step.
Typical usage for Gnu Make is to build the dependency graph only when the user has reason to believe the
dependency relationships between files may have changed. The other tools tested all compute dependency information
each time they run. We ran the Gnu Make test twice, once modeling typical usage, and once where the dependency
graph is rebuilt before each build like the other tools do.
The Test
The test was conducted on a 1.39ghz Dual Core AMD Opteron workstation running Windows XP. The workstation has a very fast RAID0 disk array running two WD Raptor740 drives. The performance test task is to build a set of C++ source code files using Microsoft Visual Studio 2005. The code consists of trivial source files generated by a python script. All tests compiled the code with the exact same build flags.
We tested three configurations of source files:
Each run consists of three tasks:
Results
All times are given in seconds. Shorter is better. Here is the source data. And some graphs:
Discussion
Full Build Times: This task is dominated mostly by the time taken for the build commands issued by each build tool to run. Given that each tool is issuing similar commands to the same version of MSVC, one would expect build times to be similar. Yet KJam is significantly faster in all cases, sometimes more than 3 times faster. Why?
Firstly KJam schedules parallel processes better than the other tools. A compiler opens a large number of files. It must sometimes process hundreds of headers for each source file. Since disk speeds have not kept up with the improvement of CPU speeds, modern compilers spend a great deal of time waiting for the disk. With parallel execution, one build thread can run while others are blocked waiting for I/O. KJam finds more opportinuties to issue commands in parallel. KJam issues more build commands in parallel than Jam or Gnu Make, and prioritizes them. MSBuild is single threaded and cannot issue build commands in parallel at all, resulting in the longest build times.
The second reason is that KJam supports MSVC's batched build commands. MSVC can generate multiple object files from multiple source files with a single call to the compiler. This is much faster than compiling source one at a time. Since we don't have access to the internals of MSVC it is hard for us to know exactly why this is. There are multiple reasons why batched building on MSVC might be faster. Certainly we reduce the number of times MSVC must be read from the disk and initialized. It may also be the case that when processing multiple source files, MSVC may save some of the work processing header files for each source file.
KJam has full support for batched building. In the current configuration KJam sends 5 source files to each invocation of MSVC. The optimum number of batched sources will depend on the number of source files in each library, and the number of cpu cores available. Greater build performance in this test can probably be achieved by batching more files but this risks losing parallelism opportunities in environments with more cores. MSBuild supports batched building, but Gnu Make and Jam do not.
Incremental Build Times: The differences are huge. In all cases Jam and KJam have negligible incremental build times, both of them complete the task in well under one second. By contrast MSBuild and Gnu Make take a significant amount of time to determine that there is no work to do, sometimes by more than a factor of 20. For large projects, with many thousands of files this difference in scanning time can make rebuilding even a single source file take several minutes. It is worth noting, that while its not competitive with Jam and KJam, MSBuild has faster incremental build times than Gnu Make, in some cases by as much as 2x.
One major reason that both Jam and KJam are so fast is that they minimize their interactions with the file system. Both tools scan the target directories, and cache the results. Further interactions with the file system are done using the cached results. KJam does more aggressive file system cacheing which would benefit only larger projects.
For 10 libraries case, the Jam and KJam build times are almost identical. This is because in this case Jam and KJam spend almost all of the time waiting for file system operations. The internal processing of each tool is faster than the time between disk accesses. The processor load for both tools during scanning is low - though KJam is more efficient and has a lower load. This means that as disk subsystem speeds increase, KJam is likely to benefit more than Jam. KJam also issues most its file system requests in parallel. In theory if the operating system could service file system requests in parallel, KJam would also benefit more. We are exploring the possibility of writing custom file system drivers to take advantage of this.
For the larger projects, such as the 2 libraries case, KJam is about twice as fast as Jam. As projects get larger this difference increases. For a highly tuned build environment, on fast build hardware, KJam can scan as many as 100k files per second. KJam uses a more sophisticated file system caching algorithm that benefits larger project.
Clean Build Times: This test shows similar performance to the incremental build test. Jam and KJam are more than an order of magnitude faster than
MSBuild and Gnu Make. For smaller projects Jam and KJam turn in almost identical times, but as projects get larger KJam is up to 2x faster than Jam. It is intersting
to note that in come cases the clean times for MSBuild approach those of Jam and KJam. This is probably because MSBuild must not be running its whole dependency
scanning engine for clean builds, but rather doing something just with the directories where generated targets go. We note that MSBuild's clean times seem to
scale with the number of output directories. This may be a problem for environments with many output directories.
Conclusion:
These tests show that in almost all cases KJam is much faster than the other tools tested. At best, for smaller projects Jam is sometimes able to keep up with KJam's incremental and clean build times. No tool is able to match KJam's full build times. Both Jam and KJam are in their own class when it comes to incremental build times.
One reason that KJam's full build times are so good is that it takes advantag of MSVC's batched building. If you are using a compiler which does not support batched building, such as GCC, then KJam's full build times will be comparable to Jam. KJam is also able to take better advantage of multi-processor workstations. On single processor workstations, KJam's build times are still significantly faster, but the differences will be less dramatic.
No matter what compiler you are using, or how many processors your workstation has, KJam's incremental and clean build times will continue to be far faster than competing tools, especially for large projects.
Network Builds: These tests were run using a single workstation. KJam also has a distributed network build mode. Due to issues of latency with network mounted file systems, coupled with todays extremely powerful processors, most compilation commands complete faster in non-network mode, than in network mode. Only the more computationally expensive build commands like linking get a significant benefit from parallel execution over a network. So for building c and c++ projects the best choice is still non-network mode. For projects where each build command may take a significant amount of time, such as projects dominated by data processing tasks, KJam's distributed network building would have dramatic benefits.