fredrikj.net / blog /

Developing mathematical software in C

January 28, 2021

I sometimes get asked whether it makes sense to implement XYZ in C, especially compared to using some language that is more advanced (C++, Julia, Python, Haskell or Rust) or perfect (Lisp).

I suspect that a lot of people are a bit intimidated by C and believe that it requires some kind of superhuman hacker ability to wield. That's at least how I felt about C before I started really using it. Other people believe that C is a horrible language that inherently produces defective software and which should be cast back into the abysses of UNIX from whence it came (they are not necessarily wrong). I personally think that C's simplicity is an advantage that often outweighs its disadvantages, but there are clearly domains where C is a bad choice. In domains where C works well, there are also good alternatives, and choosing C then just comes down to personal preference.

In this post, I will attempt to answer why you should or shouldn't use C, and I will give some general advice that may be helpful if you end up using C. This is based on my own experience developing mathematical software in C (mainly Flint, Arb and Calcium), in an academic setting. This experience will not necessarily transfer well to other settings.

Why you should use C

Why should you write your next library in C, or perhaps contribute to some existing C library? I will offer four simple arguments.

Availability

Reason number one is that C is stable, universally supported, and has reliable tooling. Your plain C library will compile and run almost anywhere, can be developed anywhere, and will require minimal dependencies. Users of virtually any other programming language can easily interface with your code through their language's C foreign function interface, at least if you take basic precautions to design a decent external API. Not only will your C library run anywhere right now; it will still run 20 years from now, and if you had a time machine, probably 20 years ago too.

Speed

Reason number two is that it will run very, very fast. I don't just mean that benchmark loops will go VROOOM; your software will also start up instantly (no need to load a bloated dynamic runtime or JIT-compile code), and there will be no hidden overhead for things like automatic garbage collection (well-written C code spends a negligible fraction of its overall execution time doing allocations and deallocations, precisely at the points in time where they are needed). This is, of course, if you know what you are doing. Writing efficient C, while not exactly rocket surgery, does require proficiency with the language and a solid understanding of fundamental algorithms and data structures.

Readability

Reason number three is that you will be able to read your own code, and others will incidentally be able to read it too. Some people are going to disagree with me here, arguing that higher level languages are better for readibility. That is trivially true in the sense that higher level languages provide abstractions that allow expressing complex ideas more succinctly. A simple example is providing operator overloading so that you can write a + b * c instead of something like add(a, mul(b, c)), or in C, often something even more verbose like the following typical GMP snippet:

mpz_t tmp;
mpz_init(tmp);
mpz_mul(tmp, b, c);
mpz_add(a, a, tmp);
mpz_clear(tmp);

This would seem like an especially important point for mathematical software. However, hiding details can also hide useful information. In an object-oriented, memory-managed, operator-overloaded language, information that may be hidden by the infix arithmetic notation includes where and how memory is allocated; how methods are resolved and how coercions are made when the operands have different types or when class hierarchies are involved; what algorithms are used to perform the arithmetic operations (irrelevant for machine integers, but potentially very important details if you are multiplying huge matrices). The infix notation is usually good for understanding the intent of the code, but something more verbose can be better for reasoning about performance and for dealing with cracks in the abstractions. Put concisely, C is good for making implementation details explicit when implementation details matter.

Viewed in this light, C's omission of certain conveniences such as namespaces, overloading and generics is actually a feature, not a bug. Figuring out what any given piece of C code does tends to be a straightforward process because of, and not despite, the fact that it is verbose: everything that happens is explicit and functions and types can only have a single definition which is easy to grep for. I can't recall ever really having trouble diving into someone else's C code or reading C code that I wrote a long time ago. The same can't be said for Python, for example, where it can be a real struggle to understand which method on which class gets called and how and when and in what context. Granted, you can obfuscate C code by abusing macros, doing complicated runtime generics, or using cryptic names, but even something like the rather dense and idiosyncratic Pari/GP codebase is penetrable after a short familiarization process.

Educational value

