Ikke's Blog

Categories: Coding Corner, Docbook, Summer of Code 06

Jun 16
Regarding string duplication

This entry might bore most of you, upset some others, and could be useful for some. Sorry!!!

Last 3 days I've been reading (in my study pauses ;-)) on code optimalisation (both code speed and memory) and DSO pitfalls (pointers and some samples might follow later).

One of the things I read was a paper by Ulrich Drepper (Glibc guy), where one of the samples was about string duplication (strdup) optimalisation.

I looked into the Glib (no, thats not glibc) code to see how it was handled there, and found a simple, straight-forward, (unoptimized) implementation.
So obviously, I wanted to find out if this could be somewhat optimized. So I started my precious gvim, and made a testcase, which does some (well, a lot of) different duplications, both using g_strdup and my own little implementation.

An overview of what the test code does:

  • Do one simple strdup using g_strdup, and free the result (so the test is "fair", think of relocation time)
  • Copy, print and free a compile-time constant string, a variable string (argv[0]), and an empty string (strlen printed here) to make sure the code works fine
  • In a loop of 10000000 iterations, duplicate a constant string, a variable one (again, argv[0]) and an empty one, and free them

Why always a constant string, a variable one and an empty one? Simply because my implementation tries to handle these cases in the most efficient way ;-)

Here's the result:

nicolas@marslander ~/tmp $ gcc -o my_strdup_test -O2 `pkg-config --cflags --libs glib-2.0` g_strdup_test.c
g_strdup_test.c:9:10: warning: #warning "Using own implementation"
nicolas@marslander ~/tmp $ gcc -o g_strdup_test -O2 `pkg-config --cflags --libs glib-2.0` g_strdup_test.c -DUSE_G_STRDUP
g_strdup_test.c:5:10: warning: #warning "Using g_strdup"
nicolas@marslander ~/tmp $ ./g_strdup_test > /dev/null && echo -e "g_strdup_test:\n==============" && time ./g_strdup_test && ./my_strdup_test > /dev/null && echo -e "my_strdup_test:\n===============" && time ./my_strdup_test
foo = foo
./g_strdup_test = ./g_strdup_test
0 = 0

real    0m9.438s
user    0m8.968s
sys     0m0.064s
foo = foo
./my_strdup_test = ./my_strdup_test
0 = 0

real    0m5.906s
user    0m5.627s
sys     0m0.033s

I know 'time' is not a very good benchmark, but I guess the result is fairly obvious.
This result is +- the average, g_strdup version ranging between 9.4 and 9.6 seconds, mine between 5.8 and 6.1 seconds. This is a 30-40% speed gain, not wasting more memory.

Obviously, not all duplications would become faster. Actually, only the ones of strings which are constant at compile-time. In some applications this can be a major amount of g_strdup calls though.

I should note this "enhancement" is only possible when GCC is used as compiler as it uses some GCC-specific extensions. This is not an issue though, as on other compilers the code won't become slower :-)

The code I used can be found here. I added comments to make some things easier to understand (I hope), but the code is not "clean". A check for GCC should be added etc, but hey, this is just a proof of concept.

I really like these rather low-level optimisation things. They allow a lot of applications to become more efficient without changing the actual app, and low-level code is fun.
I'll read some more about this, and try to blog about interesting papers/techniques/... too, got some things in mind, but lack time now (yeah, those exams).

Luckily the end is in sight, and so is GUADEC :-) Booked my plane some days ago, still awaiting one email about lodging stuff. I'm so glad and thankful I'll be able to be there. Great start of holidays ;-)

Enough now, more algebraics and geometry to learn...

May 29
SoC, GUADEC and SystemTap

Little update:
1. I got a SoC assignment, at Gentoo. I'll be (actually I am) working on Gentoo's NetworkManager backend and integration into the distribution, next to more general NetworkManager hacking (although some people seem to dislike that somehow :|).
2. I might be able to come to GUADEC, jay!
3. Experimented with SystemTap today. After seeing the DTrace demos at Fosem06, I was fairly impressed. Systemtap is no DTrace-for-Linux yet, but I the scripts I was able to run were pretty promissing.

Little HOWTO (on Gentoo, but should work on other distributions too):
$ (cd into some project folder, I used ~/Projects/systemtap)
$ mkdir elfutils && cd elfutils
$ wget ftp://sources.redhat.com/pub/systemtap/elfutils/elfutils-0.120.tar.gz ftp://sources.redhat.com/pub/systemtap/elfutils/elfutils-portability.patch
$ tar -zxf elfutils-0.120.tar.gz && cd elfutils-0.120
$ cat ../elfutils-portability.patch | patch -p1
$ cd ..
$ cvs -d :pserver:anoncvs@sources.redhat.com:/cvs/systemtap login
(pass is "anoncvs", no quotes)
$ cvs -d :pserver:anoncvs@sources.redhat.com:/cvs/systemtap co systemtap
$ cd src
$ ./configure --prefix=/path/where/you/want/the/stuff --with-elfutils=/path/to/patched/elfutils
I used ~/Projects/inst as prefix (expanded), and ~/Projects/systemtap/elfutils/elfutils-0.120 as elfutils path
$ make
make failed for me (GCC4.1.1) due to usage of -Werror in elfutils. I had to add a -Wno-error in elfutils/elfutils-0.120/src/Makefile.am on the appropriate place (you should be able to do that yourself).
$ make install

Now we need a kernel with debug info, and kprobe support.
$ cd /usr/src/linux
$ make clean
$ make menuconfig
Configure the kernel like you would normally. Make sure you change the "Local version" under "General Setup". I added -dbg to the string I already got there ("-ck1-ikke2-dbg"), so your "normal" kernel modules won't be overwritten.
Then you need these options. This list might not be complete though:
- Instrumentation Support -> Kprobes
- Kernel hacking -> Compile the kernel with debug info
- Kernel hacking -> Compile the kernel with frame pointers (this might not be necessary)
$ make
$ make modules_install
The generated kernel will be big:
# du -sh /lib/modules/ /usr/src/linux/vmlinux
21M /lib/modules/
36M /usr/src/linux/vmlinux
and compilation (actually, linking) might take longer than normally. Used diskspace will be much higher too.

$ cp /usr/src/linux/vmlinux /lib/modules/2.6.18-ck1-ikke2-dbg/
(adjust paths!)

Now install the kernel like you normally would. I didn't put it as my default kernel in grub.conf though.

When you're done, reboot inside the new kernel. I booted into single user mode (by appending "1" to the GRUB line), just to be on the safe side.
Log in as your normal user on the console.

$ cd Projects/systemtap/src/examples/small_demos/
$ ~/Projects/inst/bin/stap top.stp -v
stap will show what it's doing. In the end, sudo will be called to insmod the generated module. Enter your password. Make sure the user is allowed to use sudo with the specific program (run with one more -v to see the specific call).

When it says everything's up and running, try switching console, type in some characters,... And see what system calls these actions generate.
As you're in single user mode, you can only use one tty. Run the stap instance in a screen session to get rid of this ;-)

Whe done, press ^C to quit. You can play around with some other sample scripts too, or try to write one yourself. I didnt manage to get some of the scipts working on my system yet though. Didn't think too much about it either :-)

Thats it, have fun!

4. Started reading "Linux Device Drivers, 3th edition", at chapter 6 now. Cool stuff, concurrency and locking (ch5) seems to be a fairly difficult issue. It is in userspace (threading), seems to be even harder in kernel space imho.

5. First exam tomorrow, "Rights of Intellectual Property". Wish me luck ;-)

May 16
More messaging

Been busy lately due to uni work, so not much hacking time. I did enhance that messaging thing a little (not working on other stuff I'd like to work on yet as they're potential SoC projects :-)).

wall, write and other pty based communication support still isn't in there as I didn't manage to get something working (yet). Must be doing something completely wrong somehow.

I did add a "Reply" option to the incoming messages though. Currently the reply dialog is not HIG at all, no I18N support, it's crap PyGTK code, but it does work somewhat.

Here's a little demo (1MB animated GIF screencast, thanks Byzanz (and Company)!)

I made a first "release" for people who's want to play with this. You can find the tarball here, but note it needs work: checking for Python stuff in configure.in, fixing Python code, adding I18N support, get the dialog code inside the C daemon, as using a helper is plain stupid (I use a helper as it's pretty easy to create a GUI using PyGTK quickly).

TODO: incoming message throttling (so one can't flood you using smbclient in a shell for loop), I18N (damn intltool 's been driving me crazy), nicer UI, other messaging "protocol" support, get a Telepathy backend out of this (jdub's idea),...

May 9
Good old messaging

Davyd talked about integrating good old messaging systems like talk, wall, write and even WinPopup into the GNOME desktop. As it looked like a fun thing to do, I got my hands down on it today.

I still couldn't figure out how to catch wall and other pty-based messages, but I'm sure I will be able to get them working too.

At the moment, WinPopup messages work:

Maybe in-time one should be able to click the message popup and get a simple window allowing the user to reply on the incoming message, but thats to be done later on, first I want to get wall and talk requests working fine.

A little change to smb.conf is needed for this (the "message command" line should be set, I'm using a Python script to send the messages), and one file in the D-BUS system.d to allow the user Samba uses to spawn the message command ("nobody" on my system) to send messages on the system bus.
Obviously pty-based messages shouldn't need a callout anywhere.

Current code isn't ready for release yet (at all), I'll try to get what I got into good shape asap.

Apr 26
Latin coding

Don't like Perl? Maybe you will now:

#! /usr/local/bin/perl -w

use Lingua::Romana::Perligata;

maximum inquementum tum biguttam egresso scribe.
meo maximo vestibulo perlegamentum da.
da duo tum maximum conscribementa meis listis.

dum listis decapitamentum damentum nexto
fac sic
nextum tum novumversum scribe egresso.
lista sic hoc recidementum nextum cis vannementa da listis.

Which is translated to:

print STDOUT 'maximum:';
my $maxim = ;
my (@list) = (2..$maxim);

while ($next = shift @list)
print STDOUT $next,

<< Previous Page :: Next Page >>


Who's Online?

  • Guest Users: 457


XML Feeds

What is RSS?