4 ms·

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

by x0x0 12y ago

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.

bluecalm 12y ago
>>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 ?
- Someone 12y ago
  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"
- x0x0 12y ago
  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.
- vardump 12y ago
  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#scrolltoc 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#scrolltoc 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#scrolltoc http://docs.oracle.com/cd/E36784_01/html/E36859/gntae.html#s...
antoaravinth 12y ago
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?
- vardump 12y ago
  > 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.
  - antoaravinth 12y ago
    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?
    - vardump 12y ago

by x0x0 12y ago

bluecalm 12y ago

>>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 ?

Someone 12y ago
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"
x0x0 12y ago
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.
vardump 12y ago
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#scrolltoc 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#scrolltoc 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#scrolltoc http://docs.oracle.com/cd/E36784_01/html/E36859/gntae.html#s...

antoaravinth 12y ago

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?

vardump 12y ago
> 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.
- antoaravinth 12y ago
  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?
  - vardump 12y ago