Optimization of a Search Function in a Large Software Product

Abstract

In this work we studied the Building information modelling software Tekla Structures. Our goal was to improve the performance of a specific functionality in the case study software: the filtering of model objects. Filters are a set of rules customizable by the user. By applying filters user is able to filter model objects by their properties, for example by name, length or construction date. Filters are used in many key processes in Tekla Structures such as drawing creation, selection and how objects are visualized.

We started by investigating the current implementation of filtering and where the performance could be improved. In our methods we are partly restricted by the large size of the software product, which makes high level changes difficult to implement. After investigation we were able to find more efficient algorithms and data structures to significantly improve the equation processing related to filtering. We found significant differences in the calculation times of properties, which lead us to investigate ways to optimize the evaluation order of the rules in the filter. Finding the optimal evaluation plan is in its general form a NP-hard combinatorial optimization problem.

We then reimplemented the equation processing related to filtering. This included implementation of several algorithms to optimize the evaluation order of rules in the filter. These algorithms included a full exhaustive search of all evaluation plans and computationally less expensive methods such as an algorithm based on boolean differential algebra. The performance improvement was then calculated with user created structural models and in more controlled simulations. The reimplementation of the equation processing alone improved the performance of the filtering by more than 50% in our tests without the optimization of the evaluation order. The evaluation order optimization also gave significant improvement to the performance, which is more apparent in filters with a large number of rules. All the implemented algorithms were able to improve the performance and the computationally less expensive methods were almost as effective as the full exhaustive search of all evaluation plans.

Tässä työssä tutkittiin rakennusten mallinnukseen käytettävää Tekla Structures -ohjelmistoa. Tavoitteena oli parantaa mallikappaleiden suodatukseen liittyvää toimintoa. Suodatin Tekla Structures -ohjelmistossa koostuu säännöistä, joiden perusteella voi rajoittaa mallikappaleiden joukkoa. Rajoitus tapahtuu kappaleiden ominaisuuksien kuten nimen, pituuden tai rakennuspäivämäärän perusteella. Suodattimia käytetään useassa eri tärkeässä prosessissa, kuten esimerkiksi piirustusten luonnissa ja kappaleiden visualisoinnissa kolmiulotteisissa malleissa.

Aluksi tutustuttiin suodattimen nykyiseen toteutukseen. Tehokkuusanalyysin perusteella löydettiin algoritmeja ja tietorakenteita, joiden perusteella tehokkuutta voitiin parantaa. Ohjelmiston laajamittaisessa muokkaamisessa on haasteena sen suuri koko, monia miljoonia koodirivejä.

Mallikappaleiden ominaisuuksien laskenta-ajoissa havaittiin isoa vaihtelua. Tämän vuoksi tutkimme voisiko suodattimen sääntöjen laskujärjestystä optimoimalla vaikuttaa sen suoritusaikaan. Optimaalisen laskujärjestyksen löytäminen on NP-täydellinen optimointiongelma. Tutkimme vastaaviin ongelmiin, kuten tietokantojen taulujen yhdistämisjärjestykseen käytettyjä algoritmeja.

Tutkimusten perusteella päätimme toteuttaa suodattimeen liittyvän yhtälönratkaisijan uudelleen. Toteutimme algoritmeja, joilla pystyimme vaikuttamaan sääntöjen suoritusjärjestykseen. Toteutettuja algoritmeja olivat yksinkertainen säännön hintaan perustuva uudelleenjärjestys, boolean differentiaalialgebraan perustuva menetelmä sekä kaikki mahdolliset suoritusjärjestykset läpikäyvä haku. Uuden yhtälönratkaisijan tehokkuutta mitattiin testeissä, joita tehtiin aidoilla asiakasmalleilla sekä simuloidulla datalla. Toteutettujen muutosten myötä suodattimen suoritusaika pieneni yli 50 % testeissä jo ilman suoritusjärjestyksen optimointia. Suoritusjärjestyksen optimointi paransi suoritusaikaa merkittävästi kaikilla toteutetuilla algoritmeilla. Laskennallisesti vähemmän vaativat algoritmit olivat lähes yhtä tehokkaita kuin kaikki mahdolliset suoritusjärjestykset läpikäyvä haku.