libdynamic – vector

I think the lack of simple and basic dynamic data structures is a major reason why people sometimes struggle with programming in C.

To take a simple example the naive task of splitting a string into words is near trivial in C++ using the standard library, while in C you are challenged with how to dimension the resulting array. In most cases likely the solution here would be to declare a fixed size array with a MAX_WORDS constant size, and later when the parsing is done and you know the number of words, declare a new array into which you copy the result, and then return. Hardly an elegant solution, and you end up with making difficult assumptions regarding how many words a line realistically can contain.

std::vector<std::string> split(std::string line, char delim)
{
  std::vector<std::string> words;
  std::istringstream iss(line);
  std::string token;

  while (getline(iss, token, delim))
    if (token.size() > 0)
      words.push_back(token);

  return words;
}

Splitting a line into words in C++

Low-level data structure libraries in C

Low-level data structure libraries in C are most often distributed as macros. A commonly used example being the BSD queue.h implementation.

One major reason for this is that C, being a system programming language, requires the overhead of low-level operations to be as small as possible. Macros will be optimized when included in code, whereas a linked library typically won’t. Adding the overhead of a function call for a small operation is often not acceptable, and for example failing to inline a subroutine in an inner loop can result in performance degradations of an order of magnitude or more.

Another common reason is to promote the use of polymorphism, allowing code to be reused for different data types. An alternative approach to this is using opaque pointers which in most cases, however not all, can achieve the same result.

Unfortunately macros in C, though useful at times, have serious limitations.

  • Use cases often include magical macro expansions that are difficult to understand resulting in confusion and bugs
  • Macro code often consists of badly indented, highly compacted, large chunks of code, difficult to read and maintain
  • Use of compiler specific macro extensions is encouraged resulting in non standard and less portable code
  • Good exception handling is difficult to near impossible

As a result large macro libraries aren’t the most attractive parts of the C ecosystem.

Link Time Optimization

Link Time Optimization (LTO) is a relatively new type of compiler functionality which enables, as the name would imply, additional optimization at link time.

Previously optimization has been done at compile time only, i.e. when creating object files from source files. In the case of libraries this means that the compiled code being installed into the system can’t be optimised further when used in a project, which can lead to the loss of huge potential performance gains as mentioned above.

With LTO you can, ideally, overcome these limitations. You can write low-level libraries as well structured code, compile and install them, and still have programs reuse the library code in an optimized, case-to-case specific, way.

Worth noting is that LTO works when the compiler is statically linking object code into a program, not when dynamically linking object dependencies at run-time, which doesn’t involve the compiler. In other words for this to work we have to install static versions of libraries, and since compilers typically prefer dynamic versions when given the choice, static versions only.

libdynamic

Repository: https://github.com/fredrikwidlund/libdynamic

libdynamic is an attempt to implement dynamic data structures using LTO instead of creating ugly macro chunks.

In this first release I’ve included a C vector implementation, roughly based on the C++ std::vector interface.

vector *split(char *line, char *delim)
{
  vector *v;
  char *token;

  v = vector_new(sizeof token);
  for (token = strtok(line, delim); token; token = strtok(NULL, delim))
    vector_push_back(v, &token);

  return v;
}

Splitting a line into words in C using libdynamic

Vector operation performance benchmark

Repository: https://github.com/fredrikwidlund/libdynamic_benchmarks

The main vector operation that is interesting from a performance perspective is growing the vector size dynamically. This operation should be O(1) on average, and reasonably fast.

As a micro-benchmark, to verify the use of LTO, I’ve compared the C++ std::vector to libdynamic vector in this regard.

vector_grow

Cost of vector grow operations using C++ std::vector and C libdynamic vector

Here we see the cost (time in seconds) of incrementally adding 500M integers to a vector.

Average push_back() cost here in nano-seconds

  • C++ std::vector – 3.07 ns
  • C libdynamic vector – 1.74 ns

It seems the implementations are equally fast with the difference being the resize operations that exponentially grow the allocated memory used for the vector. In any case the libdynamic performance seems to be fast enough, despite not using macros. Indeed using macros would not lead to any performance gains.

Difference of enabling compiler LTO

Let’s try disabling LTO to see if there is a difference.

vector_grow_flto

Cost of vector grow operations using with LTO disabled and enabled

  • C libdynamic vector (without LTO) – 10.1 ns
  • C libdynamic vector (with LTO) – 1.76 ns
Advertisements

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