kristianlm / chicken-gochan Goto Github PK

Hi, I just found an annoying bug.

When signals are involved, gochan crashes my program with an “assertion failed” message.

Error: (gochan.scm:502) assertion failed: (gosem-meta semaphore)

        Call history:

        gochan.scm:488: gosem-mutex
        gochan.scm:489: gosem-cv
        gochan.scm:488: mutex-unlock!
        gochan.scm:499: g1321
        gochan.scm:347: gochan-mutex
        gochan.scm:347: mutex-lock!
        gochan.scm:348: info
        gochan.scm:349: gochan-receivers
        gochan.scm:349: %remove-queue-item
        gochan.scm:332: queue-length
        gochan.scm:334: queue-remove!
        gochan.scm:337: loop
        gochan.scm:350: gochan-mutex
        gochan.scm:350: mutex-unlock!
        gochan.scm:502: gosem-meta
        gochan.scm:502: ##sys#error             <--

This is due to the code not checking the state of the semaphore objects after a mutex-unlock! with a condition-variable. These mutex-unlock! calls might be interrupted before the condition variable is signaled, for example when a signal handler is run.

Here is a patch that fixes this behaviour. Make sure it’s ok, I’m not used to the gochan codebase. :)

Running this:

;;; stress-test gochan. This is causing deadlocks after about 25000
;;; messages (consistantly). We need to figure out what's going wrong here!
(use gochan)

(define chan (gochan))

(thread-start!
 (lambda () ;; simple echo
   (gochan-for-each
    chan (lambda (msg)
           (gochan-send (car msg)
                        (cdr msg))))))

(let loop ((n 100000))
  (if (> n 0)
      (let ((reply (gochan)))
        (gochan-send chan (cons reply n))
        (assert (eq? n (gochan-receive reply)))
        (loop (sub1 n)))))

We get a deadlock error after about 25000 loops when interpreted, 400 loops when compiled with -O5 and never when compiled with -O1. I believe there's a mutex-lock missing somewhere.

Hi! I noticed that in gochan-select* there's an unnecessary division, considering how the result is used afterwards. I removed that and replaced < with fx< on it. Since it is one of the core functions of the gochan egg I expect it to be called often, so this small change should provide (at least) a small performance improvement.

What do you think? Did some detail escape me such that this doesn't make sense?

Tests pass on latest CHICKEN. From my understanding of the C4 docs, fx< is part of the base module. I also added possible Chibi compatibility (through SRFI 143) but I haven't tested the changes there because I still haven't a working install.

You can find my changes here:

diff --git a/chibi-compat.scm b/chibi-compat.scm
index d2c97ea..2330a6f 100644
--- a/chibi-compat.scm
+++ b/chibi-compat.scm
@@ -1,4 +1,7 @@
-
+(import
+  (rename
+    (only (srfi 143) fx<?)
+    (fx<? fx<)))

 (define (current-milliseconds)
   (let ((tv (car (get-time-of-day))))
diff --git a/chicken-module5.scm b/chicken-module5.scm
index 74b8062..6f0d2b2 100644
--- a/chicken-module5.scm
+++ b/chicken-module5.scm
@@ -15,6 +15,7 @@
                 )
 (import (scheme)
        (chicken base)
+       (chicken fixnum)
        srfi-18
        (only (queues) list->queue queue->list queue-add! queue-empty? queue-remove! queue-length)
        (only (matchable) match)
diff --git a/gochan.scm b/gochan.scm
index 9cb2bfb..711c8c7 100644
--- a/gochan.scm
+++ b/gochan.scm
@@ -380,9 +380,9 @@
         ;; probably much faster ways to do this, though...
         (chans (map cdr
                     (sort (map (lambda (spec)
-                                 (cons (/ (pseudo-random-integer 256) 256.0) spec))
+                                 (cons (pseudo-random-integer 256) spec))
                                chans)
-                          (lambda (a b) (< (car a) (car b)))))))
+                          (lambda (a b) (fx< (car a) (car b)))))))
     ;; keep our semaphore locked while we check channels for data
     ;; ready, so that we can't get signalled externally while we do
     ;; this.

Kind of related to #5: I believe it may be possible to improve performance of the shuffle operation in gochan-select*.

Here's my proposed alternative:

(define (shuffle l)
  (if (null? l)
      '()
      (let ((x (car l))
            (l (shuffle (cdr l))))
        (if (zero? (pseudo-random-integer 2))
            (cons x l)
            (append l `(,x))))))

Thinking about it (though not too much, admitedly), I believe using this rather than (map ... (sort ... (map ... l))) would improve that operation from 2 traversals+sorting of the original list (which should be roughly 3 traversals total?¹) to roughly 2 traversals (assuming 50% chance of (pseudo-random-integer 2) returning either 0 or 1²).

I have no idea how I could benchmark this, however. You're certainly more familiar with the codebase, so if you think this is worth exploring I would appreciate some pointers/ideas. :)

One question I have is whether it would be a problem for shuffle not to be tail-recursive.

And another question is whether the result would be random enough to work well as a load-balancer.

Hi again :)

I'm trying to use CHICKEN exclusively for a course I'm enrolled in, which is proving to be very interesting and rewarding, but also challenging. In this course we're using Maelstrom to implement and experiment with distributed algorithms and distributed programming, and I hit a limitation with my previous "recipe", in that I have no easy way of implementing timeouts, heartbeats, and the like. Because of that I'm turning now to gochan which is more at-home for me (having a bit of experience with Erlang and Go).

However, I have a problem: let's say I have two channels Ci and Ct (for input and timeout), and that the main thread does a gochan-select on both of them. Would it be possible to somehow prioritize one of the channels over the other (Ct over Ci, specifically)?

Without the "shuffle" mentioned in #6 it's obvious to me how: just order the Ct before the Ci. (In the meantime I'll remove the shuffle from gochan-select*)