Original title:
Efficiency of data structures in implementation of automata
Translated title:
Efektivnost datových strukur v implementaci automatů
Authors:
Koval, Milan ; Smrčka, Aleš (referee) ; Holík, Lukáš (advisor) Document type: Bachelor's theses
Year:
2024
Language:
eng Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[eng][cze]
Tato Prace se soustředí na optimalizaci knihovny Mata, která je součastným leaderem na poli vykonu v oblasti operací nad automaty. Výrazdné zlepšení výkonu je dosáhnuto pomocí modifikovaného lineárního alokátoru, využitím append-only vlastnosti reprezentace automatu umozňue bleskově rychlé konstrukce a bleskově rychlým pristupúm do paměti díky prostorove lokalitě. Nálezem této práce není pouze rychlejší už ta nejrychlejší knihovna Mata ale take použitelnost lineárních alokátorů jako normálně používaná praxe při append-only strukturách, speciálně v výkonově kritických případech.
This Thesis focuses on optimazing the library Mata, that is curently the leader in performance it the fieal operations on automatas. Sygnificant performance increase is achived with the use of a modified linear allocator, using the append-only represetattion of an automata allows for blazing fast construction and blazing fast memery acces owning to resulting spatial locality. The findings of this thesis is not only faster already fastest library Mata but also the viability of linear allocaotors as a more common practice in append only structures, espessialy in performance critical uses.
Keywords:
allocator; automat; automaton; c++; lineární allocator; Mata; optimalization; allocator; automat; automaton; c++; linear allocator; Mata; optimalization
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: https://hdl.handle.net/11012/246934