art_map: Adaptive Radix Tree implemented as a std::set/std::map container

TL;DR: https://github.com/justinasvd/art_map, 10x faster searches than std::map, patches welcome!

I was happily hacking away at my ART implementation UnoDB when Justinas V. Daugmaudis noticed it and decided to implement a C++ container-style data structure using it. This thought had crossed my mind previously too, but the project looked definitely not-fun to me due to the level of C++ knowledge required, which I, a finger-tracking reader of "Effective Modern C++" do not possess. Now Justinas, a Boost contributor, knows his C++ at the language lawyer level, in fact I don't know anyone better suited to pull off a proper C++ container implementation.

There are significant differences between C++ container needs and what UnoDB provides with its in-memory-DB-ish interface and whole Optimistic Lock Coupling business, so Justinas could not just wrap my implementation. He ended up taking my source code, removing OLC and leaf node code, and writing some actual proper C++ in its place, with my surviving code being mostly internal node algorithms. He also replaced the node type bytes with tagged pointers, reducing node sizes, something I also plan to do. In other words, UnoDB now has all the attributes of a successful open source project-it was forked! /s

We exchanged ideas in the process, with me implementing several performance-related suggestions of his (I lost one bet), him following my development too, all for the better.

I also provided a fuzzing service for Justinas-by wrapping art_map into UnoDB-compatible interface and plugging it into my fuzzers. The API surface tested this is too narrow for my liking but still getting the important insert/delete/search code paths. And the fuzzers, the same ones I praised in my previous blog post, came up with absolutely nothing, to my shock. That tells something about writing code in a, uhm, mathematical way. Yet, he claims it's alpha and could kill your cat.

Besides collaborating with art_map I also added several OLC-specific optimizations, did major internal cleanups from Justinas code review, and changed the license to Apache 2.0 because someone asked me to.

On fuzzing

I am getting convinced that fuzzing is the third best thing after writing tests and using sanitizers a developer can do for their project quality. I'll start with MySQL, but it was my Adaptive Radix Tree implementation that really drove the point home.

I first encountered fuzzing - well maybe not fuzzing as such but random testing - in late 2011, when at Percona developer meeting in Prague Stewart Smith told us about Random Query Generator (RQG), introducing it as "90s Microsoft technology" - referring to a VLDB'98 paper. Stewart then proceeded by picking a random "crash happening intermittently, no clear reproduction steps" Percona Server bug, writing random test grammar for it, and getting a test case - in less than an hour.

As nice as it was, RQG still required maintaining test grammar, which as far as I can tell, happened very rarely, so Percona did not come close to using its full potential.

Then, a few years later, Roel Van de Paar had a realization that instead of bespoke maintenance-hungry grammar we could use a simpler mutating tool which then would need a large corpus to be effective - and Roel had this idea of taking the whole of MySQL MTR test suite as the seed corpus. He named the tool pquery. It was brutal, easily producing, IIRC, 60-80 crashing test cases per hour of fuzzing. Roel and his team duly sorted them, filed the bugs for MySQL and Percona Server, and then proceeded to watch in frustration as release crashers were being made private by Oracle (at least they were getting fixed), and debug build bugs were being ignored both by Oracle and Percona, myself included. This was not good - for effective fuzzing one must fix the initial crashes to let the fuzzer proceed past them. I see that currently Roel is working with pquery over at MariaDB, and I sincerely hope they do better than we did.

Later I wanted to try out fuzzing for my Adaptive Radix Tree. Most fuzzers work with the notion of input data strings rather than sequences of API calls, which suggests not to bother with the fuzzer framework to avoid the need to write the string-to-API mapping code. Instead, do a random sequence of API calls from scratch like John Regehr does, which will catch (some? most of?) bugs, but will not help with reducing test cases nor will be coverage-driven.

Enter DeepState. A data structure fuzzer written in it will look about the same as John Regehr's one, so no hairy string-to-API conversions, and it will have an actual pluggable fuzzing framework (AFL, libfuzzer, etc.) underneath, with the option of a brute force fuzzer too. There is also a tool to reduce interesting test cases. It all sounded like a very good fit for data structure fuzzing and so I used DeepState to write an ART fuzzer, with brute-force fuzzing at first for simplicity.

I had thought ART was in a reasonably good shape. The implementation was small and not too hard to reason about. I had written ART code with test-driven approach, with close-to-100% test line coverage and reasonable branch coverage too. Sanitizers and Valgrind were silent. How bad could it be?

Turned out, two-nasty-crashing-bugs-bad [1], [2], with an extra non-crashing logic bug [3] on the top.

Unfortunately, DeepState was–and still is–not without its share of issues, thus I stopped at that point, and did not bundle DS as a dependency. I did run it on my laptop regularly though.

Recently I implemented Optimistic Lock Coupling ART that uses Quiescent State-Based Reclamator (QSBR) for managing memory and find myself struggling with intermittent QSBR crashes. I try to assert() and sanitize my way out of it, but make no progress. Then I get an idea to fuzz it. Now QSBR is inherently multithreaded and fuzzing strongly dislikes that because it's a major source of non-determinism. But my QSBR implementation is serialized by a big internal lock anyway, which is bad in general, but for fuzzing, there is a only a small number of possible thread switch points, and no two threads run in parallel inside QSBR. Thus a fuzzer can launch many threads, block them all, and wake a selected thread for a selected action one at a time. Excellent, let's code that. It is likely that such fuzzer will stop being useful if/when I remove the QSBR global mutex later, but hopefully it will have produced some test cases by then.

At the same time I try to switch to libfuzzer as the DeepState backend. I chose it over alternatives because it's a part of LLVM, avoiding one more external dependency. DeepState is not without some issues in this area too, however there are strong advantages over brute force fuzzing:

• The test corpus can be persisted. In brute force fuzzing it is randomly generated every time anew.
• Fuzzing saturation can be inferred when it stops producing new paths through code for a while. With brute force fuzzing there is no insight to that.
• Presumably it will go through new paths sooner than later because it's coverage-driven.
• It can dump its coverage info, which can then be checked for suspicious omissions to improve the fuzzer.

With all that, and after a couple of iterations to improve the fuzzer, it found what I was looking for: a bug in QSBR, where the second-to-last thread quitting will cause premature deallocations. I had introduced the bug as a mistaken optimization and had been staring at that code for a long time without suspecting a thing.

Lessons learned:

• If it's fuzzable, fuzz it, no matter how "bug-free" you think it is. It is not bug-free.
• For fuzzing a data structure, I haven't found a better introduction than John Regehr's one. There is also a DeepState-specific one.
• Start with the simplest fuzzer to catch the low hanging fruit first and to get the motivation to use more advanced ones.
• Fuzzer is another client to the thing being fuzzed. While being developed, unnatural and broken things in API will be caught, leading to improvements there.
• A fuzzer works when it actually checks and catches incorrect state. For that, assert the heck out of the internal state in the implementation, and external one in the fuzzer.
• If there is, say, an API to dump some internal state–and where it is not practical to cross-check that the output is consistent–dump it anyway to a null sink for its internal asserts and for AddressSanitizer.
• Dereference all the valid pointers even if you don't know their contents, again for AddressSanitizer.
• If fuzzing a data structure, it's easy to have an oracle: an alternative implementation that mirrors all the operations and catches any differences.

Optimistic Lock Coupling for Adaptive Radix Tree

So I had so much fun writing the Adaptive Radix Tree and later SIMD'ing-optimizing it, that I decided to implement a concurrent version of it: ART with optimistic lock coupling, from a paper by the original ART authors [1]. That took the fun to the whole new level.

Each tree node has its own lock, of the kind described below. While traversing the tree, the parent lock is taken, then a child lock, then the parent lock is released, then it repeats ("lock coupling/crabbing"). ART is not a B-tree in that any modification will be contained in three nodes at most, which limits how much of the tree will be write-locked in the worst case.

Now it also would be good for reads to scale, and for that a regular RW lock where read locking writes to memory will not be good enough. So OLC ART uses a different synchronization primitive, which the paper calls the Optimistic Lock: it is a mutex with a version counter, implemented in a single machine word. Writes lock the mutex, bumping the counter, at the end they unlock and bump the counter again. Reads check the counter, copy out what they want to read, and check the counter again to see whether their copy is consistent and usable or whether they have to restart. This is just like Linux kernel seqlocks (sequence locks), which the paper fails to mention. There is one extra feature compared to seqlocks: an unlock can mark the node as obsolete, which forces all concurrent readers and waiting writers to restart their algorithms and no longer try to lock this node.

Now those obsolete nodes have to be garbage-collected somehow. For that, I implemented Quiscent-State Based Reclamation (QSBR), in which each thread periodically declares that it holds no live pointers to the shared data structures. Once all threads do that, the epoch advances and the oldest deleted nodes from two epochs ago are reclaimed. Ironically my QSBR implementation uses a big global mutex for itself, killing scalability, so no fun OLC benchmarks unless I get around to rewriting that part.

Optimistic Locks / seqlocks are not that straightforward to express in the C++11 memory model. Luckily for me the hard work has been done in [2], discussing the correctness and the trade-offs of different implementations. A fun thing is that all protected data in the critical sections needed to be declared as relaxed C++11 atomics. But I also keep the original single-threaded ART around and did not want to copy-paste otherwise identical node-level algorithm implementations between the two. This led to the following C++ template gem (well maybe a turd) of overengineering: I wrote two class templates: relaxed_atomic and not_atomic. The former is like std::atomic with a difference that all operations use std::memory_order_relaxed instead of std::memory_order_seq_cst. The latter is like std::atomic except that its implementation is not atomic at all. Then I templatized node classes on this atomic policy, and, one thousand glue code lines later, avoided the copy paste. Profit!

Debugging this whole contraption took me a while, and I cannot say with certainty that I'm done. I know I have advanced a bit into the long tail of possible concurrency bugs, but I have no idea what's out there that I haven't seen yet. I attacked this in force, wrote the stress tests, employed all the sanitizers, ThreadSanitizer included, everything is running in CI (BTW moved from Travis CI to Github Actions like the rest of world), and yet. Usually it is that writing own concurrency primitive is as good an idea as a land war in Asia, but here it caused only a smaller part (thanks to following [2], I guess) of the issues: reading protected data and not acting on it until successful read unlock is for some reason harder than it sounds. But it was QSBR where dragons lived.

Now what? I think I should rewrite QSBR to remove its Big Kernel Lock, then look at the Optimistic Lock spin loop, which currently consists of _mm_pause(), then check if it actually scales? More fun awaiting!

[1]: Viktor Leis et al, The ART of Practical Synchronization

[2]: Hans-J. Boehm, Can Seqlocks Get Along with Programming Language Memory Models?

[3]: Sorry for not figuring out how to make proper footnotes in Blogger

Optimizing Adaptive Radix Tree Implementation for CPU

For a long time in my career I wanted to learn how to better optimize for the CPU. I was lucky enough to work in places where performance matters, however it was almost exclusively I/O performance, scalability, big-O, maybe an occasional memory access pattern issue-not quite the CPU itself.

So I took my Adaptive Radix Tree implementation, and wrote a bunch of isolating microbenchmarks for all the interesting code paths. Then I tried to see how can I make things faster, on a bare metal Sandy Bridge server (AVX instruction set, state of the art, I know). Some random things I learned (or re-confirmed for myself) in the process:

