Olivier Langlois's blog

Graph breadth-first traversal algorithm C++ implementation

I have posted on my website a small C++ program that I have been asked to write during an interview with Facebook at Fall 2009. One of their interview was related to graph theory and the problem was to find the the shortest distance between to nodes in a graph. The best algorithm to use to solve this problem is the breadth-first traversal algorithm.

You can look at the source code here at:
http://www.olivierlanglois.net/archive/graph_cpp.htm

and you can read more about the breadth-first traversal algorithm in Robert Sedgewick excellent book on algorithms.

A new page in my career

Today was my last day at StreamTheWorld. I spent the last 3 years there as the company C++ Tech Lead in charge of the company C++ streaming servers development. It has been a nice ride filled with challenges.These servers are used by over 1600 radio stations including AOL/CBS radios accessible through Winamp and Flash players.

Among my various realizations. There are:

Scale and improve the performance and the reliability of the company audio/video streaming servers to the point where it can concurrently handles hundreds of thousands of live feeds every day in more than 25 countries, including during peak audience dayparts. The reliability and the quality of the server software have been proven to such industry leaders as CBS, Entercom, Multimedios, AOL and more. This represents 20x improvement over the original capacity.
Added more functionality to the server by growing the server code base from 25K lines in June 2007 to 200K lines in only 2 years while improving robustness and performance.
Designed and implemented a high performance targetted stream ad insertion system that serve end-user ads based geoip lookup. This system is now used by ESPN Radio on Internet.
Design and implement a protocol stack to support Adobe proprietary protocol RTMP clients
Add AAC support to the streaming server
Improve Microsoft MediaPlayer and Silverlight support.

I will start my new job Monday next week. Visit back my blog or my LinkedIn profile if you are curious to learn for which amazing new employer I will be working for.

Large Scale C++ Software Design

It is a very interesting book. Anyone having been involved in a large scale software development projects will recognize typical problems often seen in this type of projects while reading this book and by experience we have developed an intuition about how to deal with the complexity inherent to large scale projects. Mr Lakos book is the first, to my knowledge, that address this subject and it formalize extremely well the problems of large scale projects and propose a methodology and principles to apply to keep the development and maintainability of these projects manageable. It is a very refreshing C++ book and I recommend it to any C++ professionals not having read it yet.

The most interesting chapters in my opinion are chapter 5 and chapter 6. Chapter 5 presents refactoring methods to remove cyclical dependencies among components, reduce inter dependencies and how to layout components into software layers that will ease reusability and maintainability. Chapter 6 discuss about component insulation. Its difference with encapsulation, the benefits of component insulation and its cost and when it is wise to avoid insulation.

My new C++ source code to HTML converter

While I was integrating a fix to a bug that has been reported to me by Daniel Quadros in my primality testing C++ module and also adding gcc asm support to it. I used that opportunity to rework my C++ source code to HTML converter. The 2 things that I added to the converter are:

replace the usage of the tags with tags in combination of CSS classes
size optimization of the converted document

The size optimization came from the very simple observation that my converter was stateless and was not recognizing when multiple consecutive sections sharing the same colors were processed. I just added a small FSM to my converter to keep track of the current state and the converter now close the current tag only if there is a transition to a new color. The most impressive result came from my DCEL C++ file with a 25% file size reduction!

Also, I am just starting to appreciate to power of CSS. I will now be able to change the code snippet colors across my whole website by just updating a small CSS file. As a side bonus by having switched from the tags to , I can now use my C++ highlight feature in the code snippets contained in this blog as the blog engine was forbiding using tags on posts but allows .

Cryptography Engineering

I just started to read this book which is an updated version of Practical Cryptography. This book is coauthored by Bruce Schneier. From what I have seen so far. It looks like a very nice introduction to cryptography that is very accessible. For more in depth coverage on cryptography, I would recommend looking at Applied cryptography. I will probably have more to say about the book when I am done reading it.