Tag: C++

++it 2018 – Coroutines – coming soon… ?

Posted on by max 1 Comment on ++it 2018 – Coroutines – coming soon… ?

I really enjoyed this talk and not only because the speaker is an old friend on mine. I met Alberto back in the Ubisoft days and he was and still is one of the best C++ programmers I know and for sure the only friend who submitted a proposal to the standard committee that got approved. On the other hand I have no friends who submitted a proposal to the standard committee that was refused. So all my friends who submitted… well I’m digressing.

This talk was in Italian, that is welcome, but… weird. Usually all talks are in English even for Italian conference. Anyway here’s my summary, as usual errors and mistakes are mine. You can find Alberto’s slides here.

Coming Soon to a Compiler Near You – Coroutines

Alberto is a C++ enthusiast programmer since 1990. In this hour he’s going to talk about coroutines, their history and their relation with C++ and C++ Technical Specifications (TS).

A suspend and resume point is a point in the instruction sequence where the execution can be suspended, other stuff is executed and then the execution is resumed from there.

The most common form of suspend and resume point is a subroutine call. The execution is transferred from the caller to the callee and when the callee is done, the execution is transferred back to the caller.

Coroutines are a generalized form of suspension and resume points, that allow you to manage where you want to suspend, transfer control and resume, without be constrained in the caller/callee format.

When is this pattern useful?

Continue reading “++it 2018 – Coroutines – coming soon… ?”

++it 2018 – Key Notes

Posted on by max Leave a Comment on ++it 2018 – Key Notes

Saturday, 23 June 2018, was a sunny day in Milan. The ideal day to close yourself in Milano Bicocca University with many equally nerdy fellow programmers to attend the Italian C++ conference.

I discovered this conference, now in its 3rd edition, by chance, skimming through my never-ending queue of unread tweets. A friend of mine and C++ guru tweeted about this, so I bookmarked the website and as soon as this year’s edition was announced, I was one of the first to register.

Also, it is worth noting that this conference is free (as in beer), lasts a full day, and includes lunch. Talks are interesting, and the conference is organized in two tracks with a single starting keynote and a single closing speech.

Although free, there are famous guests – last year Bartosz Milewski, quite a famous functional programmer and category algebra expert – held a speech about C++ and functional programming; this year the keynote was by Peter Sommerlad — C++ expert and member of the C++ ISO committee.

As usual, my good intentions are to write and publish about each single talk I attended.

Comparison with other conferences I attended, such as Scala Days, Scala Italy, and Lambda World, is natural, although not always fair – ++it is completely free, while others come at a price (not light in case of Scala Days). I couldn’t fail to notice that, on average, the age was older than in the functional world. I won’t try an interpretation, but there could be more than one.

But, enough with babbling, let’s start with the keynote (based on my notes taken during the talk, errors or misunderstandings are just mine). You can find Peter Somerlad’s slides here. My comments at the end.

A – B – C : Agile, BMW, C++

In this talk prof. Somerlad basically tells about his professional career, era by era, providing a short list of lessons learned for each period.

He started programming on an HP pocket calculator. This device had some 50 steps of program instruction and no graphics whatsoever. Also, TI calculators were more widespread at the time, so he had to translate programs from one programming language to another. Although very similar (they were all stack-based), each calculator had some peculiarities.

One program he developed for fun was a ballistic simulation – define a force and a direction to fire a bullet that has to avoid a wall and hit a target. As said, the pocket gizmo has no graphics, but years later, the very same idea was re-instantiated with some graphics and sounds to become… Angry Birds.

Lessons learned:

  • Mentally execute code – there was no debugger.
  • Using the stack;
  • Reading foreign code (to translate from TI to HP);
  • Porting code;
  • Old, simple ideas remain useful.

The first home computer was a ZX Spectrum – an 8-bit computer with a rubbery keyboard that connected to a TV set and used a cassette recorder as mass storage. Each key was decorated with several keywords beside the standard letter and symbol you normally find on a key. When pressing a key, depending on the context, one of the keywords appeared on the screen – automatically typed for you. Context was determined by pressing two shift keys. The correct combo produced the required effect.

At school, he worked on a mainframe that had a curious assembly language. Notably, one instruction, by exploiting an indirection bit, could be used to create an infinite loop. He and another student tried the instruction, and the mainframe froze. After a few seconds, an angry System Administrator entered the room, asking them to quit what they were doing.

Lessons learned:

  • Basic, Z80 assembly and machine code, Pascal;
  • Keyboard shortcuts and meta layout;
  • Patience (loading from tape takes forever);
  • Dealing with errors from hardware.

In 1985, he landed his first job where he had to write a kind of customer management application on an Apple IIe. Now the software had to be professional, and one requirement was that a cat could walk on the keyboard without causing a crash of the application. At times, no commoditized databases were available, and the few DB engines available were very expensive. Since the Apple IIe had floppy discs, they may have to merge the two databases on two discs. The solution is to employ a merge sort, so he took the book from Niklaus Wirth, “Data+Functions=Algorithms” and copied the merge sort implementation. Unfortunately, the merge sort algorithm in the book was not stable, so Peter had to rewrite it from scratch.

Implementing the DB was quite a nightmare due to many technical constraints – computer memory, mass storage size, and computing power. The PC was an IBM with MS-DOS 1.x. This version had no directories. The Pascal language had no dynamic strings – they had to be statically sized.

As computer technology progressed, he switched to a 386-compatible computer and turned to Minix. During this period, Peter used PMate – an editor that sported macros, so that statement frames could be automatically generated.

Lessons learned:

  • Do not trust programming books and commercial libraries.
  • Before putting code in your book, always compile and test it.
  • Programming should be supported by a fast and powerful editor.
  • You should not need to type all of your code.
  • A generic data-driven solution makes code simpler
  • automate tests.

1987 C and Unix courses

During this period, Peter started teaching classes about C and Unix. In this class, shell, system programming, and C were taught. Also, he had to teach how to unlearn things to COBOL programmers.

In 1988, he wrote some C guidelines – some are still applicable today:

  • A function is too long if it does not fit in an 80×24 terminal; functions with longer code indicate a failure in teaching software engineering.
  • A function should not take more than 3-5 parameters, if you need more, then you have to logically group them in a struct. The Windows API had functions with 7 or more parameters, which is why Peter swore never to program this OS.
  • Everything is an int, unless it is a pointer or a double. (The reason why we need to use the typename keyword today is a legacy of this choice made by K&R).
  • Program abstract data types using opaque structs and pointers.
  • Do not use scanf() ever in production code; use sscanf() instead and check its result.

Lessons learned:

  • K&R C, Unix, sh, awk, sed, vi, nroff, make, lex, yacc,…
  • You learn the most by teaching.
  • One can program in FORTRAN/BASIC/COBOL in any language.
  • abstraction, layering, cohesion.
  • The power of plain text, regexp, pipelines, and scripting. Searching log files for what went wrong.

In 1989, Peter graduated. His master’s thesis was about a Modula-2 frontend for the Amsterdam Compiler Kit. This year also brought the first experiments with C++ using the Zortech C++ compiler. Writing code with this environment was quite intensive since any error in the code caused the whole machine to die. These were the days before Protected Memory.

Lessons Learned:

  • Compilers and AST with polymorphic nodes (polymorphism via union);
  • Virtual Machine Languages (p-code, em-code). Java bytecode is very close to em-code.
  • More RAM and CPU power make compilation much faster.
  • ADT works even within a compile.
  • Lex and yacc can be used in practice.

Conscript at Bundenswehr (the German Army). Peter worked in the Computer Center, on systems for Radar detection and analysis. This was quite a trip back in time. The computer was an 18-bit with core memory, switches to input bits into the main memory, and tape for mass storage.

Also, Peter found another computer history milestone – the VT100 terminal. This terminal defined what ANSI escape codes are today.

The language used for programming the system was Jovial, a mix of Pascal and Algol that was later replaced by Ada.

Lessons learned

  • Computer and software history can be interesting.
  • Even hardware can be used beyond its expected lifetime.
  • Source control is important (and copying to a floppy disc is not source control)

In 1990, he landed a job at Siemens and started working in an OO programming environment. Here he worked with Erich Gamma and Andrè Weinard [NdM: I tried to look up this but haven’t found anything relevant, maybe I got the name wrong].

The system Peter was working on was a framework for C++ written in C++, named OOPU, intended to replace TOROS_OBER, a C macro-based OO system used for a car diagnostic computer. Unfortunately, OOPU was killed by internal politics. The reason was that a single programming environment had to be used across several business units, and other business units didn’t want to pay for it.

In this context, Peter wrote an object inspector, named OBER, that showed the relations among objects (this was before DDD was invented). From an architectural point of view, this application sported a UI separated from the backend.

In 1991, Peter wrote the first C++ guidelines, although some are still applicable, many are obsolete because the language has evolved, and things can be done better.

1993 was the year of the PLoP (Pattern Languages of Programming), which was still before the Gang of Four Book. In this conference, many opportunities were available to learn and understand architecture by trying to explain patterns.

1995 is the year of GoF. The most important design patterns are:

Do not use the singleton since C++ has no fixed sequence of initialization. If you need a singleton, think about the design first. If you need globals, just use globals [NdM, I understand that singleton has some problems, but I don’t see what the alternatives are – globals lack of encapsulation].

In PLoPs and EuroPLoP, patterns had a community, where knowledge was shared, and it offered an environment to try out ideas. Discussing how stuff has to be written and why.

With other participants of the PLoP/EuroPLoP, Peter wrote the book POSA – Pattern Oriented Software Architecture. This is less famous than Design Patterns by the Gang of Four, but tackles the same matter.

Layers vs. Tiers -Layers are different levels of abstraction; you can swap a layer implementation with another, while in tiers, functionality is spread across multiple tiers, all the the same level of abstraction, employing different technologies.

Using layers, the team can specialize, while using tiers, the team needs to know everything.

Good abstraction is a skill. Too many layers are a problem if layers do nothing but pass values.

Lessons learned:

  • A prophet has no honor in his own country – get out to be heard;
  • Good patterns require several rewrites.
  • Sharing teaches you to become a better author.
  • Get a good copy editor when publishing.
  • Network to learn, attend, and speak at conferences;
  • The most important part of a conference is the breaks.

In 1997, he moved to Switzerland to take the job of Erich Gamma, more precisely to work on a small server framework www.coast-project.org. While in charge, Peter extended and improved the library and developed C++ Unit Test and test automation in doing so. He delivered high-quality solutions using Agile Software development and Wiki Wiki web.

