diff options
Diffstat (limited to 'fibers')
| -rw-r--r-- | fibers/internal.scm | 49 | ||||
| -rw-r--r-- | fibers/psq.scm | 544 |
2 files changed, 574 insertions, 19 deletions
diff --git a/fibers/internal.scm b/fibers/internal.scm index efb8c92..4e41324 100644 --- a/fibers/internal.scm +++ b/fibers/internal.scm @@ -21,6 +21,7 @@ #:use-module ((srfi srfi-1) #:select (append-reverse!)) #:use-module (srfi srfi-9) #:use-module (fibers epoll) + #:use-module (fibers psq) #:use-module (ice-9 atomic) #:use-module ((ice-9 control) #:select (let/ec)) #:use-module ((ice-9 binary-ports) #:select (get-u8 put-u8)) @@ -56,7 +57,7 @@ (runnables scheduler-runnables set-scheduler-runnables!) ;; fd -> ((total-events . min-expiry) #(events expiry fiber) ...) (sources scheduler-sources) - ;; ((fiber . expiry) ...) + ;; PSQ of fiber -> expiry (sleepers scheduler-sleepers set-scheduler-sleepers!) ;; atomic box of (fiber ...) (inbox scheduler-inbox) @@ -97,7 +98,11 @@ ((read-pipe . _) (epoll-add! epfd (fileno read-pipe) EPOLLIN))) (%make-scheduler epfd 0 (make-prompt-tag "fibers") - '() (make-hash-table) '() + '() (make-hash-table) + ;; sleepers psq + (make-psq (match-lambda* + (((t1 . f1) (t2 . f2)) (< t1 t2))) + <) (make-atomic-box '()) (make-atomic-box 'will-check) wake-pipe))) @@ -192,31 +197,35 @@ ((not (null? (scheduler-runnables sched))) ;; Likewise, don't sleep if there are runnables scheduled already. 0) + ((psq-empty? (scheduler-sleepers sched)) + -1) (else - (match (scheduler-sleepers sched) - ;; The sleepers list is sorted so the first element - ;; should be the one whose wake time is soonest. - (((fiber . expiry) . sleepers) + (match (psq-min (scheduler-sleepers sched)) + ((expiry . fiber) (let ((now (get-internal-real-time))) (if (< expiry now) 0 (round/ (- expiry now) - internal-time-units-per-millisecond)))) - (_ -1))))) + internal-time-units-per-millisecond)))))))) (define (wake-sleepers sched) + ;; Resume fibers whose sleep has timed out. Do it in such a way + ;; that the one with the earliest expiry is resumed last, so + ;; that it will will end up first on the runnable list. If one + ;; of these fibers has already been resumed (perhaps because the + ;; fd is readable or writable), this resume will have no effect. (let ((now (get-internal-real-time))) - ;; Resume fibers whose sleep has timed out. Do it in such a way - ;; that the one with the earliest expiry is resumed last, so - ;; that it will will end up first on the runnable list. If one - ;; of these fibers has already been resumed (perhaps because the - ;; fd is readable or writable), this resume will have no effect. (let wake-sleepers ((sleepers (scheduler-sleepers sched))) - (match sleepers - (((fiber . (? (lambda (expiry) (>= now expiry)))) . sleepers) - (wake-sleepers sleepers) - (resume-fiber fiber (lambda () 0))) - (_ (set-scheduler-sleepers! sched sleepers)))))) + (cond + ((or (psq-empty? sleepers) + (< now (car (psq-min sleepers)))) + (set-scheduler-sleepers! sched sleepers)) + (else + (call-with-values (lambda () (psq-pop sleepers)) + (match-lambda* + (((_ . fiber) sleepers) + (wake-sleepers sleepers) + (resume-fiber fiber (lambda () 0)))))))))) (define (handle-inbox sched) (for-each (match-lambda @@ -267,7 +276,7 @@ (if bool #t (return #f))) (only-finished-if (zero? (scheduler-active-fd-count sched))) (only-finished-if (null? (atomic-box-ref (scheduler-inbox sched)))) - (only-finished-if (null? (scheduler-sleepers sched))))) + (only-finished-if (psq-empty? (scheduler-sleepers sched))))) (define (run-scheduler sched) (let lp () @@ -369,6 +378,8 @@ from a finalizer thread." (round (* seconds internal-time-units-per-second)))))) (set-scheduler-sleepers! sched + (psq-set (scheduler-sleepers sched) (cons waketime fiber) waketime) + #; (let lp ((sleepers (scheduler-sleepers sched))) (match sleepers (((and sleeper (_ . (? (lambda (expiry) (> waketime expiry))))) diff --git a/fibers/psq.scm b/fibers/psq.scm new file mode 100644 index 0000000..52078ac --- /dev/null +++ b/fibers/psq.scm @@ -0,0 +1,544 @@ +#!r6rs +;;; psqs.sls --- Priority Search Queues + +;; Copyright (C) 2012 Ian Price <ianprice90@googlemail.com> + +;; Author: Ian Price <ianprice90@googlemail.com> + +;; This program is free software, you can redistribute it and/or +;; modify it under the terms of the new-style BSD license. + +;; You should have received a copy of the BSD license along with this +;; program. If not, see <http://www.debian.org/misc/bsd.license>. + +;;;; Documentation +;; +;; Priority search queues are a combination of two common abstract +;; data types: finite maps, and priority queues. As such, it provides +;; for access, insertion, removal and update on arbitrary keys, as +;; well as for easy removal of the element with the lowest priority. +;; +;; Note: where a procedure takes a key or priority these are expected +;; to be compatible with the relevant ordering procedures on the psq. +;; +;;;; Basic operations +;; +;; make-psq : < < -> psq +;; takes a two ordering procedures, one for keys, and another for +;; priorities, and returns an empty priority search queue +;; +;; psq? : obj -> boolean +;; returns #t if the object is a priority search queue, #f otherwise. +;; +;; psq-empty? : psq -> boolean +;; returns #t if the priority search queue contains no elements, #f +;; otherwise. +;; +;; psq-size : psq -> non-negative integer +;; returns the number of associations in the priority search queue +;; +;;;; Finite map operations +;; +;; psq-ref : psq key -> priority +;; returns the priority of a key if it is in the priority search +;; queue. If the key is not in the priority queue an +;; assertion-violation is raised. +;; +;; psq-set : psq key priority -> psq +;; returns the priority search queue obtained from inserting a key +;; with a given priority. If the key is already in the priority search +;; queue, it updates the priority to the new value. +;; +;; psq-update : psq key (priority -> priority) priority -> psq +;; returns the priority search queue obtained by modifying the +;; priority of key, by the given function. If the key is not in the +;; priority search queue, it is inserted with the priority obtained by +;; calling the function on the default value. +;; +;; psq-delete : psq key -> psq +;; returns the priority search queue obtained by removing the +;; key-priority association from the priority search queue. If the key +;; is not in the queue, then the returned search queue will be the +;; same as the original. +;; +;; psq-contains? : psq key -> boolean +;; returns #t if there is an association for the given key in the +;; priority search queue, #f otherwise. +;; +;;;; Priority queue operations +;; +;; psq-min : psq -> key +;; +;; returns the key of the minimum association in the priority search +;; queue. If the queue is empty, an assertion violation is raised. +;; +;; psq-delete-min : psq -> psq +;; returns the priority search queue obtained by removing the minimum +;; association in the priority search queue. If the queue is empty, an +;; assertion violation is raised. +;; +;; psq-pop : psq -> key + psq +;; returns two values: the minimum key and the priority search queue +;; obtained by removing the minimum association from the original +;; queue. If the queue is empty, an assertion violation is raised. +;; +;;;; Ranged query functions +;; +;; psq-at-most : psq priority -> ListOf(key . priority) +;; returns an alist containing all the associations in the priority +;; search queue with priority less than or equal to a given value. The +;; alist returned is ordered by key according to the predicate for the +;; psq. +;; +;; psq-at-most-range : psq priority key key -> ListOf(key . priority) +;; Similar to psq-at-most, but it also takes an upper and lower bound, +;; for the keys it will return. These bounds are inclusive. +;; +(library (fibers psq) +(export make-psq + psq? + psq-empty? + psq-size + ;; map operations + psq-ref + psq-set + psq-update + psq-delete + psq-contains? + ;; priority queue operations + psq-min + psq-delete-min + psq-pop + ;; ranged query operations + psq-at-most + psq-at-most-range + ) +(import (except (rnrs) min)) + +;;; record types + +(define-record-type void) + +(define-record-type winner + (fields key priority loser-tree maximum-key)) + +(define-record-type start) + +(define-record-type (loser %make-loser loser?) + (fields size key priority left split-key right)) + +(define (make-loser key priority left split-key right) + (%make-loser (+ (size left) (size right) 1) + key + priority + left + split-key + right)) + +;;; functions +(define (maximum-key psq) + (winner-maximum-key psq)) + +(define max-key maximum-key) + +(define empty (make-void)) + +(define (singleton key priority) + (make-winner key priority (make-start) key)) + +(define (play-match psq1 psq2 key<? prio<?) + (cond ((void? psq1) psq2) + ((void? psq2) psq1) + ((not (prio<? (winner-priority psq2) + (winner-priority psq1))) + (let ((k1 (winner-key psq1)) + (p1 (winner-priority psq1)) + (t1 (winner-loser-tree psq1)) + (m1 (winner-maximum-key psq1)) + (k2 (winner-key psq2)) + (p2 (winner-priority psq2)) + (t2 (winner-loser-tree psq2)) + (m2 (winner-maximum-key psq2))) + (make-winner k1 + p1 + (balance k2 p2 t1 m1 t2 key<? prio<?) + m2))) + (else + (let ((k1 (winner-key psq1)) + (p1 (winner-priority psq1)) + (t1 (winner-loser-tree psq1)) + (m1 (winner-maximum-key psq1)) + (k2 (winner-key psq2)) + (p2 (winner-priority psq2)) + (t2 (winner-loser-tree psq2)) + (m2 (winner-maximum-key psq2))) + (make-winner k2 + p2 + (balance k1 p1 t1 m1 t2 key<? prio<?) + m2))))) + +(define (second-best ltree key key<? prio<?) + (if (start? ltree) + (make-void) + (let ((k (loser-key ltree)) + (p (loser-priority ltree)) + (l (loser-left ltree)) + (m (loser-split-key ltree)) + (r (loser-right ltree))) + (if (not (key<? m k)) + (play-match (make-winner k p l m) + (second-best r key key<? prio<?) + key<? + prio<?) + (play-match (second-best l m key<? prio<?) + (make-winner k p r key) + key<? + prio<?))))) + +(define (delete-min psq key<? prio<?) + ;; maybe void psqs should return void? + (second-best (winner-loser-tree psq) (winner-maximum-key psq) key<? prio<?)) + +(define (psq-case psq empty-k singleton-k match-k key<?) + (if (void? psq) + (empty-k) + (let ((k1 (winner-key psq)) + (p1 (winner-priority psq)) + (t (winner-loser-tree psq)) + (m (winner-maximum-key psq))) + (if (start? t) + (singleton-k k1 p1) + (let ((k2 (loser-key t)) + (p2 (loser-priority t)) + (l (loser-left t)) + (s (loser-split-key t)) + (r (loser-right t))) + (if (not (key<? s k2)) + (match-k (make-winner k2 p2 l s) + (make-winner k1 p1 r m)) + (match-k (make-winner k1 p1 l s) + (make-winner k2 p2 r m)))))))) + +(define (lookup psq key default key<?) + (psq-case psq + (lambda () default) + (lambda (k p) + (if (or (key<? k key) (key<? key k)) + default + p)) + (lambda (w1 w2) + (if (not (key<? (max-key w1) key)) + (lookup w1 key default key<?) + (lookup w2 key default key<?))) + key<?)) + +(define (update psq key f default key<? prio<?) + (psq-case psq + (lambda () (singleton key (f default))) + (lambda (k p) + (cond ((key<? key k) + (play-match (singleton key (f default)) + (singleton k p) + key<? + prio<?)) + ((key<? k key) + (play-match (singleton k p) + (singleton key (f default)) + key<? + prio<?)) + (else + (singleton key (f p))))) + (lambda (w1 w2) + (if (not (key<? (max-key w1) key)) + (play-match (update w1 key f default key<? prio<?) + w2 + key<? + prio<?) + (play-match w1 + (update w2 key f default key<? prio<?) + key<? + prio<?))) + key<?)) + +(define (insert psq key val key<? prio<?) + (psq-case psq + (lambda () (singleton key val)) + (lambda (k p) + (cond ((key<? key k) + (play-match (singleton key val) + (singleton k p) + key<? + prio<?)) + ((key<? k key) + (play-match (singleton k p) + (singleton key val) + key<? + prio<?)) + (else + (singleton key val)))) + (lambda (w1 w2) + (if (not (key<? (max-key w1) key)) + (play-match (insert w1 key val key<? prio<?) w2 key<? prio<?) + (play-match w1 (insert w2 key val key<? prio<?) key<? prio<?))) + key<?)) + +(define (delete psq key key<? prio<?) + (psq-case psq + (lambda () empty) + (lambda (k p) + (if (or (key<? k key) + (key<? key k)) + (singleton k p) + empty)) + (lambda (w1 w2) + (if (not (key<? (max-key w1) key)) + (play-match (delete w1 key key<? prio<?) w2 key<? prio<?) + (play-match w1 (delete w2 key key<? prio<?) key<? prio<?))) + key<?)) + +(define (min tree) + (when (void? tree) + (assertion-violation 'psq-min + "Can't take the minimum of an empty priority search queue")) + (winner-key tree)) + +(define (pop tree key<? prio<?) + (when (void? tree) + (assertion-violation 'psq-pop + "Can't pop from an empty priority search queue")) + (values (winner-key tree) + (delete-min tree key<? prio<?))) + +;; at-most and at-most-range are perfect examples of when to use +;; dlists, but we do not do that here +(define (at-most psq p key<? prio<?) + (define (at-most psq accum) + (if (and (winner? psq) + (prio<? p (winner-priority psq))) + accum + (psq-case psq + (lambda () accum) + (lambda (k p) (cons (cons k p) accum)) + (lambda (m1 m2) + (at-most m1 (at-most m2 accum))) + key<?))) + (at-most psq '())) + +(define (at-most-range psq p lower upper key<? prio<?) + (define (within-range? key) + ;; lower <= k <= upper + (not (or (key<? key lower) (key<? upper key)))) + (define (at-most psq accum) + (if (and (winner? psq) + (prio<? p (winner-priority psq))) + accum + (psq-case psq + (lambda () accum) + (lambda (k p) + (if (within-range? k) + (cons (cons k p) accum) + accum)) + (lambda (m1 m2) + (let ((accum* (if (key<? upper (max-key m1)) + accum + (at-most m2 accum)))) + (if (key<? (max-key m1) lower) + accum* + (at-most m1 accum*)))) + key<?))) + (at-most psq '())) + +;;; Maintaining balance +(define weight 4) ; balancing constant + +(define (size ltree) + (if (start? ltree) + 0 + (loser-size ltree))) + +(define (balance key priority left split-key right key<? prio<?) + (let ((l-size (size left)) + (r-size (size right))) + (cond ((< (+ l-size r-size) 2) + (make-loser key priority left split-key right)) + ((> r-size (* weight l-size)) + (balance-left key priority left split-key right key<? prio<?)) + ((> l-size (* weight r-size)) + (balance-right key priority left split-key right key<? prio<?)) + (else + (make-loser key priority left split-key right))))) + +(define (balance-left key priority left split-key right key<? prio<?) + (if (< (size (loser-left right)) + (size (loser-right right))) + (single-left key priority left split-key right key<? prio<?) + (double-left key priority left split-key right key<? prio<?))) + +(define (balance-right key priority left split-key right key<? prio<?) + (if (< (size (loser-right left)) + (size (loser-left left))) + (single-right key priority left split-key right key<? prio<?) + (double-right key priority left split-key right key<? prio<?))) + +(define (single-left key priority left split-key right key<? prio<?) + (let ((right-key (loser-key right)) + (right-priority (loser-priority right)) + (right-left (loser-left right)) + (right-split-key (loser-split-key right)) + (right-right (loser-right right))) + ;; test + (if (and (not (key<? right-split-key right-key)) + (not (prio<? right-priority priority))) + (make-loser key + priority + (make-loser right-key right-priority left split-key right-left) + right-split-key + right-right + ) + (make-loser right-key + right-priority + (make-loser key priority left split-key right-left) + right-split-key + right-right)))) + +(define (double-left key priority left split-key right key<? prio<?) + (let ((right-key (loser-key right)) + (right-priority (loser-priority right)) + (right-left (loser-left right)) + (right-split-key (loser-split-key right)) + (right-right (loser-right right))) + (single-left key + priority + left + split-key + (single-right right-key + right-priority + right-left + right-split-key + right-right + key<? + prio<?) + key<? + prio<?))) + +(define (single-right key priority left split-key right key<? prio<?) + (let ((left-key (loser-key left)) + (left-priority (loser-priority left)) + (left-left (loser-left left)) + (left-split-key (loser-split-key left)) + (left-right (loser-right left))) + (if (and (key<? left-split-key left-key) + (not (prio<? left-priority priority))) + (make-loser key + priority + left-left + left-split-key + (make-loser left-key left-priority left-right split-key right)) + (make-loser left-key + left-priority + left-left + left-split-key + (make-loser key priority left-right split-key right))))) + +(define (double-right key priority left split-key right key<? prio<?) + (let ((left-key (loser-key left)) + (left-priority (loser-priority left)) + (left-left (loser-left left)) + (left-split-key (loser-split-key left)) + (left-right (loser-right left))) + (single-right key + priority + (single-left left-key + left-priority + left-left + left-split-key + left-right + key<? + prio<?) + split-key + right + key<? + prio<?))) + +;;; Exported Type + +(define-record-type (psq %make-psq psq?) + (fields key<? priority<? tree)) + +(define (%update-psq psq new-tree) + (%make-psq (psq-key<? psq) + (psq-priority<? psq) + new-tree)) + +;;; Exported Procedures + +(define (make-psq key<? priority<?) + (%make-psq key<? priority<? (make-void))) + +(define (psq-empty? psq) + (assert (psq? psq)) + (void? (psq-tree psq))) + +(define (psq-ref psq key) + (define cookie (cons #f #f)) + (assert (psq? psq)) + (let ((val (lookup (psq-tree psq) key cookie (psq-key<? psq)))) + (if (eq? val cookie) + (assertion-violation 'psq-ref "not in tree") + val))) + +(define (psq-set psq key priority) + (assert (psq? psq)) + (%update-psq psq + (insert (psq-tree psq) key priority (psq-key<? psq) (psq-priority<? psq)))) + +(define (psq-update psq key f default) + (assert (psq? psq)) + (%update-psq psq (update (psq-tree psq) key f default (psq-key<? psq) (psq-priority<? psq)))) + +(define (psq-delete psq key) + (assert (psq? psq)) + (%update-psq psq (delete (psq-tree psq) key (psq-key<? psq) (psq-priority<? psq)))) + +(define (psq-contains? psq key) + (define cookie (cons #f #f)) + (assert (psq? psq)) + (let ((val (lookup (psq-tree psq) key cookie (psq-key<? psq)))) + (not (eq? val cookie)))) + +(define (psq-min psq) + (assert (psq? psq)) + (min (psq-tree psq))) + +(define (psq-delete-min psq) + (assert (and (psq? psq) + (not (psq-empty? psq)))) + (%update-psq psq (delete-min (psq-tree psq) (psq-key<? psq) (psq-priority<? psq)))) + +(define (psq-pop psq) + (assert (psq? psq)) + (let-values (((min rest) (pop (psq-tree psq) (psq-key<? psq) (psq-priority<? psq)))) + (values min (%update-psq psq rest)))) + +(define (psq-at-most psq max-priority) + (assert (psq? psq)) + (let ((tree (psq-tree psq)) + (key<? (psq-key<? psq)) + (prio<? (psq-priority<? psq))) + (at-most tree max-priority key<? prio<?))) + +(define (psq-at-most-range psq max-priority min-key max-key) + (assert (psq? psq)) + (let ((tree (psq-tree psq)) + (key<? (psq-key<? psq)) + (prio<? (psq-priority<? psq))) + (at-most-range tree max-priority min-key max-key key<? prio<?))) + +(define (psq-size psq) + (assert (psq? psq)) + (let ((tree (psq-tree psq))) + (if (winner? tree) + (+ 1 (size (winner-loser-tree tree))) + 0))) + +) |
