5
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – rydwolf
    Commented Nov 27, 2023 at 21:00
  • $\begingroup$ @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! $\endgroup$
    – Hg0428
    Commented Nov 27, 2023 at 21:06
  • 2
    $\begingroup$ '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. $\endgroup$
    – Moonchild
    Commented Nov 28, 2023 at 6:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Moonchild
    Commented Nov 29, 2023 at 6:42
  • 2
    $\begingroup$ 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. $\endgroup$
    – kaya3
    Commented Feb 11 at 16:18

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .