Trick behind JVM's compressed Oops

Question

So I understand the compressed oops is enabled by default in HotSpot VM now. It has support for this from Java SE 6u23 onwards through the VM option -XX:+UseCompressedOops. I understand that it allows for efficient CPU cache utilization as the CPU caches can hold a larger number of references than if they had to deal with 64 bit sized references. But what I do not understand is how using only 32 bits JVM can address up to 2⁶⁴ addresses.

To simplify the problem how can we address up to 2⁴ memory address's using just 2 bits? What can be a possible encoding/decoding of such an address scheme?

Hint: CompressedOops is limited to 2^35 addresses, not 2^64. — Mooing Duck, Apr 09 '21 at 21:24

Stephen C · Answer 1 · 2018-01-20T01:35:44.027

37

For a detailed explanation of compressed oops, see the "Compressed oops in the Hotspot JVM" article by John Rose @ Oracle.

The TL;DR version is:

on modern computer architectures, memory addresses are byte addresses,
Java object references are addresses that point to the start of a word¹,
on a 64-bit machine, word alignment means that that the bottom 3 bits of an object reference / address are zero²
so, by shifting an address 3 bits to the right, we can "compress" up to a 35 bits of a 64 bit address into a 32-bit word,
and, decompression can be done by shifting 3 bits to the left, which puts those 3 zero bits back,
35 bits of addressing allows us to represent object pointers for up to 32 GB of heap memory using compressed oops that fit in 32-bit (half-)words on a 64-bit machine.

Note that this only works on a 64-bit JVM. We still need to be able to address the memory containing that (up to) 32 GB heap¹, and that means 64-bit hardware addresses (on modern CPUs / computer architectures).

Note also that there is a small penalty in doing this; i.e. the shift instructions required to translate between regular and compressed references. However, the flip side is that less actual memory is consumed³, and memory caches are typically more effective as a consequence.

^{1 - This is because modern computer architectures are optimized for word-aligned memory access.}

^{2 - This assumes that you haven't used -XX:ObjectAlignmentInBytes to increase the alignment from its default (and minimum) value of 8 bytes.}

^{3 - In fact, the memory saving is application specific. It depends on the average object alignment wastage, ratios of reference to non-reference fields and so on. It gets more complicated if you consider tuning the object alignment.}

To simplify the problem how can we address up to 2⁴ memory addresses using just 2 bits? What can be a possible encoding/decoding of such an address scheme?

You can't address 2⁴ byte addresses. But you can address 2² word addresses (assuming 32-bit words) using 2-bit word addresses. If you can assume that all byte addresses are word-aligned, then you can compress a 4-bit byte address as 2-bit word address by shifting it by 2-bit positions.

edited Jan 20 '18 at 01:35

answered Aug 04 '14 at 14:22

Stephen C

698,415
94
811
1,216

3

I do not follow the logic "on a 64bit machine, that means that that the bottom 3 bits of an address are zero". Why would the fact that references point the start of a word lead to a situation that the bottom 3 bits are all `0`s? – Geek Aug 04 '14 at 14:58
3

Because modern computer architectures are byte addressed. – Stephen C Aug 04 '14 at 15:08
1

Got it. I am also having trouble understanding what exactly you meant by "so, by shifting an address 3 bits to the left, we can "compress" up to a 35 bits of a 64 bit address into a 32 bit word,".. How did you arrive at the number 35? – Geek Aug 04 '14 at 15:18
1

Simple arithmetic. 32 + 3 == 35. – Stephen C Aug 04 '14 at 22:37
Not sure I get it : the 35 bits of get is 32 bits plus 3 bits sets to 0. You don't add space by having more zero, if such bits have to be 0... I am sure I am missing something in the reasoning but it just sounds funny... – nicolas May 19 '16 at 17:28
So it's not so much that you gain 3 bits but rather that you avoid loosing them really ... – nicolas May 19 '16 at 17:54
1

I wonder why they didn't pick 16-byte alignment? Most applications don't use a lot of bare objects with no fields; even a single boolean field will bump the object size up to 16 bytes. – kbolino May 27 '16 at 18:53
You have to measure across all objects in the JVM. I imagine that they did this ... across a range of real-world applications ... and determined that 16 byte alignment resulted in too much wasted space. There is a trade-off between space used by large refs and space used due to object address alignment. – Stephen C May 27 '16 at 23:30
Besides, the alignment decision would have most likely been made 10+ years earlier ... and baked in. – Stephen C May 27 '16 at 23:32
@StephenC fair point, I wasn't considering objects whose 8-byte-aligned sizes weren't 16-byte-aligned (e.g. 24, 40, 56, ...) and thus would waste more space under my scheme – kbolino Jul 01 '16 at 10:19
One possible argument for 8-byte alignment rather than 16-byte alignment is that it makes converting to an absolute address cheaper. On x86-64, scale by 8 and add to base address can be done with a single `LEA` instruction. If you want to scale by 16 instead, you cannot do it with a single `LEA`. I do not know if this actually factored into the decision though. – Andrew Thaddeus Martin Oct 28 '21 at 17:37

score 9 · Answer 2 · answered Aug 04 '14 at 14:22

It's not meant for 32-bit JVMs. It's to alleviate the additional overhead that occur in 64-bit JVMs. I think Oracle's page explains it well:

Compressed Oops

Compressed oops represent managed pointers (in many but not all places in the JVM software) as 32-bit object offsets from the 64-bit Java heap base address. Because they're object offsets rather than byte offsets, they can be used to address up to four billion objects (not bytes), or a heap size of up to about 32 gigabytes. To use them, they must be scaled by a factor of 8 and added to the Java heap base address to find the object to which they refer.

source

score 4 · Answer 3 · answered Dec 22 '18 at 01:59

https://blog.codecentric.de/en/2014/02/35gb-heap-less-32gb-java-jvm-memory-oddities/

I think this article explain this well. Taken away:

Because the JVM memory layout uses a 8byte addressing scheme, which means that objects can be at address 0, 8, 16, 24… but not at 2, 7 or any other non multiple of 8, compressed oops just address the virtual positions 0, 1, 2, 3 instead of the real ones 0, 8, 16, 24. To get from the compressed address to the real one, the JVM needs just to left shift it 3 times. Easy.

4G * 8 = 32

score 1 · Answer 4 · answered Aug 04 '14 at 14:23

CompressedOops.

From the article: Not all of the pointers are compressed, and the compressed ones are 32-bit values which must be scaled by a factor of 8 and added to a 64-bit base address to find the object they refer to.

Now note that you can't address 2^64 bits of memory with these 32bit pointers, but you can access plenty of Objects with them. If you have an object at memory location x, there's no way that you can have another one at x+1. That's why you don't need to access every single memory location.

Trick behind JVM's compressed Oops

4 Answers4

Linked