• ART, as a node-jumping tree structure, is cache miss-bound as sizes increase. Yet it is possible to do CPU work with L3/L2/L1D-fitting tree sizes.
• An "obviously faster" code change is not such frequently enough so that not re-measuring will bite you. The more "obvious", the more discipline is required to rerun the numbers. This point is beaten to death and yet never goes away.
• I couldn't really figure out the restrict keyword. I understand the theory behind it, yet when I put it in the code, surprises happen. Most of the time it perturbs code generation in a random insignificant direction. Including the cases when it should have been a no-op. It is not helping that it is absent from the C++ language, existing as a compiler extension only.
• Compiler generates different code for, say, unsigned vs uint8_t local variables whose all allowed values fit into uint8_t. It should be able to pick the optimal width itself, but it does not appear to do that.
• Well-predicted branching code appears to be faster than branchless code, which appears to be faster than poorly-predicted branching code. It might be easier to tell if some code is poorly-predicted than if some code is well-predicted.
• Some branchless code will trade conditional jumps for conditional data dependency chains (e.g. Intel CMOVcc), which is still an improvement, but less so.
• Looping is faster than recursing
• Sprinkling SIMD intrinsics in the code for not-quite-vector data is a thing, it is also a thing that the compiler is not likely to do for you. The smallest data amount which I saw to be processed faster in SIMD was four bytes (Node4 search in ART - exact same algorithm that the paper proposed for Node16 search, just narrower). It helps to view SIMD instructions not as something exclusively reserved for long vector loops, but as specific tools in the general purpose instruction set.
• Conversely, putting a bunch of bytes in a general-purpose register and treating them as a vector of independent bytes is also a thing, it even has a name: SWAR (SIMD within a register).

My dotfiles

My dotfiles

I started using Emacs in 2001, and have been using it for two decades continuously, circumstances permitting (in 00s-early 10s Emacs support for Java and C++ was terrible). I have kept its configuration under source control since 2009.

All that time my Emacs knowledge was quite superficial, and the configuration was mostly copy-n-paste from various online bits. Two years ago I decided that I cannot afford not to know my main editor properly, and read its manual and Emacs Lisp reference cover to cover. I did not become an expert, but at least I got a map for the territory. This enabled me to make notes of and fix numerous long-standing annoyances instead of accepting them.

At the same time I started adding various work-related (MySQL back then, Aerospike now) utilities. Still later I started adding new system configuration notes for macOS and Linux, and untangled the whole mess with the help of GNU Stow.

Now I have added a README.md and so my dotfiles are in good enough shape to be public!

The various forms of __builtin_prefetch on x86_64

Recently I learned that the GCC compiler intrinsic to prefetch data into CPU cache,  __builtin_prefetch, can actually take two optional extra arguments: rw and locality. This is slightly embarrassing for me, because as far as I can tell, the intrinsic had three-arg form from day one, starting with GCC 3.1, released in 2002.

The rw argument can take 0 or 1 value, hinting whether the anticipated memory access is going to be read (0, the default) or write (1). locality can be 0, 1, 2 or 3, with 0 hinting that the memory will be accessed just once, 3 (the default) asking to keep it cached as much as possible, 1 and 2 being in the middle.

The next thing I didn't know was what the different argument values compile to on x86_64. With GCC 10 on Godbolt I found:
__builtin_prefetch(ptr);        // prefetcht0
__builtin_prefetch(ptr, 1);     // prefetchw
__builtin_prefetch(ptr, 0);     // prefetcht0
__builtin_prefetch(ptr, 1, 0);  // prefetchw
__builtin_prefetch(ptr, 1, 1);  // prefetchw
__builtin_prefetch(ptr, 1, 2);  // prefetchw
__builtin_prefetch(ptr, 1, 3);  // prefetchw
__builtin_prefetch(ptr, 0, 0);  // prefetchnta
__builtin_prefetch(ptr, 0, 1);  // prefetcht2
__builtin_prefetch(ptr, 0, 2);  // prefetcht1
__builtin_prefetch(ptr, 0, 3);  // prefetcht0

Next let's check Intel docs on these instructions:
PREFETCHT0: prefetch to all cache levels.
PREFETCHT1: prefetch to L1 and L2. Of course if a particular implementation has an inclusive L3 cache, it will end up there too.
PREFETCHT2: Intel's Software Developer's Manual states: prefetch to L1/L2/L3, "or an implementation-specific choice." Intel's Optimization Reference Manual states that this "identical to PREFETCHT1," that is, prefetch into L1, L2, but not necessarily L3, depending on its inclusiveness.
PREFETCHNTA: the SDM tries to abstract from actual hardware a bit by describing this as "prefetch into non-temporal cache close to the CPU, try not to pollute the regular caches." The ORM explains what it means in practice: on non-Xeon, prefetch to L1, bypassing L2, and on Xeon, prefetch to "L3 with fast replacement" - I have no idea what "fast replacement" means here.
PREFETCHW: according to the SDM, prefetch into L1 or L2 and invalidate other instances of this cache line. And according to the ORM, prefetch into all levels and invalidate the same. The invalidation is of course why this is a write-specific prefetch instruction, saving an invalidation later at the actual write time.

Some common properties of all these instructions are as follows. First, prefetch stride. I always assumed it was 64, that is, L1 cache line size. Docs added a few wrinkles to that, hopefully all historical: 1) the minimum is 32 bytes; 2) NetBurst Pentium 4 used to prefetch two cache lines; 3) It should be interrogated by CPUID. In practice everyone seem to agree it's 64 nowadays.

Instruction scheduling. The Intel docs seem to be last updated for Pentium 4 (twenty years ago). For that, they state "insert a PREFETCH instruction every 20 to 25 cycles." Finding no info at the official sources, I consulted Ander Fog's instruction tables, where they are listed with 0.5-1 clock cycle per instruction per thread reciprocal throughput. That is, except for Ivy Bridge, where it's 43 for some reason. Anyway, it does not seem to be particularly harmful to issue several prefetches without interleaving with computational instructions these days.

Ubuntu 10.10 on Lenovo ThinkPad T410

Just bought a laptop for my new job. Due to requirements of the job, Linux and Mac OS were the two top options. I went with Linux and, as hardware compatibility might get tricky, chose Lenovo as I've always had good experience with ThinkPad Linux compatibility.

The model is T410 with discrete Nvidia graphics and fingerprint reader. So what I had to do to get everything working?

1. Installed Ubuntu 10.10 x64 and all updates.
2. Enabled proprietary drivers.
3. Brightness controls (Fn+Home/End) did not work out of the box. Followed this to fix them.
4. Fingerprint reader required additional setup, followed instructions over there.
5. Hard drive shock protection: sudo apt-get install hdapsd. Instructions here.

As you can see, not that many steps by Linux standards.

Update 2011-03-29: hibernate broke with various ACPI errors in the logs. Fixed by sudo add-apt-repository ppa:ubuntu-x-swat/x-updates and then updating the system. This upgraded Nvidia drivers from 269.04 to 270.29 (beta!). As a bonus, it also made to disappear zillions of NVRAM invalid context switch messages from the logs.

Update 2011-05-04: the battery indicator sometimes loses its mind (shows 0% and 5 hours remaining battery, disappears completely, etc.) Besides not knowing how much battery left when it disappears, this is mostly harmless.

Ubuntu 11.04: I'm not upgrading just yet because of this, this, and also because I have not reviewed the additional PPAs I use for 11.04 binaries. Also please review the other bugs in release notes to see if they apply to you.

Update 2011-07-18: the X started to crash at every startup with the nvidia driver being the culprit. The workaround is sudo apt-get remove binutils-gold; sudo dpkg-reconfigure nvidia-current. And no, I don't think that it is the gold linker that is faulty here...

Excellent article on the DOs and DON'Ts of Summer of Code

A very good article over at Open Source at Google blog.

Spindle Search Screenshots

Here are some screenshots of the latest Spindle Search release.

The window for selecting the drive to index:
The window for entering title and other information for the selected drive:

The selected drive is being indexed:

Finally, Google Desktop search result indicating where the file is located:

Interview on Google Summer of Code

Shahzad Saeed is doing a series of posts on GSoC offering advice for those who consider participating in the program in 2011. (Note: it has not been officially announced yet).

In one of the posts he interviews me, where we discuss the necessary background, skills, etc. for a successful SoC participant. If you find this interesting, go and read it over at Shahzad's blog!

Indexing removable media with Google Desktop

