Global Integer Compressor System

[khopesh]

Overview

Examples

Code

Usage

Table

Commonly in the bits of the integers space exists that is not being used, with this we can get the most out of each integer creating a pocket array that allows us to store new data. It can also be seen as preventing leaks at the bit level because compressing variables and therefore not using them can be interpreted as destroying or deleting them from memory. Otherwise, without this algorithm, you would have to use more variables in memory. Compression, leaks, bitmasking regardless of we see it will allow you reduce to 32KB per MB of boolean variables and from 512KB to 51,2KB per MB of integer variables.

Let's say we have a map with 12 players and stores 6 posible states in a global integer variables for each of the players, with values ranging from 0 to 5. Looking at the table, we can replace by only 1 integer variable.
Without gics, we would use (32 bits)(12) = 384 bits in global variables.
With gics, we would use (32 bits)(1) = 32 bits in global variables.
we would have a 1100% resource saving.

Another potential case is if we had global booleans (Blizzard uses 32 bits) and wanted to use gics. Looking at the table, we could compress 32 global booleans into 1 global integer.
Without gics, we would use (32 bits)(32) = 1024 bits in global variables.
With gics, we would use (32 bits)(1) = 32 bits in global variables.
we would have a 3100% resource saving.

JASS

GUI

Lua

function gics takes integer index, integer newvalue returns integer
    local integer m = //maximun integer value//
    local integer a = 1
    local integer b = m + 1
    if index > 0 then
        loop
            exitwhen a > index
            set b = b * (m + 1)
            set a = a + 1
        endloop
    endif
    set a = (YourGlobal + 2147483648) / b
    set a = YourGlobal + 2147483648 - b * a
    set a = a / (b / (m + 1))
    if newvalue < 0 then
        return a
    else
        set YourGlobal = YourGlobal + (newvalue - a) * (b / (m + 1))
        return 0
    endif
endfunction

globals
 
    integer YourGlobal = -2147483648

endglobals

• gics
  • Events
    • Player - Player 1 (Red) Presses the Escape key
  • Conditions
  • Actions
    • -------- this for set -------- replace every 5.00 for your maximun integer value, every 2.00 for you index, and located in the Set Variable action the 3 for the newvalue of the index --------
    • For each (Integer A) from (((YourGlobal + (32768 x 65536)) mod (Integer((Power((5.00 + 1.00), (2.00 + 1.00)))))) / (Integer((Power((5.00 + 1.00), 2.00))))) to (Integer A), do (Actions)
      • Loop - Actions
        • Set YourGlobal = (YourGlobal + ((3 - (Integer A)) x (Integer((Power((5.00 + 1.00), 2.00))))))
    • -------- this for get -------- replace every 5.00 for your maximun integer value, every 2.00 for you index, (Integer A) is the output --------
    • For each (Integer A) from (((YourGlobal + (32768 x 65536)) mod (Integer((Power((5.00 + 1.00), (2.00 + 1.00)))))) / (Integer((Power((5.00 + 1.00), 2.00))))) to (Integer A), do (Actions)
      • Loop - Actions
        • Game - Display to (All players) the text: (String((Integer A)))

As is usually the case in GUI, practicality are prioritized over efficiency for rapid application development. Both For loops are the same, so you only need to configure one and replace the other(for that specific index), this current configuration take 5 as maximun integer value, and 2 as index, saving a value of 3 in these index. This sample trigger is configured to print that value, checking that it has been saved. Instead of the action of Game Display Text you can use it for any of your actions, using (Integer A).

• Map initialization
  • Events
    • Map initialization
  • Conditions
  • Actions
    • Set YourGlobal = (-32768 x 65536)

GUI map template

function gics(index, newvalue)
    local m = --maximun integer value--
    local a = 1
    local b = m + 1
    while a <= index do
        b = b * (m + 1)
        a = a + 1
    end
	a = (YourGlobal + 2147483648) // b
	a = YourGlobal + 2147483648 - b * a
	a = a // (b // (m + 1))
    if newvalue < 0 then
        return a
    else
        YourGlobal = YourGlobal + (newvalue - a) * (b // (m + 1))
        return 0
    end
end

YourGlobal = -2147483648

The values of the integers that it can store range from 0 up to the //maximun integer value//, which will be configured as needed. From this maximum value, a range of indices will be obtained, also starting at 0 (like an array). The number of these indices will be inversely proportional to the maximum integer value, according to the Table.
gics("index", "newvalue")
to use for set
"index"=0,1,... // as far as possible according to the table
"newvalue"=0,1,... // as far as possible according you maximum integer value
ex: gics(0, 4)
for get
"index"=0,1,... // as far as possible according to the table
"newvalue"<0 // It doesn't matter, just put a negative number.
ex: gics(0, -1)
output:4 // if you did it as in the previous example
You can expand its use for different maximum integer values by adding argument and conditional to differentiate them, then the function take another global integer variable and another maximum integer value. Alternatively, you can copy the function with a different name and modify the two parameters mentioned.

maximun integer value=#values-1
max index=array lenght-1

#values (0 to maximun integer value)	array lenght (0 to max index)
2	32
3	20
4	16
5	13
6	12
7	11
8-9	10
10-11	9
12-16	8
17-24	7
25-40	6
41-84	5
85-256	4
257-1625	3
1626-65536	2

 

[Luashine]

Correct application of mathematical principles and algorithms in programming.
Incorrect application of software engineering

Jass is very slow to execute. Any function calls are not worth it. Lua is faster and yet this is not worth it.
Any memory savings will be eaten up by the additional source code letters (lol!).

The only use-case I can imagine is either a packed data integer inside unit's custom value or for save-load systems to reduce save code size. Although this has become nearly irrelevant, because Preloads allow for automatic save-load now.

PS: keep going

 

[khopesh]

Correct application of mathematical principles and algorithms in programming.
Incorrect application of software engineering

Jass is very slow to execute. Any function calls are not worth it. Lua is faster and yet this is not worth it.
Any memory savings will be eaten up by the additional source code letters (lol!).

The only use-case I can imagine is either a packed data integer inside unit's custom value or for save-load systems to reduce save code size. Although this has become nearly irrelevant, because Preloads allow for automatic save-load now.

PS: keep going

Hello greetings, about the algorithm it's not restricted to JASS; you can use it in any programming language, including Lua. I didn't include it in Lua because I'm not familiar with the language. If you can translate the code in Lua, I'd appreciate it, as it's not a very long code snippet. Perhaps someone will find it useful.

 

[Lizreu]

it's really just not worth it, not even on 2002 hardware. how many global variables can you have? 100? 1000? 10000? even in the worst case you're only saving a few hundred KB. it's a sound idea, but like Luashine points out, you're applying it to the wrong place. but integer packing isn't a novel idea, everywhere where it matters people already do it, it just doesn't matter all that often

 

[khopesh]

it's really just not worth it, not even on 2002 hardware. how many global variables can you have? 100? 1000? 10000? even in the worst case you're only saving a few hundred KB. it's a sound idea, but like Luashine points out, you're applying it to the wrong place. but integer packing isn't a novel idea, everywhere where it matters people already do it, it just doesn't matter all that often

Well, you have to see it as another way to prevent leaks. Except that these are quantized in the same bit architecture, creating a pocket array, keep in mind that the more global variables you have, the greater the compression will be. I'm going to try to learn a bit of Lua to implement it, as a GUI as well; and simplify the table with limit values to also expand the compression range.

 

[khopesh]

GUI version added, with template map to be able to copy and paste actions
--------------------------------------
updated, added LUA version

 

[Dr Super Good]

This seems like an incorrect target of optimisation. Memory usage from global variables is usually very small compared with other state and is almost universally considered a non-issue. Additionally the one case where one might want to use it, bit fields for packing booleans, it does not implement efficiently.

Modulo is one of the most expensive arithmetic operations for a computer to perform. It is so expensive that in industry a lot of research has gone into trying to find ways to reach as good as the same answer without touching modulo or its slightly faster but still very slow regular division operator. This is why you seldom see this principle of arbitrary number ranges being used to compress data in industry, instead with "powers of 2" being used.

When the number ranges are powers of 2, a specific set of optimisations opens up turning such packing from being extremely slow to very fast. This is because expensive operators like modulo and division can be replaced with very fast bitwise operators. These are so fast that time savings from improved data density can outdo the extra cycles needed to extract or save individual values. Despite advertising the advantage of this, such as to packing 32 booleans in a single integer, your code does not have a code path using these optimisations, instead keeping to use the very slow modulo approach. Old JASS lacks native bitwise operators but these were added with Reforged and are a basic language feature of Lua.

The principle shown here is also already widely known in Warcraft III, as it formed one of the core features of a traditional code-based save/load system. As the code length had a high cost (people literally had to write it down character by character), this was very effective. I recall some developers (possibly HINDYhat?) created systems just for this purpose. Such systems were a lot more capable than shown here, working internally on a bitfield larger than 32 bits that was backed by an array of 32 bit ints, as well as implementing the required arbitrary bit size operators. The output was even arbitrary base encoded allowing more than 64 characters to encode data even more efficiently. There were issues with scaling though (arbitrary size operators generally have poor complexity, especially that pesky modulo), but for the purposes of a chat based save/load systems these were generally not an issue and the compression it allowed was impressive.

With file I/O based save/load systems we use now, this use case has largely died out. You will be better off using the industry standard powers of 2 along with base 64 encoding as these still give a lot of the benefits of the old system but operate orders of magnitude faster, something that is important given how much more data can be trivially saved/loaded.

Well, you have to see it as another way to prevent leaks.

Global variables are static, so cannot infinitely leak memory?

 

[khopesh]

@Dr Super Good Yes I understand the confusion; in the forum, at least 10% of all the topics make some reference to or concern about leaks. A leak can be seen as data stored in memory that is unnecessarily there without being used. This compression does almost the same thing; there is space (which can store data) in the bits of the integers that are not being used. This way we can use everything in each integer while preventing leak at bit level; there is nothing more meticulous than that. The methods (the little function mics) for using them are not running over and over again as a permanent running state, only when needed. Of course, I'm not trying to get anyone to use it if they're not willing because the resources are for the people who find them useful

 

[Dr Super Good]

"Leak" has a well defined meaning in Computer Science.

Resource leak - Wikipedia

en.wikipedia.org

In computer science, a resource leak is a particular type of resource consumption by a computer program where the program does not release resources it has acquired.

Memory leak - Wikipedia

en.wikipedia.org

In computer science, a memory leak is a type of resource leak that occurs when a computer program incorrectly manages memory allocations[1] in a way that memory which is no longer needed is not released. A memory leak may also happen when an object is stored in memory but cannot be accessed by the running code (i.e. unreachable memory).

What you are describing cannot be a leak since the memory involved is statically allocated so not subject to allocation or being released during runtime. What you are describing sounds a lot like program optimisation.

Program optimization - Wikipedia

en.wikipedia.org

In computer science, program optimization, code optimization, or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources.

You are trying to make scripts use less memory (memory is a resource). As mentioned in the "Trade-offs" section, optimisations can trade 1 aspect of performance for another. In this particular case you are optimising for memory usage at the cost of execution time. This is generally not considered worth it for heap memory, especially using such a slow algorithm. It was considered worth it for save/load codes in the past due to the high cost of each character in the code.

 

[khopesh]

@Dr Super Good I understand your point of view, but I already answered that. I understand you want to explore the topic further, but it's just another resource available for anyone who wants to use it. That's the purpose of the topic. But please feel free to give your point of view or discuss the topic with anyone in this thread.