Browsing by Subject "C++"
Now showing items 1-3 of 3
-
(2024)In this thesis we study how to implement the one-dimensional fast Fourier transform (FFT) as a computer program in such a way that it works fast on inputs of all sizes. First we walk through the mathematical theory behind the continuous and the discrete Fourier transform (DFT), and study the motivation behind them. We explore both the one-dimensional and the multi-dimensional versions of the DFT. We also study the discrete cosine transform (DCT) and explore its differences to the Fourier transform. After that, we explore various known methods for implementing the fast Fourier transform. We focus especially on the Cooley-Tukey algorithm and its different forms in enough detail, that one can understand both how it works and how it was conceived. We also explore Rader’s and Bluestein’s FFT algorithms. After the theory we implement the DFT and the FFTs using the C++ programming language. We also devise and implement a combined algorithm, which seeks to provide the fastest possible transformation by choosing the optimal combination of algorithms in each case. We use C++20, which is the most recent standard version of C++ at the time of writing. We analyze the speed of the implemented methods, comparing them against each others and also compared to a famous FFT library, FFTW. In addition, we analyze the numeric accuracy of the implementations. Then we analyze the accuracy and applicability of the analysis methods and study the shortcomings and possible approaches for improving the implementations. We also present a simple example application of FFT, where the program attempts to identify the vowel sounds present in a voice sample. The purpose of this thesis is to offer the reader a clear example implementation of all the presented transforms and to thoroughly explore their limitations, weaknesses and strengths. For best value, the reader is expected to understand the basics of calculus and the basics of complex numbers. Especially the sum notation, ∑, and Euler’s formula are vital for understanding the mathematical theory. The computer source code is designed in such way that the reader does not need to know the details of the C++20 standard, or indeed even the C++ language, but experience in C programming will help.
-
(2021)Bit vectors have many applications within succinct data structures, compression and bioinformatics among others. Any improvements in bit vector performance translates to improvements in the applications. In this thesis we focus on dynamic bit vector performance. Fully dynamic succinct bit vectors enable other dynamic succinct data structures, for example dynamic compressed strings. We briefly discuss the theory of bit vectors and the current state of research related to static and dynamic bit vectors. The main focus of the thesis is on our research into improving the dynamic bit vector implementation in the DYNAMIC C++ library (Prezza, 2017). Our main contribution is the inclusion of buffering to speed up insertions and deletions while not negatively impacting non-modifying operations. In addition, we optimized some of the code in the DYNAMIC library and experimented with vectorizing some of the access operations. Our code optimizations yield a substantial improvement to insertion and deletion performance. Our buffering implementation speeds up insertions and deletions significantly, with negligible impact to other operations or space efficiency. Our implementation acts as proof-of-concept for buffering and suggests that future research into more advanced buffering is likely to increase performance. Finally, our testing indicates that using vectorized instructions in the AVX2 and AVX512 microarchitecture extensions is beneficial in at least some cases and should be researched further. Our implementation available at https://github.com/saskeli/DYNAMIC should only be considered a proof-of-concept as there are known bugs in some of the operations that are not extensively tested.
-
(2020)Programs today consist of several parts made in different languages. Different languages are used because of the different benefits they offer. In the same program, languages can be mixed by embedding an interpreter of a language into a program implemented in another language, so that the interpreter allows one language to run programs made in another. In order for the languages to work together, they need to be built into an interface that allows them to communicate. Languages are already different in their purpose, so various compatibility issues raise in the implementation of the interface between them. In addition, interpreters for multiple embeddable languages are designed for single-threaded execution only, so using them in a multi-threaded program can compromise the efficiency or integrity of the program. In this work, we look for the problems of language interface and multi-threading in interpreter embedding and the solutions used for them with the help of the literature. As a practical work, we integrate a Lua interpreter into a multithreaded MMORPG server program programmed in C++. The use case of the embedded language sets practical limits on execution speed, so maintaining concurrency is paramount. In practical work, many isolated instances of the embedded language interpreter are created, which can be performed in parallel with different threads. Due to the use case, the instances have to share information with each other, which takes place through the serialization of the information. The applied part of the work and the solutions used in it are evaluated by simulating the structure and execution of the server program. We compare a single-threaded embedding of the interpreter to a parallel implementation and find that in the test situation we achieve the desired near-ideal execution speeds with the help of the parallel implementation. In addition to acceleration, we find that the increase in memory consumption is small relative to the benefits obtained.
Now showing items 1-3 of 3