<p>Let's say I want my compiler to store objects packed (data and collection members aligned to non-word boundaries).</p>
<p><strong>Situation #1:</strong> I want to store an array of booleans.</p>
<p>A few languages already let the array be stored compressed. C++ does that in <code>std::vector&lt;bool&gt;</code>. So I presume this situation is quite practical.</p>
<p><strong>Situation #2:</strong> I want to store a ternary value. (Haskell's <code>Ordering</code>, for example)</p>
<p>A ternary value can be represented in two bits. Let <code>EQ</code> = <code>00</code>, <code>GT</code> = <code>01</code>, <code>LT</code> = <code>11</code>, representing signed 0, 1, and -1, respectively.</p>
<p><strong>Situation #3:</strong> I want to store a string.</p>
<p>Assuming the word is 64 bits long, since valid Unicode points are up to U+10FFFF, it's possible to store 3 Unicode characters in each word, treating each character as a bit-array of 21 bits.</p>
<p><strong>Situation #4:</strong> I want to store an array of ternary values compactly in a word.</p>
<p>Assuming the word is 64 bits long, it should be possible to store <code>floor(64 / log2(3))</code> = 40 ternary values in a word. But unlike the former situations, extracting one ternary value from such &quot;array&quot; cannot be done by bitmasking, but by converting binary to balanced ternary. This can be done with iterated arithmetic.</p>
<p>Which situations I'm describing are actually practical?</p>

<strings><arrays>
To what degree is it practical to let objects be stored packed?
CC BY-SA 4.0
2023-07-11T06:08:00.990Z
I don't consider `std::vector<bool>` as practical, as it violates many guarantees that `std::vector<T>` provides (item reference, concurrency, ...), and misusing it is a common pitfall. `std::bitset` is the better alternative. Another example for #1: multiple array language impls (APL, J?, K iirc) store bit arrays using 1 bit per item.
Bubbler
CC BY-SA 4.0
2023-07-11T15:30:11.147Z
having vector<bool> is considered error nowadays.
RiaD
CC BY-SA 4.0
2023-07-11T15:44:24.223Z
@RiaD: True, but `vector<bool>` is seen as a misfeature because of pitfalls like failing to meet the standard container rules in C++, not because it’s a bad idea altogether. C++ paints itself into a corner here by needing a reference to the element type, but having no way of expressing that reference, because it defines a byte as the smallest addressable unit of memory. Changing that would be possible, but a sizable amount of work.
Jon Purdy
CC BY-SA 4.0
2023-07-11T15:53:24.363Z
@JonPurdy: Another way to solve the issue would be for C++ to provide the ability to overload the member function `operator[]=(key, value)`, equivalent to Python's `__setitem__`.  Then the getter (`operator[](key) const` ) could just return by value, and you could have indexers without needing a reference.
dan04
CC BY-SA 4.0
2023-07-11T16:01:02.140Z
I attempted to answer this question rather hurriedly this morning but thinking about it again it does not seem to be specific to PLDI. It may be an XY question? What do you want to compress and why? What are the constraints? and it what way are they specific to compilation or some other aspect of your PL?
Bruce Adams
CC BY-SA 4.0
2023-07-11T20:25:19.480Z
Compression and encryption are cheap for modern CPU. AMD EPYC encrypts its whole memory at a performance cost of just 3.7%. Memory compression is SOP today and improves performance by 20-60%. But what you're describing is internal optimization, not compression.
Therac
<p>May make no harm to offer a keyword putting a hint that the structure is large, sparse and would benefit from packing. Pascal has the keyword <a href="https://www.tutorialspoint.com/pascal/pascal_packed_array.htm" rel="nofollow noreferrer">packed</a> (<code>packed array</code>). And while C++ vector of booleans (that is packed) only uses a single bit rather than the whole boolean per value,  <a href="https://stackoverflow.com/questions/17794569/why-isnt-vectorbool-a-stl-container">not all are happy</a> with this so the explicit control would be beneficial.</p>
<p>It may be too difficult for the compiler to figure out the right strategy because this depends on how large the structure could grow. This may not be obvious from the code and depend on the input of the program.</p>

CC BY-SA 4.0
2023-07-11T09:09:51.207Z
2023-07-11T09:15:50.730Z
2023-07-11T09:15:50.730Z
Audrius Meškauskas
<h1>Compression breaks references to individual values</h1>
<p>If you compress arrays, you will lose the ability to have simple references to individual values. For example, <code>std::vector&lt;bool&gt;</code> has a special <code>std::vector&lt;bool&gt;::reference</code> type that is not equivalent to <code>bool&amp;</code>. This means you can not pass that to functions that expect a <code>bool&amp;</code> argument.</p>
<p>This has a lot more consequences than you might think. Consider that for a non-compressed array, you can use <code>std::span</code> to denote a slice in that array. You can however not use <code>std::span</code> on a <code>std::vector&lt;bool&gt;</code>.</p>
<h1>Compression might impact thread-safety</h1>
<p>Continuing with <code>std::vector&lt;bool&gt;</code> as an example: if two threads have references to different values in a <code>std::array&lt;bool&gt;</code>, then they can update those values independantly without any issues. However, if they both have a <code>std::vector&lt;bool&gt;::reference</code> to different values in that vector, then they might still refer to the same byte or word in memory, and unless a mutex or other synchronization primitive is used, race conditions can occur.</p>
<p>Another example that caused thread-safety issues was <code>std::string</code> prior to C++11: most libraries implemented some form of copy-on-write optimization (effectively a form of deduplication). However, this caused all sorts of issues in multi-threaded programs.</p>

CC BY-SA 4.0
2023-07-11T16:18:31.807Z
2023-07-11T16:18:31.807Z
G. Sliepen
<h2>Consider the trade offs</h2>
<h3>Premature Optimisation is the root of all evil</h3>
<p>Why do you need to compress your data at all?
There needs to be a good motivating reason backed by measurement or reason. A reason might be if you are severely memory constrained.</p>
<h3>Compression could impact performance</h3>
<p>Any kind of compression or encoding will reduce performance. A simple encoding may not be too bad but full compression (e.g. pass everything through zlib) might not be acceptible. Also the gains from compression depend on the size of the thing you are compressing. So you might instead compress a whole related block of memory.</p>
<p>It depends on your application and access patterns.</p>
<h3>Minimal one-to-one Encoding may be acceptible</h3>
<p>4 bytes  &lt;-&gt; 3 bytes</p>
<p>Likewise some kinds of fast compression.</p>
<h3>Hide Compression and encoding in the interface</h3>
<p>You want to keep your compressed format out of the interface to the data as far as possible.</p>
<p>But you need to make exceptions for some things:</p>
<ul>
<li><p>serialisation. You should be able to save and load the compressed format.</p>
</li>
<li><p>controlling the compression itself - E.g. trading speed for memory</p>
</li>
</ul>
<h2>What do you want to compress?</h2>
<p>Considering your question again. What do you want to compress?
The data used by the compiler itself? or the data used by the programs generated by the compiler?</p>
<p>Generally you want compilers to be fast so long as they don't run out of resources.</p>
<p>Generally you want programs to be fast too.</p>
<p>What are the constraints of the problem?</p>
<p>This question does not actually seem to be specific to programming languages at all.</p>

CC BY-SA 4.0
2023-07-11T08:00:38.080Z
2023-07-11T16:05:33.550Z
2023-07-11T16:05:33.550Z
Bruce Adams
CC BY-SA 4.0
2023-07-11T14:35:35.923Z
Recommendations against "premature optimization" call for profiling before optimization but how can you profile for the compiler when you do not know yet what the program it will be? Should it be always better, or only sometimes is enough?
Audrius Meškauskas
CC BY-SA 4.0
2023-07-11T15:46:34.737Z
‘full compression would likely not be acceptable’ This depends very much on the access patterns, the compression used, and even how fast the CPU is. Using zlib for data that needs random access and is accessed frequently? Not at all practical. Using Brotli, LZ4, or Snappy for data that only needs in-order sequential access and is accessed only infrequently? Probably acceptable unless you have strict timing constraints to meet.
Austin Hemmelgarn
CC BY-SA 4.0
2023-07-11T20:19:27.287Z
Don’t forget how space affects cache-lines; I suspect 4-byte reads are fast than 3-byte reads because that seems like the sort of thing someone would optimize (with no supporting references, hm)
D. Ben Knoble
<p>I would suggest having a &quot;member pseudo-lvalue&quot; type, somewhat analogous to properties in .NET, which may defined by any desired non-empty combination of the following operations:</p>
<ul>
<li>read from</li>
<li>store to</li>
<li>add to</li>
<li>subtract from</li>
<li>multiply by</li>
<li>divide by</li>
<li>remainder-reduce by</li>
<li>bitwise-union-with (OR)</li>
<li>bitwise-intersect with (AND)</li>
<li>bitwise-maskflip with (XOR)</li>
<li>shift-right by</li>
<li>shift-left by</li>
</ul>
<p>Operations should be speciable as either acting on a non-subscripted value, or as a value with any desired number of subscripts.</p>
<p>From a client-code perspective, the operation could act upon raw data or on compressed data, without the client having to know or care.  Including compound operations would allow an operation like:</p>
<pre><code>foo.someBitField |= x;
</code></pre>
<p>where <code>someBifField</code> is stored in bits 3-5 of <code>foo.bits</code>, to be processed by simply &quot;or&quot;'ing <code>foo.bits</code> with <code>(x &amp; 7)&lt;&lt;3</code>, without having to extract the value of the bitfield, shift it right by 3, perform the &quot;or&quot; operation, shift the result left by 3, and mask-stuff it back into <code>foo.bits</code>.</p>

CC BY-SA 4.0
2023-07-11T15:45:19.467Z
2023-07-11T15:45:19.467Z
supercat
<p>This should not become a language feature, but an implementation detail of some parts of your library.</p>
<p>Design the APIs of these parts so that they hide this detail, e.g. let the <code>BitArray</code> class support methods like <code>bool getBit(int i)</code> and <code>void setBit(int i, bool value)</code>. Then, it can be an optimization choice whether to use one word, one byte or one bit for the elements, without affecting user code. You might even come up (at some time in the future) with an implementation that uses words for small arrays and bits for larger ones, and still follows the same API, thus not affecting user code.</p>
<p>Language design is about providing a good abstraction layer over the bits and bytes of the machine, and IMHO, the internal representation of strings, arrays and so on should be encapsulated by classes that provide meaningful interfaces and hide the internal details of storage. Think about objects and operations first, and hide the data structures.</p>

CC BY-SA 4.0
2023-07-11T06:53:23.153Z
2023-07-11T19:30:41.650Z
2023-07-11T19:30:41.650Z
Ralf Kleberhoff
# To what degree is it practical to let objects be stored packed?
Posted by: username_0 on 2023-07-11
Let's say I want my compiler to store objects packed (data and collection members aligned to non-word boundaries).

**Situation #1:** I want to store an array of booleans.

A few languages already let the array be stored compressed. C++ does that in `std::vector`. So I presume this situation is quite practical.

**Situation #2:** I want to store a ternary value. (Haskell's `Ordering`, for example)

A ternary value can be represented in two bits. Let `EQ` = `00`, `GT` = `01`, `LT` = `11`, representing signed 0, 1, and -1, respectively.

**Situation #3:** I want to store a string.

Assuming the word is 64 bits long, since valid Unicode points are up to U+10FFFF, it's possible to store 3 Unicode characters in each word, treating each character as a bit-array of 21 bits.

**Situation #4:** I want to store an array of ternary values compactly in a word.

Assuming the word is 64 bits long, it should be possible to store `floor(64 / log2(3))` = 40 ternary values in a word. But unlike the former situations, extracting one ternary value from such "array" cannot be done by bitmasking, but by converting binary to balanced ternary. This can be done with iterated arithmetic.

Which situations I'm describing are actually practical?
**Tags:** strings arrays
> **Comments:**
> **username_1**: I don't consider `std::vector<bool>` as practical, as it violates many guarantees that `std::vector<T>` provides (item reference, concurrency, ...), and misusing it is a common pitfall. `std::bitset` is the better alternative. Another example for #1: multiple array language impls (APL, J?, K iirc) store bit arrays using 1 bit per item.  
> **username_2**: having vector<bool> is considered error nowadays.  
> **username_3**: @RiaD: True, but `vector<bool>` is seen as a misfeature because of pitfalls like failing to meet the standard container rules in C++, not because it’s a bad idea altogether. C++ paints itself into a corner here by needing a reference to the element type, but having no way of expressing that reference, because it defines a byte as the smallest addressable unit of memory. Changing that would be possible, but a sizable amount of work.  
> **username_4**: @JonPurdy: Another way to solve the issue would be for C++ to provide the ability to overload the member function `operator[]=(key, value)`, equivalent to Python's `__setitem__`.  Then the getter (`operator[](key) const` ) could just return by value, and you could have indexers without needing a reference.  
> **username_5**: I attempted to answer this question rather hurriedly this morning but thinking about it again it does not seem to be specific to PLDI. It may be an XY question? What do you want to compress and why? What are the constraints? and it what way are they specific to compilation or some other aspect of your PL?  
> **username_6**: Compression and encryption are cheap for modern CPU. AMD EPYC encrypts its whole memory at a performance cost of just 3.7%. Memory compression is SOP today and improves performance by 20-60%. But what you're describing is internal optimization, not compression.  
---
## 5 answers
### Answer by username_12 on 2023-07-11. Score: 6 | Accepted answer
This should not become a language feature, but an implementation detail of some parts of your library.

Design the APIs of these parts so that they hide this detail, e.g. let the `BitArray` class support methods like `bool getBit(int i)` and `void setBit(int i, bool value)`. Then, it can be an optimization choice whether to use one word, one byte or one bit for the elements, without affecting user code. You might even come up (at some time in the future) with an implementation that uses words for small arrays and bits for larger ones, and still follows the same API, thus not affecting user code.

Language design is about providing a good abstraction layer over the bits and bytes of the machine, and IMHO, the internal representation of strings, arrays and so on should be encapsulated by classes that provide meaningful interfaces and hide the internal details of storage. Think about objects and operations first, and hide the data structures.
---
### Answer by username_7 on 2023-07-11. Score: 4
May make no harm to offer a keyword putting a hint that the structure is large, sparse and would benefit from packing. Pascal has the keyword [packed](https://www.tutorialspoint.com/pascal/pascal_packed_array.htm) (`packed array`). And while C++ vector of booleans (that is packed) only uses a single bit rather than the whole boolean per value, [not all are happy](https://stackoverflow.com/questions/17794569/why-isnt-vectorbool-a-stl-container) with this so the explicit control would be beneficial.

It may be too difficult for the compiler to figure out the right strategy because this depends on how large the structure could grow. This may not be obvious from the code and depend on the input of the program.
---
### Answer by username_8 on 2023-07-11. Score: 3
# Compression breaks references to individual values

If you compress arrays, you will lose the ability to have simple references to individual values. For example, `std::vector` has a special `std::vector::reference` type that is not equivalent to `bool&`. This means you can not pass that to functions that expect a `bool&` argument.

This has a lot more consequences than you might think. Consider that for a non-compressed array, you can use `std::span` to denote a slice in that array. You can however not use `std::span` on a `std::vector`.

# Compression might impact thread-safety

Continuing with `std::vector` as an example: if two threads have references to different values in a `std::array`, then they can update those values independantly without any issues. However, if they both have a `std::vector::reference` to different values in that vector, then they might still refer to the same byte or word in memory, and unless a mutex or other synchronization primitive is used, race conditions can occur.

Another example that caused thread-safety issues was `std::string` prior to C++11: most libraries implemented some form of copy-on-write optimization (effectively a form of deduplication). However, this caused all sorts of issues in multi-threaded programs.
---
### Answer by username_5 on 2023-07-11. Score: 2
## Consider the trade offs

### Premature Optimisation is the root of all evil

Why do you need to compress your data at all?
There needs to be a good motivating reason backed by measurement or reason. A reason might be if you are severely memory constrained.

### Compression could impact performance

Any kind of compression or encoding will reduce performance. A simple encoding may not be too bad but full compression (e.g. pass everything through zlib) might not be acceptible. Also the gains from compression depend on the size of the thing you are compressing. So you might instead compress a whole related block of memory.

It depends on your application and access patterns.

### Minimal one-to-one Encoding may be acceptible

4 bytes <-> 3 bytes

Likewise some kinds of fast compression.

### Hide Compression and encoding in the interface

You want to keep your compressed format out of the interface to the data as far as possible.

But you need to make exceptions for some things:

* serialisation. You should be able to save and load the compressed format.
* controlling the compression itself - E.g. trading speed for memory

## What do you want to compress?

Considering your question again. What do you want to compress?
The data used by the compiler itself? or the data used by the programs generated by the compiler?

Generally you want compilers to be fast so long as they don't run out of resources.

Generally you want programs to be fast too.

What are the constraints of the problem?

This question does not actually seem to be specific to programming languages at all.
> **Comments:**
> **username_7** (2023-07-11): Recommendations against "premature optimization" call for profiling before optimization but how can you profile for the compiler when you do not know yet what the program it will be? Should it be always better, or only sometimes is enough?  
> **username_9** (2023-07-11): ‘full compression would likely not be acceptable’ This depends very much on the access patterns, the compression used, and even how fast the CPU is. Using zlib for data that needs random access and is accessed frequently? Not at all practical. Using Brotli, LZ4, or Snappy for data that only needs in-order sequential access and is accessed only infrequently? Probably acceptable unless you have strict timing constraints to meet.  
> **username_10** (2023-07-11): Don’t forget how space affects cache-lines; I suspect 4-byte reads are fast than 3-byte reads because that seems like the sort of thing someone would optimize (with no supporting references, hm)  
---
### Answer by username_11 on 2023-07-11. Score: 2
I would suggest having a "member pseudo-lvalue" type, somewhat analogous to properties in .NET, which may defined by any desired non-empty combination of the following operations:

read from
store to
add to
subtract from
multiply by
divide by
remainder-reduce by
bitwise-union-with (OR)
bitwise-intersect with (AND)
bitwise-maskflip with (XOR)
shift-right by
shift-left by

Operations should be speciable as either acting on a non-subscripted value, or as a value with any desired number of subscripts.
From a client-code perspective, the operation could act upon raw data or on compressed data, without the client having to know or care.  Including compound operations would allow an operation like:
foo.someBitField |= x;

where someBifField is stored in bits 3-5 of foo.bits, to be processed by simply "or"'ing foo.bits with (x & 7)<<3, without having to extract the value of the bitfield, shift it right by 3, perform the "or" operation, shift the result left by 3, and mask-stuff it back into foo.bits.
---