In these years, Peter came to some interesting conclusions about high-quality software. First, high-quality leads to better developers and better retention of those developers. Unfortunately, high quality leads to canceled maintenance contracts. If nothing goes wrong, the customer doesn’t see the point in paying for something that is never used.

Also, counterintuitively, high quality leads to fewer business opportunities. Since the contacts between customer and developer are minimal and usually don’t escalate to top-level management. So the developer has less chance to meet and know the decision makers of the customer company.

Also, CUTE – the test environment – has been created to replace macro-ish tests.

Lessons learned

  • To advance, you need to take risks.
  • Do not be shy to use your network.
  • If you can not change your organization, change your organization.
  • Leading a team and evolving it is gratifying.
  • Producing software of superior quality might be bad for business.
  • Working software lives longer than intended.

1998 and Agile Development. It became evident that following rituals is not adhering to values. You can do all the scrum rituals, but without committing to its values. When doing agile, the most important things are:

  • Unit Tests and TDD;
  • Refactoring and Simple Design;
  • Rhythm and feedback, i.e., thinking about what you do and what you achieve;
  • Open and honest communication.

Lessons Learned

  • be self-sufficient, but accept and appreciate help;
  • As a patient, you are responsible for yourself.

Since 2004, Peter has been teaching agile and continues teaching C++, concurrent, and network programming. Also started working on IDE and tools to eliminate bad software.

In 2005, many people thought that a refactoring tool for C++ was impossible to write. Peter worked to prove them wrong, and Cevelop is the result.

[NdM: The talk ran out of time about now.]

My comments

Despite being sympathetic with Peter, since we shared so much in terms of computer history, programming, and software engineering, I have to admit that his talk didn’t leave me with much, and some parts were a bit too much of a self-celebration. Maybe the most interesting thought was that quality software leads to less business. The rest of the talk was enjoyable, but I couldn’t see the connection with C++ or the future (or the history) of this language.

Optimization Time – Scala (and C++)

Posted on by max Leave a Comment on Optimization Time – Scala (and C++)

The Case

It is quite a feeling when you learn that your commit, a couple of months ago, broke the build is such a subtle way that it took so long to be detected. Possibly a more thorough testing and validation of the software would have caught it earlier, nonetheless it’s there and you and your coworkers are working hard to delimit the offending code and better understanding what caused the mess.

It turned out that some perfectly working code was taking too much time in one of the hot spot of our codebase. More precisely that code operated a conversion from an incoming data packet into a format suitable for data processing… about 2500 times a second on a modest hardware.

The code resulting in such poor performances that disrupted the device functionality seemed like a good idea in a very functional idiom –

@inline final val SAMPLES_PER_BLOCK = 6
@inline final val BLOCK_LENGTH = 8
@inline final val BLOCK_HEADER = 2

private def decodeFunctional(packet: Array[Byte]): Array[Int] = {
    val lowSamples: Array[Int] = packet.drop(BLOCK_HEADER).map(x => x.toUint)

    val msbs: Int = ((packet(0).toUint << 8) | packet(1).toUint) & 0xFFF
    Array.tabulate(SAMPLES_PER_BLOCK)(
        x => lowSamples(x) | (((msbs << 2 * x) & 0xC00) >> 2)
    )
}

Basically the incoming packet holds six 10-bits samples in 8 bytes and some bits-shifting’n’pasting is needed to rebuild the six sample array for later processing.

Once found that the problem was here I decided rewrite the code to get rid of the functional idiom and take an imperative/iterative approach:

private def decodeImperative(packet: Array[Byte]): Array[Int] = {
    // the code below is ugly, but it needs to be fast, don't touch,
    // unless you know what you are doing
    val samples: Array[Int] = new Array[Int](SAMPLES_PER_BLOCK)
    val msbs: Int = ((packet(0).toUint << 8) | packet(1).toUint) & 0xFFF
    var index: Int = 0
    while (index < SAMPLES_PER_BLOCK) {
        samples(index) = packet(BLOCK_HEADER + index).toUint |
                         (((msbs << 2 * index) & 0xC00) >> 2)
        index += 1
    }
    samples
}

(the comment is a colorful note I decide to leave for the posterity :-)).

The idea is to get rid of the read-only constraint imposed by functional programming and save all the temporaries.

Optimizing is a subtle art, and even if intuition may guide you, only measurement can tell whether the optimization succeeded. So I set up some speed test (see “methodology” below) to objectively assess my results.

The speed improvement was astounding: more than 7 times faster (7.6 to be precise).

Energized by this victory I decided to switch to heavy optimization weapon. Not being sure if scala/java compiler optimization really does its optimization homework, I opted for manually unrolling the loop in the code:

private def decodeUnrolled0( packet: Array[Byte] ) : Array[Int] = {
    val PACKET0 : Int = packet(0).toUint
    val PACKET1 : Int = packet(1).toUint
    Array[Int](
        packet(BLOCK_HEADER+0).toUint | ((PACKET0 << 6) & 0x300),
        packet(BLOCK_HEADER+1).toUint | ((PACKET0 << 8) & 0x300),
        packet(BLOCK_HEADER+2).toUint | ((PACKET1 << 2) & 0x300),
        packet(BLOCK_HEADER+3).toUint | ((PACKET1 << 4) & 0x300),
        packet(BLOCK_HEADER+4).toUint | ((PACKET1 << 6) & 0x300),
        packet(BLOCK_HEADER+5).toUint | ((PACKET1 << 8) & 0x300)
    )
}

