Wednesday, October 21, 2009

Armstrong Ch2

Joe Armstrong's definition of what descriptions a software architecture should be composed of are quite good a characterizing a system.  One thing that I think should be moved out of the problem domain section into its own is that of performance constraints and requirements.  In this case, the problem domain clearly states that a telecom system should exhibit certain behavior.  But in other cases, the problem domain might not be so explicit--a system designed to revolutionize an industry by bringing priorly unheard of speed to solving problems might not characterize the performance requirements in the problem domain--this would be more an attribute of the system that we are trying to build to suit the problem domain, rather than an intrinsic property of it.   Required performance guidelines are certainly a central tenet of how a system should be architected.

Messaging for parallelism makes a lot of sense.  It helps to reduce the affect of unnecessary assumptions that can be easily imposed by shared memory type systems.  I have worked with a number of web services oriented applications which essentially use messaging, and it certainly does enforce strong separation.  However, in most of the systems I have worked on with web services, the calls have been blocking in nature, hence no parallelism gains were realized.

"Fail fast" kind of scares me.  The idea that an entire process should terminate its execution upon reaching an error case leads me to believe that performance could be detrimentally affected.  For example, in the case that a process uses a great deal of cached data, assumedly this cache would be flushed when the process "fast fails", and therefore there could be quite a bit of a performance hit by reloading this cache each time the process restarts.

I think that concurrency oriented programming makes sense in certain problem domains.  In others, I could see this style as an impediment from getting the job done.  I suppose that as the supporting tools for this type of programming evolve, the barrier to entry of this programming style will be reduced, but it seems to me that unless concurrency is priority one in the system, adopting this model would potentially make more work for you.  Having said this, more and more systems are setting concurrency as priority one (especially in the server software world), so I am by no means discrediting this style.  Rather, I am proposing that it should be adopted judiciously--only when concurrency is of high enough priority to warrant the overhead.

An unreliable messaging system makes a ton of sense to me.  Just look at how the internet has evolved, and worked well (arguably, I guess) for a wide variety of applications.  To impose a reliable messaging system would be to burden certain types of communication with overhead that they don't require.  Furthermore, as reliable messaging can be built on top of unreliable messaging with proven techniques, I believe that this is the best choice for a messaging system.

Monday, October 19, 2009

Map Reduce

The Map Reduce pattern is quite similar to the Fork/Join pattern.  However, whereas the fork/join pattern recursively subdivides one problem into smaller ones, and combines the results when the stack unwinds, the Map Reduce pattern operates over a large list of independent problems, providing a mechanism to gather results.  The primary difference, then, being whether the units of work to be completed are decompositions of a large monolithic problem, or samples in a search space--independent from one another, but culminating at a solution.

Errors should be handled in a configurable way, allowing the application developer to specify behavior on a case by case basis.  On some problems, failure of any subproblem may prevent the problem from being solved, whereas in, say, a monte carlo simulation, the failure of one task may be essentially inconsequential, presuming that the failure isn't related to a flaw in the underlying model.  As such, the application developer would like to either ignore the error, schedule the task for re-execution (in case the error was transient), or terminate the computation.  We certainly wouldn't want the framework making a decision to terminate the computation, potentially losing all existing computation results, due to a small anomaly in one task.  Hence, a configurable error handling system would be the only way to make a framework general-purpose enough.

I haven't ever used this pattern, and I actually had to a little bit of Wikipedia-ing in order to get a better idea of real applications.

This pattern excels when the majority of the work to be performed is in the "map" function, to be executed independently.  When there are a great deal of interdependencies in the "reduce" function, the pattern won't scale well, as reductions may need to be deferred until other mappings have been performed.  This case may be outside of the scope of the pattern, but if so, it can be added to the list of weaknesses of the pattern.

Event Based, Implicit Invocation Pattern

The "Event Based, Implicit Invocation" (EBII) Pattern is one that is so incredibly common, it's almost redundant to document it as a pattern, but nonetheless, for completeness, it can prove useful to understand the differences and constraints in implementing it.

The key difference between this pattern and the Observer pattern is the cardinality and loose coupling between the sender and receiver.  Whereas in the Observer pattern the "publisher" knows its "subscribers" and issues notifications, in the EBII pattern, the publisher knows nothing about its "subscribers", but rather just knows its own notification mechanisms.  These mechanisms interface directly only with a manager component, which is responsible for distributing these notifications.  Additionally, whereas the Observer pattern states a "one-to-many" cardinality, the EBII pattern says that any object can publish events and any object can subscribe to events.

