Archive

Posts Tagged ‘ruby’

Array map in C

October 16, 2010 4 comments

Last year, I got “The Ruby Way” (link) as a gift to myself. I’m not a major Ruby freak, but there are some cool things about it and I really enjoy Ruby in general.

As I read my way through the book, I remember reading about array map. Array map is cool, it let’s you do things like

my_strings.map {|s| s.strip! }

Which is roughly equivalent to

new_arr = []
my_strings.each {|s| new_arr.append(s.strip) }

Of course, this is kindof a stupid example and you can do MUCH more interesting things with Array#select or Array#reject – like write a one-liner to find all the phone numbers in an array that start with 351 or don’t hash to the same bucket, whatever. Anyway, I remember being really excited about array#map for some reason when I read that chapter. And whenever I get excited about something… weird things tend to happen. 🙂

See, I spend a lot of time writing programs in C. It’s a great language, and pretty much the only option in the kernel/filesystem/embedded world. So when I see a cool feature in another language (like Array map), I think “gee, wouldn’t it be awesome to have that in C.”

Being a frequent C coder, I do a lot of things with/to/because of arrays – and the two most common things I do with arrays are indexing and looping. Indexing is cool because it’s an O(1) operation, and that’s great for writing fast code that uses a lot of RAM. Looping, on the other hand… well, it’s usefulness depends on the problem at hand, but this is pretty common:

for(i = 0; i < count; i--);
   do_stuff_with(&my_array[i]);

Ten bonus points if you can spot the subtle bugs I put into this trivial for loop. Hint #1: there are three of them. Hint #2: the program (or kernel/firmware/driver) will not do anything useful. Beyond the obvious problems with this code (and how easy it is to accidentally slip in the extra semicolon), writing for loops gets really tedious and old sometimes.

So I keep thinking that it’d be neat to write a C library to implement Array map, select, reject. But then I start thinking about the code. To do this properly, you could use macros, something like

#define ARRAY_MAP(arr, size, func)                       \
        for(int i=0; i<(size); i++) (func)(arr[i]);
.
.
my_arr = malloc(sizeof(u32)*10);
memcpy(my_arr, arr1, sizeof(u32)*10);
ARRAY_MAP(my_arr, 10, do_stuff);

Well, that looks like junk and doesn’t really do much. You could implement it with callbacks to avoid the evils of macros, but that doesn’t help you much either. You still have to handle memory allocation, deallocation, type safety, and in the end the code doesn’t look any simpler.

Not to mention, for anything really high performance (filesystems, OSes, etc) you generally want to avoid looping over arrays in general – the Linux kernel now has a native hash table and circular buffer (among other fun data types). If performance is critical, use a better/faster/cooler algorithm and a more appropriate data type.

So I’m back to square one, array map in C is pointless. If you don’t care about runtime, just use arrays and loops, or use Python or Ruby.

But array map/select/reject is so cool… wouldn’t it be neat in C?

infinite_loop:
   printk(KERN_ERR "/me wants array_map in C");
   goto infinite_loop;

Best,

Atto

Categories: Uncategorized Tags: , , , ,