Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Don't use a stack by default #14

Open
Lonami opened this issue Jan 10, 2021 · 3 comments
Open

Don't use a stack by default #14

Lonami opened this issue Jan 10, 2021 · 3 comments

Comments

@Lonami
Copy link
Owner

Lonami commented Jan 10, 2021

Split off https://github.com/Lonami/pyndustric/pull/12/files#diff-852dce7acd90bf3bfbde1cec63522f7204b9c209cc52b3e40d23bb6f3202ef7fR29.

Given mlog's infinite "registers", the stack is only necessary when/if we do recursion. And even then, the stackless approach could be applied by default unless recursion is detected.

For this, we'll likely have one special register for each function that indicates where to jump back (like __pyc_function_ret). Loading parameters is simply a set into the parameter names (to address https://github.com/Lonami/pyndustric/pull/12/files#diff-852dce7acd90bf3bfbde1cec63522f7204b9c209cc52b3e40d23bb6f3202ef7fR330).

@TelosTelos
Copy link
Collaborator

I wonder if it would be better for us to offer a sort of simple stack data structure? E.g. compiling memory1.push() and memory1.pop() commands into operations that modify a stack-pointer variable, and read/write from that memory block? For me at least, mlog seems laggy enough that I wouldn't want to live with all the delays that using a stack to do full-fledged recursion would take, but I'd be quite happy to use an efficiently implemented stack with an intuitive interface to accomplish the same purposes I could have used recursion for.

It wouldn't be that hard to implement a list data-structure either, using an associated memory block. But any O(n) list operations (like inserting or deleting in the middle of the list) would likely end up excruciatingly slow. (Stacks are much more efficient, since no stack operation bothers with the stuff buried down in the stack.)

@Lonami
Copy link
Owner Author

Lonami commented Jan 11, 2021

Perhaps we could have a fancy way of doing the following:

memory = [] @ cell1
memory.append(1)
memory.pop()

But then again cell1 can be implicit and we just need to support append/pop. If we're able to track the size at all times, we won't need to store any actual counter in a variable, and can insert constants to access the memory in mlog. But I feel like this won't be easy.

@TelosTelos
Copy link
Collaborator

I would probably implement this object-orientedly, making memory blocks like memory1 have .push() and .pop() methods. Would be trivial to implement. Alternatively, it might make sense to have some sort of Stack( memoryblock, starting_slot) object constructor, which could free the user to situate a stack somewhere other than block[0] in a memory block, e.g., if you wanted to situate multiple smallish stacks within a single memory block.

One potentially tricky issue with these is that memory blocks can be accessed by multiple processors, so it may make sense to store things like the stack pointer in the memory block itself, so that multiple processors can all use it. E.g. one processor could push onto a communal stack things that require processing, and multiple other processors could pop items off the stack and take care of processing them in parallel. (Communal stacks would require a couple more instructions for each push/pop though, to retrieve and re-store the stack pointer in the memory block.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants