Search

Your search keyword '"Erez Petrank"' showing total 209 results
Start Over Author "Erez Petrank" Search Limiters Academic (Peer-Reviewed) Journals
209 results on '"Erez Petrank"'

4. Automated Verification of Practical Garbage Collectors

Author

Chris Hawblitzel and Erez Petrank

Subjects
computer science - programming languages, Logic, BC1-199, Electronic computers. Computer science, QA75.5-76.95
Abstract

Garbage collectors are notoriously hard to verify, due to their low-level interaction with the underlying system and the general difficulty in reasoning about reachability in graphs. Several papers have presented verified collectors, but either the proofs were hand-written or the collectors were too simplistic to use on practical applications. In this work, we present two mechanically verified garbage collectors, both practical enough to use for real-world C# benchmarks. The collectors and their associated allocators consist of x86 assembly language instructions and macro instructions, annotated with preconditions, postconditions, invariants, and assertions. We used the Boogie verification generator and the Z3 automated theorem prover to verify this assembly language code mechanically. We provide measurements comparing the performance of the verified collector with that of the standard Bartok collectors on off-the-shelf C# benchmarks, demonstrating their competitiveness.

Published
2010
Full Text
View/download PDF

26. Concurrent size

Author

Gal Sela and Erez Petrank

Subjects
FOS: Computer and information sciences, Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Distributed, Parallel, and Cluster Computing (cs.DC), Safety, Risk, Reliability and Quality, Software
Abstract

The size of a data structure (i.e., the number of elements in it) is a widely used property of a data set. However, for concurrent programs, obtaining a correct size efficiently is non-trivial. In fact, the literature does not offer a mechanism to obtain a correct (linearizable) size of a concurrent data set without resorting to inefficient solutions, such as taking a full snapshot of the data structure to count the elements, or acquiring one global lock in all update and size operations. This paper presents a methodology for adding a concurrent linearizable size operation to sets and dictionaries with a relatively low performance overhead. Theoretically, the proposed size operation is wait-free with asymptotic complexity linear in the number of threads (independently of data-structure size). Practically, we evaluated the performance overhead by adding size to various concurrent data structures in Java$-$a skip list, a hash table and a tree. The proposed linearizable size operation executes faster by orders of magnitude compared to the existing option of taking a snapshot, while incurring a throughput loss of $1\%-20\%$ on the original data structure's operations., Comment: Code: https://github.com/galysela/ConcurrentSize

Published
2022

30. Help!

Author

Keren Censor-Hillel, Erez Petrank, and Shahar Timnat

Published
2015
Full Text
View/download PDF

34. EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation

Author

Gali Sheffi and Pedro Ramalhete and Erez Petrank, Sheffi, Gali, Ramalhete, Pedro, Petrank, Erez, Gali Sheffi and Pedro Ramalhete and Erez Petrank, Sheffi, Gali, Ramalhete, Pedro, and Petrank, Erez

Abstract

Multi-Version Concurrency Control (MVCC) is a common mechanism for achieving linearizable range queries in database systems and concurrent data-structures. The core idea is to keep previous versions of nodes to serve range queries, while still providing atomic reads and updates. Existing concurrent data-structure implementations, that support linearizable range queries, are either slow, use locks, or rely on blocking reclamation schemes. We present EEMARQ, the first scheme that uses MVCC with lock-free memory reclamation to obtain a fully lock-free data-structure supporting linearizable inserts, deletes, contains, and range queries. Evaluation shows that EEMARQ outperforms existing solutions across most workloads, with lower space overhead and while providing full lock freedom.

Published
2023
Full Text
View/download PDF

37. BQ: A Lock-Free Queue with Batching

Author

Yossi Lev, Gal Milman, Erez Petrank, Victor Luchangco, and Alex Kogan

Subjects
Multi-core processor, Linearizability, Computer science, Concurrent data structure, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, Data structure, 01 natural sciences, Computer Science Applications, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Modeling and Simulation, 0202 electrical engineering, electronic engineering, information engineering, Non-blocking algorithm, Concurrent computing, Performance improvement, Queue, Software
Abstract

Concurrent data structures provide fundamental building blocks for concurrent programming. Standard concurrent data structures may be extended by allowing a sequence of operations to be submitted as a batch for later execution. A sequence of such operations can then be executed more efficiently than the standard execution of one operation at a time. In this article, we develop a novel algorithmic extension to the prevalent FIFO queue data structure that exploits such batching scenarios. An implementation in C++ on a multicore demonstrates significant performance improvement of more than an order of magnitude (depending on the batch lengths and the number of threads) compared to previous queue implementations.

Published
2022

Catalog

Books, media, physical & digital resources
See catalog results