Hacker News Reader

Comment by x0x0 | Hacker News Reader

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.

View on HN

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?

32-bit OOP pointer is just multiplied by 8, because all objects have address divisible by 8. 4 GB * 8 = 32 GB.

Example of generated code from some random web page that happened to be there:

http://cr.openjdk.java.net/~shade/8050147/rsp-minus-8.perfas...

  [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:

http://shipilev.net/blog/2014/safe-public-construction/stead...

  0x00007fc7b4971644: mov    0xc(%r12,%r11,8),%r10d  ;*getfield instance

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.

HotSpot compresses pointers on 64-bit systems to 32 bits by default.

https://wikis.oracle.com/display/HotSpotInternals/Compressed...

>>At least for data, a common win is to compress the data in ram and decompress once it is in-core

I have problems imagining how it could be done. Would you mind elaborating and/or sharing some examples ?

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.

Like anything else, you'll have to measure.

For example like what instructions below do. This is pretty standard nowadays when high performance is desired.

Here are some specific instruction examples about how it's done.

Bit field operations; Bit field extract, etc.

http://docs.oracle.com/cd/E36784_01/html/E36859/gnydm.html#s...

Parallel bits extract / deposit.

http://docs.oracle.com/cd/E36784_01/html/E36859/gnyak.html#s...

SIMD (AVX2 in this example link); Pack, unpack, shuffle, permute, broadcast, etc.:

http://docs.oracle.com/cd/E36784_01/html/E36859/gntae.html#s...

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"

Reply on news.ycombinator.com