# Recursive C #2

All day today i’ve been thinking how to implement reverse() function from yesterday post using no helper code. Still no result though. Except the realization, that this whole helper is very slow. Let’s make a test: reverse 103 character string 106 times, shall we?

time ./test2

real	0m26.846s
user	0m26.810s
sys	0m0.016s

Wow, that’s a lot. The reason for that is obviously the fact, that we call strlen() each time _rev() is called and strlen() has linear running time, so we are just adding that running time ever _rev() invocation without any gain because string length do not change during reverse() call. Not cool. We can add another constant parameter to carry initial string length:

static void _rev(char s[], int i, const int l) {
int k = l - 1 - i;

if (i > k) return;

char c = s[i];
s[i] = s[k];
s[k] = c;

_rev(s, ++i, l);
}

And then:

void reverse(char s[]) {
_rev(s, 0, strlen(s));
}

Quite simple. Here’s how it performs:

time ./test1

real	0m2.830s
user	0m2.825s
sys	0m0.002s

Fastaaaa! Mind you, that’s recursive solution which has function call overhead (tail recursion, anyone?) and is just an exercise.

So yeah. Optimize-shmoptimize.

Just started the preprocessor chapters. That should be even funnier, because of all the bugs possibilities. Really looking forward to it.

That’s it for today.

# Recursive C

Continuing with C. Last chapter i’ve finished is Recursion. There is an exercise which is to implement recursive function for reversing string in place. Here’s my solution:

void reverse(char s[]) {
static int i;
int k = strlen(s) - 1 - i;

if (i > k) {
i = 0;
return;
}

char c = s[i];
s[i] = s[k];
s[k] = c;

i++;
reverse(s);
}

Which is a bit… cheating. And that’s due to the fact, that function is not supposed to keep any kind of state. Look at static int i; which i use to keep track of which position is currently exchanging. This is not very good. Is there a better way? If i would be using Scala, i could just create nested function. In C i have to use static function, which is essentially private.

Here is goes:

void reverse(char s[]) {
_rev(s, 0);
}

static void _rev(char s[], int i) {
int k = strlen(s) - 1 - i;

if (i > k) return;

char c = s[i];
s[i] = s[k];
s[k] = c;

_rev(s, ++i);
}

Funny enough changing ++i in _rev()‘s last line, to i++ will lead to Segfault because recursion never ends. Why not stack overflow? Here is why.

That concludes recursion for now. Source file here: reverse.c.

That’s it for today.

# Playing with Unity

Today i was playing with Unity. This is a game engine, which is simple to use and it can run on almost any platform (yeah, even WP8 and Wii). Sure enough this comes with it’s own price, both dollar and performance, though i don’t have any hard numbers on latter. But just the ability do “write once, run anywhere” is head-lightening. Especially because Windows Phone.

Just for the sake of learning something new i have followed a simple tutorial on Unity site on how to build collecting game. You control the ball with arrow keys and collect spinning boxes. Got them all – you win. It’s rather primitive, i mean, i can’t even play with friends or take payments from those players who have stuck. Anyway, here is the link to the game itself: Rollerball (needs UnityPlayer). Just don’t get too addicted.

Code is on the github. It uses C# since that what they have used in tutorial, but Javascript will do too (i guess they can be mixed in one project, however i don’t see why anyone would do that).

Building games is really hard task, even having tools like Unity, which does tons of work for you. Design, arts and testing will take years, unless you are doing time killer game, in which case it will take only months.

That’s it for today.

# One day one code #17

Here we go again, skipped 5 days. Had a very nice trip to California: San Francisco, Mountain View, Santa Cruz and Carmel. I’ll have to write a post with photos later.

Today is ODOC time. I am done with the reverse Polish calculator from the last update. Here is it: calc.c. It wasn’t too hard. The main problem is lack of free time, frankly. As soon as you understand how things should work, it’s easy to extend existing solution.

Historical note: Reverse Polish notation

Switched from Vim to MacVim, which has all the same great features plus:

• point and click;
• mouse scroll;
• “usual” copy-paste shortcuts.

That’s it for today.

# One day one code #16

Time machine update: i’ve managed to get almost all my data back. Right now all 45Gb of music is downloading. Also in this time of cloud based services, like password managers and Dropbox, there is not many things you can actually loose. So computers are pretty much disposable (like Apple wants you to think about iPhone), it’s so easy to upgrade and safe. Almost always.

Back to the main topic of this blog. Coding. Bunch of stuff going on with Sonata. I am still pretty serious about writing a post about that later someday. On the other hand C learning is not going too fast. But i have managed to make progress on the calculator. Added modulus operation, negative numbers support. They also have added stack operations as a part of this exercise, so get(), clear(), swap() etc. are done too. The code is not thread safe by the way. Which is something i recon is hard to do (and is out of scope of current chapter). I will post the code in this blog when all things are done.

Tomorrow i am visiting San Francisco. So most probably will not have too much time to spend on coding. So i will post code-related photos.

# One day – one code #12

Can you believe it? It’s been almost two weeks. I am starting to feel like i am writing “learn something in 21 days” book. Maybe some day…

Right. Today i was doing some C stuff again, since this is the main goal of all this nonsense. By the way – there is only half of the book left to read and i don’t know what’s going to happen next. Guess that would be perfect time to use the knowledge from the book.

Right, so i am in a middle of functions chapter and i have to extend the calculator which is given as an example. The biggest challenge will be to add functions and variables. Because this requires syntax convention, and, well, implementation. Or maybe it’s easier: just detect the non-digit characters and check if there an opening parenthesis for function… i’ll think of something, but tomorrow. Today i just fixed atof() function to handle scientific notation.

