DESOLA: An active linear algebra library using delayed evaluation and runtime code generation

Active libraries can be defined as libraries which play an active part in the compilation, in particular, the optimisation of their client code. This paper explores the implementation of an active dense linear algebra library by delaying evaluation of expressions built using library calls, then generating code at runtime for the compositions that occur. The key optimisations in this context are loop fusion and array contraction.Our prototype C++ implementation, DESOLA, automatically fuses loops arising from different client calls, identifies unnecessary intermediate temporaries, and contracts temporary arrays to scalars. Performance is evaluated using a benchmark suite of linear solvers from ITL (Iterative Template Library), and is compared with MTL (Matrix Template Library), ATLAS (Automatically Tuned Linear Algebra) and IMKL (Intel Math Kernel Library). Excluding runtime compilation overheads (caching means they occur only on the first iteration), for larger matrix sizes, performance matches or exceeds MTL; when fusion of matrix operations occurs, performance exceeds that of ATLAS and IMKL.     

“Slimming” a Java virtual machine by way of cold code removal and optimistic partial program loading

Embedded systems provide limited storage capacity. This limitation conflicts with the demands of modern virtual machine platforms, which require large amounts of library code to be present on each client device. These conflicting requirements are often resolved by providing specialized embedded versions of the standard libraries, but even these stripped down libraries consume significant resources.We present a solution for “always connected” mobile devices based on a zero footprint client paradigm. In our approach, all code resides on a remote server. Only those parts of applications and libraries that are likely to be needed are transferred to the mobile client device. Since it is difficult to predict statically which library parts will be needed at run time, we combine static analysis, opportunistic off-target linking and lazy code loading to transfer code with a high likelihood of execution ahead of time while the other code, such as exception code, remains on the server and is transferred only on demand. This allows us to perform not only dead code elimination, but also aggressive elimination of unused code.The granularity of our approach is flexible from class files all the way down to individual basic blocks. Our method achieves total code size reductions of up to 95%.     

第三方库依赖冲突问题研究综述

软件开发过程中, 开发人员通过大量使用第三方库来实现代码复用. 不同第三方库之间存在依赖关系, 第三方库间的不兼容会导致第三方库的安装、加载、调用时出现错误, 进而导致系统异常, 这类问题称之为第三方库依赖冲突问题. 依赖冲突的根本原因是加载的第三方库无法覆盖软件引用的必需特性(例如: 方法). 依赖冲突问题会在第三方库的下载安装, 项目编译和运行时中出现, 且定位困难. 依赖冲突问题的修复要求开发人员对使用的第三方库版本间差别具有准确的理解, 并且第三方库之间复杂的依赖关系增加了修复难度. 为了能够在软件运行前, 发现软件中存在的依赖冲突, 并且能够响应和处理运行过程中由依赖冲突引发的系统异常, 国内外学者展开了各种针对依赖冲突问题的研究. 从依赖冲突问题的4个方面, 对当前已有研究工作进行了梳理, 包括: 第三方库的使用实证分析、依赖冲突原因分析、依赖冲突检测方法以及依赖冲突常用修复方式. 最后对该领域未来值得关注的研究问题进行了展望.     

Inferring specifications for resources from natural language API documentation

Many software libraries, especially those commercial ones, provide API documentation in natural languages to describe correct API usages. However, developers may still write code that is inconsistent with API documentation, partially because many developers are reluctant to carefully read API documentation as shown by existing research. As these inconsistencies may indicate defects, researchers have proposed various detection approaches, and these approaches need many known specifications. As it is tedious to write specifications manually for all APIs, various approaches have been proposed to mine specifications automatically. In the literature, most existing mining approaches rely on analyzing client code, so these mining approaches would fail to mine specifications when client code is not sufficient. Instead of analyzing client code, we propose an approach, called Doc2Spec, that infers resource specifications from API documentation in natural languages. We evaluated our approach on the Javadocs of five libraries. The results show that our approach performs well on real scale libraries, and infers various specifications with relatively high precisions, recalls, and F-scores. We further used inferred specifications to detect defects in open source projects. The results show that specifications inferred by Doc2Spec are useful to detect real defects in existing projects.     

What are the characteristics of popular APIs? A large-scale study on Java,Android, and 165 libraries

Software systems are commonly implemented with the support of libraries, which provide features via APIs. Ideally, APIs should have some characteristics, for example, they should be well documented and stable so that client systems can confidently rely on them. However, not all APIs are equal in number of clients: while some APIs are very popular and used worldwide, other may face much lower usage rates. In this context, one question appears: are there particular characteristics that differentiate popular APIs from ordinary APIs? Answering this question can uncover how worldwide APIs are actually implemented and maintained, revealing practices to better support both research and development on APIs. In this paper, we assess the characteristics of popular APIs, including their size, legibility, documentation, stability, and client adoption. We analyze 1491 APIs provided by Java, Android, and 165 libraries. We detect that popular APIs are distinct from ordinary ones, for example, often, popular APIs are larger, have more comments, and are more unstable than ordinary APIs. Finally, we provide a set of lessons learned from the popular APIs on factors that developers can control, such as the exposure of public methods and the API stability.

     

Certifying Low-Level Programs with Hardware Interrupts and Preemptive Threads

Hardware interrupts are widely used in the world’s critical software systems to support preemptive threads, device drivers, operating system kernels, and hypervisors. Handling interrupts properly is an essential component of low-level system programming. Unfortunately, interrupts are also extremely hard to reason about: they dramatically alter the program control flow and complicate the invariants in low-level concurrent code (e.g., implementation of synchronization primitives). Existing formal verification techniques—including Hoare logic, typed assembly language, concurrent separation logic, and the assume-guarantee method—have consistently ignored the issues of interrupts; this severely limits the applicability and power of today’s program verification systems. In this paper we present a novel Hoare-logic-like framework for certifying low-level system programs involving both hardware interrupts and preemptive threads. We show that enabling and disabling interrupts can be formalized precisely using simple ownership-transfer semantics, and the same technique also extends to the concurrent setting. By carefully reasoning about the interaction among interrupt handlers, context switching, and synchronization libraries, we are able to—for the first time—successfully certify a preemptive thread implementation and a large number of common synchronization primitives. Our work provides a foundation for reasoning about interrupt-based kernel programs and makes an important advance toward building fully certified operating system kernels and hypervisors.     

Beyond contracts for concurrency

SCOOP is a concurrent programming language with a new semantics for contracts that applies equally well in concurrent and sequential contexts. SCOOP eliminates race conditions and atomicity violations by construction. However, it is still vulnerable to deadlocks. In this paper we describe how far contracts can take us in verifying interesting properties of concurrent systems using modular Hoare rules and show how theorem proving methods developed for sequential Eiffel can be extended to the concurrent case. However, some safety and liveness properties depend upon the environment and cannot be proved using the Hoare rules. To deal with such system properties, we outline a SCOOP Virtual Machine (SVM) as a fair transition system. The SVM makes it feasible to use model-checking and theorem proving methods for checking global temporal logic properties of SCOOP programs. The SVM uses the Hoare rules where applicable to reduce the number of steps in a computation. P. J. Brooke, R. F. Paige and Dong Jin Song This work was conducted under an NSERC Discovery grant.     

Data mining for defects in multicore applications: an entropy‐based call‐graph technique

Multicore computers are ubiquitous. Expert developers as well as developers with little experience in parallelism are now asked to create multithreaded software to exploit parallelism in mainstream shared‐memory hardware. However, finding and fixing parallel programming errors is a complex and arduous task. Programmers thus rely on tools such as race detectors that typically focus on reporting errors due to incorrect usage of synchronization constructs or due to missing synchronization. This arsenal of debugging techniques, however, is incomplete. This article presents a new perspective and addresses a largely unexplored direction of defect localization where a wrong usage of nonparallel programming constructs might cause wrong parallel application behavior. In particular, we make a contribution by showing how to use data‐mining techniques to locate defects in multithreaded shared‐memory programs. Our technique analyzes execution anomalies in a condensed representation of the dynamic call graphs of a multithreaded object‐oriented application and identifies methods that contain a defect. Compared with race detectors that concentrate on finding incorrect synchronization, our method is able to reveal a wider range of defects that affect the control flow of a parallel program. Results from controlled experiments show that our data‐mining approach finds not only race conditions in different types of multicore applications but also other errors that cause incorrect parallel program behavior. Data‐mining techniques offer a fruitful new ground for parallel program debugging, and we also discuss long‐term directions for this interesting field. Copyright © 2012 John Wiley & Sons, Ltd.     

A fully abstract trace-based semantics for reasoning about backward compatibility of class libraries

