日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

Cooperative Memory Management of a
JavaScript Virtual Machine with Datatypebased Hardware Memory Deduplication
Zihan Li, Tomoharu Ugawa, Ryota Shioya
Recently, a memory deduplication hardware design called BCD was proposed. BCD leverages the similarityof the bit patterns between cache lines. Later, another improvement, allocating a single object aligned at
the head of each cache line and ﬁlling the remaining part with zero, achieves better deduplication for object
data. However, more consumption of virtual address space is introduced, resulting in a larger translationtable for BCD mapping from addresses to real location in memory where deduplicated data is stored. In thispaper, we allocate multiple small objects of the same type in a single cache line to reduce the consumptionof virtual addresses. Furthermore, bit patterns of cache lines holding objects of the same types are expected
to be similar because all objects in the same cache line are of the same type. We implemented this in a
JavaScript virtual machine, eJSVM, and evaluated it. Furthermore, we conﬁrmed that our proposal reduced
memory consumption by using a simulator of the deduplication hardware.

1 Introduction
Nowadays, to improve the eﬃciency of programming in embedded systems, people are seeking toapply high-level languages such as JavaScript instead of traditional C or C++. Some JavaScript engines oriented to embedded systems such as eJS [1],QuickJS [2] are proposed to facilitate embedded
system programming. Since embedded systems
provide limited memory space, reducing the memory footprint is important.
To this end, Ri et al. proposed AOBD, a codesign of memory compression hardware and virtual machines (VMs) of object-oriented managed
languages [3]. More speciﬁcally, AOBD uses baseand compressed diﬀerence (BCD) deduplication [4].
It is a hardware design that compresses data incache memory when they are written back to main
memory. Because BCD decompresses data when it
is loaded to cache, or cache ﬁll, BCD is transparent to software. In the rest of this paper, we calla cache line-sized memory block in virtual memory
space, which is subject to compression, simply a
Zihan Li, 鵜川 始陽, 塩谷 亮太, 東京大学情報理工学系
研究科, Graduate School of Information Science andTechnology, The University of Tokyo.

cache line.
BCD compresses memory by eliminating duplication from similar cache lines. It stores in memory
the contents of some representative cache lines, andthe diﬀerences between other cache lines and theirsimilar representatives. Thus, a high compression
ratio is achieved when the bit patterns of cache lines
are categorized into a small number of categories,
and when bit patters of cache lines in the same category are similar.
Regarding to the VM side, AOBD allocates objects at aligned addresses to the cache line size. Assuming that objects of the same type are likely tohave similar bit patterns in the same ﬁeld, whichis stored at the same oﬀset from the head of objects, this aligned allocation avoids divergence ofbit patterns. Furthermore AOBD categorizes cachelines based on the types of the objects in the cachelines. Ri et al. implemented AOBD in a JavaScript
VM for embedded systems, eJSVM [1], which isequipped with the optimization that represents objects of JavaScript as if they have static types.
However, aligned allocation costs large virtual
memory space. Aligned allocation means that itallocates at least one cache line for each object,and it does not use the remaining area of cachelines. In BCD, large virtual memory space de-creases the end-to-end compression ratio because
BCD has a translation table mapping from cacheline-sized memory blocks in virtual memory to thelocation of its compressed data, and the table also
consumes main memory.
We propose a technique to place multiple objects
in a single cache lines while avoiding the divergenceof the bit patterns. This reduces the consumptionof virtual memory space, which ﬁnally contributes
to a better compression ratio by reducing the sizeof the translation table.
The challenge is to avoid the divergence of the
bit patterns introduced by the second object in acache lines. We solve this problem by restricting
each cache line to contain only the same type ofobjects. We implemented this idea in eJSVM. In
the implementation, we managed unused areas ofcache lines using segregated freelists. As a result of
our evaluation, the proposal improves the compression ratio by 9.0% on average and by up to 13.6%
compared to AOBD.

2 Hardware Deduplication
2. 1 BCD
BCD deduplication [4] is a hardware design thateliminates duplicated bits in cache lines when datain cache memory is written back to main memory (in the rest of this paper, we denote memory
for main memory). It is based on the observationthat if two cache lines share the same bit pattern
in certain bits, then the remaining part of thesecache lines tend to have similar bit patterns. BCD
calls the value in certain bits signature. BCD leverages this similarity to compress data; it stores only
the diﬀerences in memory. The more bits that are
the same in the remaining part, the fewer bits areneeded to encode them. Therefore, the compression
ratio is improved.
As Fig. 1 shows, BCD provides a new layer ofaddresses called the OS physical address (OSPA)to the memory system. OSPA is between the virtual memory address and the hardware memory
address. As a result, when data is stored in memory, the OS is responsible for converting the virtual memory address to the OSPA, and BCD is responsible for converting the OSPA to the hardware
memory address. BCD deduplicates when BCD
converts addresses.

