Example Programs form the Qt 5 Performace Book

Hi all! You will meanwhile probably have learned that I wrote a book about C++ program performance in the context of the Qt framework (you can have a look at the TOC here).

But along the book I also created quite a few example programs, which, as a rule, aren't discussed in the book. Some of them are pretty nice, so I decided to write up what they are and what they do.

There are two kinds of example programs in that collection: ones that illustrate some performance optimization idea, but also ones which just show how to use some of discussed Qt features. So if you want just learn some Qt usage, you might find it interesting. Also if you are interested in details on the techniques mentioned in the book, you'd better look into the examples, because the book didn't have place for step-by-step exlanations.

Chapter 1: Intro

At the moment no code and no resources here. Sorry. Some examples for usage of basic performance techniques would fit here in nicely, so maybe in the future...

Chapter 2: Profiling

QmlWithModel

This is the program we will be using to show how to take advantage of profiling tools. It has a QML GUI showing all the countries where Qt is used. This list is fetched with an HTTP request from the internet:

As you can check in its code, we can enable:

•  a memory leak and 
•  excessive burning of CPU cycles 

in order to show how to find these problems using profilers.

Additionally, there's a recorded ETW trace file of the above application to be browsed with the UI for ETW tool mentioned in the book:

Here you can take your time and look into different metrics which can be collected with ETL!

Addendum: I always wanted to include an example usage of  some flame graph generators in your code, but never got round to it. Maybe I'll find some spare time for it.

Chapter 3: C++ and Compilers

ClassicTemplateTricks

Here we show some of the template techniques mentioned in this chapter, e.g, expression templates for optimized string concatenation, CRTP for avoiding run-time polymorphism and compile-time calculations using recursive templates.

Addendum: Because Qt 5.12 required C++11, the techniques shown in book are the ones supported by that standard. But for example the expression templates could be replaced with fold expressions in C++17!*

Compiler Explorer Tests

Some code you can copy and paste into Matt Godboldt's Compiler Explorer and look at the assembly it produces. Here we can observe such optimization as:

- compiler optimization examples: the basic examples discussed in the book - avoidance of direct summation, elision of allocations, etc.

- constexpr factorial: here you can see the proof that a factorial can be calcualted at comple time! This time without templates, but using constexpr instead!

- constexpr hash: and here is the equivalent proof for a compile-time hash function!

- restrict and pure: here we can see how the restriced and pure attributes can guide the compiler for better optimization and how it's absence worsens the generated code. Unfortunately these attributes are only avaliable as compiler extensions.

- UB examples: here we have a few UB cases mentioned in the book

So just grab the snippets from example files, paste them into Compile Explorer an see live how different compilers optimize your code behind the curtains!

MemoryMgmExamples  - these are examples of a custom memory managers and allocators. They will trace to cout to show when they are used:

MoveTest - in a similar manner, an example usage of the move semantics, also tracing to show that it's working:

Chapter 4: Data Structs and Algorithms

Interning of strings - an example implementation of string interning. As this would be to detailed to explain in the book, I just provided some code for the curious to read through:

Addendum: with Visual Studio compiler we can activate string pooling option to automatically remove duplicate strings!

Schwartzian transform - here we are using the ominous Schwarzian transforrm to paint triangles and christmas trees 🎄!

StdSearch - here we show the usage of the new C++17 Boyer-Moore searcher

Chapter 5: Multithreading

ActiveObject - an implementation of the "Active Object" pattern. You surely remember that we can use this pattern to implement a (nearly) share-nothing multithreading scheme, do you?

ConcurrentAndFutures -  here we load images asynchronously using futures and can compare this to a simple synchronous loading strategy by pressing the "Load All at Once" button:

QFutureInterfaceExample - this is an example explaining usage of the undocumented QFutureInterface class which is widely used in Qt Creator

ThreadsAndTimers - basic example for starting timers in threads (because it can be somehow confusing)

Chapter 6: Case Studies

In this chapter we could do with some more examples, don't you think? Because we have only this single one:

SvgCache - here I show an implementation for the SVG cache we discussed in 6.4.

Chapter 7: I/O and Parsing

JsonExample - example of basic JSON parsing, nothing special, I know

MemMappedFile -  a hands-on demonstration of how to map a file onto memory:

SqlLiteExample - shows example usage of the SQLite database.

First we have to create the DB offline:

then we wil perform some simple SQL manipulations on it:

StreamReaderExample - again a basic example: parsing XML data this time

Chapter 8: Graphics

These examples mainly illustrate the discussion of various Qt graphic interfaces, but the minimal FPS counter can be used as a performance tool as well.

CustomQmlElementsTest - here we paint a simple triangle in QML using several ways to define our own, custom QML element. The FrameBufferTriangle uses custom OpenGL painting on current OpenGL context.

FpsCounterExample - want to know how to implement a live FPS counter for your application? Here we use a particle system to stress the QML runtime measure (and display it in an extra widget!) the FPS rate that can we are able to achieve:

OpenGLWidgetExample - we use Qt's OpenGL support for widgets to draw this classic triangle picture:

It used the most basic (and old...) OpenGL 1.0 API, but hey, this book isn't a graphic tutorial - I just needed this picture for the explanations of how the graphics pipeline is working. Please bear with me.

Qt3DSphereExample - look what is possible with Qt 3D! We animate a rotating sphere using the Phong lighting model:

It is also a very basic program, but the result is rather cool (at least for me).

Chapter 9: Networking

Here I wanted to write some basic demonstrators running client and server on the same machine to show basic usage of TCP sockets and HTTP transport mechanism.

EchoServerTcpExample - an echo server: the client will connect on a given port and the server will echo every data it receives from client!

HttpDownloadExample - here we will connect to a given web address, then fetch and save some resources from there. Additionally, the progress of file download is visualised with a progress bar.

If you have Python installed on your machine, you could start a local web server on some directory and then run this testapp locally. As I mentioned in the book, Qt doesn't have a HTTP server component and doesn't allow us to easily write one.**

Chapter 10: Mobile and Embedded

Here we do not have much resources (sorry, publisher's deadline didn't allow that 😒) but at least one example pertinent to embedded data presentation could be included.

OpenGLAcceleratedChart - an example of using OpenGL acceleration with Qt Charts. You can parametrize the number of points if you want to stress your hardware!

There is another example implementation I should have provided is the polyline simplification, but due to time shortages I missed out on this one. But at least I provided you with this link: https://www.kdab.com/a-speed-up-for-charting-on-embedded/, which describes the implementation of a polyline simplification technique that uses a flattened min-max tree.

Addendum: If I'll find some time, I could add some example project for my Raspberry-Pi, as I was initially planning. You know, the deadlines etc... :-\.

Chapter 11: Testing and Deploying

ExampleSubdirProjectWithTests - this is an example of how to add tests to an existing project using the Qt Creator:

The tests are wiritten using QTest library, and integrate nicely with Qt Creator's UI, as you can see on the above figure. Also a minimal Qt application is created to be tested here and in the Squish tests below.

SimplestQMLProject - this one is a very simple QML project we will need in the example Squish tests below.

Squish - here we have a definition of Squish tests for both Widgets and QML applications we've introduced above:

Summing Up

So, that's all. I hope you've found something interesting there!

---
* expression templates can be replaced with fold expressions (C++17) for string concatenation, as shown in this post: https://www.qt.io/blog/efficient-qstring-concatenation-with-c17-fold-expressions

** e.g. I couldn't port my old Qt4-based embeddable web server project to Qt5 because of removal of HTTP parsing classes.

OCaml and Multithreading

As Doctor House said one day: "There was that philosopher Ocaml..." Stop, wrong start! Try again.

1. OCaml story

OK, some time ago, in a somehow better world, I became attracted to the OCaml language because of its speed, elegance, light syntax, algebraic data structures and automatic type inference (as you meanwhile might know, I'm a bit of a typing fan). I must admit, it was my first functional language, so maybe I'm a little sentimental about it. Later on I somehow didn't give it much love and affection, mostly because I got distracted by other, more fashionable languages like Clojure, F# and Haskell (shame on me!).

Nonetheless, although this one is rather an obscure language, one company has been using it big time to do some highly parallel, high-performance data processing. This company is Jane Street and they are a financial market player. The reason they chose OCaml were that the owners wanted to read every line of code performing financial transactions*:

"Early on, a couple of the most senior traders (including one of the founders) committed to reading every line of code that went into the core trading systems, before those systems went into production"

"In 2003, Jane Street began a rewrite of its core trading systems in Java. The rewrite was eventually abandoned, in part because the resulting code was too difficult to read and reason about—far more difficult, indeed, than the VBA that was being replaced."

 "The VBA code was written in a terse, straight-ahead style that was fairly easy to follow. But somehow when coding in Java we built up a nest of classes that left people scratching their heads when they wanted to understand..."

 "In 2005, emboldened by the success of the research group, Jane Street initiated another rewrite of its core trading systems, this time in OCaml."

So somehow the functional-style code was more readable than a pile of Java classes: can we put that to the superiority of functional languages in general or just to bad training of Java programmers? An open question.

OK, there are additional technical reasons as well: the type inference that makes the code concise (thus more readable) while retaining type safety. Additionally it's runtime performance is pretty good! A double win against for example Python.

2. Multithreading?

For a long time they remained the single serious industry user of which I knew, but recently also Facebook started using OCaml in their Hack and Flow language typing add-ons for PHP and Javascript implementations. Surprise! And a very nice one, my pet language got appreciated at last! Everything OK?

Not quite: when I listened to that presentation, I was surprised to learn that OCaml's mutlithreading support is pretty much completely broken. How can that be? Why didn't I notice that first place?

Well, after some more digging, I received this link from a fellow programmer. It makes it pretty clear to us all that OCaml designers were quite a nasty bunch of "multicore deniers":

"The goals of OCaml threads are (2) and (3) but not (1)"

Where (1) denotes "Parallelism on shared-memory multiprocessors"! And then:

"Shared-memory multiprocessors have never really "taken off", at least in the general public.  For large parallel computations, clusters (distributed-memory systems) are the norm. For desktop use, monoprocessors are plenty fast."

 "What about hyperthreading?  Well, I believe it's the last convulsive movement of SMP's corpse :-)"

Yes, they didn't like it, to say the least. But there's another reason as well: the GC implementation in OCaml is single-threaded and thus it could be made very fast, which was an important factor in OCaml's initial successes. But then this (ironically) proved detrimental to trying to make the language MT-safe**.

The only way to do parallel processing in OCaml is thus multiprocessing + message passing. As I learned Jane Street wrote the Parallel library to support that:

"Parallel is a library for spawning processes on a cluster of machines, and passing typed messages between them. The aim is to make using another processes as easy as possible. Parallel was built to take advantage of multicore computers in OCaml, which can't use threads for parallelism due to it's non reentrant runtime

The Facebook people went one step further: they

"...use the same model for multithreading: a specially mmap'd region shared between different fork'd processes, containing a shared, lockless hash table. "

Thus they have multithreading without threads - a couple of processes sharing the memory space (or a part of it), faking the SMP model! You must admit it's rather brilliant - you spare yourself all that serialization, deserialization, and message passing that normally shave off a significant part of the performance.

3. So why OCaml?

Apparently, despite the mutithreading disaster, companies find OCaml worth trying out. Why? I'd say the reasons are:

  1. It supports functional style (but it allows dirty tricks when they must be done)

  2. Has strong typing unlike Lisp, Python, etc.

  3. Not bound to Windows and .NET like F#
  4. Not Haskell, you'll be able to read and understand it.***

And finally, maybe this whole multithreading business isn't worth the hassle? Facebook clearly need it, but Jane Street don't. I remember having heard Yaron Minsky (of Jane Street) saying somewhere that parallel processing plus message passing is a much safer model that multithreading. And in finance you need that safety.

I can accept this argument in a more general setting as well, because the only reason we have threads are performance gains (OK, a deceptively "natural" programming model too). And if the performance of forking + message passing is sufficient, that's definitely a gain! Jane Street does some massive parallel processing in real time, so the performance seems to be not that bad after all...

Or maybe the fork+pass model is slower, but they are gaining on the excellent low-latency CG? Jon Harrop puts it like that:

"OCaml has a nice (~10ms) low latency GC and it is easy to optimise OCaml code for low latency. In contrast, the .NET GC is much more complicated and, therefore, harder to optimise for and, in my experience, has >10x higher latency. I suspect that would be a major drawback for Jane Street."

So before you port OCaml's GC to multicore, overcomplicating it and losing its excellent performance, maybe paying some price for the workarounds pays out better?

Having said that, there's recent work on improving the GC-performance even more, and even a new attempt on multicore OCaml. Maybe this time they will be successful. And be wary, not everyone likes OCaml, for some "OCAML sucks" - http://www.podval.org/~sds/ocaml-sucks.html!

Update: an impressive list of companies using OCaml: https://ocaml.org/learn/companies.html (via @jonharrop). So it's not only Jane Street and Facebook!
Update2: Facebook continues working on OCaml ecosystem - Reason, a "new interface to OCaml" ... "provides a new syntax and toolchain for editing, building, and sharing code". Plus Infer - the iOS/Android app checking tool!

--
* "OCaml for the masses" - http://queue.acm.org/detail.cfm?id=2038036

** "The rise and fall of OCaml" - http://flyingfrogblog.blogspot.co.uk/2010/08/rise-and-fall-of-ocaml.html

 ***  As someone said, Haskell was created to do research on Haskell (and OCaml was created to write theorem provers).

Who's to blame? - or the most amazing multithreading bug which wasn't one!

Typically bug-hunting is quite simple, as not to say trivial. But sometimes you encounter some species of bugs that makes you mad for weeks!!! Programming pundits maintain that this are the C++ multithreading bugs, because locks, well..., um..., they just don't compose! So what are we supposed to do? Either we should wait for transactional memory support, or switch to another language, preferably Haskell or Clojure. OK, will do that, but in the meantime there are products to be developed, delivered and sold*. So that's what happened:

1. The Bug

My current project is developed on Windows with Microsoft's Visual Studio as IDE and Intel's XE as a plug-in compiler. We choose Intel XE because it is (unsurprisingly) very good at optimizing code for the Intel platform and, not least, because of its support for the new C++11 standard. Our code is full of boost::thread, boost::mutex, std::atomic's and its ilk, so it falls in the category the gurus are warning of. But - the architecture of the system was recycled from the previous product, so there's no real use in complaining about the non-composability**, and, as we are in the business of streaming files out, the performance is more important than advanced architectural concepts. I just removed a couple of vtable race-conditions from the code and the whole stuff seemed to be running well enough!

But then we changed the Boost version, updated the compiler version, at the same time I made some changes to the threading model to make the internal architecture more dynamic, and booom!, everything stopped working in a huge crash! 

It was "Illegal instruction" and sometimes "Privileged instruction" all the time. What? I'm not issuing assembler instructions in my code! This is definitely something where I can shift the blame on the compiler! On the other side, the C++ standard says that data races constitute the dreaded undefined behavior, in short, that all your bets are off. So why not an illegal instruction? But then there was another type of crash: "Access violation". OK, that's something you could definitely blame on your programming or a data race.

Let me put one thing straight - the crashes came only when the debugger was attached; without debugger the process run without a hitch. But unfortunately this fact doesn't mean very much in the art of debugging multithreading applications - debugger changes program's memory boundaries, ant maybe only accelerates the manifestation of bugs that are otherwise hiding in dark corners of code wanting to become big, ugly Heisenbugs!

First I suspected another vtable race condition and indeed fixed some more instances of it, but that didn't change the overall picture! Next, after inspecting the assembly code following problems were revealed:

First, there were crashes in code like that:

5DF3B12C mov dword ptr [ebp-38h],edi 
5DF3B12F mov dword ptr [ebp-3Ch],esi 
5DF3B132 mov dword ptr [ebp-40h],ebx 
5DF3B135 mov dword ptr [this],ecx 
5DF3B13B mov eax,dword ptr [___security_cookie (5E054DC0h)] 
5DF3B140 xor eax,ebp 
5DF3B142 mov dword ptr [ebp-14h],eax 
5DF3B145 mov dword ptr [ebp-1E0h],eax 
5DF3B14B mov byte ptr [ok],1

where debugger was pointing at mov byte ptr [ok],1 as illegal instruction! What is here illegal! No advance was possible in this case.

But more often I could see something like:

5DF3B152 mov eax,dword ptr [input_size] 
5DF3B155 db 89h 
5DF3B156 test eax,edx 
5DF3B158 db feh 
5DF3B159 db ffh

here the current instruction was, quite understandable, db feh. The problematic part was that before the crash this code looked completely different, i.e. there wasn't a trace of the suspicious db instructions! Well, that way or another, it looked like some dangling pointer problem where memory gets overwritten at some arbitrary address. Or does it? On Windows you cannot overwrite the program section of the process, as there is the code segment protection enabled by default (at least nowadays). Whatever! - I tried to set a data breakpoint ate the changed location, but no change at the given address was reported by the debugger. What the heck, I see that my assembly codes changed, how can debugger be so stupid! So there wasn't any progress on this avenue either.

The second general class of errors was the one causing access violation. It emerged, than an innocuously looking stack pointer manipulation like add esp,0FFFFFFF0h would produce illegal stack pointer value blowing the program off, even though the previous ESP value was well in the allowed range! Looks like sorcery!

5FB4B906  cmp         eax,0BCh
5FB4B90B  jae         5FB4BC25
5FB4B911  add         esp,0FFFFFFF8h
5FB4B914  lea         eax,[conv]
5FB4B91A  mov         dword ptr [esp],2

with register contents like that:

EAX = 322CE9AC EBX = 1BB16DE0 ECX = 359A56A0 EDX = 00000021 ESI = 322CED30 EDI = 322CEBB4 EIP = 5FB4B91A ESP = FFFFFFFC EBP = 322CEB84 EFL = 00010286

Well, with stack pointer corrupted, the result of this was:

Here's another beauty - debugger reported a stack corruption here, as it was completely bewildered with what was going on:

So how was this bug to be handled, and who shall win the blame game?

2. The Explanation.

I tried to inspect the memory directly in the memory window of the Visual Studio debugger, but it was somehow too low lever for my mood at that moment. So because:

• the problems always occurred in the vicinity of a break point,
• the debugger was always displaying correct values of the operands in the "Access violation" case,
• the debugger was never showing the illegal instructions, only after the crash happened,

I decided that the single explanation left was that it's something to do with the tools. Therefore I duly reinstalled everything in my toolchain, Visual Studio, Intel compiler, Boost libraries, in the vague hope that the installation of some of them could be broken. Alas, nothing seemed to help.

At this point, I declared the issue as solved - I had some real work to be done, and if you didn't define excessively many breakpoints, the debugger typically played to the rules. Except when it really mattered of course (sigh).

I explained the problem to my worthy colleague Bernhard Z. so he could take it up, and he investigate it a little bit further. And indeed - he found out some very interesting facts about how exactly the debugger has been guilty!!! 

Contrary to what Visual Studio is telling you, it is possible to attach to a running process with two debuggers (!!!). It is done like that - first attach to it with Studio, and then start WinDebug (don't forget to check the "Nonintrusive" option, or it will complain!). Now, Bernhard did it, and he could have an independant view on the machine code!

An than, with the second view on the assembly code, the problem became obvious - the debugger inserted the debug-break instruction (int3 <=> 0xcc) at the wrong position in the machine code - not before the opcode, but 2 bytes behind it, making the arguments following the opcode to illegal instructions! Look here at the assemble code before setting the breakpoint (the line where the breakpoint has to be set is in bold):

00c7461f 89542404        mov     dword ptr [esp+4],edx
00c74623 e888d00000      call    BoostSerialize!save_data_xml (00c816b0)
00c74628 83c410          add     esp,10h
00c7462b 83c4f0          add     esp,0FFFFFFF0h
00c7462e 8d9560ffffff    lea     edx,[ebp-0A0h]
00c74634 83bd74ffffff10  cmp     dword ptr [ebp-8Ch],10h
00c7463b 8d85c0fdffff    lea     eax,[ebp-240h]
00c74641 0f439560ffffff  cmovae  edx,dword ptr [ebp-0A0h]
00c74648 890424          mov     dword ptr [esp],eax
00c7464b 89542404        mov     dword ptr [esp+4],edx
00c7464f e88cca0000      call    BoostSerialize!save_data_binary (00c810e0)
00c74654 83c410          add     esp,10h
00c74657 83c4f0          add     esp,0FFFFFFF0h
00c7465a 8d9560ffffff    lea     edx,[ebp-0A0h]
00c74660 83bd74ffffff10  cmp     dword ptr [ebp-8Ch],10h
00c74667 8d85c0fdffff    lea     eax,[ebp-240h]
00c7466d 0f439560ffffff  cmovae  edx,dword ptr [ebp-0A0h]
00c74674 890424          mov     dword ptr [esp],eax
00c74677 89542404        mov     dword ptr [esp+4],edx
00c7467b e8d0b90000      call    BoostSerialize!save_data_string (00c80050)

And now the assembler code after the breakpoint has been set:

00c74623 e888d00000      call    BoostSerialize!save_data_xml (00c816b0)
00c74628 83c410          add     esp,10h
00c7462b 83c4f0          add     esp,0FFFFFFF0h
00c7462e 8d9560ffffff    lea     edx,[ebp-0A0h]
00c74634 83bd74ffffff10  cmp     dword ptr [ebp-8Ch],10h
00c7463b 8d85c0fdffff    lea     eax,[ebp-240h]
00c74641 0f43cc          cmovae  ecx,esp
00c74644 60              pushad
00c74645 ff              ???
00c74646 ff              ???
00c74647 ff8904248954    dec     dword ptr [ecx+54892404h]
00c7464d 2404            and     al,4
00c7464f e88cca0000      call    BoostSerialize!save_data_binary (00c810e0)
00c74654 83c410          add     esp,10h
00c74657 83c4f0          add     esp,0FFFFFFF0h
00c7465a 8d9560ffffff    lea     edx,[ebp-0A0h]
00c74660 83bd74ffffff10  cmp     dword ptr [ebp-8Ch],10h
00c74667 8d85c0fdffff    lea     eax,[ebp-240h]
00c7466d 0f439560ffffff  cmovae  edx,dword ptr [ebp-0A0h]
00c74674 890424          mov     dword ptr [esp],eax
00c74677 89542404        mov     dword ptr [esp+4],edx
00c7467b e8d0b90000      call    BoostSerialize!save_data_string (00c80050)

Do you see it now? In Visual Studio's debugger you wouldn't see anything because Visual Studio hides debug-breaks in the disassembly view! That's the typical Microsoft attitude - we know better what you'd like to see - and they are right with it in about 95%. ... until it bites you!

The second type of crash can now be explained too: 0xcc overwrote the correct operand of the add esp instruction, the addition overflowed, and then we got the access violation!

A "trouble ticket" was issued to Intel: http://software.intel.com/en-us/forums/topic/489007. They didn't believe it of course...

3. The moral of the story

Only after that all became clear we could positively be sure that this wasn't a multithreading bug, and were able to continue the development as before ;).

The moral is simple, and already well known - sometimes you can blame it on your tools. 
Plus perhaps another well known one - you always need a second opinion (i.e. WinDebug's)!

And because it seems to be a good time for some bragging, it wasn't the only "you can blame it on your tools" moment in my programming career - a couple of year ago I diagnosed broken multithreaded exceptions/stack unwinding implementation in a port of the gnu compiler to some obscure UNIX derivative (won't tell the names, however, but it was rather a big Telco company). As a result the whole project had to disable exceptions in the compiler. Don't believe it's possible young Jedi? Yes, it is (or it was at that time - I never needed it again).

--

* some discussion about why locking & mutexes are the scapegoats of programming pundits can be found in the "Is Parallel Programming Hard, And, If So, What Can You Do About It?" book here. 

** for myself I'd opt for a share-nothing, message-passing, "worker threads"-oriented architecture - but well, nobody asked ;). And that post about "Threads as Workers" isn't still written anyway.

C++ Annotations not so pointless? Plus some UMTS history.

Let me start this post with a retrospection: long long time ago I promised to write a blogpost about multithreaded testing, temporal logic and (even) the boundaries of knowledge. Pretty high claims, you'd say, and you'll be of course right, as I didn't write it despite of a few false starts. So though the wholesale treatment of this theme isn't possible now because I plain and simply forgotten much of the details, I'll try to catch the opportunity to pay off my "blogging debt" and use that stuff in a condensed form as intro for this post.

1. Past struggles

So then, long long ago I was writing an multithreading application (or rather a framework* for other programmers to use) under Linux/pthreads against an underspecified multithreading interface of a "General Telco Systems Programming Platform" ;) - let call it GTSPP;). It was underspecified because it was still being developed while we were writing production code to be deployed on backplane UMTS switches.