When it comes to dispatch methods, implicit invocation provides greater decoupling than explicit invocation.  By using explicit invocation, the pattern is considerably closer to the Observer pattern.  An additional dimension of decoupling comes from using nonblocking calls.  If blocking calls were to be used, the notifying object's timing would be affected by the receiving object's handler execution to a considerably greater degree than in the nonblocking case.  Obviously, the event handler will still utilize system resources, but this won't as fundamentally affect the timing semantics inherent in the program.

Applications of this pattern are so prolific (as previously mentioned), that the author named wide classes of programs using this pattern (such as all clients registering over a network to receive some sort of notification), that it's hard to think of an example that doesn't fit under the umbrella provided.  RSS feeds would fall under this categorization as a utilization of this pattern.

As is explained in this pattern, the manager component has everything to do with how the event notification system scales.  As such, it would be inappropriate to implement a notification broker for all types of events.  Imagine the same system being responsible for handling IO Interrupts as RSS notifications--the requirements of performance and complexity are so divergent that one system could not be expected to span this expanse.

Error handling in an event based system is the responsibility of the event receiver.  If an event sender *really* needs to know about a failure in another component, it should register a listener for the receiver's error event.  This introduces a bit of a bidirectional constraint, but still maintains a great deal of decoupling.

Sunday, October 18, 2009


I haven't had a great deal of experience with testing parallel programs.  As I believe I've stated in my prior blogs, most of the applications that I've built have used totally isolated processing threads, accessing common resource only through a database server--where all but the general awareness of concurrency is abstracted away.  In the couple of instances where I have tested the concurrent nature of these programs, I've generally only used stress testing.

While Moore's Law may be one of the most widely known conjectures related to computing, I'd argue that it is still trumped by Murphy's Law: "Anything that can go wrong, will go wrong".  When we write test suites for an application, we're hoping that the "will go wrong" will rear its ugly head in the very finite amount of time allotted.  Even stress tests running on large farms of machines pale in comparison to the diversity of executions that will happen "in the wild", across an expansive space of hardware and software platforms, user interactions, environmental factors, and configurations, and possibly across years or even decades of deployment.  Hence, even if a stress test has run for weeks without failing in a test environment cannot purport to truly capture all behaviors.  Additionally, since any code change, either in the application, or in the platform, can totally invalidate a stress test, even the most exhaustive practical stress test is only good for as long as the identical bits are in play--and we all know how quickly requirements change and bugs are found.

The small scope hypothesis is quite an interesting proposition.  To be able to bound the complexity of test cases is certainly a desirable trait from the perspective of a real-world tool, such as CHESS.  I don't know that I can offer any specific critical analysis on this subject, but would rather argue that regardless of any formal proof of such a concept, code is written by people, and to the extent that they are unrestricted in the concurrency structure of the code they write, they will (again, with the Murphy's Law!).  Hence, it's my belief that only through empirical study will we find out what percentage of bugs meet the criteria of this hypothesis with given parameters.

I could envision a monitor on top of CHESS that would profile the efficiency of various interleavings of execution, such that if certain interleavings are found to be particularly efficient, design work can be undertaken to try to guide the execution towards such interleavings (such as monitoring how locking patterns occur, the duration of thread sleeps, and the relative priority of threads).

The semantics of synchronization primitives being misunderstood is minimal to the extent that the conservative option is chosen (in the happens-before graph).

Saturday, October 17, 2009

OPL Iterative Refinement

I don't believe that I have ever used this pattern before.  This is probably due to my professional experience being mainly confined to data management type applications, but perhaps because of this I'm an ideal candidate to critique the understandability of this pattern.
I understand what this pattern proposes, but what I am less clear on is when I would use it.  The pattern talks in abstract terms about the applicability, but this is perhaps a pattern that would benefit from a more concrete example.  Certainly, if I understood my problem domain to look like one of the examples, it would be obvious that this pattern could apply, but my concern is that in applicable cases that are described in terms different than those of the pattern, it might not be obvious that this pattern could be of use.

OPL Layered Systems

