Evaluating Memory Models for Graph‐Like Data Structures in the Rust Programming...

Evaluating Memory Models for Graph‐Like Data Structures in the Rust Programming Language: Performance and Usabiliy 2020 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title

Abstract [en]

Representing graphs in Rust is a problematic issue, as ownership forbids typical representations found in e.g. C++. A common approach is to use reference counting to represent graphs, but this can easily lead to memory leaks if cycles are present in the graph. As naïve reference counting is not sufficient, we must search for alternative representations. In this thesis, we explore different memory models that allow safe representations of graph-like data structures in Rust. These memory models are later evaluated in terms of performance and usability. We find that region-based allocation is, in most cases, the best model to use when performance is of importance. In cases where usability is more important, either reference-counting with cycle collection or tracing garbage collection is a solid choice. When it comes to multi-threading, we propose a new implementation of a lock-free transactional graph in Rust. To our knowledge, this is the first lock-free graph representation in Rust. The model demonstrates poor scalability, but for certain graph topologies and sizes, it offers performance that exceeds the other graph models.

Place, publisher, year, edition, pages

2020. , p. 58

Keywords [en]

Rust, graphs, performance, usability, data structures, memory models

National Category

Computer Sciences

Identifiers

URN: urn:nbn:se:liu:diva-168902ISRN: LIU-IDA/LITH-EX-A-20/045-SEOAI: oai:DiVA.org:liu-168902DiVA, id: diva2:1463648

External cooperation

Configura

Subject / course

Computer Engineering

Supervisors

Examiners

Available from: 2020-09-03 Created: 2020-09-02 Last updated: 2020-09-03Bibliographically approved