Well, what can I say, the regular multinational project's madness, alleged synergy, and all that stuff... But, perhaps surprisingly to you, I wanted to have that thing thoroughly tested! And I mean tested! After I found some unexpected behaviour of GTSPP;) and resulting deadlocks, I didn't want to allow it to happen again.

As at that time I was interested in logic, automatic theorem proving and generally in foundational speculations, I had that brilliant (or at least I thought that...) idea - why don't we just describe a multithrerading system in terms of modal logic, like that:

• []T (read: box T) meaning: T alway happens
• <>T (read: diamond T) meaning: T sometimes happens

 and then use automatic derivation do derive some theorems of thatt system? Like "Theorem 1: there will never be a deadlock here".  [In the originally planned post a lot of explanantions about Kripke, possible worlds, Buchi automata... and model checking would follow here... BUT this isn't the planned post, sorry!]

At last some sensible use of maths! Can't believe it, so these whole math classes weren't a total waste of time?

Well, yes and no. As I tried several open source products, none of them was able to read C++ code, annotate it with modal logic, and infer the needed theorems. You call me naive? But that's exactly what SPIN is doing! The only problem was that SPIN doesn't accept C or C++ code, but only it's own description language: Promela. So I had to recode my system in Promela. That was out of the question, as I didn't have so much time. Writing a general translator C++ to Promela translator was beyond question as well - Clang wasn't there yet!

SPIN's author did some interesting work for AT&T on translating C code to SPIN format and even open-sourced it, but as I tried to install it on my Linux machine I failed. Some package dependency was missing, and our sysadmin asserted that there's no no such package for the RedHat distribution... At that point I gave up** thinking: the real boundaries of knowledge are that of human laziness...

2. New hope?

You may remember that I wrote a post "Two C++ curiosities..." where I expressed my inability to grasp the reason for the introduction of attributes in C++ (apart from Microsoft's influence). Recently, the same Microsoft organized a C++ conference  with quite a good video coverage. As I happened to listen to the Clang presentation i noticed some interesting usage of that language feature. It looked roughly like that:

or in gcc's syntax:

Do you see that? Now you can add an attribute to multithreaded code and let the compiler check if it's deadlock and starvation free!

That's what I call a sensible vendor specific extension! Well, it could be, as at the present all this isn't available yet (it's a research project at Microsoft's) but at least now I learned one case where the attributes could do quite a good job!

PS: More information on that topic: the boost::thread and thread safety annotations post or LLVM docs.

--

* I know, programmers hate frameworks, we were hating GTSPP;) too, but we were merging an another telco framework used in the previous project with the hapless GTSPP;) as not to expose the application programmers to too much madness - you know, brains melting, people screaming, teams disintegrating... So it was a Good Thing in the end!

