Compilation of data structures into JavaScript: Optimizing memory usage

Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis

Authors

Date

2017-12-11

Department

Major/Subject

Computer Science

Mcode

SCI3042

Degree programme

Master’s Programme in Computer, Communication and Information Sciences

Language

en

Pages

47 + 6

Series

Abstract

This thesis studies memory usage of data structures. When storing data, there is some data structure memory overhead. There are multiple methods to decrease the memory overhead. Some of the methods come at the expense of performance, i.e. how fast the data can be accessed. The challenge is that manually coding highly optimized JavaScript code would be hard to do. This is because JavaScript engines are not as optimized as programming languages where the code is compiled. Therefore in the work I focus on how to compile an optimized data structure into JavaScript code. The problem was how to store data in as small space as possible. The motivation for this was to improve the memory usage of the frontend of an existing application, where a lot of data is stored in the browser memory. The solution should also be compatible with the existing data structure that was used in the application backend. My focus was on the memory usage optimizations because that would benefit both the existing backend data structure and the new frontend data structure. As a result, I implemented a hash map data structure with Rust programming language for storing the data. I compiled the Rust hash map implementation into JavaScript with Emscripten compiler. I did multiple experimentations that indicated that the hash map implementation was working properly. I also did experimentations where I compared the hash map memory usage to manually written JavaScript code memory usage. Based on the results of these experimentations I made several optimizations to the hash map implementation and were able to compress the data a significant amount for the purposes of our application.

Tässä diplomityössä tutkitaan tietorakenteiden muistinkäyttöä. Kun dataa tallennetaan tietorakenteeseen niin siihen sisältyy muistin hallintatietoa. Tämän hallintatiedon vähentämiseen on olemassa useita eri menetelmiä. Jotkut näistä menetelmistä kuitenkin heikentävät suorituskykyä, eli sitä kuinka nopeasti dataa voidaan lukea. Haasteena on se, että hyvin optimoidun JavaScript-koodin kirjoittaminen manuaalisesti olisi hyvin vaikeaa. Tämä johtuu siitä, että JavaScript-moottorit eivät ole yhtä optimoituja kuin ohjelmointikielet, joissa koodi ensin käännetään. Tämän takia keskityn työssä siihen kuinka optimoitu tietorakenne käännetään JavaScript-koodiksi. Ongelma oli kuinka tallentaa dataa mahdollisimman pieneen tilaan. Motivaatio tälle oli parantaa muistinkäyttöä olemassaolevalle sovellukselle, joka tallentaa paljon dataa selaimen muistiin. Ratkaisun pitäisi myös olla yhteensopiva verkkosovelluksen palvelukerroksessa käytettävän olemassaolevan tietorakenteen kanssa. Keskityin muistinkäytön optimointiin, koska se hyödyttäisi sekä olemassaolevaa palvelukerroksen tietorakennetta, sekä uutta JavaScript-tietorakennetta. Työn tuloksena toteutin hajautustaulutietorakenteen Rust-ohjelmointikielellä tiedon tallentamiseen. Käänsin Rust hajautustaulutoteutuksen JavaScript-koodiksi Emscripten-kääntäjällä. Tein useita kokeita, jotka osoittivat että hajautustaulutoteutus toimi oikein. Tein myös kokeita, joissa vertasin hajautustaulutoteutuksen muistinkäyttöä manuaalisesti kirjoitetun JavaScript-koodin muistinkäyttöön. Näiden kokeiden tulosten perusteella tein useita optimointeja hajautustaulutoteutukseen ja pystyin pakkaamaan dataa huomattavan määrän meidän sovelluksen tarkoitukseen.

Description

Supervisor

Hirvisalo, Vesa

Thesis advisor

Korri, Santeri

Keywords

emscripten, rust, JavaScript, compiler, hash map, memory

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-201712187943

Collections

[dipl] Perustieteiden korkeakoulu / SCI