search

beanlab / quest_framework

A Python framework for fault-tolerant workflows
0 stars 0 forks source link

Convert PersistentHistory to a linked list #23

Open ABCambridge opened 4 months ago

ABCambridge commented 4 months ago

As described in the comment in the __init__() method of PersistentHistory in persitence.py, we should change its implementation to be a linked list, rather than an array. Here is a copy of the comment from the code:

# TODO - use linked list instead of array list
        # master stores head/tail keys
        # each blob is item, prev, next
        # only need to modify blobs for altered nodes
        # on add/delete, and rarely change master head/tail blob
ABCambridge commented 3 months ago

@byubean I am looking at what this would actually be like to implement and am wondering if we'll want a dictionary from key node pointer so that we can get to a specific item in constant time. Is that the type of thing we need? If the History is only accessed in order (say from the tail), then it probably would be fine to have it just start searching from the tail, but I wasn't sure if there is a case when we need to jump straight to a node in the middle.

byubean commented 3 months ago

The history is modified by the prune function in historian.py.

When a step completes, then all sub-step records can (must) be removed from the history (as the outer step will no longer run and the sub steps will never be encountered).

The goal is make this sort of modification of the history efficient. The two parts to this are:

End goal:

ABCambridge commented 3 months ago

Got it! That makes sense. Thank you!

ABCambridge commented 3 months ago

@byubean If if efficiently pruning is the goal with using a linked list in the PersistentHistory, then I expect that I will write a private routine that creates an array of items from the linked list in order to provide the functionality required by __iter__() and __reversed__(). Does that sound right to you?

brazilbean commented 3 months ago

You can implement iter and reversed with a linked list. Just loop through the nodes and yield On Mar 8, 2024 at 4:43 PM -0700, ABCambridge @.***>, wrote:

@byubean If if efficiently pruning is the goal with using a linked list in the PersistentHistory, then I expect that I will right a private routine that creates an array of items from the linked list in order to provide the functionality required by iter() and reversed(). Does that sound right to you? — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you are subscribed to this thread.Message ID: @.***>

ABCambridge commented 3 months ago

I think this is complete! It appears to be working well with main.py. My only question is if we should be checking if a key exists before trying to take it out of the persistent history in the _remove_node method. I don't think there were any checks made in the previous version.

ABCambridge commented 3 months ago