FilterStore: "get" only triggered after a "put" if first element in the store matches filter.

Issue #49 resolved
Stefan Scherfke
created an issue

Test case:

def putter(env, store):
    yield store.put(2)
    print('Put 2 at', env.now)
    yield env.timeout(1)
    yield store.put(1)
    print('Put 1 at', env.now)

def getter(store, value):
    yield store.get(lambda i: i == value)
    print('Got', value, 'at', env.now)
    env.exit(env.now)

env = simpy.Environment()
store = simpy.FilterStore(env, capacity=2)
proc_1 = env.process(getter(store, 1))
proc_2 = env.process(getter(store, 2))
env.process(putter(env, store))
env.run()
assert proc_1.value == 1
assert proc_2.value == 0

Expected output:

Put 2 at 0
Got 2 at 0
Put 1 at 1
Got 1 at 1

Actual output:

Put 2 at 0
Put 1 at 1
Got 1 at 1
Got 2 at 1
AsertionError: assert 1 == 0

Thanks to Andreas Beham for reporting the issue.

Comments (8)

  1. Ontje Lünsdorf

    Shouldn't this testcase also work? I think that is a little bit clearer. Currently it should break at yield get_foo.

    yield store.put('foo')
    get_bar = store.get('bar')
    get_foo = store.get('foo')
    
    # get_foo can trigger immediately.
    assert (yield get_foo) == 'foo'
    
    # get_bar needs to wait until bar is really put into store.
    yield store.put('bar')
    assert (yield get_bar) == 'bar'
    
  2. Ontje Lünsdorf

    To elaborate my suggestion on the mailinglist, it may be as simple as pushing the decision when to stop examining the queues into the appropriate _do_get resp. _do_put methods. These methods are overridden by the individual resource types and those should know better when there's no need for evaluating the queue any further.

    For example the current code of _trigger_get:

    for get_event in self.get_queue:
        if not get_event.triggered:
            self._do_get(get_event)
            if not get_event.triggered:
                break
    

    might only be changed to:

    for get_event in self.get_queue:
        if not get_event.triggered:
            if not self._do_get(get_event):
                break
    

    All _do_get need now to add the following return statement: return not get_event.triggered. Only FilterStore needs to always return True.

    I hope this helps.

  3. Stefan Scherfke reporter

    Another possiblitiy would be to fix the FilterQueue that is used as FilterStore.get_queue. It already implements __getitem__ and __bool__ in a way that they only take events into account for which there is an item in the store. However, both of these methods are ignored by the current resource implementation, so it’s totally broken. To fix this, instead of __getitem__ and __bool__, we need to override __iter__ to return an iterator that only contains event for which there is an item in the store:

        def __iter__(self):
            if not self.store.items:
                # No items in the store, no event can be triggered.
                # Return an empty generator:
                return (i for i in range(0))
    
            # Only the newest item in the store may be interesting for an event:
            return (self[i] for i in range(len(self))
                    if self[i].filter(self.store.items[-1]))
    

    This fixes the issue with a lot less code to change. Also, it’s not very expensive (computationally).

    However, the code is rather ugly than beautiful and not very easy to read and understand. But maybe, it’s good enough to solve thips special problem.

    Your idea, @Ontje Lünsdorf , is more general and may make live easier for other people implementing special kinds of resources. However, a lot more code (with a lot more repeated lines of code) is necessary here, because we have to copy return not event.triggered into every ressource's _do_put() and _do_get() methods. So I’m not sure if this solution is to prefer, either.

    To sum up:

    • Ontje pro: More general solution that may pay of for other, new resource types.
    • Ontje con: Duplicated/copied code in a lot of places.

    • Stefan pro: Only fixes the problem we actually have with minimum amount of code and no duplicated code.

    • Stefan con: Quite hacky and maybe hard to understand for new users.

    What do you think?

  4. Ontje Lünsdorf

    Good thinking! Your solution is conceptually much better. But the execution is poor (why don't you use a generator for __iter__()?).

    Take a look at this implementation of your idea. This even has the benefit of allowing to access the raw _queue which was previously hidden at least by __getitem__. I also removed methods which seem not to be used anymore. All tests including the above example pass (I didn't check Python 2, though).

    class FilterQueue(object):
        """A queue that lists only those events for which the store's item queue
        contains matching items."""
    
        def __init__(self):
            super(FilterQueue, self).__init__()
            self._queue = []
            self.store = None
    
        def append(self, evt):
            self._queue.append(evt)
    
        def remove(self, evt):
            self._queue.remove(evt)
    
        def __iter__(self):
            for evt in self._queue:
                for item in self.store.items:
                    if evt.filter(item):
                        yield evt
    
  5. Stefan Scherfke reporter

    My __iter__ does return a generator expression. However, since the old implementation inhered list (your code :-P), I kept it as it was. You new proposed implementation with composition (instead of inheritance) is much better though. I’ll make a pull request asap.

  6. Log in to comment