Abstract Repairing software defects is crucial to improving the security and robustness of software. Traditional methods repair software defects by using the “stop-repair-restart” approach. Unfortunately, in some scenarios, such as cloud environments, restarting critical software is expensive. Dynamic methods enable the defect repair while the software is running, which can avoid software restart. However, dynamic repair requires capture the safe state of the running software (process). Otherwise, it will cause execution exceptions or even process crashes. To address the complex state issues in multi-threaded environments, existing methods modify the kernel or compiler, or even pre-adding custom code to the target software, which reduces their generality. To solve this problem, we propose a hot repair method HotFix, which can fix the defects without any software suspending. HotFix places probes in the process to receive state signals, which can avoid complex and time-consuming state identification. Then, it selects the safe zone and repairs the defects when the code in the safe zone is called, which can prevent the target process from hanging for a long time. Finally, HotFix completes multi-threaded automated migration online. Experiments and analysis show that HotFix can achieve hot repair in complex environments. We found that the affected function was executed no more than 1,000 times during the fix. Introducing 3us and 11us delays per request respectively when repairing Redis and Mem cached, and the requests influenced are limited.

Skewed write-intensive key-value storage workloads are increasingly observed in modern data centers, yet they also incur server overloads due to load imbalance. Programmable switches provide viable solutions for realizing load-balanced caching on the I/O path, and hence implementing write-back caching in programmable switches is a natural approach to absorb frequent writes and improve write performance. However, enabling in-switch write-back caching is challenged by not only the strict programming rules and limited stateful memory of programmable switches, but also the need for reliable protection against data loss due to switch failures. We first propose FarReach, a new caching framework that supports fast, available, and reliable in-switch write-back caching. FarReach carefully co-designs both the control and data planes for cache management in programmable switches, so as to achieve high data-plane performance with lightweight control-plane management. We further extend FarReach into DistReach, which reduces the reliability maintenance overhead via distributed switch deployment. Our experimental results on a Tofino-switch testbed show that FarReach achieves a throughput gain of up to$6.6\times $over a state-of-the-art in-switch caching approach under skewed write-intensive workloads. Also, DistReach reduces the crash recovery time of FarReach by 77.4%.

The paper reports on the development of a 2D geometric constraint solver. The solver is a major component of a new generation of cad systems based on a high-level geometry representation. The solver uses a graph-reduction directed algebraic approach, and achieves interactive speed. The paper describes the architecture of the solver and its basic capabilities. Then, it discusses in detail how to extend the scope of the solver, with particular emphasis on the theoretical and human factors involved in finding a solution, in an exponentially large search space, so that the solution is appropriate to the application, and so that the way of finding it is intuitive for an untrained user.

It is generally assumed that hashing is essential to solve many language processing problems efficiently; e.g. symbol table formation and maintenance, grammar manipulation, basic block optimization, and global optimization. This paper questions this assumption, and initiates development of an efficient alternative compiler methodology without hashing or sorting. The methodology rests on efficient solutions to the basic problem of detecting duplicate values in a multiset, which we call multiset discrimination. Paige and Tarjan (1987) gave an efficient solution to multiset discrimination for detecting duplicate elements occurring in a multiset of varying length strings. The technique was used to develop an improved algorithm for lexicographic sorting, whose importance stems largely from its use in solving a variety of isomorphism problems (Aho et al., 1974). The current paper and a related paper (Paige, 1994) show that full lexicographic sorting is not needed to solve these isomorphism problems, because they can be solved more efficiently using straightforward extensions to the simpler multiset discrimination technique. By reformulating language processing problems in terms of multiset discrimination, we also show how almost every subtask of compilation can be solved without hashing in worst case running time no worse (and frequently better) than the best previous expected time solution (under the assumption that one hash operation takes unit expected time). Because of their simplicity, our solutions may be of practical as well as theoretical interest. The various applications presented culminate with a new algorithm to solve iterated strength reduction folded with useless code elimination that runs in worst case asymptotic time and auxiliary space Θ(¦L¦ + ¦L'¦), where ¦L¦ and ¦L'¦ represent the lengths of the initial and optimized programs, respectively. The previous best solution due to Cocke and Kennedy (1977) takes Ω(¦L¦3¦L'¦) has operations in the worst case.

This paper reports experimental results that support the feasibility of a new transformational approach developed by the authors for implementing complex algorithms correctly and efficiently. The class of algorithms amenable to our methods includes nonnumerical graph algorithms. Experiments were performed to measure how this approach affects productivity (in terms of the number of source lines in the implementation divided by manual programming time) and running times. Comparative benchmarks showed that productivity can be increased over a conventional ad hoc approach by factors ranging from 5.1 to 9.9 Preliminary results also showed that the running time of C code produced by this new approach can be as fast as 1.5 times that of tightly coded high quality Fortran.

Based on a new version of the Hopcroft and Tarjan planarity testing algorithm, this paper develops an $O(m\log n)$-time algorithm to find a maximal planar subgraph.

Previously counting embeddings of planar graphs used P-Q trees and was restricted to biconnected graphs. Although the P-Q tree approach is conceptually simple, its implementation is complicated. In this paper, the author solves this problem using DFS trees, which are easy to implement. The author also gives formulas that count the number of embeddings of general planar graphs (not necessarily connected or biconnected) in $O( n )$ arithmetic steps, where n is the number of vertices of the input graph. Finally, the algorithm can be extended to generate all embeddings of a planar graph in linear time with respect to the output.

Pattern matching in trees is fundamental to a variety of programming language systems. However, progress has been slow in satisfying a pressing need for general-purpose pattern-matching algorithms that are efficient in both time and space. We offer asymptotic improvements in both time and space to Chase's bottom-up algorithm for pattern preprocessing. A preliminary implementation of our algorithm runs ten times faster than Chase's (1987) implementation on the hardest problem instances. Our preprocessing algorithm has the advantage of being on-line with respect to pattern additions and deletions. It also adapts to favorable input instances, and on Hoffmann and O'Donnell's (1982) class of simple patterns, it performs better than their special-purpose algorithm tailored to this class. We show how to modify our algorithm using a new decomposition method to obtain a space/time tradeoff. Finally, we trade a log factor in time for a linear space bottom-up pattern-matching algorithm that handles a wide subclass of Hoffmann and O'Donnell's (1982) simple patterns.

It is generally assumed that hashing is essential to many algorithms related to efficient compilation; e.g., symbol table formation and maintenance, grammar manipulation, basic block optimization, and global optimization.This paper questions this assumption, and initiates development of an efficient alternative compiler methodology without hashing or sorting.Underlying this methodology are several generic algorithmic tools, among which special importance is given to Multiset Discrimination, which partitions a multiset into blocks of duplicate elements.We show how multiset discrimination, together with other tools, can be tailored to rid compilation of hashing without loss in asymptotic performance.Because of the simplicity of these tools, our results maybe of practical as well as theoretical interest.The various applications presented culminate with a new algorithm to solve iterated strength reduction folded with useless code elimination that runs in worst case asymptotic time and auxiliary space linear in the maximum text length of the initial and optimized programs.1. Introduction.with linear search time and a hash table.They also pro-An important practical and theoretical question in Computer Science is whether there are algorithms whose worst case performance can match the expected performance of solutions that utilize hashing.In the context of this broader question, we initiate an investigation of efficient compilation without hashing and, consequently, raise some doubts about the prevailing view that hashing (e.g., universal hashing [5]) is essential to the various 2. The research of this author was partiatly

An important research goal in software engineering and programming languages is the development of principles underlying the specification of computable problems, the translation of these problems into efficient and correct programs, and the performance analysis of these programs. This paper uncovers some of these principles, which are used to design a problem specification language L1 restricted to problems that can be compiled automatically into programs whose worst case asymptotic time and space complexities are linear in the input/output space. Any problem expressible in L1 can be compiled into a linear cost program. A compiler for L1 has been implemented in the RAPTS transformational programming system.