Reason number four is that you will learn a lot in the process of writing C. Implementing algorithms in C instead of a higher-level language can lead to a deeper understanding since you have to do more of the groundwork yourself. You will also probably have to think things through more carefully; when I write Python, I can often get away with implementing something half-broken and fixing it piecemeal, but C more often forces me to be correct up-front.

Why you shouldn't use C

Now on to the far more interesting case against C, or rather, a fair and balanced evaluation of C's weaknesses.

Mathematical understanding

Since we are talking about mathematical software, it is likely that implementing XYZ actually involves solving two problems: understanding the mathematics of XYZ, and translating that understanding to concrete algorithms and code. If you don't understand the mathematics, you might be better off exploring the problem using a high-level language or a computer algebra system and postponing a C implementation (if you need it) until your mathematical understanding has crystallized. If you decide to start a C project right away to figure out the mathematics in parallel with the software development, you will probably still want to use another language for experimentation (more on this later). Be prepared to continuously reevaluate your assumptions, and expect having to rewrite code from scratch more than once.

Portability and deployment

The following comments mainly apply to starting a new project intended to be used by other people.

In practice, the claims about C's amazing portability are somewhat exaggerated. As a C library maintainer, you will have a lot of fun gradually discovering new inconsistencies in build systems and standard library implementations between different operating systems and hardware configurations. You will probably run into the occasional rare compiler bug (though C might be one of the better languages in this regard). Over time, your header files will probably accumulate hundreds of #ifdefs intended to work around compatibility problems that may or may not still exist.

The large majority of your prospective users will probably be unable or unwilling to build and install your library from source, so you will either have to distribute binaries yourself or rely on distribution via third-party package repositories such as those of the major Linux distributions. In the interest of stability or because of a lack of manpower, such repositories typically keep software 1-10 years out of date. (Yes, I once found Travis CI's default Ubuntu configuration sporting a nearly 10 years old Flint-1.6.) In other words, you can't count on users having access to the latest features and bugfixes in your library, and it goes without saying that you should work very hard to preserve backward compatibility. I suppose this lag in deployment has one advantage for reproducible research: if you submit a journal paper based on the cutting edge version of your software, readers will probably still have access to that version in Debian LTS by the time the publishing process completes three years later (hi, ACM Transactions on Mathematical Software).

A good idea for widespread deployment is to get your mathematical library into SageMath. SageMath is maintained by a large community and tested on many platforms, and packages in SageMath are usually only several months out of date.

Deploying software written in more modern programming languages is typically easier since they have more sane build processes and standard libraries that eliminate most of C's platform-dependent headaches. Nowadays many languages also have their own easy-to-use packaging systems and centralized package repositories. In practice, the best languages for portability and easy distribution right now are probably (1) JavaScript (in the browser), and (2) Python. Julia is not far behind, and in many respects better designed than Python, but Python currently has the benefit of being preinstalled on many systems. All of this being said, Emscripten is a promising alternative distribution method for C code which may change the equation, especially if you think a browser-based interface makes more sense than linking together libraries and running code in the terminal in the traditional way.

Safety

C has a reputation of leading to buggy, crash-prone software and disastrous security vulnerabilities. Commonly criticized aspects of C include its manual memory management, weak type system, and deviously undefined or implementation-defined semantics. This reputation is generally deserved, though in C's defense, I think the problems often have nothing to do with the core C language but rather revolve around poor legacy coding practices and libraries (including C's standard library). I do believe that C's weaknesses can be mitigated with good foundations and modern software development practices (more on this below); there is a lot of extremely reliable C code out there, after all. Nevertheless, it is definitely true that C often requires substantial developer effort to avoid bugs that don't exist in many other languages.

Probably the central safety problem with C is that it is extremely difficult to guard against all forms of adversarial input. Luckily, the mathematical software I develop is not safety-critical in the same sense as network software, kernel drivers, etc. While mathematical correctness is paramount, mathematical software will typically be run by trusted users in a controlled environment, taking sensible data as input. (I'm obviously excluding mathematical software explicitly designed for doing crypto on the battlefield here.) In other words, we need to guarantee correctness for correct input, but it is not a high priority to guarantee safety for incorrect input.

For example, there are hundreds of functions in Flint and Arb that let the user input a machine integer to specify an array index or the size of some object. We rarely put in safeguards to handle clearly unreasonable input (accessing an array at index -1, allocating LONG_MAX bytes of memory, etc.); instead, we put the burden on the user to sanitize input. Accidental errors can be handled with assertions to some extent, but it is an enormous amount of work to fully proof C code against adversarial input; this is far easier in a language that automatically traps integer overflow and out-of-bounds access.

Generics

C tends to work best for writing specialized functions that process specific types of data. C notably lacks builtin support for generic programming (allowing a single function to process many types of data). As far as I can tell, there are essentially four ways to do generic programming in C, none of them perfect:

  1. Static (compile-time) generics using macros.
  2. Dynamic (runtime) generics using function pointers.
  3. God-objects: use one data type but make it versatile enough to represent any kind of data you will need (often with big switch statements, if not in combination with function pointers).
  4. Use C++.

By doing generics in C using either of the first three methods, you will likely sacrifice code clarity and give up many of the correctness and documentation benefits afforded by C's (admittedly rudimentary) type system. My best advice is probably to avoid C if you need generics; either duplicate functionality for each type where you need it, or use another language. Implementing your very own object system in C can make sense if you have specific requirements, but this seems like a terrible idea if your goal is just to do be able to write generic functions.

I'm not a fan of C++, but the generic collections in the C++ standard template library are pretty neat (I have used C++ a couple of times for this reason). Point 4 in the list above is not a joke entirely; you can certainly write "C-style" C++.

Yet another possibility is to write specialized code in C and interface with it from a high-level language to do generic programming. This is basically what we ended up doing with Flint and Nemo. Flint implements one C type for each mathematical ring: fmpz_t for $\mathbb{Z}$, fmpz_poly_t for $\mathbb{Z}[x]$, fmpq_t for $\mathbb{Q}$, fmpq_poly_t for $\mathbb{Q}[x]$, etc., and each operation (addition, multiplication, assignment, printing, etc.) needs to be implemented separately for each type in C. This involves less code duplication than it might sound like since the algorithms tend to be specialized for each type for performance reasons, but we clearly don't want to to add millions of new types to Flint to cover all the algebraic structures mathematicians can write down, nor do we want to implement hundreds of mathematical operations in C for each the types we already have. Fortunately, now that we have Julia wrappers for most Flint types in Nemo, you can use Julia to implement generic algorithms that work over any ring. (There is also Python-FLINT in Python, and SageMath wraps some of the Flint types.)

Parallelism, memory management

Similar things can be said about multithreading in C: it's doable, but not convenient. The easiest way to do parallel computation with C is to write single-threaded code and split the input into independent batch jobs that can be run in separate processes. Fortunately, mathematical computation problems are often massively parallel by nature, so this tends to work quite well. (I often write a quick Python script to start such jobs and assemble output dumped to text files.) You can also write threadsafe kernel functions in C and do thread-level parallelism using wrappers in a higher-level language. If you need more fine-grained parallelism in C itself, prepare to get your hands dirty. For heterogeneous parallel computing, GPUs, etc., C may be worth it if you need the last ounce of performance and have the expertise to achieve it, but chances are the hardware and external tooling will change faster than you can keep up adapting your code.

Memory management is its own can of worms. C works well if you can structure your data hierarchically in time and space so that it is obvious where memory needs to be allocated and deallocated, and if you encapsulate low-level memory management details (for example, by using methods that do automatic resizing when you need resizable strings or arrays). If you need objects that cross-reference each other (as opposed to having a strict hierarchy of ownership), and especially with unpredictable lifetimes, then life will be much easier in a language with automatic memory management. In my experience, manual memory management in C is straightforward 99% of the time, only tedious. Your mileage may vary.

Development time

Overall, implementing things in C is not necessarily harder than in other languages, but it often takes more time. If you like breaking a problem down into atoms and then building up a solution in which you control all the details, and if you have the time to do so, then C is a good language. If you just need things done quickly, not so much. I usually enjoy the intellectual challenge of turning ideas into C, but it's also sometimes just drudgery.

Some advice for developing in C

You've decided to write some C. Excellent! How can you avoid shooting yourself in the foot, or better, actually achieve your goals? I will try to provide some foundations. I assume that you already know the basics of C programming; if not, there are lots of resources on the internet for learning C.

Documentation

First of all, if there's code, there should be documentation. This isn't optional. I really shouldn't have to say this, but there are already too many projects out there with lousy documentation. If there is a function, I want to know what it outputs, what assumptions it makes about the input, and where relevant what algorithm it uses (ideally with reference to a paper). Complete API documentation is the minimum, and strongly recommended even if you're only writing code for yourself; for users, you will also want well-documented example code, tutorials, and general explanation. I think I've done a decent job with the Arb documentation; it's not perfect, but it can be a starting point.

Version control and build system

Use version control (for example, git), an automated build system, and continuous integration. This doesn't really deserve elaboration. Once you have a stable codebase, tests should always pass on the main branch, and making a new release should be as easy as updating the version number and changelog and tagging a version in git.

Organizing code

Since C provides very few builtin abstractions and many of the tools it does provide are flawed (null-terminated strings, pervasive undefined behavior, unhygienic macros, nearly useless standard library, and so forth), you can't approach software development in C thinking that you will just start implementing end-goal features. If you want to do anything nontrivial in C, you will have to start by building infrastructure, use the infrastructure to build foundations, and only then use the foundations to build features.

In effect, you will probably need to implement your own domain-specific "dialect" of C, comprising informal coding conventions (how you name things, do memory management, etc.) together with a custom "standard library" for basic functionality. If you contribute to an existing project, you will not have to do all this work from scratch, but you will have to take some time to learn the project's C dialect. Needless to say, consistent coding conventions are a good idea in any language: the advantage is not just that a neat and uniform codebase is easier to understand; when you have a mental template for how to structure code, you don't have to waste time thinking about all the alternative ways you could do it.

Let us look at how code is organized in the Flint family of projects (including Flint, Arb, Antic, Calcium). This is just an example; other C projects are organized completely differently, and one way is not necessarily better than another.

First of all, Flint defines some global functionality in flint.h and in a couple of related header files. This includes the following:

Any big C project will probably need similar support code. In Arb, Antic, Calcium and other projects that use Flint as a base library, much less work needs to be done from scratch since all this basic functionality can just be imported from flint.h.

Flint is organized as a collection of modules. Most modules correspond to a single mathematical type: for example, the fmpz_poly module implements the fmpz_poly_t type, which represents elements of $\mathbb{Z}[x]$. Each module consists of a header file (fmpz_poly.h) together with a directory of source files (fmpz_poly/add.c, fmpz_poly/mul.c, etc.) and test files (fmpz_poly/test/t-add.c, fmpz_poly/test/t-mul.c, etc.). Each module has its own page in the documentation describing the complete API.

As a general rule, each public function (such as fmpz_poly_add) goes into its own file and has a corresponding test program, with filenames corresponding to the function name. It may seem like overkill to have one file per function, but it does help keep code neatly organized and easy to browse by the time you have 100+ public functions in a module. There are exceptions: internal helper functions used only by one function can be declared static and placed in the same file as the parent function, and very short functions can be defined inline in the module header file.

Flint defines the fmpz_poly_t type as follows:

typedef struct
{
    fmpz * coeffs;
    slong alloc;
    slong length;
}
fmpz_poly_struct;

typedef fmpz_poly_struct fmpz_poly_t[1];

The structure contains a pointer to an array of coefficients of type fmpz (the Flint arbitrary-size integer type), information about the allocated size of the array, and information about the used size of the array (the length of the polynomial). Some notes about memory management:

Code using the fmpz_poly_t type may look something like this:

/* Compute res = a + b + c */
void add_three_polynomials(fmpz_poly_t res, const fmpz_poly_t a, const fmpz_poly_t b, const fmpz_poly_t c)
{
    fmpz_poly_t t;
    fmpz_poly_init(t);

    fmpz_poly_add(t, a, b);   /* Set t = a + b */
    fmpz_poly_add(res, t, c);  /* Set res = t + c */

    fmpz_poly_clear(t);
}

By convention, Flint functions are called with the output variables (for writing the result) first, followed by const input variables, and possibly extra parameters. Memory management is simple: the user calls the init method to initialize an object, and calls clear when done with it. These operations will almost always be paired at the start and end of the same function or code block. In between, this initialized object may be passed to functions for reading or writing. The reason for using in-place mutation instead of having functions return new objects is performance: avoiding allocating/initializing/copying objects can easily speed up code by a factor two or more. One of the main reasons why C tends to be "fast" is that this kind of code is idiomatic, whereas the automatic memory management facilities and object systems in many higher-level languages encourage wasteful initializations/copies.

Many operations in Flint have several different algorithms. There is only one algorithm for adding polynomials, but there are several versions of polynomial multiplication: fmpz_poly_mul_classical (classical multiplication), fmpz_poly_mul_karatsuba (Karatsuba algorithm), fmpz_poly_mul_KS (Kronecker segmentation), and fmpz_poly_mul (Schönhage-Strassen). The main method fmpz_poly_mul tries to choose the optimal algorithm automatically based on heuristic cutoffs, and also implements a special inlined version of classical multiplication for short polynomials with small coefficients. This is all rather typical for mathematical software. A less typical design decision made in Flint is that all methods are public: all the alternative multiplication functions are part of the public API, with public documentation. In effect, we provide the same API for users and for developers. This makes it easier to experiment with the code (for example, benchmarking the various algorithms), and expert users can choose a specific algorithm when they know better than the default heuristics. I believe that this also creates a lower barrier to entry for new contributors.

Most modules in Flint, Arb, Antic and Calcium follow very similar conventions for naming objects, organizing files, calling functions, managing memory, etc. Together these projects have around 800,000 lines of code (as measured by sloccount), but the structural complexity of this code taken together is not much higher than for a single module 1/100 the size. I shouldn't paint a too rosy picture: when you look closer, these projects are full of little inconsistencies and regrettable design mistakes, like any software. But overall, Flint's foundations have held up quite well over more than 10 years of development.

Test code

Test code is even more important than documentation. As Bruce Eckel says: "if it's not tested, it's broken".

Testing mathematical software is relatively easy, because mathematical operations tend to be clearly definable, providing obvious invariants to check. Flint and its descendants rely very heavily on randomized unit tests, following the lead of GMP. Most of the test code uses the strategy of computing the same mathematical quantity in two or more different ways (for example, using functional equations, interchanging the order of parameter, or varying the precision and other algorithm parameters) and verifying that the results are consistent.

For example, to test a polynomial multiplication function, we may generate random input polynomials and check properties such as $A(B + C) = AB + AC$ and $A(BC) = (AB)C$. We also test for aliasing problems: for example, when a function computes $C \gets AB$, we need to check that it works when the output variable for $C$ is aliased with $A$ and/or $B$. We may also compare two algorithms (most commonly, using the simple classical algorithm as the reference for a more complex algorithm). Numerical code is typically more difficult to test than exact algebraic code, but strong testing is possible in Arb since we can check the inclusion properties of interval arithmetic: for example, if $X$ and $Y$ are computed balls for $x$ and $y$ and $x = y$, then $X$ and $Y$ must overlap. In MPFR, the output must be correctly rounded, which can be checked. There is actually a rather deep and universal point to be made here: stronger contracts allow stronger tests.

Effective testing is a bit of an art as well as a science. Bugs tend to occur at the edges and corners of the input space (literally, at edge and corner cases), so it is important to generate random input non-uniformly. GMP, Flint, Arb and friends provide random generation functions for each type designed to produce good test input: sparse objects, objects with many zeros, objects with many small factors, objects with no factors at all, objects of very small magnitude, objects of very large magnitude, and so on. Designing good test cases and choosing good test parameters can be tricky. A time-honored strategy is to introduce deliberate bugs into your code; if the test code passes, it needs to be strengthened until it fails. Repeat for all critical sections of the code. (And for all that is holy, don't forget to take the bugs out when you are done.) Speed is an important factor; we usually want to run thousands or millions of test iterations for each function, but the tests should not take hours to finish, so it is best to test small input. Algorithms that make case distinctions only for huge input can be problematic for this reason.

Prototyping and interactive testing

It's relatively difficult to test code interactively or do rapid prototyping in C. There are REPL tools for C, but they are not very helpful (in my view). The reason is that C's verbosity and manual memory management work against REPL use; you will spend too much time typing to be productive.

I have two solutions; the first is to set up an environment where it is very, very easy to run C programs. Personally, I have a "scratch" directory located at ~/src/test. If I need to quickly test some idea or prototype some functionality, I create a .c file in this directory (or pick an old file and repurpose it). When I have working, reasonably clean code, I migrate it to the actual project directory (e.g. ~/src/arb) and put it under version control. I never delete or organize old scratch files; at the time of writing, ~/src/test contains some 800 .c files dating back to 2014, with names like bundesliga.c (apparently some old test code for logarithms in Calcium), megamul.c (some code I used to test matrix multiplication algorithms) and agamemnon.c (an early version of Legendre polynomial evaluation for Arb). The point is that dumping something into this scratch space requires no effort; if I need to revisit some old idea, I can just search the file contents. In the scratch directory, I keep some scripts that let me run C files easily. For example, I use the following shell script named go to test Arb files:

set -e
cd ../arb
make
cd ../test
export LDFLAGS="-R/home/fredrik/src/flint2 -R/home/fredrik/src/arb"
export LD_LIBRARY_PATH=/home/fredrik/src/flint2:/home/fredrik/src/local/lib:/home/fredrik/src/local:/home/fredrik/src/arb:$LD_LIBRARY_PATH
gcc -std=c99 -g -O2 -I/home/fredrik/src/arb -I/home/fredrik/src/arb/build/include -I/home/fredrik/src/local/include -L/home/fredrik/src/arb -L/home/fredrik/src/flint2 -L/home/fredrik/src/local/lib $1 -o a.out -larb -lflint -lmpc -lmpfr -lgmp -lm -lpthread
objdump -d -M intel -S a.out > asm.txt
echo "-------------------------------------------------------------------"
time ./a.out $2 $3 $4 $5 $6 $7 $8 $9 ${10} ${11} ${12} ${13} ${14} ${15} ${16} ${17} ${18} ${19} ${20}

Running ./go foobar.c first rebuilds Arb if it's not up to date (useful if I'm editing some Arb source files at the same time, to make sure I'm not accidentally testing against the wrong version), then compiles foobar.c (linking to the development versions of all the libraries I'm using) and runs it. The compile-run cycle takes a fraction of a second; basically as fast as an interactive REPL. At this point, IDE users are probably screaming out in horror, but this setup works pretty well for me. (For the record, for actually editing code, I use Geany together with my Linux desktop environment's basic text editor (Pluma), and rarely nano.)

The second solution is to use a different language. To test and prototype new functionality for Flint and Arb, I use either Python (Python-FLINT) or Julia (Nemo), and occasionally SageMath. I mostly use Python since I'm used to the language and since Julia has annoying JIT compilation delays. I use the terminal-based REPL about 50% of the time and a Jupyter notebook otherwise. For Calcium, I decided to maintain a ctypes-based Python interface as part of the project itself, and I keep this up-to-date with changes to the C codebase. This interface is not very efficient (unlike Python-FLINT which is written in Cython), but it does not require recompilation and works extremely well for testing. A good chunk of the permanent test code for Calcium is actually written in Python now, which makes some kinds of testing much easier than when only using C.

It's difficult to give general advice about how to approach implementing mathematical algorithms, because my own workflows vary a lot. Sometimes, I just start coding in C without any prototyping at all. Other times, I write a complete implementation in Python and translate it to C almost verbatim only when I've made sure that the Python version is completely correct. The last approach is useful for complex algorithms where a lot of things can go wrong; being able to use the Python version as a reference for the C code can be invaluable.

Debuggers and other tools

I personally don't use a debugger such as GDB (printf is the universal debugger), but I do use Valgrind. Valgrind is a wonderful piece of software which to a significant degree compensates for the lack of memory safety in C by detecting memory errors at runtime. Valgrind will detect when a program reads uninitialized memory, reads or writes outside of allocated memory (before allocation or out of bounds), or leaks memory. Valgrind can also be used for profiling code and for detecting other kinds of errors.

Valgrind is extremely easy to use: instead of running test_program, you run valgrind test_program or better valgrind --leak-check=full --show-reachable=yes test_program. Valgrind shows quite specific information about where and how any problems occur, so it is usually a simple process to fix the bugs. In fact, Valgrind works so well for catching memory leaks that it's arguably as easy to write leak-free software in C/Valgrind than in some languages with automatic memory management; you can also use Valgrind with other languages, but it will be more difficult to debug code when you have to understand that language's memory manager and not just what your own code is doing. A feature of Flint that I omitted mentioning earlier is that it includes an internal memory manager for fmpz integers; we have an optional fallback version of this memory managers that simply uses malloc/free to facilitate debugging with Valgrind.

I always run new test code with Valgrind. If I had a beefy multicore development machine and not just a dual-core laptop, I would probably run Valgrind even more often. I always make sure that the Valgrind output is completely clean, which is possible since Valgrind rarely seems to report false positives. I can only recall one instance of a false positive: Valgrind reports that some GMP assembly functions read out of bounds on certain machines. Valgrind is actually technically correct (GMP does read out of bounds), but GMP is also correct, for subtle reasons (its out-of-bound reads are deliberate and safe due to intricacies of data alignment). It is possible to tell Valgrind to permanently suppress such specific false positives.

It's important to stress that Valgrind only detects certain classes of bugs, and only bugs that actually get triggered by tests, so it will only be effective when combined with high-quality test code. Developers who are serious about software correctness and safety should also consider using tools for static code analysis, formal verification, fuzzing, and test coverage. I have much less experience with such tools myself. Just for fun, I just now tried to run cppcheck on Arb, and it found no errors except for a handful of supposedly uninitialized variables (all false positives) and one missing deallocation (also a false positive). This is not because I write bug-free C code, but because I have been diligent about writing test code and running Valgrind, which goes a long way to excise the kind of bugs that code analysis tools will catch. That being said, there are far more accomplished C/C++ programmers than me who swear by static analysis tools, and the proprietary tools are apparently better than the free ones, for those who can afford them. On this note, I will recommend the blog of John Regehr.

A possibility that shouldn't be overlooked is to write your own tools. Some problems are easy to check for with scripts without even parsing code (for example, unmatched init / clear calls in Flint). I will sometimes write a script to validate a function or algorithm by an exhaustive computation when I can't convince myself that randomized testing is sufficient. Finally, a useful way to minimize bugs is to generate code automatically from high-level descriptions instead of writing it by hand (commonly used for parsers and for converting formulas like a + b * c into sequences of function calls).

Keeping it simple

This post is not intended to be a detailed C coding guideline, but I feel compelled to offer at least a few vague platitudes for your consideration:

Alternatives to C

So what should you be using if not C?

If you you want something higher-level, more mathematical, more functional, more object-oriented, or more dynamic, the question is too broad to answer. You will have to study the features of different languages and pick one that suits your needs.

If you want something with the performance and portability of C, there are fewer options. C++ is the obvious choice, provided that it agrees with your aesthetic sensibilities. Fortran is just as mature as C and excellent for purely numerical applications. By far the most promising contender to replace C for me personally is Zig, but this is just my impression from reading about the language; I have not tried to use it yet. D and Rust also look like options, more in line with C++ than C. One drawback of using Zig, D or Rust instead of C or C++ is that the pool of potential contributors will be smaller, and there is a shortage of mathematical software developers even for the most popular languages. Rust and Zig also seem to be evolving rapidly, so you will not have the long-term stability of C/C++ for a while.

Combining C with a dynamic high-level language such as Python or Julia isn't a terrible solution. Many languages try to achieve "the best of both worlds", but I have yet to see one that really succeeds to be great for both low-level and high-level programming. More about that in a future post, perhaps.



fredrikj.net  |  Blog index  |  RSS feed  |  Follow me on Twitter