COMS10008 Aside: Trickery

Why use C?

Often, programmers use C because they want total control to use whatever trickery they can, to do something unusual such as control hardware or gain maximum efficiency

The C language brings its own problems, and so trickery is also needed to handle those problems

This aside discusses some lesser known C trickery

Advanced debugging

The advanced debugging options used in this unit:

-fsanitize=undefined -fsanitize=address

are relatively recent and not very well known

Yet they can almost eliminate the old problems with segfaults

What `sanitize` does

The sanitize options to gcc or clang adds extra code to your C program to detect undefined behaviour

The extra code slows your program down, so this is only for testing, not for production

For example -fsanitize=bounds adds array bound checking, to catch going past the end of arrays

The -fsanitize=undefined flag bundles a whole lot of options together, to try to catch almost all undefined behaviour situations

What you gain

The main problem with undefined behaviour is finding the line in the program that is causing the problem

You have to add more and more print statements to narrow down gradually where the problem is

With gdb or valgrind, as well as a learning curve for using them, you still have to use search techniques to find the problem

With sanitize, the extra code stops your program the instant it does something wrong and reports the line number

What you need

You need a reasonably recent version of gcc or clang

The sanitize options began in version 4.9 of gcc, unfortunately, version 4.8 is common, so clang is a better bet if you have it

You also need the ubsan library for generating error messages, and you may need to add the -g option for line number info and remove the -O2 or similar option

Windows

As usual, Windows causes problems - first you need Cygwin or MSYS2 to get gcc or clang

Then the ubsan library is probably not available, so add the -fsanitize-undefined-trap-on-error option to cause a trap instead of an error message

Then use gdb in the simplest way (gdb program then run) to get an error message

Read-only structures 1

Suppose you want to make a structure read-only; here's one way:

struct point { int x, y; };
typedef struct point const point;

Now, any variable of type point only has read-only access to the fields

But, by using the type struct point instead, code can gain write access

Read-only structures 2

Here's another way:

struct point;
typedef struct point point;
int x(point p);
int y(point p);

struct point { int x, y; };
inline int x(point p) { return p->x; }
inline int y(point p) { return p->y; }

Compiling with the -flto cross-module-optimisation flag makes x(p) as efficient as p->x

Flexible arrays 1

Suppose you do this:

int n = 24;
char *p = malloc(n);
...
n = 2 * n;
p = realloc(p, n);

Conventional wisdom is to start small (smaller than n=24 gains nothing) in case of lots of empty arrays

And to double, to reduce the cost of copying in realloc to constant time per item on average

Flexible arrays 2

If you keep doubling the size of an array, you might end up with previous arrays of sizes 1, 2, 4, 8, 16, 32, which add up when freed up and coalesced to 63, at the moment you want a new array of size 64, so you may end up never reusing old space

So many programmers now do n = n * 3 / 2 to multiply by 1.5 or some other factor below 2

Flexible arrays 3

If you double the size of an array, you end up with up to half of it unused

If you know the array won't grow any more, you can use realloc to reduce the size to the amount that is used, freeing up the remainder (and it is likely to be a low-cost call, because realloc is unlikely to move the array)

Flexible arrays 4

You can look out for special cases in your programs

Take scanning, for example, where a source text is divided up into a (flexible) array of tokens

The special case is the tokens are created in one go, with no other allocations going on at the same time

You can increase the size of the array by a fixed amount (n = n + b) because most realloc calls will extend the array, not copy it, so will be low-cost (try it!)

Flexible arrays 5

To make flexible arrays convenient, you need to encapsulate them:

struct list;
typedef struct list list;

struct list {
    token *tokens; int capacity, length;
};

The user makes function calls on a list object, which never moves, whereas the tokens array is moved by realloc calls

Flexible arrays 6

A disadvantage of a flexible array is that you can't let the user have a pointer into it, because the data moves

You should look for special cases where you can allocate objects in fixed positions, but give the illusion of an array or linked list

Take tokens again for example: after creating them, you only ever need to iterate through them, not index them at random, so you can give the illusion of a linked list (doubly linked if you want) as follows

Fake linked list

The header looks something like this:

struct list; typedef ...;
struct token; typedef ...;
token *addToken(list ts);
token *next(token *t);

Allocate token structures in blocks, reducing the overhead of malloc, which is 8 to 16 bytes per object

The next function is "if at end of block, move to the next block, else increase the token pointer by one" and you can inline it and use -flto

Global variables

The problems with a global variable are:

it is inflexible - if you want a variable size or later want two or more of it, you have to change your design
it is not thread safe, if you ever move to multiple threads

If you are 100% sure these will never apply to your program, a global variable may be a valid trick

But it is surprising how often a little ingenuity yields a better approach

Compressed pointers

Languages and libraries often use compressed pointers, because real pointers are now usually 64 bits, which can seem too much

A compressed pointer is a 32-bit integer relative to the base of the heap

Instead of *p you use base[cp] = *(base + cp)

It seems that the base pointer needs to be global, so that it can be accessed from anywhere, but there is a better way

Relative compressed pointers

Instead of using offsets relative to the heap base, you can use offsets relative to the object they are stored in

For example, for tree nodes, you can implement:

struct node { int left; ... };
inline node *leftChild(node *n) {
    return n + n->left;
}

See how simple this is - it assumes left is measured in sizeof(node) units, otherwise you have to convert to and from (char *)

Where is memory allocated?

To make relative compressed pointers work, you need to know two things

malloc increases the size of the heap as necessary for small allocations, but uses mmap to allocate somewhere completely different for large allocations (say >=128k) so you need to avoid large allocations in your program

If your program needs more than 4Gb (more if using larger units), it may stop working, if a 32-bit integer offset overflows

Trickery