BCD uses the following four data structures tomanage hardware memory.
• translation table• base array• diﬀerence array• overﬂow region
The translation table is used to record the conversion from OSPAs to hardware memory addresses.
Each table entry translates from an OSPA to a
hardware memory address. The base array is ahash table to store uncompressed contents of representative cache lines. The key for the hash table isthe signature of the cache line. The diﬀerence arrayis a hash table to store compressed contents. As forthe overﬂow region, if the base or diﬀerence arrayis full for a certain signature, then the new uncompressed or compressed cache line data is stored in
the overﬂow region.
When a cache line is evicted, BCD compresses
the data in the following steps.
1. BCD extracts the signature of cache line to beevicted. The signature is computed by combining the leading 2 bytes of every 8-byte unit in
one cache line, as Fig. 2 shows.
2. BCD looks up the base array by the signature. If a base entry with the same signature
is not found, data in the evicted cache line arestored to a new base entry in the base array.
3. If a base entry is found, the remaining data
(every ending 6 bytes of every 8-byte unit, seeFig. 3) are compared. If the base entry has exactly the same data as that of the evicted cacheline, the base line entry is shared.
4. Otherwise, BCD computes the diﬀerence between the data from the evicted cache line andthat of the base entry by bit-wise xor. BCD
compresses it with the LZC compression algorithm and stores in the diﬀerence array. Again,
if the diﬀerence array already has the exactly
entry, the entry is shared.
BCD works well if, for cache lines with the same
signature, the remaining parts have similar bit patterns.
2. 2 AOBD
In object-oriented managed languages, all thedata is represented by objects. Ri et al. proposed
AOBD [3], a combination of an improved BCD anda JavaScript VM that achieves a high compression

BCD

Translation Table
Entry

VirtualMemoryAddress

OS pysicaladdress(OSPA)

Operation
SystemDRAM
Address

Entry

...

Translation entry

Entry

Fig. 1

2B

6B

2B 6B

...
...

Fig. 2BCD Signature

Address Translationcache line size
2B 6B

cache line 0 TA I

2B
Fig. 3

6B

2B 6B

...
...

P

cache line 1 TB D D P
cache line 2 TC P

2B 6B

Remaining Part For Compression

ratio for the heap of the JavaScript VM. AOBD isbased on the observation that objects of the same
type have values of the same low level type, suchas int, double, or a pointer, in the same ﬁelds, andthe values of the same low level type tend to have
similar bit patterns.
To leverage the similarity of bit patterns between
objects of the same type, AOBD allocates objects
at the head of cache lines as shown in Fig. 4. Thisﬁgure shows six cache lines, each of which has an
object of type TA , TB , or TC . The dotted boxes
with TA , TB , TC are ﬁelds containing the object
types. The symbols in other dotted boxes, I, D,
and P, represent the low level types of the ﬁelds.
Owning to aligned allocation, ﬁelds with the same
low level type of objects of the same type are arranged at the same oﬀset to the head of their cachelines. For example, each of cache lines 0, 3, and 5
has an object of type TA . These cache lines have
low level type I in the second word and P in thethird word. As a result, cache lines with objectsof the same type are likely to have similar bit patterns.
Furthermore, AOBD ﬁlls the remaining area of
each cache line with zero to avoid diversity of bit
patterns. Cache lines with objects of the same typehave zero-ﬁlled areas at the same oﬀset to the head

000...

cache line 3 TA I

P

000...

000...

P

000...

cache line 4 TB D D P

Pcache line 5 TA I

000...

P

000...

objectFig. 4

Object Allocation in AOBD

of the cache lines. Thus, when BCD deduplicates,
the diﬀerence of these zero-ﬁlled areas is computed
and the diﬀerence is compressed to virtually zerobit. However, these zero-ﬁlled areas of cache lines
registered to the base array would consume memory. To avoid this waste, AOBD has an option tocompress trailing zero bits in the base array.
Finally, AOBD uses the value of the type information ﬁeld of an object as the signature of cacheline containing the object. As a result, signatures ofcache lines with similar bit patterns are computed
to the same value.

3 Allocate the Same Type of Objects
within a Single Cache Line
Although AOBD improves the compression ratio,
the cache line alignment enlarges the size of translation table. Since one cache line can hold only one
object regardless of its size due to cache line alignment, each cache line consumes one virtual memory
address in Fig. 1. Therefore, if we want to store two
objects whose sizes are 32 bytes and the size of acache line is 64 bytes, by cache line alignment, weconsume two virtual memory addresses, each one

AOBD
Cache line 1 Type A

00...00

Cache line 2 Type A

00...00

Cache line 3 Type A