A bit over a year ago I took over maintainership of two open source software packages, which I have been using for a few years before:

• Spindle Search. It integrates with Google Desktop to provide indexing and search over removable media: you type a (part of) file name and it says which of your DVD-Rs (or USB keys etc.) the file sits on. Very useful once you have burnt 10+ DVD-R with large file collections on them.
• .NET Wrappers for Google Desktop. It is a supporting library for Spindle Search providing a mappings from Google Desktop API, exposed through COM, to .NET.

Today I have made new releases of both these packages.

Thanks to Manas Tungare, original maintainer of both Spindle Search and Wrappers, for creating them in the first place and trusting me to continue to maintain them, and to beta testers of Spindle Search who have been very, very helpful!

Summer of Code: Conclusion

(Summer comes)

Originally I have planned to write a "things not to do" post, but now I've dropped the idea. Positive advice is better than negative one, and people that do those things are not going to read it anyway.

So let's conclude Summer of Code posts. If I had to sum up everything with one word, it'd be "communicate."

This blog is going to take a break, until I get a new idea what to blog about. That might be my Ph.D. topic – efficient spatial indexing. Or something else.

Good luck with your applications!

Summer of Code: Summer comes

(CV and qualifications in the application)

So the application is completed and submitted and, a few weeks later, the acceptance notification day comes. Then one of two things happens: either your application was rejected, either it was accepted.

It it was rejected, do not let these news sadden you too much. The positive thing you are carrying away from all this effort is the practice in writing technical project applications. This is a very useful skill and makes you much better prepared for the next such contest.

If it was accepted, congratulations; now get busy with the project! Some advice for the summer:

• So this is your full-time job now, just with very flexible hours. See [4] for an example of time commitment requirement.
• Communicate with your project. Hard to overstate, hard, although possible, to overdo. In particular, do not write to mentor only when it's more appropriate to write to the mailing list – most of the technical questions should go there.
• Communicate with your mentor, especially if something went wrong or you have doubts about the project:
• If you feel that project scope is too big.
• If you think that the project deliverables need to be adjusted.
• If you experience some strange difficulties involving the organization, for example, if getting source code repository access takes ages.
• If you feel that discussions with other project developers are unproductive in some, maybe even bad, way.
• Don't be afraid to do so. Remember that your mentor wants you to succeed and will do what he can to help you.
• Check-in code often to your branch. It's much better to post small incremental patches than to work silently for two months and then de-lurk with one big code change. In addition to the usual source code version control advantages, the organization will see your progress and you will get feedback earlier - when you actually can act on it.
• Do not expect to follow your project plan to the letter. It is almost guaranteed that things will change. When you see it coming, discuss the necessary change with your mentor and make it. Repeat as needed. Do not stick to the original plan just for plan's sake.
  

That's almost it! Conclusion next.

Summer of Code: CV and qualifications in your application

(Writing the application)

An important part of the application is the one where you talk about yourself instead of your proposal. Here your goal is to show that you are actually able to do what you promise to do.

• If you do not have previous experience with the project codebase, suggesting that you will "work really hard" or that the feature "will be totally awesome!" might not cut it [1]. In such case playing with the code (see above) is important.
• In similar spirit, "I use this application every day!" is not enough, especially if the application in question is a very popular one, (e.g. Firefox) [1]. There is nothing wrong with stating that, but make sure that this is not your only qualification.
• Good personal references/recommendations help.
• Previous projects help, especially in the related area.
• Do not copy paste your CV from some other application if you fail to tailor it for the one you are applying for [1].
  
• Be prepared to back your experience claims in CV with specific examples and descriptions, for example, of the projects done.
  
• Needless to say, lying and padding is bad.

Yet your effort to write the application is ultimately more important than your CV. If you have limited time and have to choose between gathering personal references and spending time on a technical part of the application, choose the latter.

Next: summer comes.

SoC GCC podcast

When Leslie Hawthorn learned that I'm doing internship at Google, she made me and Ian Lance Taylor record a podcast about Summer of Code and GCC. Daniel Berlin, my mentor from the last summer, was also invited, but managed to escape.

