lkubuntu

A listing of random software, tips, tweaks, hacks, and tutorials I made for Ubuntu

The Perfect C Array Library

I love C. And I loathe C++.

But there’s one thing I like about C++: The fact that I don’t have to write my own dynamic array libraries each time I try to start a project.

Of course, there are many libraries that exist for working with arrays in C. Glib, Eina, DynArray, etc. But I wanted something as easy to use as C++’s std::vector, with the performance and memory usage of std::vector.

By the way, I am not talking about algorithmic performance. I’m writing this assuming the algorithms are identical (i.e. I’m writing purely about implementation differences).

There is a few problems with the performance and memory usage of the aforementioned libraries, the major one being that the element size is stored as a structure member. Which means an extra 4-8 bytes per array, and constantly having to read a variable (which means many missed optimization opportunities). While this may not sound too bad (and in the grand scheme of things, probably isn’t), it is undeniably less efficient than C++.

This isn’t the only problem, there are other missed optimization opportunities in the function (vs macro)-based variants, for example, calling functions for tiny operations, calling memcpy for types that fit within registers, etc.

All of this might seem like splitting hairs, and it probably is. But knowing that C++ can be faster, more memory efficient, and less bothersome to code in than C is not a thought I like very much. So I wanted to try to level the playing field.

It took me a rather long amount of sporadic work for me to create my very own “Perfect C Array Library”, that, I thought, fulfilled my requirements.

First, let’s look at some example code using it:

array(int) myarray = array_init();
array_push(myarray, 5);
array_push(myarray, 6);

for (int i = 0; i < myarray.length; i++) {
    printf("%i\n", myarray.data[i]);
}

array_free(myarray);

Alright, it might be a tiny bit less pretty than C++. But hey, this is good enough for me.

In terms of performance and memory issues, I fixed the issues I wrote above. So in theory, it should be just as fast as C++, right?

Turns out I missed one issue. Cache Misses. In my mind, if everything was written as a macro, it would, in theory, be faster than functions. I was wrong. Large portions of code inlined can result in cache misses, which will quite negatively impact the performance of the function.

So, as far as I can see, it is impossible to write a set of array functions for C that will be as fast and easy to use as C++’s std::vector. But please correct me if I’m wrong!

With that being said, this implementation is the most efficient I’ve been able to write so far, so let me show you the idea behind it:

#define array(type)  \
  struct {           \
      type* data;    \
      size_t length; \
  }

#define array_init() \
  {                  \
      .data = NULL;  \
      .length = 0;   \
  }

#define array_free(array) \
  do {                    \
      free(array.data);   \
      array.data = NULL;  \
      array.length = 0;   \
  } while (0)

#define array_push(array, element)                \
  do {                                            \
      array.data = realloc(array.data,            \
                           sizeof(*array.data) *  \
                             (array.length + 1)); \
      array.data[array.length] = element;         \
      array.length++;                             \
  } while (0)

The magic is in sizeof(*array.data). For some reason I never knew this was legal in C, but it does exactly what it says it does: it returns the size of type. Which eliminates the need to store this in the struct.

The code above is vastly oversimplified to demonstrate the idea. It’s very incomplete, algorithmically slow, and unsafe. But the idea is there.

To summarize, I am not aware of any way to write a completely zero-compromise array library in C, but the code above shows the closest I’ve come to that.

 

P.S. There is one problem I am aware of with this method:

array(int) myarray;
array(int) myarray1 = myarray; /* 'error: invalid initializer' */

There are 2 ways to get around this:

memcpy(&myarray1, &myarray, sizeof(myarray));
/* or */
myarray1 = *((typeof(myarray1)*)&myarray); /* requires GNU C */

Both of which should, under a decent optimization level, result in the same assembly.

Advertisements

4 responses to “The Perfect C Array Library

  1. wilkgr76 January 26, 2017 at 1:00 am

    “But there’s one thing I like about C++: The fact that I don’t have to write my own dynamic array libraries each time I try to start a project.”
    LOL. I will be honest, simplicity *was* one of the reasons I lent to C++ when I was comparing a C++ or C book.

    On a different note- Hangouts says you were last online 4 months ago. Did I annoy you too much?

    • Anonymous Meerkat January 26, 2017 at 1:12 am

      Haha yes, C++ is really nice in that respect :P

      And sorry!! I had actually logged out of hangouts with the intention of logging back in once I got my work done … I know this sounds bad, but I actually forgot to log back in (I only check my email every once every few days, and close the tab asap to conserve ram … it honestly didn’t occur to me I had forgotten to log back in). But no, it had absolutely nothing to do with you, I’m so sorry for the confusion!!

  2. grisumbras January 26, 2017 at 3:01 am

    You reallocate on *every* push to array? That’s insanity!

    • Anonymous Meerkat January 26, 2017 at 4:55 am

      Yes. Yes it really is. My actual allocation code (for every operation) is >200loc, so I figured I should keep it simple instead :P

      Hence the line “The code above is oversimplified to demonstrate the idea. It’s very incomplete, algorithmically slow, and unsafe” :)

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

%d bloggers like this: