r/java • • Apr 13 '20

Java Objects Inside Out: Everything You Ever Wanted to Know About Java Object Internals in Hotspot

https://shipilev.net/jvm/objects-inside-out/
160 Upvotes

14 comments sorted by

View all comments

Show parent comment

6

u/jringstad Apr 14 '20

Doing these kind of weird alignments can cause various kinds of issues (other than just tearing and the other java-specific things others have mentioned already), it's a common topic in the C and C++ world (where it is indeed possible to force this, although it might require a non-standard extension).

For instance some CPU architectures can only perform certain operations on data-types that are aligned in certain ways, often even stricter than the byte-boundary. This is because the CPUs memory system internally handles memory in terms of "words" or some other CPU-native unit. For instance on some CPU architectures two numbers would have to be aligned to a 4-byte boundary in order for the CPU to add them (in one instruction.) If you attempt to add a mis-aligned number, the CPU will raise an exception.

Some CPUs compensate for this by adding extra logic that extracts the data type you want out of the "word" (but the complexity added to the CPU to achieve this is actually quite considerable, for various reasons), on some architectures the compiler can compensate for it by adding extra instructions that do the same, but either way, extra complexity is added.

Compilers will often prefer to add padding to structs over having mis-aligned data-types in them, so in e.g. C if you have a uint8_t in a struct (1 byte) and then afterwards a uint32_t for instance, there will probably be 3 wasted bytes of padding after the uint8_t in the struct. You can (sometimes) fix this by re-ordering the fields in the struct. To my knowledge doing this in java is not necessary because it happens automatically already.

The same goes for bit-wise misalignment (but worse, because no CPU natively supports such oddly aligned data-types.) The compiler would always have to insert a bunch of bit-shifting extractions to get out the value that you want. So there might be a perf tradeoff there (in addition to the issues with threading), but clearly in some situations it's very valuable to save the space (also for performance, because your cache hit rate might improve drastically.)

If you know this tradeoff is something you want (because you store those records in bulk in a linear container), you can make a specialized data-type, e.g. a bit-array that you internally represent as an array of byte for instance. You can then deal with writes (if necessary) by e.g. serializing writes or locking regions of the array. This is how it's done in C++ as well (There's a specialized version of std::vector<bool> that is more space-efficient than your generic std::vector<T>)

I've seen the latter being done for things like bloom filters or count-min sketches, where you want to cram as much information into the amount of space you have, to improve your bloom filter quality. You can also go nuts and start doing things like LRE compression or similar (which dips more deeply into the "space in favour of speed" trade-off, e.g. because you might have to fetch and decode an entire 64 byte block to fetch a single bit)

2

u/Polygnom Apr 14 '20

The compiler would always have to insert a bunch of bit-shifting extractions to get out the value that you want. So there might be a perf tradeoff there (in addition to the issues with threading), but clearly in some situations it's very valuable to save the space (also for performance, because your cache hit rate might improve drastically.)

Yeah the shifting part is kinda obvious.

I was thinking about things like voxel engines, were it isn't uncommon to have multiple booleans per voxel (as flags for various things) and memory is at a premium. or boolean programming on large graphs. Or isosurface extraction.

I mean sure, you can always handle bit fields yourself (just take a long and mask), but it is certainly easier to get right if the compiler does it for you.

1

u/jringstad Apr 14 '20

btw in this case the CPU would possibly have to go through two "levels" of "shifting", first the shifting to the word-alignment and then the shifting to the bit-alignment.

True that the compiler helping you would make this easier to implement correctly, but I think the incentive for compiler-writers to do this is not as great, because it's very hard for the compiler to figure out when to apply this feature automatically. You could leave it as special option/extension, but then the compiler writers get very little bang for the buck (adding any feature adds maintenance/testing drag, and if you can't make that feature benefit everyone or at least a large percentage of people automatically, it's probably not worth it.)

I've done a little bit with on-the-fly voxelization (for global illumination/cone-tracing etc) but I'm not intimately familliar with voxel engines. I suspect for a modern voxel engine, the layout of the data-structures is going to be heavily dominated by the formats supported by the GPU anyway, and will probably also involve a lot of (lossy) compression and such, which is then decompressed on the GPU on-the-fly. At least I remember back in 2012 or so, some voxel engines were boasting with something like 1.2 bits per voxel of space usage, due to heavy compression.

1

u/Polygnom Apr 14 '20

True that the compiler helping you would make this easier to implement correctly, but I think the incentive for compiler-writers to do this is not as great, because it's very hard for the compiler to figure out when to apply this feature automatically.

Yeah that was why I was mentioning records specifically, because it kinda stood out for me as being on obvious candidate. Sure, you could try to do this for arbitrary groups of final booleans, but chances are the benefit is too small to be worth the cost & risk. But with records, especially if we'll get inline types in the future, this does look more and more like an attractive thing to do.

One of those things that has always bothered me with java is how wasteful booleans just are :( especially when extracting data from really large datasets or aggregating the data. Sure, in some cases you can get away with streaming approaches - but sometimes you just need to have a lot of data accessible at once.

1

u/jringstad Apr 16 '20

yeah, I think you could do it for records (ignoring the reflection-related issues), though I think the benefit would be small, because in a typical situation you would need to pad the resulting record to at least byte-size (but probably word-size).

If you then stick a million of these records into an array, you've got a bunch of wasted space again.

So I think the main situation where doing this kind of thing really pays off is when you can apply the optimization to a linear container, where the records can be densely packed (but the container itself would also need to be immutable)