Java bytecode instruction usage counting with algator

Tomaž Dobravec

Java bytecode instruction usage counting with algator

Číslo: 4/2018
Periodikum: Acta Electrotechnica et Informatica
DOI: 10.15546/aeei-2018-0028

Klíčová slova: Algorithm evaluation, Java bytecode counting, time-complexity prediction

Pro získání musíte mít účet v Citace PRO.

Přečíst po přihlášení

Anotace: Development of algorithms for solving various kinds of computer related problems consists of several consecutive and possibly repetitive phases. The final and very important step in this process is to implement the developed algorithm in a selected programming language, to test its behavior on some real-world test cases and to compare the results with the results of other algorithms. This evaluation can be done by comparing different execution indicators among which the time consumption is usually considered to be the most relevant. On the other hand, timing the algorithms in practice is very difficult since it is hard to ensure a fair and reproducible environment in which algorithm’s implementations can be compared. To overcome this barrier, we introduce a system called ALGATOR that was developed to facilitate the algorithm evaluation process. Besides the time complexity and the project-specific indicators, ALGATOR also measures the counters of Java code and Java bytecode usage. The measurement of the former is implemented by using special tags that are to be inserted in the appropriate lines of Java code while the measurement of the latest is enabled by using an adapted Java virtual machine, which counts the Java bytecode usage and reports the statistics. By using this counters new timingindependent criteria for algorithm assessment can be derived. In this paper we present some basic concepts of the ALGATOR system and give some examples of how to use the system in practice. We show the distribution of the usage of Java bytecode instruction for the sorting problem and the usage of the Java bytecode indicators in the time-complexity prediction for the matrix multiplication algorithm. The examples presented in this article show how the classic time measurement methods can be replaced by measuring some other more reliable indicators, and how this measurements can help to asses the quality of our algorithms.