Backward compatibility is the property that an old version of a library can safely be replaced by a new version without breaking existing clients. Formal reasoning about backward compatibility requires an adequate semantic model to compare the behavior of two library implementations. In the object-oriented setting with inheritance and callbacks, such a model must account for the complex interface between library implementations and clients.In this paper, we develop a fully abstract trace-based semantics for class libraries in object-oriented languages, in particular for Java-like sealed packages. Our approach enhances a standard operational semantics such that the change of control between the library and the client context is made explicit in terms of interaction labels. By using traces over these labels, we abstract from the data representation in the heap, support class hiding, and provide fully abstract package denotations. Soundness and completeness of the trace semantics is proven using specialized simulation relations on the enhanced operational semantics. The simulation relations also provide a proof method for reasoning about backward compatibility.     

Parallel distributed-time logic simulation

The Chandy-Misra algorithm offers more parallelism than the standard event-driven algorithm for digital logic simulation. With suitable enhancements, the Chandy-Misra algorithm also offers significantly better parallel performance. The authors present methods to optimize the algorithm using information about the large number of global synchronization points, called deadlocks, that limit performance. They classify deadlocks and describe them in terms of circuit structure. The proposed methods that use domain-specific knowledge to avoid deadlocks and present a way to reduce greatly the time it takes to resolve a deadlock. For one benchmark circuit, the authors eliminated all deadlocks using their techniques and increased the average number of logic elements available for concurrent execution from 45 to 160. Simulation results for a 60-processor machine show that the Chandy-Misra algorithm outperforms the event-driven algorithm by a factor of 2 to 15     

How Java APIs break – An empirical study

ContextIt has become common practice to build programs by using libraries. While the benefits of reuse are well known, an often overlooked risk are system runtime failures due to API changes in libraries that evolve independently. Traditionally, the consistency between a program and the libraries it uses is checked at build time when the entire system is compiled and tested. However, the trend towards partially upgrading systems by redeploying only evolved library versions results in situations where these crucial verification steps are skipped. For Java programs, partial upgrades create additional interesting problems as the compiler and the virtual machine use different rule sets to enforce contracts between the providers and the consumers of APIs.ObjectiveWe have studied the extent of the problem in real world programs. We were interested in two aspects: the compatibility of API changes as libraries evolve, and the impact this has on programs using these libraries.MethodThis study is based on the qualitas corpus version 20120401. A data set consisting of 109 Java open-source programs and 564 program versions was used from this corpus. We have investigated two types of library dependencies: explicit dependencies to embedded libraries, and dependencies defined by symbolic references in Maven build files that are resolved at build time. We have used JaCC for API analysis, this tool is based on the popular ASM byte code analysis library.ResultsWe found that for most of the programs we investigated, APIs are unstable as incompatible changes are common. Surprisingly, there are more compatibility problems in projects that use automated dependency resolution. However, we found only a few cases where this has an actual impact on other programs using such an API.ConclusionIt is concluded that API instability is common and causes problems for programs using these APIs. Therefore, better tools and methods are needed to safeguard library evolution.     

一种并发面向对象同步模型研究

同步是并发语言的一个重要特征,然而在面向对象的框架下,同步约束的存在可能导致不期望的方法的重定义.基于并发面向对象规约语言VDM++(Vienna development method)的两种同步机制,提出一种适合于并发面向对象广谱规约语言的同步模型-卫式路径结构.它不但可以支持一般代码的复用,而且可以全方位地支持对同步代码的复用.     

An exploratory study of api changes and usages based on apache and eclipse ecosystems

Frameworks are widely used in modern software development to reduce development costs. They are accessed through their Application Programming Interfaces (APIs), which specify the contracts with client programs. When frameworks evolve, API backward-compatibility cannot always be guaranteed and client programs must upgrade to use the new releases. Because framework upgrades are not cost-free, observing API changes and usages together at fine-grained levels is necessary to help developers understand, assess, and forecast the cost of each framework upgrade. Whereas previous work studied API changes in frameworks and API usages in client programs separately, we analyse and classify API changes and usages together in 22 framework releases from the Apache and Eclipse ecosystems and their client programs. We find that (1) missing classes and methods happen more often in frameworks and affect client programs more often than the other API change types do, (2) missing interfaces occur rarely in frameworks but affect client programs often, (3) framework APIs are used on average in 35 % of client classes and interfaces, (4) most of such usages could be encapsulated locally and reduced in number, and (5) about 11 % of APIs usages could cause ripple effects in client programs when these APIs change. Based on these findings, we provide suggestions for developers and researchers to reduce the impact of API evolution through language mechanisms and design strategies.     