00...00

Cache line 1 Type A Type A Type A Type A

Cache line 4 Type A

00...00

Cache line 2

Cache line 5

Type B

00...00

Cache line 6

Type B

00...00

Fig. 5

ProposalType B

Type B

00...00

Multiple Same Type of Objects in Single Cache Lineis for a cache line. However, originally, both objects can be stored in one cache line, and only one
memory address is consumed. As a result, AOBD
consumes more virtual memory addresses. Fig. 1
shows that each virtual memory address consumed
is converted to an OSPA. For each OSPA, there isa corresponding entry in translation table to record
the conversion from the OSPA to a hardware memory address. Therefore, the size of translation table
is increased.
To solve the problem above, we propose the allocation of the same type of small objects within
a single cache line. Here, the ‘small object‘ meansthat its size is less than half of one cache line size.
The main idea to reduce the consumption of virtual memory address in AOBD as well as keep thesignature valid for memory compression is to allocate multiple same type of small objects into single
cache line, as Fig. 5 shows. To do that, all thesignature is captured from the ﬁrst object. The
way to calculate the signature is the same as thatfor AOBD. The signature is computed from specialﬁelds that contain the type information in the ﬁrst
object. Objects of the same type share the same
signature. Therefore, we check only the ﬁrst object. Since one cache line holds only the same typeof objects sharing the same signature and the same
signatures indicate similar bit patterns in the remaining part of the cache lines, therefore, the signature is valid for memory compression and deduplication. In addition, we apply the following strategies to avoid introducing more bit patterns for certain cache lines that contain the same types of objects. In AOBD, zero ﬁlling is applied to all unused
space in the heap. However, here, we only do zeroﬁlling if the whole cache line in the heap becomes

unused. As long as at least one object in a cacheline is alive after garbage collection (GC), we do
not ﬁll the block with zero for the unused part init.

4 Implementation to eJSVM
4. 1 eJSVM
We implemented our proposal in eJSVM as Ri
et al. implemented AOBD in eJSVM. eJSVM is a
JavaScript virtual machine (VM) for embedded systems. Because JavaScript is a dynamic language,
objects do not have types, but properties are dynamically added to objects. Thus, AOBD does notwork for a naive implementation of JavaScript VM.
However, eJSVM uses optimizations to deal with
objects as if they have types: hidden classes, pretransitioning of the hidden classes, and in-object
properties to implement JavaScript objects [5]. In
this section, we describe the eJSVM equipped with
AOBD.
4. 1. 1 JavaScript Objects
The layout information of an object is recorded
in a separate meta-object, called hidden class. The
hidden class is shared with objects with the samelayout. Because JavaScript object may get a newproperty dynamically, the layout may change after
the object is created. eJSVM feedbacks this change
to the allocation site of the object (the location in
the JavaScript program that created the object),so that hereafter objects are created with the new
layout.
Figure 6 shows an example of the implementation of a JavaScript object. It comprises two parts.
One is a JSObject data structure and the other isa hidden class. The hidden class is a mapping fromthe property names to the indexes of them in thestorage. The JSObject has a pointer to the hidden

[0]foo’s value[1] bar’s value

name index
foo
0
bar
1
hidden class

JSObjectFig. 6

JSObjectname index
foo
0
bar
1
[0]

foo’s value

baz2

hidden class
JSObject[1] bar’s value[2] baz’s value
property array

Fig. 7

Property Overﬂow

class and the storage for property values. For example, the index of the property bar is one according to the hidden class. Thus, its value is stored in
the third word of the JSObject. Note that the ﬁrst
word of the JSObject is used to hold the pointer tothe hidden class.
The size of JSObjects diﬀer from object to object
depending on the expected number of properties,
which allocation site knows. When an unexpected
property is added to a JavaScript object, however,the JSObject cannot be expanded. In such a case,an external property array is introduced to holdthe overﬂowed properties, and the last slot of the
JSObject is replaced with the pointer to the property array. Figure 7 shows the object shown in Figure 6 after a property baz is added. The pointerto the hidden class is updated, and a property array is created to hold the overﬂowed property baz
and the property that used the last slot, which isoverwritten by the pointer to the property array.
4. 1. 2 Non-JSObject Data
The memory manager of eJSVM deals with
JSObject, hidden classes, and property arrays as
separate data. In addition to hidden classes andproperty arrays, eJSVM uses several non-JSObject

data: boxed primitives, property storages and VM
internal data structures.
JavaScript’s numbers are double-precision ﬂoating numbers, which requires 64 bits. To handle alltype of data uniformly in one word, eJSVM boxes
numbers except for small signed integers. Strings
are also boxed. When such a primitive data is created, eJSVM allocates a chunk of memory to holdthe data, and uses the pointer to the memory chunkas the primitive value.
In addition to the property arrays for overﬂowed
properties, JavaScript’s Array objects have separate property arrays. In eJSVM, Array objects’
properties of integer indexes, which are technicallystring property names representing the integers, arestored to the array for quick access.
VM internal data structure including hiddenclasses is also allocated as separate data chunks.
However, the number of them is small.
4. 1. 3 Identifying Data Type and Size
Each data of eJSVM has a header word that contains type and size ﬁelds. The type ﬁeld identiﬁes
the type of the data, i.e., if it is JSObject or not,and if not, the type of non-JSObject data. Becausesome data structures, such as JSObjects and property arrays, have not ﬁxed sizes, the header word
also describes the size of the data.
Figure 8 shows a JSObject, a property array, anda boxed number with the header. The type ﬁelds ofthe headers describe corresponding types. The size
ﬁeld for the JSObject with n properties is n + 1,
that for the property array with m properties is m,
and that for the boxed number is one.
4. 1. 4 Signature of Cache LineFor JSObject data, AOBD uses the pointer tothe hidden class as the signature of cache line that
holds the JSObject. Fig. 9 shows the algorithm tocompute the signature for the cache line whose address is cache line addr. To distinguish JSObject
data from non-JSObject data, AOBD checks thevalue of type ﬁeld in the header. For non-JSObject
data, AOBD uses the combination of the type andsize ﬁelds as the signature of the cache line.
For the second or following cache lines of a large
object, which is larger than the cache line size, there
are no bits describing type information. AOBD
does not handle these cache lines correctly; it parses
the ﬁrst word of a cache line as if it is a header word
even for the second or the following cache lines, andheaderheader[0]

hidden class
[0]

size

property
valuesdouble value
property
values[n]Fig. 8type = value arraysize = m words

Computing Signature

headernext free chunk
000...

000...

cache line size

cache line size(a) free chunk
000...

(b) cache line-size memory block in use

Fig. 10type = boxed number
size = 1 wordType and Size Fields of Header

compute_signature(cache_line_addr):
header = *(HeaderType*) cache_line_addr;
if header.type == JS_OBJECT:
obj = (JSObject *) cache_line_addr;
return obj->hidden_class;else:
return (header.type, header.size)

objectsize[m]type = JSObject
size = n + 1 words

Fig. 9headerFree chunk and memory block in use

if the false type ﬁeld indicates that it is a JSObject,
it uses the combination of the false type ﬁeld andthe second word, which is a false hidden class ﬁeld,
as the signature.
4. 1. 5 Memory Management
AOBD uses a modiﬁed version of mark-sweep
GC with a ﬁrst-ﬁt free-list memory allocator implemented in eJSVM [6]. Because AOBD allocates asingle object in each cache line, the memory manager manages memory at a granule of the cacheline size. To avoid unnecessary variety of cachelines, the modiﬁed memory manager ﬁlls the unused area of both allocated and free memory chunkswith zero. Furthermore, the modiﬁed mark-sweep
GC uses bitmap marking.
More speciﬁcally, elements of the free list are
one or more consecutive cache lines. Figure 10 (a)shows a free chunk of two cache lines. The ﬁrst
block has a header describing the size of this freechunk and a pointer to the next free chunk. The
remaining area and following cache lines are ﬁlledwith zero.
When eJSVM allocates memory of a certain size,
it rounds up the size to the multiple of the cacheline size. For a small object that ﬁts in a single
cache line, an entire single cache line is allocatedfor the object. The object is placed at the headof the cache line as shown in Figure 10 (b). The
remaining area of the cache line is ﬁlled with zero.
The mark-sweep collector has a bitmap outsideof the heap. Each bit of the bitmap corresponds
to a cache line. When the mark phase ﬁnds a live
object, it sets a bit corresponding to the cache line
where the live object resides.
4. 2 Implementation
Our implementation consists of three parts, freelists to manage partially used block, a two-layer
memory allocator and modiﬁcation to original
mark sweep GC [6] in eJSVM.
4. 2. 1 Free lists for partially used block
management
Our proposal allocates multiple small objects ofthe same type to a single cache line in the heap.
However, the heap size is not inﬁnitely large. To
eﬃciently use the limited heap, memory manager
collects spaces occupied by objects that are not notneeded for application running to recycle spaces for
future allocation, which is called garbage collectionHiddenclass
Fig. 11

Head of List

Free List Head for JSObject

Head of List ... Head of List

MemoryFig. 12

