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

[Andrew Bennetts]

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.