Original title: Efektivnost datových strukur v implementaci automatů
Translated title: Efficiency of data structures in implementation of automata
Authors: Koval, Milan ; Chocholatý, David (referee) ; Holík, Lukáš (advisor)
Document type: Bachelor's theses
Year: 2025
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [eng] [cze]
Tato práce se zabývá výkonnostní optimalizací knihovny Mata, která slouží k manipulaci s nedeterministickými konečnými automaty (NFA) v jazyce C++. I když Mata patří k nejrychlejším nástrojům svého druhu, práce ukazuje, že i u špičkově optimalizovaného kódu lze najít prostor pro další zlepšení. Největšího zrychlení bylo dosaženo zavedením vlastního lineárního alokátoru, který výrazně snížil režii při konstrukci automatů, a implementací odloženého řazení, které nahradilo per-insert třídění efektivnějším dávkovým přístupem. Tyto dvě změny přinesly měřitelná zlepšení výkonu především u výpočetně náročných operací, jako je průnik a doplněk. Ostatní zkoumané přístupy, včetně paralelizace a alternativních datových struktur, vykázaly zanedbatelný nebo žádný přínos. Výsledky byly ověřeny na sadě standardních benchmarků v reprodukovatelném prostředí. This thesis focuses on performance optimization of the Mata library, a high-performance C++ toolkit for manipulating nondeterministic finite automata (NFA). Although Mata is already among the fastest tools of its kind, this work demonstrates that even in highly optimized code, there is still room for meaningful improvements. The most significant speedups were achieved through the introduction of a custom linear memory allocator, which greatly reduced allocation overhead during automata construction, and the implementation of deferred sorting, which replaced costly per-insert sorting with a more efficient batch-based approach. These two techniques led to measurable performance gains, particularly in computationally intensive operations such as intersection and complement. Other explored strategies, including parallelization and alternative data structure designs, showed negligible or no benefit. All results were validated using a standard benchmark suite in a controlled, reproducible environment.
Keywords: alokátor; C++; datové struktury; konečný automat; lineární alokátor; Mata; NKA; optimalizace; allocator; C++; data structures; finite automaton; linear allocator; Mata; NFA; optimization

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/253199

Permalink: http://www.nusl.cz/ntk/nusl-682128


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses