Archive

Posts Tagged ‘STL’

Pragmatically Feasible?

September 17, 2013 6 comments

From the MISRA web site:

The Motor Industry Software Reliability Association (MISRA), is a collaboration between vehicle manufacturers, component suppliers and engineering consultancies which seeks to promote best practice in developing safety-related electronic systems in road vehicles and other embedded systems.

While browsing through the MISRA C++:2008 standard, I came across this not-unexpected requirement:

No Heap

I don’t know enough about the standard to know if it’s true, but I interpret this requirement as banning not only the use of “new/delete“, but also as banning the use of the dynamically managed STL container abstractions (vectors, lists, sets, maps, queues) and, hence, the many standard library algorithms that operate on them. I wonder what the MISRA Java specification, if there is one, says about dynamic memory allocation.

If my interpretation of 18-4-1 is correct, then the requirement can severely jack up the cost, schedule, and technical risks of any software component that is required to be compliant with the specification. For non-trivial applications requiring more than low-level, statically allocated arrays…..

Complexity is pushed out of the language and into the application code. The semantics of language features are far better specified than the typical application code. – Bjarne Stroustrup & Kevin Carroll

Because of the safety-critical nature of embedded automotive software, I can understand the reasoning behind the no-dynamic-memory-allocation requirement. But is it pragmatically feasible in today’s world; especially since software components keep getting larger and commensurately more complex over time? In other words, is it one of those requirements that doesn’t scale? Is it too Draconian?

For those C++ programmers who work in the automotive industry and happen to stumble upon this blog (which will probably be none), what has been your experience with this MISRA requirement and some of the other similarly unsettling requirements in the specification? Are “waivers” often asked for and granted? Is it an unspoken truth that people/companies pay public lip service to the requirement but privately don’t comply?

misrable

The Emergence Of The STL

August 10, 2011 2 comments

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 “overheadObject 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.

%d bloggers like this: