Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays

Since its inception Functional Programming, J. McCarthy, has almost universally used the Linked List as the underpinning data structure. This paper introduces a new data structure, the VList, that is compact, thread safe and significantly faster to use than Linked Lists for nearly all list operations. Space usage can be reduced by 50% to 90% and in typical list operations speed improved by factors ranging from 4 to 20 or more. Some important operations such as indexing and length are typically changed from O(N) to O(1) and O(lgN) respectively. A language interpreter Visp, using a dialect of Common Lisp, has been implemented using VLists and the benchmark comparison with OCAML reported. It is also shown how to adapt the structure to create variable length arrays, persistent deques and functional hash tables. The VArray requires no resize copying and has an average O(1) random access time. Comparisons are made with previous resizable one dimensional arrays, Hash Array Trees (HAT) Sitarski [1996], and Brodnik, Carlsson, Demaine, Munro, and Sedgewick [1999].

RRB-Trees: Efficient Immutable Vectors

Tiark Rompf

Immutable vectors are a convenient data structure for functional programming and part of the standard library of modern languages like Clojure and Scala. The common implementation is based on wide trees with a fixed number of children per node, which allows fast indexed lookup and update operations. In this paper we extend the vector data type with a new underlying data structure, Relaxed Radix Balanced Trees (RRB-Trees), and show how this structure allows immutable vector concatenation, insert-at and splits in O(log N) time while maintaining the index, update and iteration speeds of the original vector data structure.

2011

Functional and Adaptive Construction for Rescue

Hadi Ardiny

Although recent advances in the field of robotics have greatly increased robotic capabilities for several applications, autonomous robots are still in their infancy regarding their support of onsite construction. Unlike production robots that are used, for instance, in automotive industries, autonomous robotic systems should be designed with special considerations, such as the complexity of the cluttered and dynamic working space, inaccuracy in positioning because of the nature of mobile systems, and so forth. Thus, construction has been known as a highly complex application field for robotic systems, especially in unknown environments. In this thesis, we focus on the developments of an autonomous construction system by taking inspiration from architectural designs found in the animal kingdom. The construction system allows robots to build functional structures over a different range of environmental conditions or in unknown sites without the use of any predefined construction plan (i.e., blueprint). We call this approach adaptive and functional autonomous construction (AFAC). Indeed, AFAC is a robust and intelligent system that can tackle unforeseen problems of unknown environments and faults made during the course of building. We present two approaches for AFAC. One is a local approach that enables robots to locally sense features of their environment and then act immediately according to defined rules without using any global representation or knowledge of the world. Second is a global approach, which involves building structures by analysing global representations and knowledge produced by the robots. This approach consists of three phases: the first phase is exploration, to map the unknown environment and to find important elements. In the second phase, an effective construction plan is autonomously computed using collected data and the defined functions. Finally, in the last phase, the robot builds structures based on the computed construction plan. One interesting implementation of the introduced construction system is its potential use in a post disaster environment, where an autonomous robotic system can perform construction tasks in the rescue operation. Robots can be employed to build protective structures for rescue functions, including stabilizing large structures or protecting victims in unknown environments, where the environment are perhaps covered by debris. Inasmuch as the robots cannot plan in advance to build these structures, the rescue application is a well suited case for the study and implementation of AFAC in unknown and cluttered environments. Through implementation of AFAC in the rescue situations, we develop AFAC from scratch to the level at which the robots can autonomously apply AFAC's principles for use in the new classes of construction applications. We also study and compare the local and global approaches of AFAC. In addition, we develop new exploration methods and construction plan computation methodologies for the global approach to efficiently lead AFAC.

EPFL2017

Log-Free Concurrent Data Structures

Tudor Alexandru David, Aleksandar Dragojevic, Rachid Guerraoui, Mihail Igor Zablotchi

Non-volatile RAM (NVRAM) makes it possible for data structures to tolerate transient failures, assuming however that programmers have designed these structures such that their consistency is preserved upon recovery. Previous ap- proaches are typically transactional and inherently make heavy use of logging, resulting in implementations that are significantly slower than their DRAM counterparts. In this paper, we introduce a set of techniques aimed at lock-free data structures that, in the large majority of cases, remove the need for logging (and costly durable store instructions) both in the data structure algorithm and in the associated memory management scheme. Together, these generic techniques enable us to design what we call log-free concurrent data structures, which, as we illustrate on linked lists, hash tables, skip lists, and BSTs, can provide several-fold performance improvements over previous transaction-based implementations, with overheads of the order of milliseconds for recovery after a failure. We also highlight how our techniques can be integrated into practical systems, by presenting a durable version of Memcached that maintains the performance of its volatile counterpart.

USENIX Association2018

Functional and Adaptive Construction for Rescue

Hadi Ardiny

EPFL2017