Re: bugs in queue operations

   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.

By the way, the patch introduced some mixed spaces and tabs, in case
you care about making the whitespace consistent.

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?