The result is here.

Thanks to Leslie and Ian! And Danny too :) The SoC posts will resume now.

Summer of Code: Writing an Application

(Introduction and table of contents)

By now the preparations are done and it's time to write. Here is a list of assorted writing tips, in no particular order.

• Copying project description from proposed project list does not cut it.
• Choose a short but descriptive title, that will create enough interest to read the whole proposal.
• Whatever the idea, make sure to state it briefly and clearly (surprisingly, some people fail to do so [1]).
• List deliverables clearly and specifically, both optional and required, and designate them as such.
• Read dev docs, code, play with the code, try to actually implement something in order to help fill in technical details of your application.
• Some projects might require you to provide a specific schedule, even though you might have only a vague idea here (But how do you know that your project is going to take three months then?). Playing (see above) with the code should help there, and don't be afraid to change timeline later as needed. Make sure to communicate that!
  
• Do not leave template text in [1]. If you want to give credit to template author, do it clearly in your own words.
• Use the provided form for application as much as possible. Do not just include a link to external web page here. If 7500 symbols are not enough, shorten [1].
• Include brief references to support your claims - links to e-mail archives, specific chapters in the development documentation, etc.
  
• Should be obvious, but check your spelling and grammar.
  

The part of application that outlines your qualifications, including CV, deserves separate treatment. That's coming next.

Summer of Code: Planning to write an application

(Introduction and table of contents)

So, by now you have a rough idea what your project proposal will be about. Here are a few things to consider before you start writing. First, expect to commit significant time for it (I spent about a week full-time) and it's best to start early. Starting writing early means more iterations, more feedback that is more thorough – it's all good for you.

Does that seem like a lot of work? That's the whole point – in summer you are going to have even more work, after all [5]. Also that means that you should go for quality, not quantity: do not try to write three or more applications that are actually good. It might be possible, but it's very hard to pull off.

Before you start actual writing, it is helpful to look at previous accepted applications. Search for them with Google, or follow the links from [7].

Also it'd be very helpful if you arranged with somebody to review your application once it's written. Usual ways to seek help here involve talking to staff at your faculty, in the case they know you and have time to spare, or at any NGOs you are affiliated with or have friends at – usually they are very good at this sort of thing. The reviewers do not have to be familiar with your project area, and it even might be better if they weren't - an outsider's perspective can be very valuable.

Next: writing tips.

Summer of Code: Choosing an interesting project idea

(Introduction and table of contents)

First of all you have to choose an organization you want to work to with. I don't have much to say here. I guess you just have to go to the list of organizations and pick the one you like the most.

After that you have to choose a project idea to work on. For that, it's best to start early: you will have to do a lot of iterative communication, and the more iterations you will complete, the better your application will be.

Now what to look for in idea itself? First and foremost, ambitious ideas are good, especially if they are not in the proposed project list. Tell it to the project and it may even end up on that list [3]. That's a strong case for your application, and you haven't even started writing it yet. Second, original ideas, outside the current "hot" thing, show that you are an independent thinker. Furthermore, your idea should be not merely "nice", but something that the project genuinely needs.

At the same it's a good idea to start reading development docs and some code for the project. This will help to see if the idea is feasible - especially if it's not in the list of the suggested projects - and to get general feel about the project. Even more important is to contact project developers: ask for feedback for your project idea, find yourself a mentor, file a bug, submit a simple patch - get involved!

Finally, learn about organization specific things: see if there are particular requirements for applications in you organization. And do not be afraid to ask how one or another option would be evaluated and which route you should pursue. Organization might have a sound reason to prefer one perfectly good approach over another perfectly good one, so don't get burned just because both approaches seemed good to you.

Next: planning to write the application.

Summer of Code: The Big Picture

(Introduction and table of contents)

The idea of Summer of Code is simple. Students choose open source projects they would like to work on and write applications, the open source projects evaluate those applications, the selected students spend their summer working on what they wanted to and Google pays everybody. Everybody wins. The students get experience with application writing and open source development, attention and help with their projects, potentially useful contacts for the future and some money. Organizations get new developers - their lifeblood - and some money. Google gets opportunity to help FOSS developement (FOSS is used a lot in Google), positive publicity and some (very little) recruiting done for themselves.

Note that in the long list of the benefits for students (that means you), money is just one thing, even if it is the first thing you hear about in relation to the program. And in the long run, it's probably the least important benefit. Think of it as a necessary means for Google to win your time away from other potential summer employers. That's it. The really important benefits you get are the skills and contacts, these will serve you well into the future. Funnily, mentioning in your application that you are doing this just for money will surely fail it. And no, I'm not suggesting lying about it – if you do, your application will show it in thousand other ways, with the exactly the same end result. But more on application writing later.

What's more? If you ever wanted to join an OSS project but it seemed daunting and complicated, here is your chance, with added bonus that the project developers will be extra-nice to you. If you have never participated in a successful team OSS project, or any team software project for that matter, this will be a very interesting and useful experience. There is a major difference between coding an application alone and doing a project in a team. So you are going to learn a lot of exciting stuff about having to deal with other developers, how and when to communicate with them, what kind of support infrastructure every project needs and many other things. Again, what you learn is for lifetime.

This concludes the big-picture benefits of SoC for you. The other big-picture thing which you have to be aware of is the time planning. If you are accepted to SoC, do not plan any other full-time commitment for the summer. The project will expect you to commit about full-time worth of effort. This is a perfectly reasonable requirement, since three months of single developer time is not much in the software world. You will need all of this time to create something substantial. But don't get upset – the "working hours" are extremely flexible and you will be able to plan some time for holidays as well.

Next: on choosing an interesting project idea.

SoC Experience: Introduction

Hello world again. Just almost a year behind the schedule, this is the first post in series offering some advice for SoC participants, that, very hopefully, will be at least a bit useful to somebody.

SoC has changed my life, in a sense. In summer 2006, I applied to work on the GCC with this project. I was accepted and successfully completed my project, although at a significantly reduced scope. Then I got to travel a little bit, to see how Google is doing in London. And a year later, this has helped me to land an internship position half a world away at Google. And my work here involves continuing my old SoC project. What more could I ask for right now?

That's why I want to share some of the things I learned. While searching for advice a year ago, I have found many excellent resources on how to write an application (all of them linked to below), yet there are some things which I want to emphasize more. Most important of them is the need to communicate early and often – in general communication, soft skills, etc. is something that us engineers tend to dismiss and this is a big mistake.

So I am writing down advice based on my personal experience, with added advice from other sources that I can relate to. Of course, it is very subjective and in no way I can guarantee that it is correct and true in all (or any) situations. Also, parts of it will seem like a very common sense. That's because it is. But common sense tends to be forgotten or vary person to person, so I feel I should include "very obvious“ stuff as well.

Here is the table of contents for easier navigation. I will convert it to links as I add new material.

1. Introduction (this post)
2. Summer of Code: the big picture
   
3. Choosing an interesting project idea
4. Planning to write an application
5. Writing tips
6. CV and qualifications
7. Summer comes
8. Conclusion

Finally, if nothing else is useful, then at least this part will definitely be. This is a list of links to other SoC participation advice, written by much smarter people than me, with SoC mentors among them, whose advice matters much more directly than mine.

1. http://weblogs.mozillazine.org/gerv/archives/2006/05/how_not_to_apply_for_summer_of.html
2. http://groups.google.com/group/google-summer-of-code-discuss/browse_thread/thread/4cccd94e0b9aefc9
3. http://alex.dojotoolkit.org/?p=604
4. http://summer.cs.pdx.edu/propose
5. http://shlang.com/writing/soc2005.html
6. http://venge.net/mtn-wiki/SummerOfCode2006
7. http://drupal.org/node/59037
8. http://code.google.com/p/google-summer-of-code/wiki/AdviceforStudents
9. http://www.postgresql.org/developer/summerofcodeadvice.html
10. http://shlang.com/writing/soc2005.html

Good luck!
Next: The big picture of SoC