Re: [Twisted-Python] Re: [Twisted-commits] Today is screw with twisted's guts day.

Nov. 19, 2003

      On Wed, Nov 19, 2003 at 08:12:56PM -0500, Jp Calderone wrote:
...
On Thu, Nov 20, 2003 at 11:53:19AM +1100, Andrew Bennetts wrote:
[patch to keep count of items used from the list]
That looks a little more complex than it needs to be.  What about this
version?
def runUntilCurrent(self):
        """Run all pending timed calls.
        """
        if self.threadCallQueue:
            calls, self.threadCallQueue = self.threadCallQueue, []
            for (f, a, kw) in calls:               
                try:
                    f(*a, **kw)
                except:
                    log.err()
Yeah, that looks ok too, I think.  I'm less certain though... is it possible
for this to happen:

     reactor thread                 other thread
     --------------                 ------------
                                    call callFromThread
                                      ...get reference to self.threadCallQueue
     call runUntilCurrent
       ...set self.tCQ to a new list
       ...do for loop
                                      ...append to now old threadCallQueue

So that again, a call can go missing?  Hmm, I think this is possible, so
that version is also bad.  It's also harder to reason about than my patch --
I had to disassemble it to help me think about it :)
...
I considered doing it this way first, but wasn't sure if anyone relied on
the identity of threadCallQueue (not that anyone should, but one never
knows).  If anyone thinks changing its identity should be avoided, I'd like
this version:
def runUntilCurrent(self):
        """Run all pending timed calls.
        """
        if self.threadCallQueue:
            calls = self.threadCallQueue[:]
            del self.threadCallQueue[:]
            for (f, a, kw) in calls:
                try:
                    f(*a, **kw)
                except:
                    log.err()
That's definitely racy!  What if the call to callFromThread happens between
the "calls = ..." and the del statement?

A version which does
    calls = self.threadCallQueue[:]
    del self.threadCallQueue[:len(calls)]

Should be ok though, for the same reason my patch is (or at least I think it
is :)

The main difference between that version and my is this one involves a small
list copy, but it might still be faster than executing "count += 1" on every
loop iteration.  Either way, it's at the point where I don't care :)
...
I suppose reverting it entirely is an option, seeing as how no one has yet
*actually* been bitten by the quadratic behavior (nor does it seem likely
that anyone will be), but all other things equal, it's nicer to use O(N)
algorithms deep down in the guts of Twisted than to use O(N**2) algorithms.
I think I'd like to see it improved to have O(N) complexity too.

-Andrew.