Some time ago i’ve bought Steve Wozniak’s autobiography “iWoz”, which is a big fun to read, so i’ve spent several hours reading it today instead of coding. You can find it on Amazon used for about \$10 and i would recommend reading it (i find it a lot more interesting read than “Steve Jobs” book).

That’s it for today.

# Some C and some C++ (hhvm).

Nice day today. Just look at this fog:

Really nice day today. Too warm to go shredding though. Well, i guess you can’t always get what you want.

Alright, back to the coding stuff. Learning C. Made couple exercises. Nothing special. I bet pointers are much more fun than just writing a function that returns value through it’s parameter (character array). Scratched the surface here.

assert.h is really helpful module. So i can write my functions and then put all tests in main() and be sure they work. Poor’s man unit testing. But since i haven’t tried writing my own modules that’s all i have now.

Next thing is hhvm. I’ve managed to compile it overnight. And it even works. I was surprised that there is a huge lag. Just invoking it on empty PHP file

<?php
die();

takes around 300ms. Just PHP 5.3.10 (which installed on my virtual ubuntu box) is 3 times faster on this not particularly hard task. I was also trying to make measurements with ‘fold‘, but picture remained unchanged. Which does not make any sense, except maybe that i am not testing it properly. Well, will see how it will work in server mode later.

Here is a bunch of documents on how to install hhvm on different systems: https://github.com/facebook/hhvm/wiki/_pages. I am pretty sure that hhvm will get only better and we will eventually all switch to it. But not for another couple years for sure.

That’s it for today.

# Lazy day? Friday!

Very unproductive day today. I had a plan to play with hhvm on Openshift. But two problems:

1. the gcc there is older than hhvm needs; and
2. when building new gcc i hit 80000 user files limit.

I still not quite sure how they want others to build cartridges for the platform.
End of story here for now.

But, i’ve managed to get hhvm erm… building on the Ubuntu virtual machine. Well, frankly speaking it is still building, and i suppose this will happen for another hour or so.

But, i’ve been reading the C book meantime and doing some exercises. Which is very helpful. Now i can write valid C programs like this one:

#include

int main(void) {
{
{
{ {{ printf("%s", "I was surrounded by curly brackets\n"); }} }
} {{{ printf("%s", "But managed to escape\n"); }}}
}
return 0;
}

Meanwhile hhvm build progress have come up to 60% and my laptop battery level is 7%. I wonder who will win?..

That’s it for today.

Here is how my laptop saluted me in the morning couple days ago:

# Learning C even more

Continue to read C book. Bitwise operations today. Not a very hard, but a crucial topic. Every programmer should be able to do binary math. Well, I have learned all this stuff in high school and than again in university, but doing web development relaxes the muscle which ticks in tact with CPU.

So I was playing with bits, mostly on paper, imagining how programmers did their job in times of PDP-7, times were men were men; when this idea came: let’s build some function to determine if the number is even and do it quick.

My first try looked like this:

bool odd(int i)
{
return 1 & i;
}

This takes about 11.5 seconds on my Core 2 Duo, and it’s 1 second slower than traditional i % 2 == 0 solution. Who said re-inventing the bicycle?

Now, what does it actually do under the hood? Here’s how my odd function looks like:

_odd:
0000000100000f00	pushq	%rbp
0000000100000f01	movq	%rsp, %rbp
0000000100000f04	movl	%edi, 0xfffffffffffffffc(%rbp)
0000000100000f07	movl	0xfffffffffffffffc(%rbp), %edi
0000000100000f0a	andl	\$0x1, %edi
0000000100000f10	movl	%edi, %eax
0000000100000f12	popq	%rbp
0000000100000f13	ret

I have used otool to generate this disassembly listing, but gcc can do it too with -S key
Ok, it moves stuff around and does “andl” which corresponds to the one operation, the function actually does. Interesting… Now what’s going to happen if I will ask gcc to optimize things a bit? `gcc even.c -O1 -f even` yields this:

_odd:
0000000100000ef0	pushq	%rbp
0000000100000ef1	movq	%rsp, %rbp
0000000100000ef4	andl	\$0x1, %edi
0000000100000ef7	movl	%edi, %eax
0000000100000ef9	popq	%rbp
0000000100000efa	ret

Which runs just under 3.5 seconds. By removing memory access commands, gcc made this function three times faster!
Interesting enough here’s how ‘traditional’ function work after compile optimization:

_even:
0000000100000ef0	pushq	%rbp
0000000100000ef1	movq	%rsp, %rbp
0000000100000ef4	andl	\$0x1, %edi
0000000100000ef7	xorl	\$0x1, %edi
0000000100000efa	movl	%edi, %eax
0000000100000efc	popq	%rbp
0000000100000efd	ret

Which is just one operation longer, but runs a bit faster still. Well, that’s something i will have to dig into next time.

Today’s takeouts:

• don’t re-invent the bicycle;
• re-invent the bicycle only if you want to understand how things work;
• C is fast, but using your compiler right is even faster;
• writing fast code is hard (for obvious reasons);
• is there a good C IDE for Mac?

# Fold. End of story.

Finally. That took only four posts and several hours. Prototyping in familiar language to get grip onto the algorithm totally worth it, at least right now, while i still noob in C. Here is how my fold.php compares to my fold.c to local Mac OS fold command:

\$ time cat big.txt | php fold.php 12
real	0m22.143s
user	0m8.559s
sys	0m2.682s
\$ time cat big.txt | ./fold
real	0m7.495s
user	0m2.101s
sys	0m1.183s
\$ time cat big.txt | fold -w 12
real	0m5.037s
user	0m1.659s
sys	0m0.959s

There are obviously optimizations to be made, will see later. Also i am using default compiler settings, whatever difference that makes. The “big.txt” file is this one, 6.2Mb.

Here’s the source code: fold.c.

That’s it for today.