0
$\begingroup$

I am implementing a WASM backend and I hope to optimize the size.

I have collected a series of static data. After erasing the type, it can be simply considered as list<u8>.

However, these data may be repeated or partially covered. I hope to find a way to arrange them, so that the overall size will reduce.

In other words, such a transformation:

list<list<u8>> -> (data: list<u8>, span: list<(start: u32, length: u32)>)

But I don't know how to achieve this efficiently. And is there a special name for this kind of optimization?

$\endgroup$
4
  • 3
    $\begingroup$ It is not clear to me that this is really a question about programming languages, at least without adding more details. As asked, it seems like you are just asking about lossless data compression, which is a rather vast field of its own. Can you clarify what sorts of things you have in mind? $\endgroup$
    – Alexis King
    Dec 6, 2023 at 12:21
  • 2
    $\begingroup$ Assuming I understand correctly, you want to produce a shortest string (of bytes) which contains all of the desired substrings. This is a variant of the travelling saleman problem on a directed graph, where edges have lower weights when the overlap between the two strings is greater. I agree with Alexis; this problem isn't really specific to PLs, it's the kind of thing I'd expect to see in an algorithms textbook. Chances are, for a compiler the possible space savings are small, and for performance it's probably more important to have word-aligned pointers. $\endgroup$
    – kaya3
    Dec 6, 2023 at 14:26
  • $\begingroup$ Related question on Stack Overflow $\endgroup$
    – dan04
    Dec 6, 2023 at 17:50
  • $\begingroup$ I think it is impossible to provide an adequate answer without knowing anything about the source language or how much you can influence its semantics or that of core types. $\endgroup$
    – feldentm
    Dec 6, 2023 at 19:58

1 Answer 1

3
$\begingroup$

Compression algorithms

Data compression is about finding repeated data of arbitrary size inside bigger sequential data.

You may not store the data in compressed form, but the dictionary-building stage of most compression algorithms are well-studied part of computer sciences.

I suggest starting with classical compression formats like LZW and BWT.

The BWT in particular can be extremely efficient in finding all substrings in a string, as its algorithm "generates" all rotations of input string and compares all rotations: any two or more rotations that compare equals more than one "letter" is repetition or a substring.

$\endgroup$

You must log in to answer this question.

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