** You don't really think I gave up on this, do you? So what was my solution? Right! I wrote a Python test driver repeating testcases by 1000s and grepping the output for specified error messages. The classic and proven multithreading testing strategy. Maybe a little brute-force and old-fashioned, but you know what? It did the job!

Javascript on the server?

Recently, I stumbled upon an iteresting presenation about server I/O parallelism and multithreading. Surprisingly it was in a Javascript conference, as I sometimes have a look at the Javascript language developments. I'd never expect to find something like that in this contex though.

The general message of the presentation was that threads suck and asynchronous programing is the king. Come again? I don't quite agree with that (or rather agreed, as you'll see in brief) - wasn't that for the threads to save us from the onerous asynchrounous programming with its context information and callbacks (remember Windows event programming?)! The threads justly delivered a convenient abstraction to group the logically connected data and logic in separate units of execution. So now we are doing a full circle: from asynchronous to threads to asynchronous?

OK, on the surface that may be looking like that, but there's more to that. The problem is that when we apply threads to parallel I/O they are just to slow (you know, context switching, thread stampedes and all that). Thus there's a host of asynchronous I/O methods starting with the venerable select() UNIX call. Ok, agreed, for that special field the threading model isn't very appealing, but for the general usage I'd just hide this inside of an I/O thread...