I was somewhat disappointed to learn that this version is only marginally faster (x1.6) than the original functional version. This didn’t really make sense to me, since the loop is completely unrolled and just trivial computation needed to be performed. So I decompiled the .class file:

public int[] CheckPerf$$decodeUnrolled0(byte[] packet)
{
  int PACKET0 = UnsignedByteOps(packet[0]).toUint();
  int PACKET1 = UnsignedByteOps(packet[1]).toUint();
  return (int[])Array..MODULE$.apply(Predef..MODULE$.wrapIntArray(new int[] {
    UnsignedByteOps(packet[2]).toUint() | PACKET0 << 6 & 0x300, 
    UnsignedByteOps(packet[3]).toUint() | PACKET0 << 8 & 0x300, 
    UnsignedByteOps(packet[4]).toUint() | PACKET1 << 2 & 0x300, 
    UnsignedByteOps(packet[5]).toUint() | PACKET1 << 4 & 0x300, 
    UnsignedByteOps(packet[6]).toUint() | PACKET1 << 6 & 0x300, 
    UnsignedByteOps(packet[7]).toUint() | PACKET1 << 8 & 0x300 }), ClassTag..MODULE$.Int());
}

Instead of the Java array I expected, some Scala internals are used to create the array and then converting it into the Java thing. Possibly this was the cause of the slowness. By looking around at the decompiled code I found another function that just used a Java int array. So I rewrote the unrolled version accordingly –

private def decodeUnrolled1( packet: Array[Byte] ) : Array[Int] = {
    val samples = new Array[Int](SAMPLES_PER_BLOCK)
    val PACKET0 = packet(0).toUint
    val PACKET1 = packet(1).toUint
    samples(0) = packet(BLOCK_HEADER + 0).toUint | ((PACKET0 << 6) & 0x300)
    samples(1) = packet(BLOCK_HEADER + 1).toUint | ((PACKET0 << 8) & 0x300)
    samples(2) = packet(BLOCK_HEADER + 2).toUint | ((PACKET1 << 2) & 0x300)
    samples(3) = packet(BLOCK_HEADER + 3).toUint | ((PACKET1 << 4) & 0x300)
    samples(4) = packet(BLOCK_HEADER + 4).toUint | ((PACKET1 << 6) & 0x300)
    samples(5) = packet(BLOCK_HEADER + 5).toUint | ((PACKET1 << 8) & 0x300)
    samples
}

The main difference is that here the array is first declared and allocated, then filled. In the above code the array was created, initialized and returned all in the same statement.

The speed improvement was good, but not much better than my imperative version: x7.77 times faster.

Then a colleague pointed out that I was using the “old” Scala 2.10 compiler and that I should try the latest 2.12 that benefits from a better interoperability with the underlying JVM 1.8.

In the following table you get the performance comparison:

Attention: The internal data of table “1” is corrupted!

Functional and unrolled0 are quite unsurprising, just what you expect from the next version of the compiler. Imperative approach yields quite a boost – 22 times faster than the functional version on the previous compiler. The shocking surprise is in the last column – the unrolled1 version of the code runs in excess of 1200 times faster than the original code!

Before jumping to conclusions, I performed the same tests on the code translated into C++. Here is the equivalent code:

typedef std::array<int,SAMPLES_PER_BLOCK> OutputArray;
typedef std::array<uint8_t,BLOCK_LENGTH> InputArray;

OutputArray decodeImperative( InputArray const& packet )
{
    OutputArray samples;
    uint32_t msbs = ((packet[0] << 8) | packet[1]) & 0xFFF;
    for( int index=0; index< SAMPLES_PER_BLOCK; ++index )
    {
        samples[index] = packet[BLOCK_HEADER + index] |
                         (((msbs << 2 * index) & 0xC00) >> 2);
    }
    return samples;
}

OutputArray decodeFunctional( InputArray const& packet )
{
    OutputArray lowSamples;
    std::copy( packet.begin()+2, packet.end(), lowSamples.begin() );
    uint32_t msbs = ((packet[0] << 8) | packet[1] ) & 0xFFF;
    OutputArray samples;

    int index=0;
    OutputArray::const_iterator scan = lowSamples.begin();
    std::generate(
        samples.begin(),
        samples.end(),
        [&index,&scan,msbs]()
        {
            return *scan++ | (((msbs << 2*index++) & 0xC00) >> 2);
        }
    );
    return samples;
}

OutputArray decodeUnrolled0( InputArray const& packet )
{
    uint8_t PACKET0 = packet[0];
    uint8_t PACKET1 = packet[1];

    return OutputArray{
        packet[BLOCK_HEADER+0] | ((PACKET0 << 6) & 0x300),
        packet[BLOCK_HEADER+1] | ((PACKET0 << 8) & 0x300),
        packet[BLOCK_HEADER+2] | ((PACKET1 << 2) & 0x300),
        packet[BLOCK_HEADER+3] | ((PACKET1 << 4) & 0x300),
        packet[BLOCK_HEADER+4] | ((PACKET1 << 6) & 0x300),
        packet[BLOCK_HEADER+5] | ((PACKET1 << 8) & 0x300)
    };
}

OutputArray decodeUnrolled1( InputArray const& packet )
{
    OutputArray samples;
    uint8_t PACKET0 = packet[0];
    uint8_t PACKET1 = packet[1];

    samples[0] = packet[BLOCK_HEADER+0] | ((PACKET0 << 6) & 0x300);
    samples[1] = packet[BLOCK_HEADER+1] | ((PACKET0 << 8) & 0x300);
    samples[2] = packet[BLOCK_HEADER+2] | ((PACKET1 << 2) & 0x300);
    samples[3] = packet[BLOCK_HEADER+3] | ((PACKET1 << 4) & 0x300);
    samples[4] = packet[BLOCK_HEADER+4] | ((PACKET1 << 6) & 0x300);
    samples[5] = packet[BLOCK_HEADER+5] | ((PACKET1 << 8) & 0x300);
    return samples;
}

I’m positive that functional purist will scream in horror at the sight of C++ functional version of the code, but it is the closest thing I could do using the standard library. Should you have any idea on how to improve the functional idiom using the standard library, let me know and I’ll update my test set.

Here are the C++ results –

Attention: The internal data of table “2” is corrupted!

This is mostly unsurprising but for the the lower right column which seems to indicate that Scala version is faster than C++. I guess that the reason is because I am using timing values that are rebased considering a standard price you pay for executing the code under test and that I don’t want to consider in my measurements (see below about the methodology I used). My interpretation is that the overhead in Scala hides the cost for a trivial expression so that the base time is much more close to the execution time than it is in C++.

Conclusions

Drawing general conclusions from a specific case is all but easy and trivial. Anyway according to data and to intuition, if you want to code using the functional idiom you pay a price that sometimes can be hefty. Paying an execution price, be it memory or cpu cycles, to raise the abstraction level is something that has been with computer programming from the dawn of this craft. I remember echoes from the ranting against high level languages in favor of assembly to avoid paying a 30% penalty. Now those times are gone, but facing a x4-x7 overhead can be something not always you can afford.

(Raising the level of abstraction by employing the functional idiom is something that is not undisputed, but I will spare this for another post).

Writing efficient code is not always intuitive. Constructs that seem innocent enough turns out to be compiled into time consuming lower level code. Peeking at compiled code is always useful. While languages as C++ are accompanied by detailed information about performances of various constructs and library components, Scala (as Java) lacks of these information. Also the huge amount of syntactic sugar employed by Scala does not simplify the life of the programmer that has to optimize code.

Eventually I cannot save to remarks the performances of interpreted languages (and even more so functional interpreted languages), despite of the progress in the JVM technologies, are still way behind native language ones. Even employing a functional approach C++ is some 80 times faster than Scala. You can argue that the C++ code above is not really functional, but there is nothing preventing me to use a mostly functional library for C++, with roughly the same performances of the functional version of the C++ code. It could be more tedious to write because of the lesser grade of syntactic glucose in C++, yet it is still functional.

I’m curious to see how scala-native compares, but this again is a topic for another post.

The last thought I want to report here is that you can make Scala code much faster, by avoiding the functional paradigm and peeking at compiled code. It is something you are not usually expected to do, but and improvement of 1200 times is a worth gain for the most executed code.

A very last thought for those who think that after all nowadays we have such powerful computers that analyzing performances and optimizing is a waste of time. I would like to remember that data processing requires energy and today energy production mostly relies on processes that produce CO2, something that the world doesn’t need. A data processing that runs just twice the speed of another will produce half of the carbon dioxide emissions. The environment benefits for switching to C and C++ should be clear to everyone.

Methodology

A couple of words on methodology. The compilers were Scala 2.10.6, Scala 2.12.2 and GNU c++ 7.3.1. All the test were performed on Linux (Fedora Core 27) using the command /bin/time –format=”%U %S”  command to print the User and Kernel times of the command and summing the two values together. These are times that CPU spent executing the process, not wall clock. The decoding function is executed 0x7FFFFFFF (some 2 billions) times per run and each program is tested for 12 runs. The fastest and the slowest run are discarded and the other are used to compute an average that is considered the measure of the test.

The base time is computed by employing a dummy decoder that does nothing but filling the result array with constants.

This setup should take in account the JIT effect and measure just the code I listed above.

Comparisons

Posted on by max 6 Comments on Comparisons

Recently I had to spend some time trying to adapt my imperative/OO background to a piece of code I need to write in functional paradigm. The problem is quite simple and can be described briefly. You have a collection of pairs containing an id and a quantity. When a new pair arrives you have to add the quantity to the pair with the same id in the collection, if exists, otherwise you have to add the pair to the collection.

Functional programming is based on three principles (as seen from an OO programmer) – variables are never modified once assigned, no side-effects (at least, avoid them as much as possible), no loops – work on collections with collective functions. Well maybe I missed something like monad composition, but that’s enough for this post.

Thanks to a coworker I wrote my Scala code that follows all the aforementioned principles and is quite elegant as well. It relies on the “partition” function that transforms (in a functional fashion) a collection into two collections containing the elements of the first one partitioned according to a given criteria. The criteria is the equality of the id so that I find the element with the same id if it exists, or just an empty collection if it doesn’t.

Here’s the code:

    type Collection = List[Data]

    def merge( collection : Collection, data : Data ) : Collection = {
        val result = collection.partition( _.id == data.id )
        result match {
            case (List(),other) =>
                data :: other
            case (List(old),other) =>
                Data( data.id, data.quantity+old.quantity ) :: other
        }
    }

Yes, I could have written more concisely, but that would have been too much write-only for me to be comfortable with.

Once the pleasant feeling of elegance wore off a bit I wondered what is the cost of this approach. Each time you invoke merge the collection is rebuilt and, unless the compile optimizer be very clever, also each list item is cloned and the old one goes to garbage recycling.

Partitioning scans and rebuild, but since I’m using an immutable collection, also adding an item to an existing list causes a new list to be generated.

Performance matters in some 20% of your code, so it could acceptable to sacrifice performance in order to get a higher abstraction level and thus a higher coding speed. But then I wonder what about premature pessimization? Premature pessimization, at least in context where I read the them, means the widespread adoption of idioms that lead to worse performances (the case was for C++ use of pre or post increment operator). Premature pessimization may cause the application to run generally slower and makes more difficult to spot and optimize the cause.

This triggered the question – how is language idiomatic approach impacts on performances?

To answer the question I started coding the same problem in different languages.

I started from my language of choice – C++. In this language it is likely you approach a similar problem by using std::vector. This is the preferred collection and the recommended one. Source is like this:

typedef std::vector<Data> Collection;

void
merge( Collection& collection, Data data )
{
    auto iter = std::find_if( collection.begin(),
                              collection.end(),
                              [&]( Data const& probe ){ return probe.id == data.id; } );
    if( iter == collection.end() )
    {
        collection.push_back( data );
    }
    else
    {
        iter->quantity += data.quantity;
    }
}

Code is slightly longer (consider that in C++ I prefer opening brace on a line alone, while in Scala “they” forced me to have opening braces at the end of the statement line). Having mutable collections doesn’t require to warp your mind around data to find which aggregate function could transform your input data into the desired output – just find what you are looking for and change it. Seems simpler to explain to a child.

Then I turned to Java. I’m not so fond of this language, but it is quite popular and has a comprehensive set of standard libraries that really allow you to tackle every problem confidently. Not sure what a Java programmer would consider idiomatic, so I staid traditional and went for a generic List. The code follows:

    static class Data
    {
        public int id;
        public int quantity;
    }

    private static void merge( List<Data> collection, Data data )
    {
        ListIterator<Data> iterator = collection.listIterator();
        while( iterator.hasNext() )
        {
            Data probe = iterator.next();
            if( probe.id == data.id )
            {
                probe.quantity += data.quantity;
                return;
            }
        }
        collection.add( 0, data );
    }

I’m not sure why the inner class Data needs to be declared static, but it seems that otherwise the instance has a reference to the outer class instance. Anyway – code is decidedly more complex. There is no function similar to C++ find_if nor to Scala partition. The loop is simple, but it offers some chances to add bugs to your code. Anyway explaining the code is straightforward once the iterator concept is clear.

Eventually I wrote a version in C. This language is hampered by the lack of basic standard library – beside some functions on strings and files you have nothing. This could have been fine in the 70s, but today is a serious problem. Yes there are non-standard libraries providing all the needed functionalities, you have plenty of them, gazillions of them, all incompatible. Once you chose one you are locked in… Well clearly C shows the signs of age. So I write my own single linked list implementation:

struct Data
{
    int id;
    int quantity;
};

struct ListNode
{
    struct ListNode* next;
    struct Data data;
};

typedef struct ListNode* List;

void merge( List* list, struct Data data )
{
    for( struct ListNode* scan = *list; scan != NULL; scan = scan->next )
    {
        if( scan->data.id == data.id )
        {
            scan->data.quantity += data.quantity;
            return;
        }
    }
    pushFront( list, data );
}

Note that once cleaned of braces, merge function is shorter in C than in Java! This is a hint that Java is possibly verbose.

I just wrote here the merge function. The rest of the sources is not relevant for this post, but it basically consists in parsing the command line (string to int conversion), getting some random numbers and getting the time. The simplest frameworks for this operation are those based on the JVM. The most complex is C++ – it allows a wide range of configuration (random and time), but I had to look up on internet how to do it and… I am afraid I wouldn’t know how to exploit the greater range of options. Well, in my career as a programmer (some 30+ years counting since when I started coding) I think I never had the need to use a specific random number generator, or some clock different from a “SystemTimeMillis” or Wall Clock Time. I don’t mean that because of this no one should ask for greater flexibility, but that I find daunting that every programmer should pay this price because there is case for using a non default RNG.

Anyway back to my test. In the following table I reported the results.

C++ Scala Java C C++
vector list
time (ms) 170,75 11562,45 2230,05 718,75 710,9
lines 81 35 69 112 81

Times have been taken performing 100000 insertions with max id 10000. The test has been repeated 20 times and the results have been averaged in the table. The difference in timing between C++ and Scala is dramatic – with the first faster about 70 times the latter. Wildly extrapolating you can say that if you code in C++ you need 1/70 of the hardware you need to run Scala… there’s no surprise (still guessing wildly) that IBM backs this one.

Java is about 5 times faster than Scala. I’m told this is more or less expected and possibly it is something you may be willing to pay for higher level.

In the last column I reported the results for a version of the C++ code employing std::list for a more fair comparison (all the other implementations use a list after all). What I didn’t expected was that C++ is faster (even if slightly) than C despite using the same data structure. It is likely because of some template magic.

The other interesting value I wrote in the table is the number of lines (total, not just the merge function) of each implementation. From my studies (that now are quite aged) I remember that some researches reported that the speed of software development (writing, testing and debugging), stated as lines of code per unit of time, is the same regardless of the language. I’m starting having some doubt because my productivity in Scala is quite low if compared with other languages, but … ipse dixit.

Let’s say that you spend 1 for the Scala program, then you would pay 2.31 for C++, 1.97 for Java and 3.20 for C.

Wildly extrapolating again you could draw a formula to decide whether it is better to code in C++ or in Scala. Be H the cost of the CPU and hardware to comfortably run the C++ program. Be C the cost of writing the program in Scala. So the total cost of the project is:

(C++) H+C×2.31

(Scala) 68×H+C

(C++) > (Scala) ⇒ H+C×2.31 > 68×H+C ⇒ C×1.31 >67×H ⇒ C > 51.14×H

That is, you’d better using Scala when the cost of the hardware you want to use will not exceed the cost of Scala development by a factor of 50. If hardware is going to cost more, then you’d better use C++.

Beside of being a wild guess, this also assumes that there is no hardware constraint and that you can easily scale the hardware of the platform.

(Thanks to Andrea for pointing out my mistake in inequality)

Ugly Code

Posted on by max Leave a Comment on Ugly Code

Unfortunately, I’m a sort of a purist when it comes to coding. Code that is not properly indented, global and local scopes garbled up, obscure naming, counter-intuitive interfaces… all conjure against my ability to read a source and causes a headache, acid stomach, and buboes. “Unfortunately,” I wrote, meaning that’s most unfortunate for the poor souls that have to work with me to whom I should appear as sort of source code Taliban.

Recently my unholy-code-alarm triggered when a colleague – trying unsuccessfully to compile an application produced by a contractor – asked me for advice.

More and more I delved into the code, more and more my programmer survival instinct screamed. The code was supposedly C++ and the problem was related to a class, that I would call – to save the privacy and dignity (?) of the unknown author – SepticTank. This class interface was defined inside a .cpp and then again in a .h. Many methods were inlined by implementing them in the class interface (and this possibly was part of the problem).

After resolving some differences, the code refused to link because there was a third implementation of the SepticTank destructor in a linked library. I claimed that such code couldn’t possibly work (even after disabling the dreaded precompiled headers – never seen a Visual Studio project working fine with precompiled headers), even if we could manage to get it compiled and linked the mess was so widespread that nothing good could come.

My colleague tried to save the day by removing the implementation of the SepticTank destructor so as to leave the implementation found in the linked library.

In the end, he had to give up because the code was broken beyond repair, and even if it compiled and linked it crashes on launch (not really surprising).

What stroke me most, basically because it caused a slight fit of dizziness, was the sight of the mysterious operator below –

class SepticTank
{
    public:
        // code removed for your comfort
        operator SepticTank* ()
        {
            return this;
        }
        // other code removed, again for your comfort
};

My brain had some hard moments trying to decode signals from my eyes. Then it figured out that the coder was redefining the implicit conversion to the class pointer so as to use instances and references where pointers were expected… why on the Earth one should want something like that?!?

Implicit conversions if not handled correctly are a sure way to kick yourself on the nose and this is enough a good reason to stay away. But… trying to enter the (criminal) mind that wrote that code, what’s the purpose? Just to avoid the need for the extra ‘&’ ? Or is it a Javism? Maybe it is better to stay out of such minds…

I’d like to introduce…

Posted on by max Leave a Comment on I’d like to introduce…

Say you have slightly more than one hour to talk about C++ to an audience of programmers that range from the self-taught C-only programmer to the yes-I-once-programmed-in-C++-then-switched-to-a-modern-language. What would you focus your presentation on?I started composing slides thinking C++ for C programmers, but it is a huge task and sure the result won’t fit into a single week.
Also I must resist the temptation to teach, since a single hour is not enough to learn anything.
Then I am planning to re-shaping my presentation in form of wow-slides. I mean every slide (no more than 10-15 of them) should show a C++ idiom / technique / mechanism that would cause a wow-reaction in a C programmer or in a C++80 programmer.
Advices are highly appreciated.

Having a Good Time

Posted on by max Leave a Comment on Having a Good Time

Once upon a time, there was this Unix thing powering departmental mainframes. When it came to keeping track of system time, it sounded like a perfect solution to have a virtual clock ticking once every second and counting seconds since the EPOCH was the way to keep track of the current date and time. Such a clock, stored in 32 bits, had several advantages – it was simple and easy to store and manipulate, and it was guaranteed to be monotonically increasing for such a long time that it would have been someone else’s problem the day that this guarantee would have been broken. Now switch context, you are working on a micro within an embedded system. The micro has the standard nowadays System On Chip parade of peripherals, including a hardware timer that can be programmed to interrupt your code at any frequency that is convenient to you.

Using 1ms as a clock base may seem a little aggressive, but that timespan makes a lot of sense – it is unnoticeable for us sluggish humans, but it’s sort of eons for a speedy electron. In other words, it is a good compromise to base your time engine. You can build on this some timer virtualization so that you may employ multiple timers, either periodical or one-shot, in your application.

So far, so good, but there’s a catch. Consider using a 32-bit variable to keep the time (as the glorious Unix time_t). Starting from 0 on every power-up (after all, it is not mandatory to keep the full calendar information), it will take one-thousandth of the time it takes Unix to run out of seconds. Is that enough to be someone else’s problem? No, that’s much closer to your paycheck. It takes some 49 days to roll over if the variable is unsigned.

At the rollover, you lose one important property of your clock – increasing monotonicity. One millisecond, you are at 0xFFFFFFFF, and the next one, you are at 0x00000000. Too bad.

Every comparison between times in your code is going to fail.

Is there anything that we could do? Let’s say we have a code like this –

if( now > startTime + workingSpan )
{
    // timeout
}

It seems perfectly legit, but what happens if startTime approaches the rollover boundary? Let’s say that startTime is 0xFFFFFFF0, workingSpan is 0x10, and now is 0xFFFFFFF8. That means that now is within the working span, and we expect the test to succeed. Instead, the test will fail, because 0xFFFFFFF0 + 0x10 rolls into 0x0000000,0 which is NOT greater than now (0xFFFFFFF8).

Is there any way around before going into 64-bit?

You may try to check if the operation is going to overflow and act accordingly, e.g.

uint32_t LIMIT = MAXUINT32 - workingSpan;
if( startTime > LIMIT )
{
    handle overflow...
}

Or you may check if the operation overflowed –

uint32_t timeLimit = startTime + workingSpan;
if( now < startTime || now > timeLimit )
{
    handle overflow
}

You may have to trim a bit of the code for corner cases, but I wouldn’t care because there is a simpler way. An interesting property of modulo arithmetic is that

a - b = modulo[n]( a- b )

as long as a – b < n. That means that if we manage to transform the comparison operation from absolute to relative, then we can forget about the overflow and rollover problem. So the following code:

if( workingSpan < now - startTime )
{
// timeout
}

It is correct from an overflow/rollover point of view, does not require extra computing time, nor space, and is as readable as the original code.

Java vs. C++, last call

Posted on by max Leave a Comment on Java vs. C++, last call

Well, I dragged this for too long. Now I have to pick the language for the next project. My language of choice is C++, but there are some serious motivation for using Java, one is that all of the junior programmers involved has some experience of Java, another is that middle management is biased toward Java. So, I can still chose C++, but I have to put forward strong and sound engineering reasons. Also because this can become a little … political. I mean – should the project be late for “natural” development reason, or whatever other reason, I don’t want to be blamed because I decided for a language perceived as complicated and rough.
The application isn’t going to need machoFlops or be resource intensive, therefore performance-wise there is no reason to avoid Java.
Java has a thorough and complete library, quite homogeneous even if not always well designed.
I consider C++ to be more flexible and expressive, but is there a more demonstrable software engineering property of C++ that I can use in my argumentations to favor the choice of this language?
(Or conversely is there any demonstrable advantage of Java the could convince me to switch my language of choice).

C++ lambda functions, my first time

Posted on by max Leave a Comment on C++ lambda functions, my first time

Some days ago I wrote my first lambda expression in C++.

    int n=0;
    std::for_each( begin, end, [[&n]](std::uint8_t& a){a=n++;});

If you are back at the C++85 age, this could look like any other alien language from a Star Trek episode. If you are updated at the more recent C++98, the syntax would look funny at minimum.
At least, that is what it looked to me before starting to get some information about the new standard (you can find a brief yet comprehensive recap of what changed in C++ on this specific page of Bjarne’s website).
You should read the code above as follows. The square brackets defines the intro for the lambda function. Within the square brackets you should put what the lambda function should capture of the environment.
In the code, I stated that n should be captured by reference (&). I could have replaced the ampersand if I wanted to have the capture happen by value. Or I could have put nothing should I wanted the lambda function to capture everything.
Next the argument comes, not different from standard function. Eventually the function body.
Once you get this quick start, you will easily decode as a way to fill a range with increasing integers. Take a breath, get another look at the code, ok, now it should make sense.
Well, I’m quite with Stroustrup when he says that he has mixed feelings about lambda functions (I am looking for the quote, but I don’t have it handy). For simple function lambdas are a godsend. On the other hand, lambdas can yield a terrific potential of hiding mechanism and causing major headaches should they escape your control.
If you compare the line above with the code you have to write previously, it is obvious that lambda expressions are a giant leap forward.
In the C++98 days you ought to write –

class DisposableNameForClass
{
public:
    DisposableNameForClass() : n( 0 ) {}
    void operator() ( int& a ) { a = n++; }
private:
    int n;
};

//..
DisposableNameForClass disposableNameForInstance;
std::foreach( begin, end, disposableNameForInstance );

And that is very uncomfortable and inconvenient. By looking at code like this it easy to question whether it makes sense to use the std::for_each at all rather than roll your own code.
But, look at the traditional code

    int n=0;
    while( begin != end )
    {
        *begin++ = n++;
    }

This code is pretty clear to anyone has a minimum familiarity with C or one of the derived language (yes, there is the dereference operator which involves pointers, but shouldn’t pose real obstacles to comprehension).
Is it error prone? Possibly as any code longer than 0 bytes. std::for_each saves you at least two errors – messing up the loop termination condition (e.g. forgetting the ! from the comparison, or comparing for equality rather than inequality) and missing the increment of the iterator (this happened to me at least once).
These reasons may not be enough to recommend std::for_each in C++98, but it is hard to argue against if you can use the lambda functions.