Assessing the capability of code smells to explain maintenance problems: an empirical study combining quantitative and qualitative data

Code smells are indicators of deeper design problems that may cause difficulties in the evolution of a software system. This paper investigates the capability of twelve code smells to reflect actual maintenance problems. Four medium-sized systems with equivalent functionality but dissimilar design were examined for code smells. Three change requests were implemented on the systems by six software developers, each of them working for up to four weeks. During that period, we recorded problems faced by developers and the associated Java files on a daily basis. We developed a binary logistic regression model, with “problematic file” as the dependent variable. Twelve code smells, file size, and churn constituted the independent variables. We found that violation of the Interface Segregation Principle (a.k.a. ISP violation) displayed the strongest connection with maintenance problems. Analysis of the nature of the problems, as reported by the developers in daily interviews and think-aloud sessions, strengthened our view about the relevance of this code smell. We observed, for example, that severe instances of problems relating to change propagation were associated with ISP violation. Based on our results, we recommend that code with ISP violation should be considered potentially problematic and be prioritized for refactoring.     

软件库调用规约挖掘

软件库调用规约是一种描述软件库提供函数正确调用顺序的规约.客户代码应按此规约描述的内容调用函数,否则可能引入缺陷,从而降低软件的可信性.由于能够描述可信软件应该满足的性质,软件库调用规约在可信软件、模型检测等研究中扮演特殊的角色.但是,受制于编写规约的巨大代价,软件库通常并不提供已编写好的调用规约.为此,研究者提出了各种自动挖掘此种规约的方法.阐述了其中代表性的方法及其最新的研究进展,并在此基础上探讨了将来的研究方向.     

Concurrent access to data

Summary Problems caused by concurrent access to data can be solved by locking. This, however, diminishes efficiency and may cause deadlocks among the accessing processes. In this paper the structuring of data sets is deduced from assertions about accesses which may be performed simultaneously. This structuring supports the development of operations which synchronize concurrent access to these data. Thus the provisions for locking are transferred from programs to data structures where the requests for locking actually arise. The synchronization operations will exclude all undesired interferences and will maximize the number of possible simultaneous accesses in accordance with the original assertions.     

CORBA request portable interceptors: analysis and applications

Interceptors are an emerging middleware technology enabling the addition of specific network‐oriented capabilities to distributed applications. By exploiting interceptors, developers can register code within interception points, extending the basic middleware mechanisms with specific functionality, e.g. authentication, flow control, caching, etc. Notably, these extensions can be achieved without modifying either the application or the middleware code. In this paper we report the results of our experiences with CORBA request portable interceptors. In particular, we point out (i) the basic mechanisms implementable by these interceptors, i.e. request redirection and piggybacking and (ii) we analyze their limitations. We then propose a proxy‐based technique to overcome the interceptors' limitations. Successively, we present a performance analysis carried out on three Java‐CORBA platforms currently implementing the portable interceptors specification. Finally, we conclude our work with a case study in which portable interceptors are used to implement the fault‐tolerant CORBA client invocation semantic without impacting on the client application code and on the CORBA ORB. We also release fragments of Java code for implementing the described techniques. Copyright © 2003 John Wiley & Sons, Ltd.     

基于PushRegistry移动图书通知的设计与实现

针对移动通讯的便利性,利用J2ME开发移动图书服务终端应用程序,构筑智能客户端.通过PushRegistry注册机制动态注册引人的网络连接及定时提醒实现移动图书"随时、随地、随身"的离线及在线服务与通知,同时采用SyncML实现服务器中读者数据与终端中的同步.基于注册机制的优势在于信息的主动性、及时性及灵活性,充分满足移动用户的需求.     

Using wait-free synchronization in the design of distributed applications

Wait-free synchronization has been recognized in the literature as an effective concurrent programming technique. The concurrent programming community, however, has been slow to adopt this technique. This paper addresses the practical application of wait-free synchronization in the design of distributed applications. In this paper, we present an implementation of a server that uses wait-free synchronization. The resulting code is more easily seen to be fault tolerant. The performance analysis of the wait-free synchronization server outperformed a server that uses traditional locking techniques. This practical demonstration of the benefits of wait-free synchronization should help foster its adoption in the development of distributed applications.