++it18 – Zero Allocation and No Type Erasure Futures

This talk by Vittorio Romeo tackles a subject that could go ignored if your programming style doesn’t feel the need for parallelism (or if it does, pthreads satisfies such a need). Futures have been introduced in C++ with 2011 ISO standard, they hardly can be deemed as novelty.

I’ve been hit by futures some 4 years ago when confronted with a large code base in Scala that exploited futures and actors. So, at least to save my ego, there is nothing wrong if you don’t know what a future is :-).

In brief a future is a way to model a concurrent operation. The future can be either in execution or succeeded with a result value, or failed with an error. As user, you request an async operation and you get a future of the expected result. You can set callbacks on the completion, or combine several futures together either by chaining or by synchronize them. As you may imagine futures vastly simplify the handling of async computation by hiding the synchronization and communication details and by providing a common and clear usage pattern.

So, no excuse, if you need to do async programming, you’d better know this tool.

Read more++it18 – Zero Allocation and No Type Erasure Futures

++it18 – Time Travel Debug

This talk presented a very interesting object – the debugger the could go backward.  But I don’t want to steal the scene, since Paolo Severini from Microsoft explained everything quite well in his talk. Here you can find the slides. Nedless to say errors are mine.

Everyone knows that debugging is twice as hard as writing the code in the first place. So if you’re as clever as you can be when you write it, how long will it take to debug it?

Debugging could be both hard and time consuming. Bugs can be difficult to replicate, especially those involving memory corruption, race conditions, or those that happen randomly or intermittently.

More often than not, it can be hard to spot the cause from logs or crash dumps. Also step by step debugging may require several restarts.

When doing step-by-step debugging is quite common something like:

step into, step over, step over, step over, step ov.. @!# I should have stepped into!.

The more information we can get from debugging tools the better. A tool that could tell “what just happened” would be very very useful.

Reverse debugging is such a tool. The idea is to record state by state everything happens in the CPU that’s executing the code and then the reverse debugger allows the programmer to play back and forth to spot the problem.

First ideas of such a tool dates back to 70s [NdM. I keep noticing that most of the computer science has been invented back in the 60-70s years. They just lacked the CPU resource for practical applications].

There are several tools for reverse debugging native code:

In this speech I will present TTD.

TTD is the reverse debugger for Windows. It is fully integrated with WinDbg. TTD can be used for all user-mode processes, for multithread and multicore

In order to use TTD, you need to set WinDbg to record data. This option needs to be explicitly enabled since has two main drawbacks – first all the program execution is slowed down and then quite a large amount of data is produced. You can expect anywhere between 5 and 50 Mb/s.

After recording has started, debugging works as expected, plus you can step back and forth and also continue backward or forward.

Take note that TTD works only in the latest versions fo Windows 10.

Interestingly you can perform queries on data collected during execution. Every line in the database matches an assembly instruction executed. So you can query how many times some instruction has been executed, how many exceptions have been thrown and so on.

[NdM: A working demo follows, unfortunately the time is quite constrained. A sample program to recursively compute the byte size of file in a directory tree is presented. The program just crashes when executed. So it is executed in WinDbg with TTD enabled. The execution halts as usual in the middle of exceptionland where nothing can be understood unless you speak advanced assembly. By pressing back a couple of time the debugger, going backwards, reaches the last function executed, the one who crashed. At this point Paolo places a breakpoint at the beginning of the function and – with a good implementation of the WOW effect – runs the program backwards. The execution back-reaches the function beginning and can be step forward to better understand why it crashed]

The presentation has been very interesting to show the tool capabilities. I tried an evaluation of UndoDB back in 2006, but it was as uncomfortable as it could be since it had to be used from command line. WinDbg+TTD is light years ahead in terms of usability.

Also I found very interesting the data query feature. Having the db of the program execution states allows the programmer to get a number of important statistics and events without the need of adding instrumentation or specific breakpoints.

The drawback is the execution time, but I guess that without a specific hardware support this is the price we have to pay still for some time in the future.

++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?

Read more++it 2018 – Coroutines – coming soon… ?

++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 neverending queue of unread tweets. A friend of mine and C++ guru twitted about this, so I bookmarked the website and as soon as this year 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 the 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 to.

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 to a price (not light in case of Scala Days). I couldn’t fail to notice that age on average was older here 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 a HP pocket calculator. This device had some 50 steps of program instruction and no graphics whatsoever. Also TI calculators were more widespread at time, so he had to translate programs from one programming language to another one. 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 reamain useful.

The first home computer was a ZX Spectrum – an 8bits computer with rubbery keyboard that connected to a TV set and used a cassette recorder as mass storage. Each key was decorated with several keyword beside the standard letter and symbol you normally find on a key. When pressing a key, depending on the context, one of such a keyword 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. Notable one instruction, by exploiting an indirection bit, could be used to create an infinite loop. He and another one student tried the instruction and the mainframe froze. After 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 on the book was not stable, so Peter had to rewrite it from scratch.

Implementing the DB was quite a nightmare for 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 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 fast and powerful editor;
  • you should not need to type all of your code;
  • generic data driven solution make code simpler
  • automate tests.

1987 C and Unix courses

During this period Peter started teaching classes about C and Unix. In this classes 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 actual today:

  • a function is too long if it does not fit in a 80×24 terminal; functions with longer code tells 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 struct. Windows API had function with 7 or more parameters, that 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 thesis was about a Modula-2 frontend for the Amsterdam Compiler Kit. In this year, also 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 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 travel back in time. The computer was an 18 bits 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 floppy disc is not source control)

In 1990 he landed a job at Siemens and started working in 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 at was a framework for C++ written in C++, named OOPU, intended to replace TOROS_OBER a C macro based OO system used for 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 architectural point of view this application sported an UI separated from the backend.

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

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

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

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

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

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

Layers vs. Tiers -Layers are different level of abstraction , you can swap a layer implementation with another; while in tiers, functionality spread on 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;
  • most important part of a conference are 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 developer and better retainment of those developer. 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, counter intuitively, high quality leads to less 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 test.

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 with a 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 started teaching agile and continued teaching C++, concurrent and network programming. Also started working on IDE and tools, with the goal to eliminate bad software.

In 2005 many people thought that 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. Also I fail to see the lack of some 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.

podcast

Since few years ago my daily commute time increased reaching some 25′ per leg. This time is quite long and listening to latest pop music hits for two half hours a day, or worse to speakers and DJs easy talks, quickly became boring. So I discovered the world of podcast (well, Max, welcome in the new Millenium…).

There are so many so I would like to share what I found. If you have a good podcast you want to share please leave me a comment, I’ll be happy to try it out.

English podcasts

Techbyter World Wide – “The hi-tech podcast in plain English”, this is the subtitle of this podcast. One issue every week talking about software applications and operating system (mainly Windows) from the user and power user perspectives. About 20′ of tech talk without advertising. Though the podcast is not aimed at pro, it has quite many helpful advices and tips and tricks. I listened all the back issues since the very first when Bill Blinn, the author who worked professionally as a radio speaker, tried out the new media after he quit from the radio.

Over the time I got several good advice – Adobe Light Room to process and manage my digital pictures, Clementine for listening to audio files, Carbonite and Crashplan for backing up data. FastCopy and too many other to cite them all here.

Read morepodcast

Despicable People

Every place I worked had a different culture. I found this interesting and, when the conditions are proper, very entertaining. The workplace culture is something that can strongly motivate you, something that makes you feel part of something unique that’s happening right here and now.

When I worked at Ubisoft I collected all the jargon we used in a dictionary.

My current job is not different. During the years, recurring rants and complains made my friend Francesco and I create a list of despicable types of people. You know when you see something in the code that it is not just right or some approach to the problem that you consider plainly wrong? That’s the base idea. Then take into account other colleagues that have strong ideas about what is Holy and what is Evil and you get lot of jokes only you and your team can understand.

So the list has a split nature, half a satire against Absolute Truth and half a complain against those who write code for a living, but are not Real Programmers. That’s how this ever groving list of wrongdoers came together.

Here are our current list. It is very nerdy and most pun and jokes are likely difficult to catch even if you are a seasoned programmer, so I will offer a decoding table at the end of the post. Ready? Let the rant begin?

Despicable types of people (in no particular order)

  1. those who don’t do a memset at the beginning of each function
  2. those who define nonsense operators
  3. those who start counting from 1
  4. [C++] those who pass references without const modifier even when they do not change the argument
  5. [C++] those who don’t place const in the signature of methods that don’t change the status of the instance
  6. [C++] those who use delete without [] to free an array
  7. those who don’t program in C
  8. those who don’t use Windows XP
  9. those who use the very same logging message in several lines of their code
  10. [C++] those who do delete this with no reason
  11. those who don’t know Z80 assembly
  12. those who don’t remove every warning from their code
  13. those who check in an if condition if a boolean variable is == true in languages where booleans can only be true or false
  14. those who name variables and functions in a language but English
  15. those who use DBs
  16. those who create animations using .obj files
  17. those who punctuate randomly
  18. those who pronounce acronyms half in Italian and half in English
  19. those who write programs that exceed 48k RAM.

So here is a little analysis/explanation

1 This means “to perform a memset of the variables on the stack, so that everything is initialized in a function before doing actual work”. Therefore this belongs to a sort of self defensive programming approach – trust no one, yourself included (after all who is going to use the variables freshly created on the stack?).

2. It is aimed mostly at languages where you can redefine operators – C++ and Scala. In Scala you can define every sequence of symbols as a custom operator. Usually this is utterly confusing for beginners and everyone that is not fluent with the library the defines such operators. Personally I find DSL a messy confusion that brings no real advantage for at least two reason – first you know the host language but you need to learn the DSL that has different syntax/semantic and then the DSL forces the “host language” but has to comply with it and this results in odd looking syntax, misleading punctuation or phrasing. I much prefer a traditional library with a possibly well defined interface to Vulcan gibberish such as :::, |–>, ~>.

3. How many times have you found code where the programmer started counting from 1, even if the language was C? This is annoying because there are very good reasons to start from 0… but someone prefers to ignore them and sticks with medieval culture lacking the concept of zero.

4,5. In C++ (and to a lesser extent in C) you can enforce a type checking strategy called const-correctness. Basically this strategy marks data that is expected to stay constant through-out some operation. This helps in writing better code because the user programmer can make stronger assumptions. Unfortunately you can’t use non const-correct code from const-correct code (and possibly this is why Java has no const-correctness concept) so the lazy programmer prefers to ignore the whole issue.

6. This is a plain bug, because delete new int[10] is undefined behavior as per C++ standard. Nonetheless poorly written (and tested) code has such patterns.

7, 8 and 15 are basically exaggerations of what some people with Absolute Truth assert. Taken out of their contexts these sentences sound even more absurd, but the meaning is “simple and tested systems tend to be more reliable than complex and new ones”.

9. Logging is helpful to get insights on the sequence of operations inside a running software. If you replicate the very same text then it is quite hard to figure out what the executed sequence was. This is plain dumb.

10. Deleting this in C++ can be colorfully depicted as cutting the branch on which you are sitting. This is something that usually you don’t want to do. If you find yourself needing this it is likely that you are approaching the problem from a wrong perspective. Seldom this operation is correct.

11. Z80 CPU was a popular microprocessor back in the 80s. Programming in Z80 assembly was easy, surely easier than programming the 6502, another popular micro of the same years. This point is another overstatement that refers back to a Golden Age where everything was proper and sound.

12. Compiler warning, most of the times, are just picky annoyance, not much different than a crooked picture on the wall. Sometimes they are actually errors – the intention of the programmer was not caught by the lines he wrote and some subtleties were detected and reported by the compiler. This is one of the reasons why you want zero warnings when compiling your code. The other reason is that if your output space is cluttered by harmless warnings hardly you will notice the dangerous one.

13. When a programmer is insecure of the language she/he is programming in, the first thing that she/he should do is to study the language rather than writing code with it. Adding redundant or useless structures (such as this – comparing with true) is a clear sign of doubt and uncertainty and usually it appears in code with below average quality.

14. As many programmers I like tidy and well sorted out thing (even if my desk could tell a different story to the casual observer). Programming languages (at least most of the commonly used ones) have English keywords. So, yes the official reason is that your code should be read internationally, the real reason is that mixed language code looks really ugly.

15. See 7.

16. Once upon a time you made animations by playing different images (frames) one after another at a given speed. This worked fine, but the production was labor intensive. Obj files contains static 3D model, so in order to play them you need to perform a lot of data transfer to the graphics adapter. New techniques based on morphing and skeletal deformations arose in the years so that animations can be created with less data production and transferring, and – more important – can be optimized by the 3D accelerator. Making an animation with objs means that you miss where the bottlenecks in the graphics pipeline are, together with a good part of the last decades in 3D technology.

17. Code punctuation is used to separate stuff. Keeping a consistent punctuation style (i.e. relative position between spaces, parenthesis, commas and the likes) is a good habit, is good manner to those who will read it and shows that you care for your code. And if you don’t care about your code, then you don’t care about your work, and don’t care about who is going to read your code, then you are despicable.

18. This is much like 14. Italian programmers (but I guess that this is shared by all non English native programmers), while speaking, mix Italian and English words in the same sentence. This is fine because quite often technical documentation is written in English and for many terms there are no Italian equivalents. Pronouncing an acronym half in Italian and half in English is something that tells about the English knowledge of the speaker and his/her desire to show off with unfamiliar buzzwords.

19. 48K RAM was the memory size of the ZX Spectrum a popular home computer back in the 80s. This is much on the line of point 7, 8 and 15 – a simple system tends to be more reliable than a complex one. There are also some implications about how lazy programmers are that are no longer willing to spend time in doing their homework (optimization) and waste memory and CPU for no good reason.

There are basically two main interesting ideas: the love for the code, meaning the care for your craft, and that simpler is better. I am not sure I actually heard the sentence “this code hasn’t received enough love” referring to a ugly or messy source file, but that’s the care idea. What I wrote above is true – if you don’t care for the details, why should you care for less evident characteristics?

Simpler is better, though put a little dramatically on the list, is not a new concept. KISS principle is also called. No sane programmer is going to oppose this, on the other hand it has to be balanced with development time. Programmers that uses more than 48k are not lazy, but have deadlines to hit.

The list is over, but we’re still looking for wrongdoers to add. Have you any suggestion?

Ti sembra possibile?

“Il Voyager I è stata la prima sonda spaziale inviata dalla erra (1977) verso i pianeti esterni al Sistema solare. Viaggiando alla velocità di circa 17km/s […] si sta allontanando dal Sistema solare, verso lo spazio interstellare.

Calcola quanto tempo impiegherebbe per raggiungere la stella a noi più vicina: Proxima Centauri, che dista da noi 4,2 anni luce. Ti sembra possibile che l’uomo, in futuro, possa visitare altri pianeti al di fuori del Sistema solare?”

Questo è il contenuto di un riquadro che si trova fuori dal testo principale al capitolo 17 del libro per le terze medie “Noi Scienziati 3”.

La prima risposta al problema, volendo essere scientifici fino in fondo, è che, nemmeno se andasse al doppio della velocità attuale arriverebbe mai su Proxima Centauri visto che sta andando in un’altra direzione. Quindi, visto che si tratta di un testo che ha l’obiettivo di insegnare il pensiero scientifico ai ragazzi, dovrebbe quantomeno cercare di essere rigoroso.

Ma questo non è quello che mi porta a scrivere di questo triste riquadro quanto la cupezza e la rassegnazione che può ispirare alle giovani menti. Da dove arrivano le nuove scoperte scientifiche e gli incredibili progressi tecnologici se non da dove nessuno pensava potessero arrivare?

A livello teorico ci sono almeno un paio di possibilità per arrivare velocemente là dove nessun uomo (o donna) è mai giunto prima. La prima è l’Alcubierre Drive – ispirata dai telefilm di Star Trek, questa teoria sviluppata da un fisico Messicano, ipotizza di distorcere lo spazio in modo che una “bolla” di spazio normale scivoli più veloce della luce. L’altro dispositivo classico è il Ponte di Einstein-Rose – una deformazione dello spazio tempo che crea una sorta di tunnel collegando due punti remoti dello spazio attraverso una scorciatoia.

Le difficoltà tecniche per entrambe queste soluzioni sono inimmaginabili al nostro livello di sviluppo tecnologico. Il nostro livello tecnologico è però inimmaginabile solo un centinaio di anni fa. Se avessimo dato retta ad Einstein, che pure non si poteva tacciare di vedute ristrette, non ci saremmo messi a cercare di captare le onde gravitazionali. Il grande scienziato infatti riteneva altamente improbabile che la tecnologia sarebbe un giorno stata capace di percepire di delle perturbazioni così piccole del continuun.

E allora perchè mettere questo falso spunto di riflessione che si aspetta la grigia risposta rinunciataria, dell’ovviamente non è possibile? Perchè tarpare le ali del pensiero creativo, dell’entusiasmo e della voglia di superare i limiti dei ragazzi di oggi e scienziati e ingegneri di domani?

button down -> light on

Picture this project – you have a battery operated gizmo with LEDs that has to light up at a given time and light off at another one. Reality is a bit more complex than this, but not that much.

So what could possibly go wrong? How much could cost the development of its firmware?

The difficult may seem on par with “press button – light on”.

As usual devil is in the details.

Let’s take just a component from the whole. If it is battery operated you need to assess quite precisely the charge of the battery, after all – it is expected to do one thing and it is expected to do it reliably. The battery charger chip (fuel gauge) comes with a 100+ pages datasheet. You may dig out of internet a pseudo driver for this chip only to realize that it uses undocumented registers. Eventually you get some support from the producer and get a similar, but different data-sheet, and a initialization procedure leaflet that is close, but doesn’t match exactly neither of the two documents.

Now may think that a battery is a straightforward component and that the voltage you measure to its connectors are proportional to the charge left in the battery. In fact it is not like that, because the voltage changes according to temperature, humidity and the speed with which you drain the energy. So the voltage may fall and then rise even if you don’t recharge the battery.

To cope with this non-linear behavior the fuel-gauge chip keeps track of energy in and energy out and performs some battery profile learning to provide reliable charge status and sound predictions about residual discharge time and charging time. The chip feature an impressive number of battery specific parameters.

Since the chip is powered by the battery itself (or by the charger) and doesn’t feature persistent storage, you have to take care of reading learned parameters, store into some persistent memory, and rewrite them back at the next reboot.

Btw, this is just a part of the system which is described by some 2000 pages programming manuals specific to the components used in this project.

In a past post, I commented an embedded muse article about comparing firmware/software project cost to the alternatives. The original article basically stated that for many projects there is no viable mechanical or electrical alternative.

This specific project could have an electromechanical alternative – possibly designing a clock with some gears, dials and a mechanical dimmer could be feasible. I am not so sure that the cost would be that cheaper. But the point I’d like to make now is that basically you can’t have an electro-mechanical product today – it is not what the customer wants. Even if the main function is the same, the consumer expects the battery charge meter, the PC connection, the interaction. That’s something we take for granted.

Even the cheapest gizmo from China has the battery indicator!

And this is the source of distortion, we (and our internal customer who requested the project) have a hard time in getting that regardless of how inexpensive the consumer device is, that feature may have taken programmer-years to be developed.

This distortion is dangerous in two ways – first it leads you to underestimate the cost and allocate an insufficient budget; second and worse it leads you to think that this is a simple project and can be done by low-cost hobbyists. Eventually you get asked to fix it, but when you realize how bad the shape of the code (and the electronics) is, you are already overbudget with furious customers waving pitchforks, torches and clubs knocking at your door.

Digital Apollo

It’s no secret that I was a child during the space age, going to the moon was just taking a different kind of plane and there was no doubt, we all were going to spend y2k vacations on some asteroids or even Mars. Rockets and space keep fascinating me even when I got to know y2k for another reason and now that Mars still remains a distant shore where no man has gone before (and possibly it will take yet some more time to get there).

Growing older, and becoming an engineer just increased my respect and admiration for those people that using 60’s technology achieved such an incredible goal. Space is hard, unforgiving, there are millions of things that could go wrong. Timing and counting are especially critical. Just the first example that comes to my mind – switch the rocket off too early and you’ll plunge back to Earth, switch the rocket off too late and you’ll be cruising on a non-return-path to the Sun or the Outer Space.

This book starts from the beginning of the space era in the USA and follows the story up to the moon landings.

A bit surprisingly, the first half of the book is focused on the human side – the test pilots, the political propaganda, the strong will about having a human in the cockpit and in command of the mission. Von Braun, the German scientist behind many successes of the American rocket science, was a strong supporter of having humans out of the control loop – the rocket is fired, autopilot and physical laws of gravity take it to the destination, without the need of a pilot doing anything. This view was strongly opposed by the ideology of the space hero – the man that conquest the space, driving rockets and starships.

From the first orbital maneuvering it was clear that the pilot intuition was too misleading to proper control the spaceship – changing the orbit to get closer or farther from Earth it’s too different from the action you do on a plane, you need to take in orbital speeds when approaching your target, not just the relative positions.

Eventually the space program came to agree on avoiding human piloting the rocket during the launch phase and having some control operations with man in the loop and some other completely automatic. Humans where there as a reliability and recovery mechanism in the control loop. Having a spaceship flying to the Moon, is a very complex operation, that requires many activities to keep the capsule functional, aligned with the objects and preserving the passengers’ life.

While the story narrated in the book unfolds, the digital computer appears on stage. It was back in the sixties, when the single chip computer was yet to come. So the MIT took the task to design and build the so called Apollo Guidance Computer. It had 2k of work memory and 36k of persistent memory and ran at 2Mhz. The book describes the story of the development of the hardware and the software never going into technical details. You get to know that the computer was built using only NOR gate chips to ease repair and replacement of faulty components (operation that was later ruled out from on-board activities). Also you get to know that the user launched specific subprograms by input a number describing the “verb” followed by another one describing the “noun” of the required operation. Also all the operations that involved firing rockets were programmed to require the pilot authorization. This lock saved at least one mission when, during a lunar orbit, the pilot accidentally attempted to run a pre-launch sequence.

Maybe the digital computer played an even more crucial role in the lunar lander. This flying machine was something so radically different from every machine built to that time that designers and pilot could not tap into any previous experience.

The flight was not based on aerodynamics, but was only powered by rockets. By properly controlling the rocket attitudes and thrust the lander could move around and hover at a fixed point. Engineers and programmers made an incredible achievement by having such a complex machine controlled via a joystick, that proved quite intuitive to the pilot.

The computer on the lander had several programs to be selected according to the flight phase. A specific one had to be selected for landing. A graduate ruler was print on the portholes. By aligning the view of the pilot to the desired landing point, you get a reading on the ruler that had to be input in the computer. An automatic program would take control of the lander and took it to the desired position. This struck me for the ingenuity of the designers. They had to overcome the lack of interactive computer and did it in a simple yet effective way by using low technology equipment. Kudos!

During the first mission to the moon – Apollo 11 – the story wants that the landing computer failed requiring the two astronauts in the cockpit – Neil Armstrong and Buzz Aldrin – to manually take control. This is partly true. First because the lander couldn’t fly at all without a computer that translated manual input on the control joystick to rocket pulses. Second because the computer was in fact working properly reporting a real problem that, thanks to the ability of the programmers, had no consequences on the computer reliability.

The problem was that the lander computer had to be used for many different things, as the computer in the Apollo spaceship, it was controlled by the user that launched subprograms for every specific phase or maneuver during the mission. The landing sequence had many abort points, i.e. specific moments when the pilots had to decide whether abort the descent to the moon surface and get back to the Apollo capsule (the Command Module), or to proceed. Each part of the sequence had a specific procedure to operate. Right after the lander detached from the Command Module a first decision had to be taken – dock back to the Command Module or proceed to the next step? If the descent was aborted at that point, the pilot had to switch on the docking radar and use the computer to execute the docking sequence.

The docking radar had to be engaged also during the flight to the Moon when the lander was extracted from the 3rd stage of the rocket and then docked to the Control Module. So, during the simulations, the astronauts asked whether they could keep the radar on to avoid having something to think of in the case they aborted the descent.

This switch caused data from the radar to be fed to the lander computer causing some extra processing. The operating system and the programs were designed with a 30% margin on CPU load, and an error were reported if the load exceeded a safety threshold. Being a real time operating system with sound priorities, the computer continued working properly offering reliable pilot controls and descent trajectory. Nonetheless during the mission the mission control preferred to avoid any risk and asked the pilots to switch off the trajectory control, leaving Neil Armstrong and Buzz Aldrin to manually operate the lander to the landing spot.

This served also the propaganda to claim the reliability of human and the fallibility of the machine. In the next missions most the pilots decided to avoid automatic landing and go for manual landing even if there were no problems in the software and they landed very close to the programmed spot.

Very interesting also the role that the software played in the design and development of the missions. Initially no one considered software. I mean literally – there was no account for software on the initial plan. Likely it was considered part of the engineering system, not a main activity. Also the activity of software production started without an industrial process and without an effective leader. Around mid ’66, things changed, software switched from being a pet project for a few tens of programmers into a project with hundreds of people, project managers, documentation, review…

Overall I enjoyed this book a lot. In the first part felt a bit slow, and apparently not going to the point of computers in space, but in the next chapters that long introduction helps to better understand the human factor behind the story.

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:

 functionalimperativeunrolled0unrolled1
scala 2.10 times (lower is better)26.153.4016.603.36
scala 2.10 improvements over functional (higher is better)1x7.68x1.58x7.77
scala 2.12 times (lower is better)24.951.1713.30.021
scala 2.12 improvements over scala 2.10 functional
x1.05x22.32x1.97x1245

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 –

 FunctionalImperativeUnrolled 0Unrolled 1
C++ times (lower is better)0.320.0740.0530.049
Improvements over functional (higher is better)x1x4.36x6.1x6.6
Improvements over Scala 2.10 (higher is better)
x81x46x313x69
Improvements over Scala 2.12 (higher is better)x77x16x250x0.43

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.