Free List Head for Non-JSObject(GC). The objects are not needed for application
running during GC is called ’dead objects’ and in
opposite, the objects are still needed is called ’live
object’. As a result, as Fig. 13 and Fig. 14 show,
many partially used blocks in which only some slots
are ﬁlled with live objects and can still hold moreobjects of the same type are generated after each
GC cycle. We call the unused parts in a partiallyused block ’free slots’. To manage such partiallyused blocks with free slots, we use a free list foreach signature of cache line, which is the pointer tohidden class for JSObject and the combination of
the type and size ﬁeld for non-JSObject.
Since the signatures for JSObject and NonJSObject consist of diﬀerent ﬁelds in the objects,
we need a diﬀerent way to manage the free lists.
For JSObject, we put the head of such a free list
into hidden class objects, as shown in Fig. 11. In
this way, to ﬁnd the free list to allocate a free slot
in a partially used block for JSObject, we can access the hidden class reference in the JSObject toﬁnd the head of the free list. For Non-JSObject, we
use a table to manage such free list head, as shownin Fig. 12. The index of such a table is computedby the combination of type and size ﬁeld in small
Non-JSObject headers, so we can also access thehead from a Non-JSObject. When a new unused
slot is added to a free list, the pointer of the slot isstored in its previous element in the free list.
Fig. 13 and Fig. 14 show what such free lists look
like for JSObject and Non-JSObject. The reference
to the next element in the free list, an free slot, isstored to a ﬁeld in the ﬁrst dead object in the freeslot. However, the bit patterns between the reference value and the value of the ﬁeld overwritten by

the referent may be diﬀerent. Therefore, some differences in the bit pattern are introduced into theblock . Therefore, to both record the reference tothe next unused slot and make as little modiﬁcation
to the dead object as possible, in our implementation, for Non-JSObject, as Fig. 14 shows, we makeone unused slot contain more than one dead object
by combining the adjacent dead objects for a larger
slot. So, we create one element in the free list with
only one modiﬁcation to a dead object ﬁeld insteadof multiple elements with multiple modiﬁcations,which introduces more bit patterns.
As a result, there are two kinds of free lists tomanage the free space in our memory manager; one
is for partially used block for JSObject and NonJSObject, the other is for completely unused blockwith cache line size. We call the former ’slot freelists’ and the latter ’block free lists’.
4. 2. 2 Allocator
Here we introduce how the allocator works to allocate those partially used blocks managed by the freelists above. To implement our proposal, we applied
two allocators, one is ’free block allocator’ which
allocates blocks whose sizes are integral multiplication of one cache line size, the other is ’partiallyused block allocator’ for small objects.
When allocation for small object starts, depending on its type and size information, a proper allocator is used. If an object is a small JSObject, thenﬁrst, a free list for such type of object is checked.
We can access the head of such a free list by following the hidden class reference in JSObject andcheck that hidden class to access the free list head,as shown in Fig 11. If the free list is not empty, thenwe allocate the space occupied by the head of freelist and set the next element in the free list as thehead. This is the work of the partially used block
allocator. Otherwise, if the free list is empty, thenwe use free block allocator to allocate a block withcache line size and record the unused slots in thatblock to the corresponding free list so that during
the next allocation for the same type of small object, we can use partially used block allocator for
it.
Fig. 15 shows the transfer of states of one cacheline that holds at most two small objects of thesame type. At state 1, the block is unallocated,managed by free block allocator, and ﬁlled withzero. Then when an allocation starts and free blockFree Slot

Head of List

Free Slot
Dead JSObject Object

Free Slot0

Dead JSObject
ObjectHeader8
16
24

Fig. 13

Free List for JSObject

Free Slot

Free Slot

Head of List

Referecence to ahidden class
Reference to thenext Node

Free Slot

Free Slot

Dead Non-JSObject Object

Free Slot0

Dead NonJSObject Object 1

8Dead NonJSObject Object 2

16

Header
Reference to thenext Node

Dead NonJSObject Object 3

Fig. 14

Free List for Non-JSObject

1

2

3

4

5
A Live Object

Allocation

A Dead Object

Deallocation during GC

UnallocatedFig. 15

States of a block

allocator is used, the block is allocated to a small
object, as state 2 shows. Now, the remaining unallocated part is managed by partially used block allocator. Then, after one more allocation, the blockis allocated with two objects and no more room foranother object with the same type. After GC, depending on the whether those two objects in theblock are live or not, the state changes. If there
is no object alive, then the block goes to state 1,
the block is ﬁlled with zero and managed by theblock allocator again. Otherwise, if only one object is alive, then the block goes to state 4 or 5, theslot occupied by a dead object and not zero ﬁlled ismanaged by partially used block allocator, and thenext time an allocation of the same type of object
occurs, the same slot is allocated, and the block
goes back to state 3.
However, if the size of allocated space is larger
than the size of a small object (half of a cache linesize), then we round up the requested size to multiple times one cache line size and use only free block
allocator to allocate those space.
In short, if the allocation is for small objects, thenwe use the partially used block allocator for priority. When free slots in partially used block run out,

