<p>For my programming language, I have built an engine that goes after the parser and before the compiler. This engine analyzes, validates, and simplifies the AST.
During the analasys, it determines as much information as possible about each and every variable. So, for each variable, I have a tree representing every possible value  the variable may have at any given point in the program (or just minimum/maximum values (for numbers) and possible elements (for strings) if there is such a pattern).</p>
<p>Because of this, I have the capability to determine the most memory efficient type that stores only the minimum information required to reconstruct the value.
For example, in the following code:</p>
<pre class="lang-py prettyprint-override"><code>import random

possible = ['a', 'c', 'n', '2', '8', '1', 'o']
string = &quot;&quot;

for i in range(10):
  string += random.choice(possible)

print(string)
</code></pre>
<p>(My language does not actually look like Python, this is just an example).</p>
<p>My system would determine that <code>string</code> can only ever have a maximum of 10 characters, and those characters will always be one of <code>['a', 'c', 'n', '2', '8', '1', 'o']</code>.
This compels it to store <code>string</code> in a way such that 3 bits are allocated to every character (this is the minimum to represent every possible character). It will also note the maximum number of characters (10) and so choose to allocate 10 * 3 = 30 bits (usually 32 because of alignment).</p>
<p>This makes it really memory efficient, but it's not too good for speed because it has to be processed on storing and reading to change it to that type.
I was wondering if there was a way to determine the fastest data type for a particular scenario on a specific platform. I'm new to this, so I'm not sure how to determine which one is best optimized for the platform. Some platforms natively support IEEE 754, some don't. Some have their own data types they want programmers to use. How can I know which will run the fastest?</p>
<p>If it helps, I plan to compile to LLVM IR, though I don't have the compiler done yet.
The language is written in (an interpreter version of) itself, if that's relevant.</p>

<types><optimization><type-inference><llvm><type-conversion>
Determining the most optimized data type for the platform with type inference
CC BY-SA 4.0
2023-11-27T21:00:28.823Z
Oh my bad, I've gotten a bit complacent with assuming new posts are from new users. I know the refinement types thing isn't an answer to the question itself, it's just nice google-able term for what you were describing with keeping track of what values a variable might have.
rydwolf
CC BY-SA 4.0
2023-11-27T21:06:16.340Z
@RydwolfPrograms Ah, that makes more sense. I am the kind of person who knows how to build something, but doesn't exactly know the terms to describe what I am building. Thanks for telling me!
Hg0428
CC BY-SA 4.0
2023-11-28T06:51:08.727Z
You would need a _global_ cost model, and that is not feasible.  Representing characters with three bits each could very well be faster than the alternative in some cases (in particular, when cache pressure is great).  I would suggest a best-effort approach combined with a concise and convenient mechanism for users to hint representation choices.
Moonchild
CC BY-SA 4.0
2023-11-28T06:55:55.440Z
'most memory efficient type' not necessarily true given your description.  For example, if your RNG state is 128 bits in size, and you generate more than 128 bits of output from it, then it would be more space-efficient to store the RNG state rather than the output from it.  There are parallels to lazy evaluation.
Moonchild
CC BY-SA 4.0
2023-11-28T16:17:46.790Z
@Moonchild I need to determine what the fastest type would be in the given scenario. The case you stated in which the cache pressure is high can be handled with runtime optimizations, but I need something that will tell me the *fastest* type to use for the platform. I can handle balance between raw speed and memory efficiency later with runtime optimizations.
Hg0428
CC BY-SA 4.0
2023-11-29T06:42:08.720Z
Once again, there is no such thing as 'fastest' in isolation; there are always global concerns.  There is no such thing as 'raw speed'.  To give another example, suppose you have a sum type; you could have the opportunity to make accesses to one variant faster than another; making a choice requires frequency information.  Performance is also microarchitectural, not architectural; two CPUs implementing the same architecture could have markedly different performance profiles.
Moonchild
CC BY-SA 4.0
2023-11-29T16:58:42.947Z
@Moonchild I'm really just asking, at the most basic level, is there anything that will tell me for a given type on a given platform, how much a particular operation will cost? I just need something that will give me a vague idea on what types to use for what purposes on what platforms.
Hg0428
CC BY-SA 4.0
2024-02-11T16:12:11.770Z
*"This compels it to store string in a way such that 3 bits are allocated to every character (this is the minimum to represent every possible character)."* ─ Why is it compelled to do this, when the `print` statement will require translating out of that encoding and into (probably) UTF-8 for the actual output? Surely it would be more optimised to build the string in the format it needs to be output in; not just for speed, but also because the re-encoded form is also going to exist in memory.
kaya3
CC BY-SA 4.0
2024-02-11T16:18:13.783Z
More generally, the optimal data structure for some particular data often depends more on what you want to do *with* that data, than on how the data is constrained. So it makes more sense to look at what operations will be performed after the value is constructed, rather than how the value is constructed.
kaya3
CC BY-SA 4.0
2024-03-15T17:23:52.050Z
@Hg0428 You can't know the absolute optimal. Performance of reading and writing to memory on a cached hyper-threaded multicore processor (like all mainstream CPUs) is a function of too much global state. Things that impact it: All currently scheduled threads, exact thread arrangement, branch prediction, stack prediction, cache state, DMA state, memory interface configuration, clock boost state. The best you can manage is a heuristic approximation, and even then its going to be questionable as things depend on the input data as much as fine detail of the representation.
user1937198
<h2>Test suit</h2>
<p>If you plan to compile to LLVM IR, then you can write a small set of programs in LLVM IR to determine what variations of encoding/representation of data are fast for some common operations.</p>
<p>In some new compiling environments, you can then compile, run and cache the result of these probe programs, to then use in your code generation.</p>
<h2>Bigger than necessary types</h2>
<p>C++ defines <code>uint_fast8_t</code> (and other sized ints). You could also inspect how they are defined, or as above, generate probe programs to inspect the sizes/align/stride of these fast variations.</p>
<h2>Align, stride and holes</h2>
<p>As hinted above, &quot;fast&quot; is not only about bigger sized types to avoid bit fiddling, but may involve the alignment and stride of sequential data in memory, even leaving &quot;holes&quot; of unused data between elements.</p>
<p>The probe tests above should also expose as a pair of basic types are layout, after compiling for fast execution. This may be irrelevant if using LLVM as back end, but it will show that optimizing for fast execution really <em>not</em> generates compact representations.</p>

CC BY-SA 4.0
2024-02-11T11:55:56.660Z
2024-02-11T12:10:44.957Z
2024-02-11T12:10:44.957Z
André L F S Bacci
# Determining the most optimized data type for the platform with type inference
Posted by: username_0 on 2023-11-27
For my programming language, I have built an engine that goes after the parser and before the compiler. This engine analyzes, validates, and simplifies the AST.
During the analasys, it determines as much information as possible about each and every variable. So, for each variable, I have a tree representing every possible value  the variable may have at any given point in the program (or just minimum/maximum values (for numbers) and possible elements (for strings) if there is such a pattern).
Because of this, I have the capability to determine the most memory efficient type that stores only the minimum information required to reconstruct the value.
For example, in the following code:
import random

possible = ['a', 'c', 'n', '2', '8', '1', 'o']
string = ""

for i in range(10):
  string += random.choice(possible)

print(string)

(My language does not actually look like Python, this is just an example).
My system would determine that string can only ever have a maximum of 10 characters, and those characters will always be one of ['a', 'c', 'n', '2', '8', '1', 'o'].
This compels it to store string in a way such that 3 bits are allocated to every character (this is the minimum to represent every possible character). It will also note the maximum number of characters (10) and so choose to allocate 10 * 3 = 30 bits (usually 32 because of alignment).
This makes it really memory efficient, but it's not too good for speed because it has to be processed on storing and reading to change it to that type.
I was wondering if there was a way to determine the fastest data type for a particular scenario on a specific platform. I'm new to this, so I'm not sure how to determine which one is best optimized for the platform. Some platforms natively support IEEE 754, some don't. Some have their own data types they want programmers to use. How can I know which will run the fastest?
If it helps, I plan to compile to LLVM IR, though I don't have the compiler done yet.
The language is written in (an interpreter version of) itself, if that's relevant.
**Tags:** types optimization type-inference llvm type-conversion
> **Comments:**
> **username_1**: Oh my bad, I've gotten a bit complacent with assuming new posts are from new users. I know the refinement types thing isn't an answer to the question itself, it's just nice google-able term for what you were describing with keeping track of what values a variable might have.  
> **username_0**: @RydwolfPrograms Ah, that makes more sense. I am the kind of person who knows how to build something, but doesn't exactly know the terms to describe what I am building. Thanks for telling me!  
> **username_2**: You would need a _global_ cost model, and that is not feasible.  Representing characters with three bits each could very well be faster than the alternative in some cases (in particular, when cache pressure is great).  I would suggest a best-effort approach combined with a concise and convenient mechanism for users to hint representation choices.  
> **username_2**: 'most memory efficient type' not necessarily true given your description.  For example, if your RNG state is 128 bits in size, and you generate more than 128 bits of output from it, then it would be more space-efficient to store the RNG state rather than the output from it.  There are parallels to lazy evaluation.  
> **username_0**: @Moonchild I need to determine what the fastest type would be in the given scenario. The case you stated in which the cache pressure is high can be handled with runtime optimizations, but I need something that will tell me the *fastest* type to use for the platform. I can handle balance between raw speed and memory efficiency later with runtime optimizations.  
> **username_2**: Once again, there is no such thing as 'fastest' in isolation; there are always global concerns.  There is no such thing as 'raw speed'.  To give another example, suppose you have a sum type; you could have the opportunity to make accesses to one variant faster than another; making a choice requires frequency information.  Performance is also microarchitectural, not architectural; two CPUs implementing the same architecture could have markedly different performance profiles.  
> **username_0**: @Moonchild I'm really just asking, at the most basic level, is there anything that will tell me for a given type on a given platform, how much a particular operation will cost? I just need something that will give me a vague idea on what types to use for what purposes on what platforms.  
> **username_3**: *"This compels it to store string in a way such that 3 bits are allocated to every character (this is the minimum to represent every possible character)."* ─ Why is it compelled to do this, when the `print` statement will require translating out of that encoding and into (probably) UTF-8 for the actual output? Surely it would be more optimised to build the string in the format it needs to be output in; not just for speed, but also because the re-encoded form is also going to exist in memory.  
> **username_3**: More generally, the optimal data structure for some particular data often depends more on what you want to do *with* that data, than on how the data is constrained. So it makes more sense to look at what operations will be performed after the value is constructed, rather than how the value is constructed.  
> **username_4**: @Hg0428 You can't know the absolute optimal. Performance of reading and writing to memory on a cached hyper-threaded multicore processor (like all mainstream CPUs) is a function of too much global state. Things that impact it: All currently scheduled threads, exact thread arrangement, branch prediction, stack prediction, cache state, DMA state, memory interface configuration, clock boost state. The best you can manage is a heuristic approximation, and even then its going to be questionable as things depend on the input data as much as fine detail of the representation.  
---
## 1 answers
### Answer by username_5 on 2024-02-11. Score: 2 | Accepted answer
## Test suit

If you plan to compile to LLVM IR, then you can write a small set of programs in LLVM IR to determine what variations of encoding/representation of data are fast for some common operations.

In some new compiling environments, you can then compile, run and cache the result of these probe programs, to then use in your code generation.

## Bigger than necessary types

C++ defines `uint_fast8_t` (and other sized ints). You could also inspect how they are defined, or as above, generate probe programs to inspect the sizes/align/stride of these fast variations.

## Align, stride and holes

As hinted above, "fast" is not only about bigger sized types to avoid bit fiddling, but may involve the alignment and stride of sequential data in memory, even leaving "holes" of unused data between elements.

The probe tests above should also expose as a pair of basic types are layout, after compiling for fast execution. This may be irrelevant if using LLVM as back end, but it will show that optimizing for fast execution really *not* generates compact representations.
---
