a cache line is the unit of read from ram, and is at a premium
At least for data, a common win is to compress the data in ram and decompress once it is in-core; this is often essentially free as many machine learning algorithms are bandwidth starved but have plenty of compute available. Suppose you are eg storing small integer counts in ints; if it's a java int you are using 4B to store 1B, while if it's a java.lang.Integer it costs 16 bytes plus most likely an 8B pointer.
Another way to consider this is if you are using 8B pointers, you waste a lot of that as constant zeros -- 1TB is 2^40, so even on a 1TB machine 3B/24b are wasted. Particularly with (all? at least that I know of) jvms that have 8B alignment, another 4 bits are wasted. This is how the CompressedOops hack words to access 32G ram w/ 32b pointers.
I didn't get them fully. Sorry for novice questions, but wish to understand your statement completely.
>Suppose you are eg storing small integer counts in ints; if it's a java int you are using 4B to store 1B, while if it's a java.lang.Integer it costs 16 bytes plus most likely an 8B pointer.
This wastage does happens only in reference types? Tomorrow say if value types are been created, then these sort of issue will get resolved?
>Another way to consider this is if you are using 8B pointers, you waste a lot of that as constant zeros
Why of constant zeros? And in the line your saying "-- 1TB is 2^40", your referring 1TB of cache line?
> This wastage does happens only in reference types? Tomorrow say if value types are been created, then these sort of issue will get resolved?
That would solve most of the issue, yes.
> Why of constant zeros? And in the line your saying "-- 1TB is 2^40", your referring 1TB of cache line?
He was not referring to cache line or anything like that. He was referring to the fact if you can address just 40 bits, upper 24 bits in a 64-bit pointer are wasted in a pointer. I think on x86 real virtual address size is currently 48 bits, so upper 16 bits are "wasted". This wastage will occur with heaps larger than 32 GB when using compressed pointers JVM option. And of course 4 GB (or 2 GB?) with that JVM option disabled.
Similarly, if you use "bool" type, it still takes a byte in current JVM implementations. So you could say 7 bits are wasted there.
Thanks for the explanation. Looks like Java has more memory problems:
1. If OOP pointer is going to eat up our memory, there we loose / waste some bits of memory.
2. And as you have said even using bool type, is going to say waste by 7 bits!
Since we are dealing more with objects in java world, then I guess, 32 bit VMs will be much faster than 64 bit VMs. Or even 16bit will be more faster, from my understanding.
Still I have a final question over here, all the OOP pointers does goes the CPU caches and registers?
[0x7f189918ae07:0x7f189918ae54] in org.openjdk.VolatileBarrierBench::testWith
# [sp+0x30] (sp of caller)
0x00007f189918ade0: mov 0x8(%rsi),%r10d
0x00007f189918ade4: shl $0x3,%r10
That "shl $0x3,%r10" multiplies the pointer in register r10 by 8 (2^3). So looks like JVM computes the base pointer to an object to a register (r10 in this case) and uses relative addressing from it.
Here's example of using x86 indirect addressing mode to multiply the pointer by 8:
In this case effective address for the load from heap is r12 + r11 * 8. Register r12 probably represents heap base pointer or similar in this case - I'm not sure.
16-bit would be significantly slower, but for entirely other reasons. Also, you could have at most 512 kB heap with 8 byte address alignment...
The issue with 64-bit pointers is that Java (and JVM) is a very pointer happy language, so the cost is significantly more than for pretty much any other language I can think of. Memory usage and more cache misses is the issue.
The insight is that on a modern processor memory bandwidth is scarce but it can issue several floating point ops per clock. So multiplying and adding stuff in L1 or already in registers is cheap. Streaming algorithms that walk large chunks of ram will be repeatedly memory starved, so anything you can do to effectively increase memory b/w is valuable.
Say you have 8bit integers; store them packed in ram, then upon reading, unpack. So instead of striping an array of int[], you have an internal array of long[] and you read them with a function. Your memory read will suck in 8 at once.
The same technique works for floats or ints with a small-ish range and limited precision; you can store a scale and offset, then pack on write / unpack on read. It's common to be able to quadruple your effective memory bandwidth, then the read operation -- ie
// instead of:
double[] _data;
// accessed as
_data[idx];
//instead you do
getd(idx);
// using the below
bytes[] _mem;
float _bias, _scale;
double getd(int idx){
long res = _mem[idx];
return (res + _bias) * _scale;
}
executes entirely from registers, and is essentially free. The price of all this is you have to process your data on ingestion, but if you run iterative algorithms -- like convex optimizers -- that repeatedly walk your entire dataset, this is often a big win. You can often lose some of the low precision bits on the float or double, but those probably don't matter much anyway.
If you build your own hardware, you don't even have to decompress it. Let's limit each process to 2^40 bytes of RAM. Build your virtual address space so that it masks out the top 24 bits of each address before doing address translation. Then, you can store 24 bits of extra information in each pointer. For example, you could store 3 bytes of a C++ object in a vtable pointer (with 'interesting' repercussions for the sizeof and offsetof macros)
That is more or less what the original Macintosh did with its handles. The hardware wrapped addresses around at 24 bits. That allowed Apple to store 3 bits of data in each handle ('data can be purged from memory if needed', 'data cannot be moved', 'data is read from a resource'). Third parties sometimes used the other 5 bits. With the introduction of Macs with more memory, that led to the "program has special memory requirements" system error, which actually meant "this is Excel version so and so. It cannot run on a machine that has 32 address bus lines because it mangles pointers"
if your cache line is 75% zeroes, then half of it respects the objective of "should contain 50% of each bit", and the other half is all zeroes, which is a waste (according to this objective)... in other words, only half the cache is 'correctly' used. This is just another way of saying that your D$ size is effectively halved.
> Rule #1: Cache lines should contain 50% of each bit (1/0) > – E.g., if cache lines are 75% zeroes, your D$ size is effectively halved
Can anyone explain this?