Archive
The Emergence Of The STL
In the preface to the 2006 Japanese translation of “The Design and Evolution of C++“, Bjarne Stroustrup writes about how the C++ STL containers/iterators/algorithms approach to generic programming came into being. Of particular interest to me was how he struggled with the problem of “intrusive” containers:
The STL was a revolutionary departure from the way we had been thinking about containers and their use. From the earliest days of Simula, containers (such as lists) had been intrusive: An object could be put into a container if and only if its class had been (explicitly or implicitly) derived from a specific “Link” or “Object” class containing the link information needed by the compiler (to traverse the container). Basically, such a container is a container of references to Links. This implies that fundamental types, such as ints and doubles, can’t be put directly into containers and that the array type, which directly supports fundamental types, must be different from other containers. Furthermore, objects of really simple classes, such as complex and Point, can’t remain optimal in time and space if we want to put them into a container. It also implies that such containers are not statically type safe. For example, a Circle may be added to a list, but when it is extracted we know only that it is an Object and need to apply a cast (explicit type conversion) to regain the static type.
The figure below illustrates an “intrusive” container. Note that container users (like you and me) must conform to the container’s requirement that every application-specific, user-defined class (Element) inherits from an “overhead” Object class in order for the container to be able to traverse its contents.
As the figure below shows, the STL’s “iterator” concept unburdens the user’s application classes from having to carry around the extra overhead burden of a “universal“, “all-things-to-all people”, class.
The “separation of concerns” STL approach unburdens the user by requiring each library container writer to implement an Iterator class that knows how to move sequentially from user-defined object to object in accordance to how the container has internally linked the objects (tree, list, etc) and regardless of the object’s content. The Iterator itself contains the container-specific equivalent navigational information as the Object class in the “intrusive” container model. For contiguous memory type containers (array, vector), it may be implemented as a simple pointer to the type of objects stored in the container. For more complex containers (map, list) the Iterator may contain multiple pointers for fast, container-specific, traversal/lookup/insertion/removal.
I don’t know about you, but I think the STL’s implementation of containers and generic programming is uber cool. It is both general AND efficient – two desirable properties rarely found together in a programming language library:
…the performance of the STL is that it – like C++ itself – is based directly on the hardware model of memory and computation. The STL notion of a sequence is basically that of the hardware’s view of memory as a set of sequences of objects. The basic semantics of the STL maps directly into hardware instructions allowing algorithms to be implemented optimally. The compile-time resolution of templates and the perfect inlining they support is then key to the efficient mapping of high level expression of the STL to the hardware level.
DataLoggerThread
The figure below models a program in which a pipeline of worker threads communicate with each other via message passing. The accordion thingies ‘tween the threads are message queues that keep the threads loosely coupled and prevent message bursts from overwhelming downstream threads.
During the process of writing one of these multi-threaded programs to handle bursty, high rate, message streams, I needed a way to periodically extract state information from each thread so that I could “see” and evaluate what the hell was happening inside the system during runtime. Thus, I wrote a generic “Data Logger” thread and added periodic state reporting functionality to each worker thread to round out the system:
Because the reporting frequency is low (it’s configurable for each worker thread and the default value is once every 5 seconds) and the state report messages are small, I didn’t feel the need to provide a queue per worker thread – YAGNI.
The figure below shows a more detailed design model of the data logging facility in the form of a “bent” UML class diagram. Upon construction, each DataLoggerThread object can be configured to output state messages to a user named disk file and/or the global console during runtime. The rate at which a DataLoggerThread object “pops” state report messages from its input queue is also configurable.
The DataLoggerThread class provides two different methods of access to user code at runtime:
void DataLoggerThread::record_txt_block(const Data&)
and
void DataLoggerThread::operator<<(const Data&).
Objects of the DataLoggerThread class run in their own thread of execution – transparently in the background to mainline user code. On construction, each object instance creates a mutex-protected, inter-thread queue and auto-starts its own thread of operation behind the scenes. On destruction, the object gracefully self-terminates. During runtime, each DataLoggerThread object polls its input queue and formats/writes the queue entries to the global console (which is protected from simultaneous, multiple thread access by a previously developed CoutMonitor class) and/or to a user-named disk log file. The queue is drained of all entries on each (configurable,) periodic activation by the underlying (Boost) threads library.
DataLoggerThread objects pre-pend a “milliseconds since midnight” timestamp to each log entry just prior to being pushed onto the queue and a date-time stamp is pre-pended to each user supplied filespec so that file access collisions don’t occur between multiple instances of the class.
That’s all I’m gonna disclose for now, but that’s OK because every programmer who writes soft, real-time, multi-threaded code has their own homegrown contraption, no?
Cpp, Java, Go, Scala Performance
I recently stumbled upon this interesting paper on programming language performance from Google researcher Robert Hundt : Loop Recognition in C++/Java/Go/Scala. You can read the details if you’d like, but here are the abstract, the conclusions, and a couple of the many performance tables in the report.
Abstract
Conclusions
Runtime Memory Footprint And Performance Tables
Of course, whenever you read anything that’s potentially controversial, consider the sources and their agendas. I am a C++ programmer.
Unneeded And Unuseful
On Bjarne Stroustrup’s C++ Style and Technique FAQ web page, he answers the question of why C++ doesn’t have a “universal” Object class from which all user-defined C++ classes automatically inherit from:
I felt the need to post this here because I’m really tired of hearing Java programmers using the “lack of a universal Object class” as one reason to stake the claim that their language of choice is superior to C++. Of course, there are many other reasons in their arsenal that undoubtedly show the superiority of Java over C++.
Milliseconds Since The Epoch
On a recent project, our team needed a fast and portable C++ way to time stamp messages flowing into our system at high rates – down to the millisecond level of resolution. Here’s the boost-based implementation that I concocted. Notice the classic “midnight, January 1, 1970” epoch and the 64 bits required to preclude multiple rollovers in milliseconds since the epoch. What would your fast and portable C++ solution look like?
Update 1/5/13: Ever since C++11 arrived on the scene, Boost.Date_Time is longer needed for high resolution timing. As the “Milliseconds Since The Epoch 2” post shows, this functionality is now standard in the <chrono> library.
Using The New C++ DDS API
PrismTech‘s Angelo Corsaro is a passionate and tireless promoter of the OMG’s Data Distribution Service (DDS) distributed system communication middleware technology. (IMHO, the real power of DDS over other messaging services and messaging-based languages like Erlang (which I love) is the rich set of Quality of Service (QoS) settings it supports). In his terrific “The Present and Future of DDS” pitch, Angelo introduces the new, more streamlined, C++ and Java DDS APIs.
The UML activity diagram below illustrates the steps for setting up and sending (receiving) topic samples over DDS: define a domain; create a domain participant; create a QoS configured, domain-resident publisher (or subscriber); create a QoS configured and type-safe topic; create a QoS configured, publisher-resident, and topic-specific dataWriter; and then go!
Concrete C++ implementations of the activity diagram, snipped from Angelo’s presentation, are presented below. Note the incorporation of overloaded insertion operators and class templates in the new API. Relatively short and sweet, no?
Even though the sample code shows non-blocking, synchronous send/receive usage, DDS, like any other communication service worth its salt, provides API support for blocked synchronous and asynchronous notification usage.
So, what are you waiting for? Skidaddle over to PrismTech’s OpenSplice DDS page, download the community edition libraries for your platform, and start experimenting!
The Assumption Was Wrong
While performing maintenance on some legacy C++ code, a colleague came across a code fragment that performs a large, buffer-to-buffer byte copy. Instead of using the std::memcpy function to implement the copy, it was written the homegrown way – using a loop over the number of bytes to copy. The reason given for the choice was to “avoid the overhead of a function call“.
As the test code and results below show, the performance of std::memcpy blew away the loop-dee-loop strategy by a factor of 40X. The untested assumption behind the decision to write the loop was that std::memcpy was implemented under the covers as a loop by the compiler writers. An alternative assumption, that the compiler replaces std::memcpy with highly efficient, CPU-architecture-specific, inline code, either wasn’t known or it didn’t come to mind.
It took me about twenty minutes to prove, with objective data, that “the assumption was wrong“.
So, what’s the lesson here? There is none. It’s impractical to challenge and test every single assumption we make as programmers – and as people, no? Perhaps the original programmer was a newbie who hadn’t yet learned the rule of thumb that it’s almost always better to use compiler-supplied library functions and classes over equivalent homegrown code. Perhaps the assumption was so ingrained (like the theory X assumption that “anointed” superiors are smarter, more trustworthy, and more responsible than subordinates) it didn’t occur to the programmer to test it out. Perhaps it did occur to the programmer that he/she should test the assumption but he/she felt immense schedule pressure to plow ahead with blinders on.
21st Century Assembler
I love working in the malleable medium of C++, but I wonder if it is becoming, or has already become, the “assembly language” of the 21st century – powerful and fast, but hard to learn and easy to make hard-to-diagnose mistakes. I recently stumbled upon this 5 year old interview with C++ creator Bjarne Stroustrup. The interviewer opened with:
Mr. Stroustrup, the honest soul that he is, essentially validated the opening, but with a trailing caveat:
C++ has indeed become too “expert friendly” at a time where the degree of effective formal education of the average software developer has declined. – Bjarne Stroustrup
Since “experts” tend to be more narrow minded than the average Joe, they tend to look down upon newbies and non-experts in their area of expertise. And so it is with many a C++ programmer towards new age programmers who side step C++ for one of the newer, easier to learn, specialized programming languages. In the classic tit-for-tat response, new age programmers belittle C++ users as old timers that are out of touch with the 21st century and still clinging to the horse driven carriage in the era of the lamborghini.
So, who’s “right“? And if you do share your opinion with me, what language do you work with daily?
Fully Qualified
When I’m coerced into inheriting from one or more base classes to reuse pre-existing functionality, I prefer to fully qualify my calls to base class member functions like this:
Coding this way helps me to keep a conceptual separation between classes and eases downstream maintenance – I know where to look for the function definitions. Since I’m a “has a” instead of an “is a” programmer, I prefer black box composition over white box inheritance; unless it’s necessary or authoritative coercion is involved. How about you? What’s your preference?
Ammunition Depot
In preparation for a debate, both sides usually spend some time amassing evidence that supports their distorted view of the issue. Well, this post is intended to serve as a repository for my distorted side of an ongoing debate.
All the above snippets were strategically and carefully culled from various discussions posted on the wonderful Joel Spolsky and Jeff Atwood site: Stackoverflow.com.
Why am I here?
WTF?
Meh!
D'oh!
My BTC Address
Bulldozer00's Blog 