Wednesday, April 18, 2012

Nitpicking on "No Silver Bullets", part 1, HLL disadvantages

A recent post on John Cook's blog mentioned a presentation by Mike Swaim (titled "No Silver Bullet") about the advantages and disadvantages of certain programming techniques. Looking through the PDF, a few points bothered me. (Yes, nitpicking over bullet points is not exactly fair, and I am not at all claiming that the presenter was not aware of the issues.)

The disadvantages of high level languages were basically listed as reduced performance, "inappropriate runtime requirements" (which might be excessive resource requirements or things like garbage collection pauses in a tightly constrained hard real-time environment), and (based on the NT example) the inability to fix or even work around errors in architecture/design or implementation.

Performance issues

It seems that the performance problem comes from two issues. First, the compiler (and runtime system) does not fully exploit the available information. This comes from two sources: the lack of machine resources allocated to the compiler and the lack of programming effort applied to developing systems for translating higher level specifications to machine language code. While this can be seen as approaching artificial intelligence requirements, the difficulty of the goal is not as great as for generic artificial intelligence.

Some strengths of existing computing systems could be more fully exploited, most particularly the relative abundance of idle time on many computing systems and the relative reliability of detailed long-term memory. Offloading some analysis effort of the compiler to development time could provide more extensive analysis without increasing compilation time. Caching information about software could also substantially reduce the amount of analysis required at compilation time (or run time).

The software effort problem is unnecessarily hindered by issues with the definitions of behavior for programming languages (which can include behavior expected by existing software)

The second issue is the lack of communicating necessary information to the compiler (and runtime system). Information which is known (or assumed) by a human programmer is often not communicated to the compiler, and frequently the compiler is not allowed to ask questions for clarification. In some cases, the programming language provides no mechanism for communicating such information and seemingly more often makes communicating such information more difficult by the use of inappropriate default semantics (e.g., C pointer/array aliasing), discordant syntax for adding information (e.g., using __builtin_expect versus something like assuming (condition) {stuff to do} else {other stuff to do} or case 5 probability=20%: stuff to do; requiring the use of a different dialect or even language to express information adds an unnecessary barrier), and inability to use layered abstraction (e.g., providing a generic implementation of an operation with an optimized implementation that can "overload" the generic implementation with constraints [additional information] expressed so that the optimized implementation can be validated; furthermore optimized implementations could be provided as hints--"compiler, try this implementation"--or directives--"compiler, do it this way" and multiple implementations could be provided for different constraints--and the compiler might even use different implementations to generate a new implementation).

This second issue is compounded by the relatively weak support for profiling. Not only is the generation and use of profile information more complex than strictly necessary, but the overheads for generating such information seem to be greater than necessary. In addition, some information is generally not gathered by typical profiling tools. E.g., the temporal distribution of values for a variable and even the temporal correlation of values for different variables can be as important as the net frequency of values. Likewise, infrequent and limited use of whole program analysis prevents the compiler from using even relatively simple transformations in data structures and algorithms.

(Compiler writers not understanding computer architecture or being informed about specific microarchitectures--not necessarily by choice--does hinder the development of better compilers.)

While providing additional information would in many cases reduce the productivity advantages of a higher level language, in many such cases, the use of "overloading" implementations might provide good performance without losing the maintainance and extension advantages of the higher level representation. When a constraint of an optimized implementation is violated or the optimized version no longer matches the generic version, these effects can be noted allowing a decision to accept the optimization loss or rework the optimized implementation. In some cases, the reworking could be fully or partially--i.e., suggested fixes provided--automated. In some cases, multiple optimized implementations could be used to synthesize new implementations to better fit resource availability or optimization goals.

As an example, in many cases it should be possible for a compiler to recognize that the keys of a hash are immutable or restricted to a particular set of values or are accessed in a particular order, allowing a simple programming concept to be implemented in an optimized fashion. Providing directive or expectation information may allow the use of a higher level construct like a generic container while allowing the compiler to use an optimized implementation--preventing or generating a fatal error in the case of directives, dynamically recompiling or using an alternative implementation in the case of expectations. In theory, a hash which uses only unsigned integer keys could be implemented as an array. One might even generalize the hash concept to provide a syntax like container_of_records[element=variable] to index the element (or a collection of elements) where the record member 'element' equal the value in 'variable') with the ability to imply 'element=' based on the type information of 'variable' or the use of a default element (perhaps indicated by a qualifier in the definition like 'indexer' or by some precedence mechanism--though such could make bugs too easy to generate and too difficult to find) or a combination (where multiple indexers are provided and type information and/or precedence is used to determine which is used).