Similar to the OPL Pipes & Filters pattern, the OPL Layered Systems pattern is considerably simpler and quicker to grasp than the previously presented pattern.  The previous pattern pointed out (and the OPL pattern omitted) that designing a good error handling system can be difficult in layered systems.  The OPL pattern made more explicit notice of the performance implications, and was more prescriptive in defining how the number of layers should be managed, whereas the previous presentation simply stated that "crossing component boundaries may impede performance".  I'm not sure if it's a strength or weakness of the OPL pattern, but the previous presentation details how to go about deriving a layered architecture, whereas the OPL pattern does not.  I guess this would be an argument for what the contents of a pattern should be.  It's been my feeling, however, that a pattern should read like a short encyclopedia entry--giving enough information to understand the basics, and deferring specific non-core details to other texts.  The OPL pattern does this, whereas the previous presentation goes into considerably more depth.  This may be due to the difference of one being an online library of patterns and the other being a chapter in a book, but to describe the best way to get a grasp of a large number of patterns, the former is more expeditious.

OPL Pipes & Filters

The OPL version of the Pipes & Filters pattern is definitely simpler and easier to understand than the previous description.  Part of this is due to the fewer detailed examples.  The first presentation of this pattern uses a rather complex example of building a programming language, which in my opinion clutters the essence of the pattern.  The few short examples in OPL, presented *after* we understand the pattern to a large degree, provide enough detail to grasp the purpose and types of applications for this pattern, and I believe that this is the extent of what a pattern should be--it's not supposed to be an exhaustive reference for the entire body of knowledge relating to the subject, but rather concise enough to be "thumbed through" when searching for a pattern to fit a design need.

The OPL pattern ignores the detail of "push" vs. "pull" pipelines, which in my opinion is bordering on being too implementation specific to be included in the high level pattern.  It excels, however, at describing how the granularity of pipe data should be managed to exploit optimal buffering and potentially, concurrency.

Friday, October 16, 2009


Smalltalk's treatment of all constructs as instances of a very few primitives makes it a fundamentally very simple language.  This is not to say that it's necessarily easy to express an idea in the language, but rather just that the language itself is compact.  Using these constructs alone allow it to reason using a common fundamental model, rather than having to worry about the semantics of a plethora of language constructs.  Messages, specifically, make it easier to perform code analysis related to interactions of code blocks, and therefore make it easier to express algorithms in a way that will be more conducive to parallelization.

Programming and design using inheritance is generally a mixed blessing.  To the extent that the system grows in the anticipated manner, inheritance works great to encapsulate functionality and reuse code.  It's when one or more of the fundamental assumptions of the inheritance model are challenged that the headaches begin.  At that point, you either have to rework your entire inheritance hierarchy to be consistent with the updated model, and incur the risk of breaking something, or hack in an ill fitting subclass which breaks the fundamental reasoning about the system, but not the implementation--either way, this breaks something.  I think in very well understood domains, inheritance works well, but in arenas with rapidly changing requirements and/or models which are not very well understood, inheritance leaves something to be desired.

Regarding dynamic dispatch, this is essentially a similar method to that used in C++ inheritance, using a virtual method table.  It's just another level of indirection in memory, and we've seen time and time again levels of indirection added to software to solve problems of complexity, so I don't feel that this one additional layer would do much to change the overall scalability of the software.

The open nature of Smalltalk classes violates the principle that a system should be "open to extension, but closed to modification".  While it's useful to ensure that no arbitrary constraints are put in place, it could certainly pose problems for maintenance.  Whereas in other languages you might declare a class as "final" or "sealed", such that you would be free to modify its structure whilst maintaining the external interface, leaving classes open to modification would make these types of changes more likely to break other code.

While the chapter argues that compile-time checking can garner a false sense of security, it has been my experience that when dealing with applications heavy in definition/data, and dealing less with complex algorithms, static typing and design/compile time tools/checking can go a long way to making an application sound.  While it doesn't ensure that the program executes without error and generates the correct output, it at least ensures that the types of operations that are occurring are semantically valid, and by building a smart type structure in the program, this can provide a great number of advantages.  Metaprogramming requires good code coverage from a test suite before it can touch the kind of whole-program checking that statically typed languages can offer.

Thursday, October 15, 2009


Reentrancy is important in order to allow for safe concurrent execution.  Being reentrant, we can know that an execution of a program will be totally independent of any other execution that may be running, and therefore assures us (to whatever degree possible) that we can scale this application, such as for handling concurrent requests of different users.  We can do this without performing additional analysis to verify that the application will function as expected.

I believe that this refactoring is sufficient to create reentrancy.  To think about why this is the case, it's useful to think of how different threads of execution might come to "know" or influence one another.  When a thread/execution starts from a blank slate, it has to obtain access to resources in order to do its work.  It can either create objects of its own, or access shared state, represented in the OO world as static constructs.  Objects created by one thread cannot be seen in other threads unless a reference is somehow communicated.  This communication can essentially only happen through static constructs--hence the differentiation between mutable and immutable static constructs.  Immutable static constructs, once created, are essentially harmless as they are read-only.  Mutable static constructs, however, would open the door for this type of troubling communication.  By moving these type of constructs to a thread local type storage, each thread thinks that they are accessing an application-wide static construct, where in reality, they are accessing only their own copy, so in this way, threads are almost "tricked" into being reentrant.

Unfortunately the real world is a bit messier than this.  When it comes to libraries/system calls, external state can find its way in.  Whether it be an externally managed singleton type resource, or some externally shared medium, problems can arise.  Though it makes this tool more cumbersome to use, I think that warnings about library functions is about the best that can be expected at this point.  The semantics at the source code level are pretty straightforward, but when a library call may delegate responsibility to any sort of platform dependent implementation of some function, a tool like this couldn't expect to be able to analyze all possible cases.

I think it's pretty clear that reentrant programs are thread safe--the programmer has gone through a great deal of effort to effectively sandbox each execution so that it can't substantively interact with any other execution.  Thread safety alone, however, generally implies that resources are being shared and that attention is being paid to how these interactions occur, but the bottom line is that they still occur, hence reentrancy is not guaranteed.

Wednesday, October 14, 2009


I've never touched Fortran, but from what I understand from a little Googling, the loop parallelization in Fortran was probably largely related to declarative data parallelization.  Modern languages such as Java have considerably more complex semantics in common usage.  Apparently in Fortran independence between these operations was considerably more common, whereas in OO, sharing of objects makes this harder.

In terms of usefulness factors, I found it quite complete from an abstract perspective.  If I were to use a tool like this on a commercial project, I would want a way to know what kind of benefit I might expect to see at a whole-program level.  Even if it were a considerably simplified algorithm, to at least know that there are X potential refactoring opportunities would be beneficial.

For safeness of concurrent execution, while I didn't understand some of the notation in the analysis, I can think of a couple ways in which it would be hard/impossible to know about safeness.  Any place involving dynamic binding would obviously cause an issue with "static analysis" (obviously, hence the name), but I could see that some applications that make heavy use of such methods would have essentially no use for such a tool.  Additionally, I'm not sure if its possible in Java, but in .NET there is an interop layer with unmanaged code, where you would have no facility available for code analysis.

Tuesday, October 13, 2009

Functional OO

Let me preface this by saying that my only foray into functional programming has been through a languages & compilers course as an undergrad, so my experiences are limited.

I feel that this chapter was quite heavily biased towards OO techniques, but though it certainly colored the conclusions drawn, I find it neither inaccurate nor particularly unfair.  The problem domain clearly emphasized structure over compact expressiveness, so within this problem domain, OO has a clear advantage.  Functional languages excel at expressing a fixed set of computation in a certain way, as well as extension through substitutability of chunks of functionality.  Functional languages benefit from a reduced set of ways to express some piece of computation.  Whereas in OO, there are structural decisions that affect how a system will be composed, there are fewer such decisions in functional languages, leading to more unified conventions.

The aforementioned structural decisions in OO are, however, one of its greatest advantages.  By encoding a great deal of the problem domain knowledge into the structure, the programmer can plan for future expansion and enforce a much stronger separation of concerns.  In my opinion, OO is a better technique for any problem domain dealing with data, behavior, and variations of these.

While functional languages gain the benefit of mathematical models which automatically facilitate a certain amount of architectural reasoning, OO benefits from the experience of the rest of the world, in that it can be used to more closely model real world things and scenarios.

Tuesday, October 6, 2009


When deciding whether to parallelize an existing sequential application or to re-architect for parallelism, I think it is of great concern to consider whether the underlying algorithms and structures are sufficiently decoupled (in algorithms, iteratively decoupled), such that parallelization would be practical and useful.  In applications using algorithms where each iteration explicitly depends on the next, and where there is little or no "fan out", the underlying algorithms should be inspected to see if the solution can be formulated in a different manner, and therefore parallelization through refactoring should be decided against.  On the other hand, however, if the structures and algorithms exhibit good decoupling, parallelization through refactoring may bring great results, and thus should be further investigated and possibly undertaken.

Parallel libraries are of a great advantage to the programmer for several reasons.  Firstly, they abstract a great deal of the complexity of concurrent programming away from the developer, and therefore let the developer work with a simplified/abstracted model.  This leads to a decrease in subtle timing issues/bugs related to hard-to-test situations, arising from lack of complete knowledge by the developer.  They additional provide the benefit of disseminating knowledge about parallel patterns, by encapsulating relevant functionality.  This provides a library of paradigms which will become known to the developer, and therefore provide the developer with a variety of new perspectives from which to model their algorithms.

When it comes to semi-automatic vs. fully automatic refactoring, I believe that there is an appropriate place for each.  To the extent that exact semantics can be ensured, a fully automatic approach would be preferred, as it keeps the codebase simpler and more to the point.  In the event, however, that the semantics of the application would be changed, no matter how slightly, it would be best to place this control in the developer's hands, as ultimately, they must decide what the application must do, and stand responsible for its operation.

Cluttering of code due to parallel refactorings are certainly an issue when it comes to maintainability.  I believe that as languages become more expressive, and essentially more functional, the code will be more conducive to fully automatic refactorings, which can happen in the compilation process, as opposed to at the source code level.

Not so much a refactoring, per se, but in order to achieve parallelism in a number of my applications, I use a SQL Server database, which has a great deal of internal parallelization built in, and then I try to formulate my solution in terms of operations across this database.  In this manner, I can gain a great deal of parallelization over a purely sequential program.

Another factor i would have liked addressed is an analysis of how these parallelizations affect total system scalability when faced with a large number of copies of the same algorithm running--i.e. if different users were running instances of the algorithms on a shared system.  Perhaps this would be able to be accomplished by providing a single core benchmark, to show the overhead of the parallel refactorings.

What a Bazaar Cathedral that is!

From my experience, newer technologies make building software, simpler, quicker, less error prone, and more feature rich.  Therefore, when a new subsystem or fundamental paradigm becomes available, the developer must take a good look at what that change will do to their software product.  In many cases, the maintainability and performance of migration are reward enough for the effort, but even when they are not, the developer needs to look towards future requirements, and the difference in how they would be supported under the old and new subsystems.  It's my philosophy to upgrade to new frameworks (such as in this case Qt3 to Qt4) as soon as they are stable, and at times, even delay the implementation of new features while awaiting the release of such a new framework, as a general rule.

As I already mentioned, new frameworks often make things easier to do, more stable once their built, and easier to understand and maintain. If a team were to ignore such innovations, and plow headlong into features without considering the new framework, they'll find themselves with an obsolete codebase sooner than they think, as the updated framework makes much of the work they have done redundant.  I furthermore embrace the update of said frameworks as an opportunity to challenge existing assumptions, perform a rather detailed review of the system as it stands, as well as architecturally plan for future needs--essentially as an opportunity for a large scale refactoring.  Even in "cathedral" style projects, requirements change, technology changes, people change, and updated frameworks are a great driver to readdress the architectural and quality concerns of the system.

I feel that the bazaar type project falls in the middle of the spectrum in terms of efficiency and output quality, as compared to well managed (and understood) cathedral projects, and poorly managed cathedral projects.  The Bazaar certainly has the advantage over the poorly managed cathedral, as the workers can stop working on a portion of the software that they are certain are doomed to fail, for whatever reason, and can redirect effort elsewhere.  This freedom to do so, however, would be detrimental in a well managed cathedral project, where perhaps its hard to communicate the full scope and applicability of a portion of the software to the developers.  A certain portion of the application may fill great needs for HR and Accounting personnel, but if the programmers aren't interested in these fields, and therefore don't see the need, this portion of the user base would be alienated.  In this manner, a (well managed) cathedral project manager could better allocate resources than an open project would, by simply working on what is interesting.

Overall, my feeling is that a bazaar structure works very well when the user base is very well in line with the developer base, and that the total number of hours worked is not of prime concern.  From here, I shall refer to the cathedral style meaning a well managed cathedral project.  However, I feel that the cathedral style is much more effective when there are silent user bases, or maybe user bases that are sufficiently unskilled to foresee the use of the software to the extent that they fail to participate in its design.  Cathedral style also benefits when there is concern with the productivity per developer hour spent (such as in a company desiring to minimize costs of constructing said software).

The real strengths of the bazaar is that anyone can contribute.  This benefits the project when people with unique skills, perspectives, and goals join a project, and are then able to contribute in a way that the existing developer base would have been unable to.