Free Slot

Free Slot
Head of List
Fig. 16First Slot
(Free)First Slot (Free)

free block allocator is used and newly generated
partially used block is allocated during the next allocation for small objects with the same type. Otherwise, if the allocation is not for small objects, theallocation is done by cache line allocator.
4. 2. 3 Modiﬁcation to mark-sweep GC
Since we allocate a partially used block by ourallocator, we need to recycle those blocks and rebuild free lists at appropriate time. And such work
is ﬁnished during mark-sweep GC. Mark sweep GC
is a non-moving GC, it marks all the live objects
whose pointers are held by other objects or data
structures during mark phase, then it sweeps freespace during sweep phase, which means it scans all
the objects in the heap one by one, combines all
the adjacent small slots occupied by dead objects
into a larger one and links all those larger slots into
free lists, to manage all the free space available fornext allocation.
In our implementation, we applied block marking, which means that if at least one object alive ina cache line, the whole block is considered as aliveand such block may be a partially used block, otherwise, if no object alive in a block, then such block
is considered as a free block. Partially used blockis managed by partially used block allocator after
GC. To do that, we need to rebuild the free lists
for those partially used blocks. Details are introduced below. As for free block, it is managed byfree block allocator after GC and the way to recycle
such block is the same as that to recycle the space
occupied by dead objects in original mark sweepGC.
To rebuild the free lists for partially used blocks,
instead of directly scanning the heap based on object units by scanning objects in it one by one inoriginal mark sweep GC, we scan the heap basedon block units with cache line size. Then, in eachblock, we scan objects one by one and the free slots
in partially used blocks are recorded to slot freelists. After the scan of a block, if no object alive inthe block, then the whole block is recycled in thesame way as how it is recycled by original marksweep GC and zero-ﬁlling is applied to such block
after GC. Otherwise, for all the free slots occupied
by dead objects in a block, we combine the adjacent small slots into a larger one, as mentioned inprevious section, except for the ﬁrst slots of a cacheline, as Fig. 16 shows,
the reason for the ﬁrst slot cannot be combinedwith the one next to it is that combining free slots
modiﬁes the size ﬁeld in its header. Since for NonJSObjects, the size ﬁeld is a part for its signature,such modiﬁcation may change the signature of acache line unconsciously and provide false signature to memory compression hardware. In short,
we should not change the header ﬁelds for signature in the ﬁrst slot of a block.
Then the combined free slots are added to thehead of the free list by substituting the original
head to the current free slot. Unlike a free blockwith no object alive and zero ﬁlled, no zero ﬁlling
is applied for free slots in a paritally used block.

5 Evaluation
We evaluated the compression ratio for oureJSVM with our implementation and the eJSVM
modiﬁed to support AOBD for cache line alignment(called AOBD eJSVM) to check the improvementof our proposal. In addiction, we measured the execution time of three eJSVMs, the original eJSVM,
AOBD eJSVM and the eJSVM for our proposal.
We use Are We Fast Yet [7] benchmark suite torun each eJSVM for evaluation.
5. 1 Compression Ratio Results
5. 1. 1 Methodology
To evaluate compression ratio, we run two eJSVMs
with a heap size set to 3 times minimal heap size
needed to run each benchmark. We use Pin [8]tools to monitor the running of the eJSVM to getmemory trace, which records the memory read andwrite in the heap and the function call for Garbage
collector. Then the obtained memory trace is analyzed by a simulator for the compression and deduplication hardware to get the result, which is com-pression ratio.
5. 1. 2 Deﬁnition of compression ratio
The deﬁnition of compression ratio is the same asthat for the evaluation of AOBD, shown by following equation.
1 ∑ Compress(Ri )
N
Ri
i=1
(1)
In the equation above, R means the size of live objects after each GC cycle, compress(R) means thesize needed to store all the cache line containing
those live objects after memory compression, andN means the number of GC cycles (how many times
GC starts during the running of a eJSVM with abenchmark). After each GC cycle, we calculate acompression ratio and the average of all those compression ratios is the ﬁnal compression ratio that
we measured.
5. 1. 3 Results
Fig. 17 shows the comparison ratio of our eJSVM
to AOBD eJSVM for compression ratio. It showsthat our proposal improves compression ratio by
9.0% on average compared with AOBD method.
We perform evaluations for two eJSVM withthe same AOBD memory compression methods, AOBD-HWSIG-ALIGNMENT and AOBDCOMP-HWSIG-ALIGNMENT in Fig. 17. The
AOBD-HWSIG-ALIGNMENT is the AOBD method
introduced in previous section, and AOBD-COMPHWSIG-ALIGNMENT is the same as AOBDHWSIG-ALIGNMENT except that it compresses
the base array. Since AOBD allows only one object
allocated to a cache line and applies zero-ﬁlling forunused part in the cache line, it is not necessary
to store all those ﬁlled zero in base array as it is,
those zero bits can be compressed by counting thenumber of zeros and encoding the counting in thebase array to reduce the bits occupied by those zeros. This is how further compression to base arrayachieved. For both compression methods, our proposal outperforms AOBD.
Fig. 18 shows the proportion of the size of eachdata structure in memory compression and deduplication hardware. It shows that our proposal decreases the size of translation table, as expected,
and diﬀ array, which means that the compressionof one cache line ﬁlled with multiple small objectsof the same type outperforms the compression ofN

Compression Ratio =multiple cache lines, each of which contains only
one small object of the same type. And that is thereason why the size of diﬀ array decreased.
cache line
Combined with the result in Fig. 17, Fig. 19
shows that the more small objects alive after each
GC cycle, the better the compression ratio for our
proposal, which is consistent with our anticipation
because our proposal only aims to improve the compression for small objects. For Storage benchmark,the proportion of the size of small objects alive after
each GC cycle is very small, around 10%. Therefore, there is no signiﬁcant improvement for suchbenchmark. While for NBody benchmark, the proportion for small objects is large, around 40%, somore improvement (up to 13.6%) is achieved. As aresult, for our proposal, the improvement for compression ratio is more signiﬁcant for benchmarks
with larger proportion of small objects alive after
each GC cycle.
5. 2 Execution TimeWe also measured the execution time to see theoverhead introduced by our proposal, as Fig. 20
shows. We set heap size to 100 MB to diminish
the eﬀect of GC to run time, and run those benchmarks by three eJSVM: the native eJSVM (represented by ’native’ in the ﬁgure), AOBD eJSVM(’AOBD’) and modiﬁed eJSVM for our proposal(’Proposal’). The result shows that when heap size
is not large enough to run a benchmark without
running many GC cycles (for Mandelbrot-small and
NBody-small benchmarks), our implementation results in better performance because of the reduction of GC cycles, as Fig. 21 shows, which resultsin less time consumed by GC, as the orange bar in
Fig. 20 shows. Even if the heap size is large enoughto run a benchmark without GC (for other benchmarks), the overhead introduced by our memory
manager is relatively low as shown by the blue barin Fig. 20. Therefore, no signiﬁcant overhead is introduced by our proposal compared with memory
manager in original eJSVM.

6 Related Work
Many memory compression techniques have been
proposed so far. However, most of them concentrate on hardware design and rarely consider how

Fig. 17

Fig. 18

Compression Ratios

Detailed Compression Ratios of

Fig. 19

Proportion for Live Objects per GC

NBody Benchmark

Cycle

memory allocator in virtual machine can aﬀect thedata layout in heap memory, which ﬁnally aﬀect
compression ratio and is considered in our proposal.
For general applications, there are many hardware designs that compress the data in the lastlevel cache or main memory, like BDI [9], PSS [10],EPC [11], etc. For special use cases, some memory
compression techniques are proposed. SMASH [12]handles the problem of accelerating sparse matrix computation by providing a hardware-softwarecooperative mechanism. Tavana et al. investi-

gated the potential of applying data compression
for multi-GPU architectures [13]. In addition, somemethodologies for the evaluation of memory compression have been studied. For example, Sartor
et al. analyzed Heap data compressibility [14] andprovided some formulas to evaluate memory compression.
However, all of these methods do not consider much about memory compression for objectoriented managed programming language. Zippads [15] ﬁlls this blank by a design of a compressedAcknowledgements This work was supported
by JSPS KAKENHI Grant Number JP18KK0315
and JP20H00578.

Mandelbrot- NBody-small
smallRichardssmall

Native
AOBD
Proposal

Queenssmall

Native
AOBD
Proposal

Native
AOBD
ProposalCD-smallNative
AOBD
ProposalBouncesmall

Native
AOBD
Proposal

Native
AOBD
Proposal

Native
AOBD
Proposal

References

Native
AOBD
ProposalTime (ms)

Run Time
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
0

Sieve-small Storagesmall

Benchmarks
Run Time without GC

Fig. 20

GC Time

Run Time for benchmarks

GC Cycles for Benchmarks
100
90
80

GC cycles

70
60
50
40
30
20
10

Mandelbrot- NBody-small
smallRichardssmall

Native
AOBD
Proposal

Queenssmall

Native
AOBD
Proposal

Native
AOBD
ProposalCD-smallNative
AOBD
ProposalBouncesmall

Native
AOBD
Proposal

Native
AOBD
Proposal

Native
AOBD
Proposal

Native
AOBD
Proposal

0

Sieve-small Storagesmall

Benchmarks

Fig. 21

GC Cycles for benchmarks

object-based memory hierarchy, which is specialized for object compression. Our proposal handles
memory compression for object data from anotherperspective, the cooperation between hardware system and virtual machine.

7 Conclusion
In this paper, we propose a way to allocate multiple small objects of the same type into a single
cache line to help a memory compression hardware to achieve better compression ratio for objects. The evaluation shows that our proposal reduces the compression ratio by 9.0% on averagecompared with AOBD method. Our proposal reduces the size of translation table in AOBD. In addition, we ﬁnd that the compression for one cacheline containing multiple objects with the same typeis better than that for the multiple cache lines holding one object of the same type in each of them, thisis shown by the reduction of the size of diﬀerence
array in AOBD.

[ 1 ] Tomoharu Ugawa, Hideya Iwasaki, and Takafumi Kataoka. ejstk: Building javascript virtual
machines with customized datatypes for embedded
systems. Journal of Computer Languages, 51:261–
279, 2019.
[ 2 ] QuickJS. https://bellard.org/quickjs.
[ 3 ] Yukitada Ri, Zihan Li, Tomoharu Ugawa, andRyota Shioya. オブジェクトの型を利用したキャッシュ
ラインの重複除去によるハードウェアメモリ圧縮の高効率化 (eﬃcient hardware memory compression by
object-type based cache line deduplication). (ARC)
2022-ARC-248, March 2022.
[ 4 ] Sungbo Park, Ingab Kang, Yaebin Moon,
Jung Ho Ahn, and G. Edward Suh. Bcd deduplication: eﬀective memory compression using partial cache-line deduplication. In ASPLOS ’21:
26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Virtual Event, USA, April 19-23,
2021, pages 52–64. ACM, 2021.
[ 5 ] Tomoharu Ugawa, Stefan Marr, and Richard
Jones. Caching hidden classes for pre-transitioning
object memory layout in javascript, 2021. Workshop on Modern Language Runtimes, Ecosystems,
and VMs (MoreVMs ’21).
[ 6 ] Hiro Onozawa and Hideya Iwasaki. Customizing
javascript virtual machines for speciﬁc applications
and execution environments (in japanese). Computer Software, 38(3):23–40, 2021.
[ 7 ] Stefan Marr, Benoit Daloze, and Hanspeter
Mossenbock.
Cross-Language Compiler Benchmarking: are we fast yet? 2016.
[ 8 ] Intel. https://www.intel.com/content/www/us/
en/developer/articles/ tool/pin-a-dynamic-binaryinstrumentation-tool.html.
[ 9 ] Gennady Pekhimenko, Vivek Seshadri, Onur
Mutlu, Phillip B. Gibbons, Michael A. Kozuch,and Todd C. Mowry. Base-delta-immediate Compression: Practical Data Compression for On-chipCaches. 2012.
[10] Daniel Rodrigues Carvalho and André Seznec.
A case for partial co-allocation constraints in compressed caches. In Alex Orailoglu, Matthias Jung,and Marc Reichenbach, editors, Embedded Computer Systems: Architectures, Modeling, and Simulation, pages 65–77, Cham, 2022. Springer International Publishing.
[11] Jinkwon Kim, Mincheol Kang, Jeongkyu Hong,and Soontae Kim. Exploiting inter-block entropy
to enhance the compressibility of blocks with diverse data. In 2022 IEEE International Symposium on High-Performance Computer Architecture(HPCA), pages 1100–1114, 2022.
[12] Konstantinos Kanellopoulos, Nandita Vijaykumar, Christina Giannoula, Roknoddin Azizi,
Skanda Koppula, Nika Mansouri Ghiasi, Taha
Shahroodi, Juan Gomez Luna, and Onur Mutlu.
Smash: Co-designing software compression andhardware-accelerated indexing for eﬃcient sparse
matrix operations. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO ’52, page 600–614, New
York, NY, USA, 2019. Association for Computing
Machinery.
[13] Mohammad Khavari Tavana, Yifan Sun, Nicolas
Bohm Agostini, and David Kaeli. Exploiting adaptive data compression to improve performance andenergy-eﬃciency of compute workloads in multi-gpu
systems. In 2019 IEEE International Parallel andDistributed Processing Symposium (IPDPS), pages
664–674, 2019.
[14] Jennifer Sartor, Martin Hirzel, and Kathryn
McKinley. No bit left behind: the limits of heap
data compression. pages 111–120, 01 2008.
[15] Po-An Tsai and Daniel Sanchez. Compress objects, not cache lines: An object-based compressed
memory hierarchy. In Proceedings of the TwentyFourth International Conference on Architectural
Support for Programming Languages and Operating Systems, ASPLOS ’19, page 229–242, New York,NY, USA, 2019. Association for Computing Machinery.