(Expectation information can also be used to reduce compilation effort. If the expectation is correct, the only overhead is in evaluating the expectation--compared to searching through all possibilities. If the expectation is incorrect, it may be acceptable to use less aggressive optimization and provide a notification or even delay final compilation of the component dependent on the expectation until a new expectation is provided by the programmer or possibly by some automated method, potentially taking advantage of lazy evaluation of the program source code. Obviously, the communication of the expectation should be lightweight, perhaps something like Some_record_type container[uint?] to define a container of 'Some_record_type' values that is expected to be indexed by unsigned integer values.)

Runtime Requirements

Runtime requirements issues would seem to have similar solutions as the performance issues. While it would be unreasonable to expect existence of even the limited form of artificial intelligence necessary to fully solve this issue, a more moderate degree of intelligence (or extensive searching) would seem likely to greatly reduce the problems. In particular, it is disappointing to me that automated memory management is often exclusively implemented as generic garbage collection. I suspect that in many cases the source code provides sufficient information to determine when a resource can be freed or when reference counting would be a better choice (with or without a saturating reference count--where a saturated reference count might indicate the use of a generic garbage collection mechanism); likewise, choices of allocators (region/stack/FILO/FIFO, binary buddy, fixed-sized arrays, limited size diversity exploiting expected frequencies and best fit with limited splitting and fusing of default partitioning, object caching, etc.) could be optimized by a compiler (or perhaps even a runtime system).

In addition, a high level language should support the ability to use lower-level directives (as well as communicate expectations) without degenerating into bare assembly language. (If assembly language is used, it should be annotated with constraints--obviously at minimum the assumed ISA--and a higher level implementation should be provided, which ideally could be used to validate the assembly language implementation.) Even if the lower-level directive cannot be validated against a higher-level representation or other information in the source code (or specification)--e.g., one might use a bald assertion which is not checked at runtime and need not be validated at compile time (though notification would be provided if compile-time validation was not possible), information would be available in the source code about the assumptions made and automated tools could use such assumptions to provide assistance in debugging. In some cases, debugging aids could be selectively applied (to reduce overheads). In the case of memory deallocation, in some cases it might be possible use virtual memory with page deduplication or compression to reduce the cost of not reusing deallocated memory by overwriting the
deallocated region with a given pattern.

Unfixable Environments

While the problems of bugs in the design or implementation of a runtime environment cannot be completely avoided (though using formal methods would limit such bugs to the design--and the development tools), using a modular design even in the runtime environment would seem likely to substantially reduce the impact of many design and implementation bugs/misfeatures. Allowing individual components to be swapped out would seem to greatly facilitate working around implementation and even design issues. Even layering a foreign interface over a required system interface might be practical in some circumstances. E.g., it might be possible to provide a specialized automated memory managment system over a generic garbage collector with modest overheads by using a minimum number of allocations using the system memory manager. Ideally, the functionality of such module implementations could be validated according to a higher level specification.

Unfortunately, not only are the inadequacies of tools a barrier to achieving such an ideal, but human factors are likely to hinder adoption. Humans are often disinclined to spend now to save later, often have difficulty admitting mistakes, often have difficulty throwing away a work (perhaps especially if it was well done and only recently became unfit for current or expected use), and often have difficulty recognizing the validity in another perspective (especially when that perspective is poorly communicated or is bundled with aspects that are invalid [Absolute tolerance of falsehood or wrongs is not a virtue, but often saying "you really shouldn't do that" is more appropriate than excommunication. {In the context of programming language design, making something awkward to do is often more appropriate than prohibition--with bonus points if repentance and reform is made easy.} The love of truth should be accompanied by humility and mercy.]).

No comments:

Post a Comment