Now there's this pesentation (Ryan Dahl’s talk on Node.js) and what the author says is exactly that: callbacks and asynchronicity are good! How that? We all know it's a pain in practice? His response (an this is the valuable insight got when watching this) is that we just didn't have a good enough programming language to realise that! When you do in in C (as you'd likely to do when programming performant I/O) you are messed up, but if you take Javascript...

See, that's the crux here: Javascript was designed to work in a callback driven environment, so the language has unique mechanisms which no other language can offer. Thus if we take Javascript and do event oriented programming it's a breeze then! The idea is to take the ultra higspeed C library (libev in that case) and wrap it with event-friendly Javascript hull. Here's an example code from node.js site:

  var net = require('net');
  net.createServer(function (socket) {
    socket.setEncoding("utf8");
    socket.addListener("connect", function () {
      socket.write("Echo server\r\n");
    });
    socket.addListener("data", function (data) {
      socket.write(data);
    });
    socket.addListener("end", function () {
      socket.end();
    });
  }).listen(8124, "127.0.0.1");

Well, maybe it isn't a thing of beauty (if you're not into Javascript) but it's concise, everything is at one place, and you can read it without reading tons of manuals first. So maybe this is the way of doing this? Another thing I liked that node.js never provides a blocking API - even filesystem calls are asynchronous! That's consequence!

Sorry for the short post, but it's summer, I want to go out and watch some worldcup!

