Re: bugs in queue operations
Robert Ransom <[email protected]> Thu, 24 Dec 2009 11:59:09 -0800
| Newsgroups | gmane.lisp.scheme.scheme48 |
|---|---|
| Message-ID | <[email protected]> |
On Tue, 22 Dec 2009 15:53:56 +0100 Michael Sperber <[email protected]> wrote: > 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. It's certainly not as easy to understand as it needs to be, largely because I didn't use enough utility functions; I think I've fixed that now (see the attached bundle). > > 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. No -- he made the queue record's HEAD field immutable and stuck an extra pair at the beginning of the queue's list, so that queue operations only need to modify cdrs and the queue's TAIL field. His data structure allows all queue mutations to be performed through two functions, one to insert elements and one to remove them (NULLIFY-CDR! is a special case of COPY-CDR!). > Robert's code addresses a few more concerns than > yours, namely, the fact that proposals and exceptions don't interact > well. No -- his DEQUEUE! is careful to throw its exception outside its proposal. In any case, the fact that proposals and exceptions don't interact well is really more of a bug in the proposal system -- the current proposal should probably be part of the dynamic environment, rather than an attribute of the thread. > 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.) For future reference: $ wget -o scheme/big/queue.scm URL-OF-CAMPBELL'S-QUEUES-IMPLEMENTATION $ hg commit -m 'Import Taylor Campbell's replacement for the QUEUES package.' And keeping the coding style consistent is rather less important than keeping bugs out. > > 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? Yes, when I was still thinking about ways to optimize DELETE-FROM-QUEUE!. Our mutation-based queue implementations allow both ENQUEUE! and DEQUEUE! to be implemented in constant time; I am not aware of any functional data structures which would allow this. I have attached to this message a bug-fix patch for Taylor Campbell's queue package, and a Mercurial bundle for Scheme 48 that simplifies my QUEUES package and then changes it to use his data structure. Both revision 9d81f8fb4bef and revision d6d3adc25cf6 compile and pass their test suites. Robert Ransom
rransom-campbell-scheme-cml-patch-2009-12-24-01.diff
(text/x-patch, 4.6 KB)
diff -x _darcs -x '*~' -r -U 5 campbell-scheme-cml/s48-optimistic-queue.scm campbell-scheme-cml-work-2009-12-22-01/s48-optimistic-queue.scm
--- campbell-scheme-cml/s48-optimistic-queue.scm 2009-12-22 10:54:29.215986501 -0800
+++ campbell-scheme-cml-work-2009-12-22-01/s48-optimistic-queue.scm 2009-12-22 12:45:31.212104678 -0800
@@ -179,19 +179,22 @@
(define (delete-from-queue! queue element)
(delete-from-queue-if! queue (lambda (element*) (eq? element* element))))
(define (delete-from-queue-if! queue predicate)
- (call-ensuring-atomicity!
+ (call-ensuring-atomicity
(let ((front (queue.front queue)))
(lambda ()
(let loop ((pair front))
(let ((tail (provisional-cdr pair)))
(if (pair? tail)
(if (predicate (car tail))
- (copy-cdr! pair tail queue)
- (loop tail)))))))))
+ (begin
+ (copy-cdr! pair tail queue)
+ #t)
+ (loop tail))
+ #f)))))))
(define (queue-length queue)
(call-ensuring-atomicity
(let ((front (queue.front queue)))
(lambda ()
@@ -210,18 +213,33 @@
(let ((tail (provisional-cdr pair)))
(if (pair? tail)
(loop tail (cons (car tail) list))
list))))))))
-(define (queue->list! queue)
+(define (queue->provisional-list! queue)
(call-ensuring-atomicity
(let ((front (queue.front queue)))
(lambda ()
(let ((list (provisional-cdr front)))
(nullify-cdr! front queue)
list)))))
+(define (queue->list! queue)
+ (call-with-values
+ (lambda ()
+ (queue->provisional-list! queue))
+ (if (current-proposal)
+ (lambda (list)
+ ;; We are running within a larger transaction, so LIST must
+ ;; be traversed using PROVISIONAL-CDR. The caller expects
+ ;; this procedure to return a list it can traverse using
+ ;; CDR, so we need to make a new one.
+ (let loop ((list list))
+ (cons (car list)
+ (loop (provisional-cdr list)))))
+ (lambda (x) x))))
+
(define (list->queue list)
(if (pair? list)
(let ((front (cons 'SENTINEL '())))
(let loop ((pair front) (list list))
(if (pair? list)
@@ -229,29 +247,33 @@
;; effects, not visible to any thread but the current one
;; until LIST->QUEUE returns. But CAR and CDR mean you
;; can't pass in a list undergoing concurrent update.
(let ((tail (cons (car list) '())))
(set-cdr! pair tail)
- (loop tail (cdr list)))))
- (%make-queue front front))
+ (loop tail (cdr list)))
+ (%make-queue front pair))))
(make-queue)))
(define (provisional-list->queue list)
(if (pair? list)
(let ((front (cons 'SENTINEL '())))
- (call-ensuring-atomicity!
+ (call-ensuring-atomicity
(lambda ()
(let loop ((pair front) (list list))
(if (pair? list)
;; Using SET-CDR! here is safe, as above. But we use
;; PROVISIONAL-CxR instead of CxR, to make it safe to
;; use PROVISIONAL-LIST->QUEUE on a list undergoing
;; concurrent update.
(let ((tail (cons (provisional-car list) '())))
(set-cdr! pair tail)
- (loop tail (provisional-cdr list)))))))
- (%make-queue front front))
+ (loop tail (provisional-cdr list)))
+ (%make-queue front pair))))))
(make-queue)))
(define (list->queue! list)
(let ((front (cons 'SENTINEL list)))
- (%make-queue front front)))
+ (let loop ((pair front))
+ (let ((d (cdr pair)))
+ (if (null? d)
+ (%make-queue front pair)
+ (loop d))))))
diff -x _darcs -x '*~' -r -U 5 campbell-scheme-cml/s48-packages.scm campbell-scheme-cml-work-2009-12-22-01/s48-packages.scm
--- campbell-scheme-cml/s48-packages.scm 2009-12-22 10:54:29.572978720 -0800
+++ campbell-scheme-cml-work-2009-12-22-01/s48-packages.scm 2009-12-24 11:51:57.684104072 -0800
@@ -117,11 +117,18 @@
;;; Correct bugs in Scheme48's queues. (Unfortunately, they're what
;;; Scheme48's run-time system uses -- eeeek!)
(define-structure optimistic-queues (interface-of queues)
- (open scheme proposals srfi-23)
+ (open scheme
+ ;; CURRENT-PROPOSAL could be replaced with the
+ ;; PROPOSAL-ACTIVE? function exported by the PROPOSALS
+ ;; structure in the current development version of Scheme 48.
+ (subset low-proposals (current-proposal))
+ proposals
+ srfi-23
+ )
(optimize auto-integrate)
(files s48-optimistic-queue))
;;;; Parameters
work-2009-12-15-01_rev1447_to_rev1451.hg
(application/octet-stream, 6.3 KB) - not displayed