3 ms·

I wonder how it would fare compared to "software-only" solution, that is re-architecturing your algorithm to work with compressed data directly. For example, c

by js8 8y ago

I wonder how it would fare compared to "software-only" solution, that is re-architecturing your algorithm to work with compressed data directly. For example, consider an analytical engine going over values in a column of a database to sum it together. To increase the bandwidth, you can consider compressing the values (for example, with some form of Huffman encoding), and you have two options: 1. Decompress the values before passing them onto calculation, then do the calculation. This is what the paper proposes (transparently in HW as the data are being used in the cache). 2. Do the "addition" directly on the compressed values. This requires more logic. (But it doesn't have to be just implemented in software, it could be hardware assisted by some FPGA or something like that.) So I wonder, instead of compressing the cache, wouldn't it be better to implement the 2nd solution? The disadvantage of the 1st solution is that since it has to work in the general case, the compression is more likely to be bad in special cases, where the 2nd solution with a specialized compression/processing combo could be superior.

chii 8y ago
How does one work with compressed data directly? If you are dealing with the data in blocks, then your compression is only as good as the repetition in each block (perhaps the dictionary can be shared). But even in this case, you don't deal with compressed data directly, but decompress only 1 block at a time.
- lifthrasiir 8y ago
  There are some operations that can be efficiently done over the compressed data itself. Compressed bitmap is a good motivating example (and I really liked Roaring Bitmap [1]). But I guess that such efficiency is very specific to the exact operation and the viability of general compressed operation is unclear; as a related example, fully homomorphic encryption (FHE) that does the same over ciphertexts is still an active research problem. [1] https://github.com/RoaringBitmap/RoaringBitmap https://github.com/RoaringBitmap/RoaringBitmap
- js8 8y ago
  No, the quality of the compression depends on what is the probability distribution of your data blocks. If some blocks are much more likely to occur, then you can compress them better (put them in a smaller number of bits). What I mean by "directly" is instead of having to do y = y + c^-1 (x_i) where c(x) is the compression function (and c^-1 is its inverse, decompression), we could define a function f such that z = f(z, x_i) and final y = c^-1(z). This f would entail both the "+" (operation to be done on the data) and c^-1 (the decompression). In general, it's non-trivial to come up with f, but I do believe that it would be in many cases a better approach than to use the first method. Floating-point numbers can be seen as a simple case of this. If we represent numbers in fixed decimal point, then we have a lot of 0s in the numbers (and also lot of digits of very low significance) that we mostly don't need to have there. Therefore, in practice, we use compression - floating-point representation. The operations on FP are more complicated (you have to align the mantissas before you do arithmetic operations), but it's a good trade-off.
  - davrosthedalek 8y ago
    In most, if not all compression schemes, your "compression function" depends on all x_j with j<i. So it's really a new function for every i.
hinkley 8y ago
You glossing over the ugly truth here. Structured data and mutable data don't respond well to the type of operations you're talking about, and that is most of the interesting data in most programs. Most data requires random access to the middle, which is something compression is usually very bad at doing cheaply. You would have to leave boundary markers which eats into your size and speed advantage. Updating a record will change its length, requiring you to reallocate and possibly rewrite subsequent values, or even the entire parent data structure. Imagine updating the Z coordinate of the 3rd element in an array of a million objects.
- gameswithgo 8y ago
  >Most data requires random access to the middle, In domains where people need speed they are pretty clever at arranging to not need that.

by js8 8y ago

chii 8y ago

How does one work with compressed data directly? If you are dealing with the data in blocks, then your compression is only as good as the repetition in each block (perhaps the dictionary can be shared). But even in this case, you don't deal with compressed data directly, but decompress only 1 block at a time.

lifthrasiir 8y ago
There are some operations that can be efficiently done over the compressed data itself. Compressed bitmap is a good motivating example (and I really liked Roaring Bitmap [1]). But I guess that such efficiency is very specific to the exact operation and the viability of general compressed operation is unclear; as a related example, fully homomorphic encryption (FHE) that does the same over ciphertexts is still an active research problem. [1] https://github.com/RoaringBitmap/RoaringBitmap https://github.com/RoaringBitmap/RoaringBitmap
js8 8y ago
No, the quality of the compression depends on what is the probability distribution of your data blocks. If some blocks are much more likely to occur, then you can compress them better (put them in a smaller number of bits). What I mean by "directly" is instead of having to do y = y + c^-1 (x_i) where c(x) is the compression function (and c^-1 is its inverse, decompression), we could define a function f such that z = f(z, x_i) and final y = c^-1(z). This f would entail both the "+" (operation to be done on the data) and c^-1 (the decompression). In general, it's non-trivial to come up with f, but I do believe that it would be in many cases a better approach than to use the first method. Floating-point numbers can be seen as a simple case of this. If we represent numbers in fixed decimal point, then we have a lot of 0s in the numbers (and also lot of digits of very low significance) that we mostly don't need to have there. Therefore, in practice, we use compression - floating-point representation. The operations on FP are more complicated (you have to align the mantissas before you do arithmetic operations), but it's a good trade-off.
- davrosthedalek 8y ago
  In most, if not all compression schemes, your "compression function" depends on all x_j with j<i. So it's really a new function for every i.

hinkley 8y ago

You glossing over the ugly truth here. Structured data and mutable data don't respond well to the type of operations you're talking about, and that is most of the interesting data in most programs. Most data requires random access to the middle, which is something compression is usually very bad at doing cheaply. You would have to leave boundary markers which eats into your size and speed advantage. Updating a record will change its length, requiring you to reallocate and possibly rewrite subsequent values, or even the entire parent data structure. Imagine updating the Z coordinate of the 3rd element in an array of a million objects.

gameswithgo 8y ago
>Most data requires random access to the middle, In domains where people need speed they are pretty clever at arranging to not need that.