---
Resources:
1. the talk to be found here: http://jsconf.eu/2009/video_nodejs_by_ryan_dahl.html
2. and here's the code: https://gist.github.com/a3d0bbbff196af633995
3. if you'd like some more technical details, here's an excellent post by Simon Wilson: http://simonwillison.net/2009/Nov/23/node/
4. node.js critique (yes, there's such a thing too!): http://al3x.net/2010/07/27/node.html

Addendum:
- here is a simple blog engine in less than 200 lines of code using node.js : http://github.com/zefhemel/persistencejs/blob/master/test/node-blog.js. Not bad, I'd say.
- Multi-node: how to implement a concurrent node.js HTTP server: http://www.sitepen.com/blog/2010/07/14/multi-node-concurrent-nodejs-http-server/
- Hummingbird: an impressive application based on node.js - http://mnutt.github.com/hummingbird/

Fibers, at last!

As I'm recently doing Windows programming again after some 10 years of a pause, I keep learning about new things. One of them are fibers. Come again? What's that??

A fiber, as the name implies, is a piece of a thread. More precisely, a fiber is a unit of execution within a thread that can be scheduled by the application rather than by the kernel. *

So fibers are just user space threads, aka cooperative multitasking, which I knew since the stone-age DOS times and which weren't supposed to be cool at all!

It were native kernel threads which were supposed to be cool back then! But I must admit that in the past as I was working with cooperative multitasking in a rather big, multithreading system, I was quite happy with it! It gave a nice, predicatble feel to the system; you just new at what times what threads are supposed to run! The sole problem was (of course) that a long running user task couls block all the system. But then we moved on to native threads and I forgot about cooperative multitasking.

But something has changed since then: first, as it was already said, Windows has got it, although allegedly only as a good-enough implementation to support the SQL-Server (fibers have severe restrictions on the kinds of Win32 API’s they can call!). Second, Oracle 10g has got it too, I cite**:

Fiber model support
- An extension of the thread support already in place since Oracle7. Users may now run the database in fiber mode, which employs Oracle-scheduled fibers instead of O/S scheduled threads.
- For CPU intensive apps, this will provide a performance boost and reduce CPU utilization.

Moreover, recently I discovered a fiber library for Windows XP to remedy the unsufficient native Windows fibers support named FiberPool***. And then there are Green Threads (user space level, cooperative multitasking threads) in Java's JVM for some time now! The recent Windows 7 beta has introduced User Mode Scheduled Threads (UMS Threads)**** , which are like Win32 Fibers, as they can be scheduled by hand, but are backed by real bona-fide kernel level threads! Sounds rather interesting!

So at last it's the old, good cooperative mutitasking rediscovered? There's a growing evidence! Will be the ol' good times of DSET maybe back then Stefan?

---
* Johnson M. Hart: Windows System Programming Third Edition, Addison Wesley 2004
** http://download.oracle.com/owsf_2003/40171_colello.ppt
***http://www.fiberpool.de/en/research.html
**** http://blogs.msdn.com/nativeconcurrency/archive/2009/02/04/concurrency-runtime-and-windows-7.aspx

Reading the new C++ Standard

Recently I've read on my local German C++ forum* that's there was a new draft document for C++09 Standard** and immediately I rushed out to read it. I mean, something tangible at last! Well, actually it wasn't really a read, but rather a very superficial skimming-over. There are good reviews of C++09 on the Web***, so I didn't actually want to read it in depth, but rather to get an overall impression of the changes: just how it all would feel like in C++0x: x < a.

And guess what? It was last year in November (sic!!!) when I read it and then wrote some things up :-(((. Somehow I'm too busy with my current project! Of course I'd like to read the proposal in depth and analyze it here thoroughly, but alas, it's not possible. So let's start with just few of my very personal impressions:

1. Ranges and initializers

What I perhaps liked best of the new features! Now I can write things like:

    map<type-expr> m = {{}, {}, {}};
    int a[] = {1};
    vector<type-expr> v = { a, b, c };
    SomeClass obj({ a, b, c, d });

and that for any class I want! How is that done? You have to implement the initializer_list constructor for your class! Wow, it feels just (like) Groovy to me :-). A great improvement over the oldskool tricks used to force initialization where it wasn't possible by the language definition!

A realated feature I liked are ranges:

    for(int& x: array)
    {
        x = 0; // for example!
    }

This is accomplished internally by a Range<> class being internally instantiated with the array instance: Range<type-expr>(array). It gives you a nice, scripting language like feeling when iterating; I mean, even Java's got it, and the boost::FOREACH macro was in my personal opinion rather an ugly hack than anything else!

When talking about ranges: actually I was expecting that the ranges will be included for the STL algorithms, so we don't have to write the annoing:

    find(v.begin(), v.end(), not_zero());

each time. I was quite positive that we'll going to have something like:

    find(v, not_zero());

as an overload of the traditional STL signature using the new Range<> class (there is a boost::range library after all!), so I must say I'm a bit disappointed here.

2. Some nice utilities I found

There were suprisingly large number of small interesting things to be discovered, like:

• error support: error_code, system_error - well, I can definitely use some of it!
  
• compile time (i.e. template) rational arithmetic - suprise! BTW do we really need it?
  
• clock and time_point classes - useful!
  
• stoi: string to int conversion - a suprise!, so don't we take the road of lexical_cast<> as I was expecting all the time?
  
• alignment control - at last I can say what the aligment is and not the machine! Will then the machines revolt?
  
• unique_ptr - just what we need most often, or auto_ptr fixed!
  
• addressof - even if the actual & operator is overloaded!
  
• reference_closure as Callable - what was that again??? But I wrote it up in my original notes, so it must be something funny!
  
• delegating constructors - we can reuse one constructor in another one, like in this example from the draft document:

    struct C {
        C(int){}     // 1: non-delegating constructor
        C(): C(42){} // 2: delegates to 1

• nullptr as a keyword - no more the annoing (XXX*)0 casts!

I liked these little things, and there is probably more like that to be discovered. It's refreshing to see that the smaller problems of day-to-day programming are addressed too!

3. Some expected things

As expected we've got the hash tables at last, as actually the whole TR.1 stuff like regular expressions, type traits for templates, tuples, general binders and function objects, is in there too. Plus the move constructors and rvalue references.

Moreover the auto keyword and the lambda functions are there, so now we can write

    auto iter = m.begin();
    // and not
    map<string,string>::const_iterator iter = m.begin();

at last! Just think how many keystrokes/copy and pastes it will save!

Speaking of lambdas - as I read it, there isn't one example of a lambda function in the draft! And moreover, in "Chap. 14.3.1 Template type arguments" there's something missing: namely the old restictions about the non-global linkage of the template parameters! This means, I can write a functor in local scope and pass it to the STL algorithm like that:

    void XXX::someFunc()
    {
        struct my_not_zero {
            bool operator() (const X& p) { return p != 0; }
        };

        // use the local functor 
        find(v.begin(), v.end(), my_not_zero());
        // OR use a lambda function:
        find(v.begin(), v.end(), [] (const X& p) -> bool { return p != 0 });
    }

I'd say, what was the reason for lambdas again (at least for me)? To be able write a functor which doesn't have to have global linkage! Are lambdas obsolete then? Well, both yes and no. Just look at the code example above, writing a local functor still requires quite a lot of plumbing, and a lambda expression is somehow more terse (we could even spare the return type of bool in our example!). IMHO both of them are not wholly satisfactory. Using a lambda library solution I could write it in a much more terse way:

    // OR using my pocket lambda library:
    find(v.begin(), v.end(), _$1 != 0 });

Another expected (and somehow dreaded) new thing are the Concepts. I must say thery are everywhere in the standard library section, like in this new std::list move constructor:

    requires AllocatableElement<Alloc, T, T&&> list(list&& x);

I mean, now the standard library header files will get even less readable, but the compiler errors will be (hopefully) more so. So I'm in two minds about this feature: isn't it too much of the type system? What about the duck typing in templates? Are we giving it up? For me it was a very nice feature. I guess it won't come that bad, and the templates without Concepts will be working as before but are Concepts only for compiler support or are we supposed to use meta-typing everywhere?

The next expected thing, which however deserves its own section is:

4. Multithreading support

Sorry, I didn't read it yet... It's two whole chapters (29 and 30) ant they aren't exactly short.

But instead it started me thinkig: how was I writing multithreading applications before there was the C++ memory model defined? How on earth was this possible? Well, it was all vendor (i.e. compiler) specific. When a compiler supported the POSIX thread library (pthreads) for example, it would pose some memory fences around the pthread calls****. It would treat some pieces of code in a special way - just like in Java's String magic. The local static initializes would be automatically guarded by locks (Gnu compiler) or maybe not (Sun compiler). The volatile keyword would be given an extra visibility guarantee (Microsoft compiler). And I never initialized global static variables out of the multithreading part of the program, only in the main thread portion. An the best of it is, that all these techniques wasn't guaranteed to work****! But hey, the 1st Java memory model wa buggy too, wasn't it?

Now it's all supposed to be portable.

One thing which I did read up (however on the Web and not in the proposal itself), and what was a littel unexpected for me, is about the volatile keyword. The proposal didn't stengthen the volatile keyword in the way it's been done in Java or C#. I suppose that out of the reasons of backward compatibility with C's volatile remained only a compiler (dis)optimisation directive, while for the visibility guarantees between threads we are supposed to use the atomic<> library!

How will the old programs using volatile for visiblity between threads be running now? Are they broken? I suppose so, they probably must be rewritten using the atomic<> types.

5. Summing things up

My impression so far is, that there are many small things you wouldn't expect, and that they are fun! I was expecting the big new chunks of functionality to be added (and they were added indeed) to be the most impressive ones, but it's rather the small things which make the difference. Look at that code snippet in the new, cool layout style (which I picked up in this Ferbruary's issue of the MSDN Magazine) :

    for_each(values.begin(), values.end(), [](int& value)
    {
        // now we can nest STL at last! (or can we???)
        for_each(value.begin(), value.end, DoSomething);
    });

I'd dare to say that C++ seems to have put away its 90-ties image, as it allows to write programs more in style of the scripting languages than the old and venerable K&R C! I can only add "at last" and "Amen".

---
* Thanks Jens!
** Herb Sutter's announcement and some discussion with the inevitable C++ bashing: http://herbsutter.wordpress.com/2008/10/28/september-2008-iso-c-standards-meeting-the-draft-has-landed-and-a-new-convener/, the Draft document itself is here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2798.pdf
*** like the article in the Wikipedia, which I found to be surprisingly good: http://en.wikipedia.org/wiki/C%2B%2B0x
**** Hans Boehm: "Threads cannot be implemented as a library" Technical Report HPL-2004-209, HP Laboratories Palo Alto, 2004, http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf