Profiling C++ applications: class composition

In the latter half of last year, my research went down an OOP path especially in the direction of C++; both the hardware containers project and my thesis touch elements of OOP concepts. With the hardware containers we were interested in how C++ developers use inheritance, composition, and encapsulation. For my thesis work, I was interested in how applications use the STL; I wrote an appendix in my thesis describing this aspect. For this post, my focus is on the hardware containers work, which is in my paper pipeline waiting for submission.

I found 21 free and commercial (oxymoron?) open-source C++ programs for this investigation: dimacs-sq, Dijkstra's algorithm; Opal and GEM5, processor simulators; Geant4, physics particle simulator; FlightGear, flight simulator; Wesnoth, video game; OpenCV, computer vision library; Boost, library for C++; MySQL, database server; LibreOffice, office productivity suite; Doxygen, documentation generation; Haiku, OS based on BeOS; ReactOS, OS based on Windows NT; Chromium, web browser; povray, soplex, dealII, namd, xalancbmk, astar, and omnetpp, C++ benchmarks from SPEC CPU 2006.

Using synthetic microbenchmarks, Eugen and I determined that the important C++ code behavior attributes that affect performance when using hardware containers are the ratio of private access specifiers to total number of class variables, depth of inheritance, number of objects a class includes by value, and number of public accessor methods that expose private variables. Nicely enough, all of these can be determined by examining source code: no need to run the C++ programs!

I used two tools to analyze the 21 programs: Understand by SciTools, and CCCC. The former is commercial and comes with an evaluation license, which was enough for me to get the data I wanted; the latter is open-source, which was good enough for me to modify to get data I wanted. I used Understand! to measure the ratio of private:class variables and the depth of inheritance, but the tool did not provide enough data for the objects included by value or for accessor methods. Ultimately I did not get any data for the latter, but I was able to hack CCCC to measure how many objects a class includes by value.

For the composition of classes I used my modifications to CCCC to count how many classes each class includes by value. On average, classes do not include very many objects of other classes by value (perhaps by reference), although large outliers exist. The chart shows the average number in orange, with one standard deviation as an error bar; the maximum among all the classes is in blue.

I used both CCCC and Understand to calculate the inheritance tree depth of these C++ programs. Using both tools showed some difference in the tool quality, since for a metric as simple as inheritance depth the two tools should get identical numbers. The following chart shows the maximum depth of the inheritance tree reported by each of the two tools with CCCC in blue and Understand in orange.

 

Although the tools occasionally agreed, vastly different numbers were obtained for lots of the programs. The maximum inheritance depth is less than 10 for almost all of these programs, with small (near 1) averages and standard deviations. Thus most classes are decoupled with small inheritance and composition factors, but some strong outliers do exist. For hardware containers, we can treat the outliers as a special case and make safe (enough) assumptions about an object's composition.

My new job

As of last week I have started my new full-time job as a Postdoctoral Research Scientist at GWU. I'm working with my thesis co-adviser, and my job is an expanded version of what I was doing before graduating. In addition to continuing my research, I will also be overseeing/assisting the research of some graduate students and writing grant proposals.

The appointment is for the next 18 months or so, and I'm excited about carrying forward the momentum I have in my research.

Looking back to 2012, forward to 2013

Of the many post ideas back-logged in my head, I wanted to recap the past year and perhaps look forward to the new year before making it out of January. For me, 2012 was a busy year in which I

• Became a dad.
  
• Defended my Ph.D. dissertation.
• Dropped 20 pounds to 18% body fat, BMI 23.
• Bicycled 2300 miles, ran another 160 or so.
• Published 2 papers and a book chapter.
• Continued RTEMS involvement as an admin and mentor for GSOC and GCI.
• Went on a Caribbean cruise.
• Bought my first car, a minivan.
• Repaired/Improved my house: foundation crack sealed, water line repaired, water line replaced, water heater replaced, roof repairs, HVAC heat pump and blower replaced, ventilation ducts cleaned, and kitchen cabinets refaced.

For 2013 some of my goals, resolutions, and expectations are to

• Turn 30. Done!
• Get a job. Done, more on that soon.
• Publish more.
• Get more research funding.
• Read more.
• Learn a new (non-programming) language, probably ASL or suomi.
• Continue RTEMS involvement.
• Resume regular exercise. I cut way back after my daughter was born.
• Finish a century ride, solo or supported. Current best: 88 miles.
• Finish a half-marathon, solo or organized. Current best: 8 miles.
• Take up swimming.
• Go on a family vacation.
• Build a "front porch."
• Construct a new cat tower.
• Get rid of stuff.
• Be a better person.

Hood me!

I successfully defended my dissertation thesis yesterday, thus overcoming the final hurdle to the Ph.D. other than some paperwork and formatting/publishing the thesis itself. The title of my thesis is "Operating System Support for Shared Hardware Data Structures" and it spans a range of computer science topics from low-level computer hardware—not quite circuits, but close—up to application software and everything in between. I'm pleased with both the scope of the work, the technical contributions, and the outlook for carrying this work forward. I chose to find and pursue a topic that interested me, and my advisors (and wife!) were flexible enough to permit me to do so. It feels great to take the seed of an idea through germination and see it begin to grow.

Critical Bugs and Quality Assurance

Sebastian Huber recently posted a nasty RTEMS bug and fix. While simple, the bug manifested in their application as an increase in one task's latency from 20us to 170us! The cause of the problem was that RTEMS has two kinds of critical sections—dispatch and interrupt—and new SMP-aware code added a dispatch critical section to the thread dispatch code. The problem happens with overlapping a traditional interrupt disable critical section. The SMP dispatch code looks like:

void _Thread_Dispatch(void) {
  Thread_Disable_dispatch();
  SMP_Dispatch_other cores();
  Interrupt_Disable();
  ...
  ... do things, including context switch if needed
  ...
  Interrupt_Enable();
  // problem here!
  Thread_Unnest_dispatch(); // enable
  ...
}

The problem is that an interrupt can occur between Interrupt_Enable and Thread_Unnest_dispatch. Suppose a low-priority task (L) is executing _Thread_Dispatch, and the interrupt enables a high-priority task (H), but
H will not be dispatched because dispatching is disabled. Instead L enables dispatching and resumes executing, which is a priority inversion!

The fix reverts the changes made for SMP. For the SMP code, the priority inversion still exists and is unresolved. (RTEMS currently does not make real-time guarantees for the SMP support, so no one cares yet.)

In the broader picture, the bug seems like it should be easy to detect. The issue with free open-source software (FOSS) is that quality assurance (QA) is almost non-existent: the "many eyeballs" philosophy argues against QA. But what else can FOSS do? No one is going to pay for extensive testing, and if they do they have no incentive to share.

FOSS communities (and corporate developers) need better tools for software QA. This summer RTEMS had a GSOC student who was looking at testing. Testing is probably the first tool in the QA toolbox, and the only one most developers have a clue about; how about static analysis, path coverage, standards conformance, or certification? Some interesting work modeling, proving, and certifying systems is out there: Where is the undergraduate textbook and course on QA?

Web site update

Last night I decided to provide an html version of my CV, and then I remodeled my website. The old version was ugly and broken; the main problem were my iframes. I simplified the design, tried to make it mobile-friendly, and reduced the content. I kept my basic design elements (boxes), and tried to eliminate cruft. I think the product is leaner and cleaner.

Version control for text/LaTeX?

I often use version control (VC) for text documents—especially LaTeX. Modern VC software is good for code, and even text when working alone, but collaboratively editing text with VC is a nightmare. The biggest challenge for text VC seems to be structure/formatting. Code is well-structured within and between lines: text less so. Words/sentences can be re-arranged within sentences/paragraphs, and lines are meaningless. With VC, line wrapping propagates small changes and frustrates reviewing and merging.

Word processors track revisions, but such tools are restrictive and won't work for markup languages. Cloud tools for collaboration such as Docs exist, including some for LaTeX, but requiring connectivity while editing is a non-starter for me.  I would even be happy with a custom LaTeX solution; the features I desire for text VC are similar to those for code:

• Non-proprietary, application-agnostic, platform-independent FOSS
• Revision history: see what has changed.
• Revert: undo changes back to forever.
• Lock-free: work in parallel, which requires...
• Pain-free merge: help resolve conflicting commits.
• Distributed and offline editing: no active (server) connections
• External contributions: integrate changes made outside of VC

Most VC tracks changes either with changesets or snapshots. Changesets seem worthless because of the structural problems of text. Snapshots seem viable, but I haven't seen turn-key solutions for plain text or LaTeX, and handling external contributions seems especially troublesome.