Enhancing methods and testing means for string searching
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Authors
Date
2021-01-25
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
68
Series
Abstract
Exact online string matching research predominantly employs two testing environments, H&S and SMART, for experimentally evaluating string matching algorithms by measuring their running times. While string matching is an extensively studied problem, the testing environments are less studied and understood. Thus, this thesis instrumented the testing environments with calls to Performance Application Programming Interface (PAPI) in an attempt to evaluate interferences that might negatively impact the experimental evaluation. The interferences, which stem from the testing environment designs, manifest as specific interactions between the string matching algorithms and a computer system running the algorithms. PAPI allows monitoring such interactions through hardware performance counters. Experiments on the instrumented testing environments revealed insights on two interferences. First, in H&S and to a much lesser extent in SMART, the algorithms read the searched text from cache instead of main memory. The impact on running times, however, seemed to be negligible and negated by hardware prefetchers. Second, in SMART, the first memory access to every page caused a page fault during each algorithm run. The page faults continuously interrupted the algorithms which incurred significant overhead in the running times. In the extreme cases, this overhead was nearly an order of magnitude larger than an algorithm's actual running time. Lastly, this thesis presents an optimization -- a guard test -- on comparison based string matching algorithms. The guard test compares q-grams between a pattern and an alignment window to determine whether to enter a match loop or to shift the pattern. The effectiveness of this guard test was evaluated with experiments: it works considerably well on small alphabets.Merkkijonohakualgoritmien tutkimus on valtaosin hyödyntänyt kahta testausympäristöä, H&S ja SMART, algoritmien kokeelliseen vertailuun suoritusaikoja mittaamalla. Vaikka merkkijonohaku on kattavasti tutkittu ongelma, testausympäristöt ovat vähemmän ymmärretty alue. Tässä diplomityössä instrumentoitiin testausympäristöt kutsumalla Performance Application Programming Interface (PAPI) -funktioita testausympäristöjen sisältä. PAPI monitoroi prosessorin toiminnallisuuksia laitteistotehokkuuslaskureilla, joiden avulla voidaan arvioida testausympäristöjen aiheuttamia häiriöitä merkkijonohakualgoritmien ajojen aikana. Työssä ajetut kokeet testausympäristöillä valottivat kahta häiriötä. Ensinnäkin H&S:ssä ja hieman SMART:issa merkkijonohakualgoritmit lukivat tekstiä välimuistista eikä keskusmuistista. Häiriön vaikutus algoritmien suoritusaikoihin näytti kuitenkin olevan vähäpätöinen ja välimuistin laitteistopohjainen esihaku mitätöi sen. Toiseksi SMART:issa jokaisen muistisivun ensimmäinen muistiviittaus aiheutti sivutusvirheen kussakin merkkijonohakualgoritmin ajossa. Sivutusvirheet keskeyttivät algoritmien ajon jatkuvasti, mikä kasvatti mitattuja suoritusaikoja merkittävästi. Äärimmäisissä tapauksissa suoritusajat kasvoivat melkein kymmenkertaisiksi. Lopuksi työssä esitetään optimointi merkkivertailu-pohjaisille merkkijonohakualgoritmeille, missä verrataan merkkijonohahmon ja tekstin välisiä q-grammeja. Vertailun perusteella päätellään, pitääkö hahmon mahdollinen esiintymä verifioida täsmäyssilmukassa vai voidaanko hahmoa siirtää oikealle ilman verifiointia. Optimoinnin tehokkuus osoitettiin kokeilla, joiden perusteella optimointi on erittäin tehokas pienillä aakkostoilla.Description
Supervisor
Tarhio, JormaThesis advisor
Tarhio, JormaKeywords
exact string matching, cache, hardware performance monitoring, page fault, q-gram