Re: bugs in queue operations

Taylor R Campbell <[email protected]> writes:

>    Date: Tue, 22 Dec 2009 15:15:25 +0100
>    From: Michael Sperber <[email protected]>
>
>    Taylor R Campbell <[email protected]> writes:
>
>    > Several queue operations have optimistic concurrency bugs because they
>    > don't use provisional readers and writers.  For example, if you call
>    > QUEUE-LENGTH twice in a single transaction without performing any
>    > destructive operations on the queue in the meantime, it should, but
>    > doesn't, return the same answer both times, whether or not other
>    > threads have committed changes to the queue.  The problem is that
>    > QUEUE-LENGTH uses the non-provisional LENGTH.  At the end of this
>    > message is a program demonstrating this bug.
>
>    Thanks for the report - I just pushed a patch (from Robert Ransom -
>    thanks!) to fix the problem.
>
> Hmm...  I have to say that the new implementation looks even more
> complicated than the old one.  Was there a particular reason not to
> use <http://mumble.net/~campbell/darcs/scheme-cml/s48-optimistic-queue.scm>?
> I wrote it specifically to be compatible with the existing interface,
> and to my mind at least it seems simpler and easier to reason about,
> but maybe that's just because I wrote it.

Yours and the one in place seem pretty much equivalent, in terms of the
changes you made.  Robert's code addresses a few more concerns than
yours, namely, the fact that proposals and exceptions don't interact
well. Robert's implementation is also a bit more in line with the coding
style of the stuff around it.  (It also helped that he sent me a
Mercurial bundle, which as easier for me to integrate.)

> I also notice that the new code discusses performance of the various
> queue operations.  Have you considered replacing it by a functional
> data structure, and storing it in a cell, to reduce the number of
> provisional references to a queue per transaction from O(f) to O(n
> |---> 1), as a function of the number of memory references performed
> by queue operations in the transaction?

Not yet, but it's probably the way to go at some point.

-- 
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla