Fast inverse lookup

[Involture]

Hi,

Thank you for your work !

Having a background in computer science, I quickly envisionned a high level language that would compile to mindustryLogic. I then stubble upon your work and I have to say I am in awe. I couldn't have done better. Every design choice is exactly the one I would have done and it is wonderfully executed. If I may ask, I am quite interested to know your academic background and how long mindcode took to develop.

The inverse lookup problem

Coming back to the issue, I have a piece of code I want to optimise. It uses several (understand a linear amount) inverse item lookups. I have some ideas as how I could get rid of them but it would be quite cumbersome and clutter the code.

There is no native inverse lookup that I know of and the complexity of an implementation is thus always linear. However, the constant factor is quite significant in my case.

My implementation in mindustry logic

I though of a way to implement the inverse lookup that I think has the lowest average complexity in time, at the cost of taking a linear (in the number of item/etc.) lines of code. Please find below an implementation of an inverse item lookup in mindustry logic. It is troncated for brievety.

sensor itemType unloader1 @config
set startCounter @counter
    jump 5 notEqual itemType @copper
    set endCounter @counter
    jump ilend always
    jump 8 notEqual itemType @lead
    set endCounter @counter
    jump ilend always
    jump 11 notEqual itemType @metaglass
    set endCounter @counter
    jump ilend always
    jump 14 notEqual itemType @graphite
    set endCounter @counter
    jump ilend always
    [...]
ilend:
    op sub temp endCounter startCounter
    op sub temp temp 2
    op idiv itemIndex temp 3
    print itemIndex
    printflush message1

As you can see, it uses the instruction pointer to save an incrementation instruction while iterating through item types. Thus the average complexity of this code (omitting the first sensor and print statement) is :

Let N be the number of entries to test against

• one jump for each jump until the index is found : avg(index + 1) = (N + 1) / 2
• Other single instructions including : -- Reading the instruction pointer at the start : 1 instruction -- Reading the instruction pointer when the index is found : 1 instruction -- Computing the index from these values : 3 instructions

Hence the final average complexity of N / 2 + 5.5 instructions

A naive approch with mindcode

In comparison, I tried to implement the inverse lookup in mindcode with a simple for loop and optimization on. Here is the code I gave the compiler :

itemType = unloader1.config

for i in 0 ... 16
    it = lookup(item, i)
    if it == itemType
        break
    end
end

print(i)
printflush(message1)

And the resulting mindustry logic code, truncated for brievty :

sensor itemType unloader1 @config
set i 0
lookup item it 0
jump 50 equal it itemType
set i 1
lookup item it 1
jump 50 equal it itemType
op add i 1 1
lookup item it 2
jump 50 equal it itemType
op add i 2 1
lookup item it 3
jump 50 equal it itemType
op add i 3 1
lookup item it 4
jump 50 equal it itemType
[...]
print i
printflush message1
end

Which is an impressive display of code optimization already. However, without the instruction pointer trick, I believe the average complexity of this code is 3N / 2.

Conclusion

If I didn't make any mistake and if you agree with my analysis, do you know of a way to produce the faster code with mindcode ? If you think there is none, would you consider implementing a standard library function to perform the inverse lookup ? It should use the instruction pointer trick when expanded. When the available lines are scarce, it would follow the current behavior and default to a folded loop.

If you think that this is interesting but do not wish (or have) the time to implement this, I would gladly submit a pull request. I am not familiar with java but I understand the inner workings of a compiler quite well. I don't think it would take me much more than a day of work.

I do believe that this instruction pointer trick a wider range of for loops, albeit very specific ones. I do not know if implementing this optimization in more cases would be useful though.

[Involture]

I found the answer to my issue just after submitting it. Here is some mindcode producing the optimized code :

itemType = unloader1.config

print(fastInverseItemLookup(itemType))
printflush(message1)

def fastInverseItemLookup(itemType)
    startCounter = @counter
    for it in (
        @copper,
        @lead,
        @metaglass,
        @graphite,
        @sand,
        @coal
    )
        if itemType == it
            endCounter = @counter
            break
        end
    end
    return (endCounter - startCounter - 2) \ 3
end

I think it may still be interesting to implement the inverse lookup as a standard library function. That way the loop can stay folded when available lines are scarce.

[Involture]

I had the intuition that this code wouldn't be robust because it depends heavily on a step of three lines between test jumps. And indeed it broke when I replaced the equal with a strictEqual. One more reason to make it a stdlib function

[Involture]

I feel stupid now that I realize that the inverse lookup is implemented in the form of the id property in the sensor function. Issue closed

[cardillan]

Sorry, I was away for the weekend and couldn't respond earlier.

I'm really grateful for your feedback and I'm glad you find Mindcode useful! This project was created by @francois, who designed the Mindcode syntax, created the parser and compiler and came up with a lot of ideas, so there already was a huge foundation to build upon. As for me, while I do have a bachelor's degree in IT, I work as a developer in an unrelated field and this is just a hobby project. I haven't tracked the time I've spent on it, but I'd say it certainly goes to many tens of mandays. What can I say - it was fun :)

Regarding the id property, there's no need to feel stupid - this feature is easy to overlook. I currently don't aim to document how the Mindustry Logic itself works (unlike, for example, the mlogjs project), and while I hope all Mindcode functionality is documented to some extent, the documentation is far from well organized. Furthermore, the inverse lookup was actually missing from Mindustry Logic for a long long time.

I was intrigued about your use of the @counter value. I think it unfortunately doesn't provide an advantage over a solution based on indexes, which is a pity really - I'd love to use a trick like this! If we modify your last example this way:

itemType = unloader1.config

print(fastInverseItemLookup(itemType))
printflush(message1)

def fastInverseItemLookup(itemType)
    i = 0
    for it in (
        @copper,
        @lead,
        @metaglass,
        @graphite,
        @sand,
        @coal
    )
        if itemType == it
            return i
        end
        i += 1
    end
    return -1
end

we see the compiled code of the loop is structurally identical to the one generated from your example, but instead of saving the @counter value, an index is maintained. This avoids the need to compute the actual index from the value of the counter at the end, meaning the code is overall both shorter and faster.

As I already said, I'm grateful for your feedback, so please don't be discouraged! I hope to be able to work on Mindcode again in the coming weeks - and I'll be glad to hear about any ideas you might have.