Re: [Chicken-hackers] PATCH Re: slow polling

[Jörg F . Wittenberger]

Hi Megane,

thanks for looking at my submission.  Let me try to answer your questions.

On Nov 17 2018, megane wrote:



Jörg F. Wittenberger  writes:


Am 19.02.2016 um 22:39 schrieb Jörg F. Wittenberger:

...

I opened ticket 1259 for this.

To make the kind reviewers job easier, I'll post diffs in piecemeal 
here.


This patch goes after killing a single - but important - comment line in
scheduler.scm:

;; This should really use a balanced tree:

Now it does.

This patch replaces the timeout queue with a balanced tree.


   It does not matter so much, which kind of tree we use.  But a
   linear list is really a bad choice.



Hi Jörg,

What kind of performance benefits did you see with this patch?


Sorry, it's 10 years since I wrote this code
http://lists.nongnu.org/archive/html/chicken-users/2008-10/msg00103.html

I'm not sure that my observations from those days still hold.


Do you think the performance gains are worth the added complexity to the
scheduler?


At that time it definitely did.


Did you consider binary heap as the priority queue implementation? It
can be implemented with a vector and has nicer cache performance than
search trees which your patch seems to use.


Still I would not go with the patch today anymore: since I learned that the 
pure version of the llrb tree is considerable faster under CHICKEN (at 
least since argvectors days; I did not bother to try older versions).


(The llrb-tree egg includes a - for that reason now disabled - mutating 
version of the llrb-tree, which you could try.)


Given that experience I'd at least pitch the pure version against 
alternative algorithms to implement the priority queue.


Yes I tried a heap for my initial implementation using poll(2) with 
chicken. That is at least for the fd-list. (I failed to locate the code 
right now; should be in this context: 
http://lists.nongnu.org/archive/html/chicken-hackers/2012-05/msg8.html 
)



I did play with some heaps for a toy coroutine scheduler and binary heap
was faster than binomial heap and pairing heap in simple synthetic
tests. Less garbage too. The latter two implementations use separate
node structures which add garbage.


That's interesting as it contradicts my observation where mutation appears 
to be worse than garbage. Though the latter was found measuring the very 
same algorithm (llrb tree) in pure and mutating versions.


Best Regards

/Jörg






___
Chicken-hackers mailing list
Chicken-hackers@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-hackers

Re: [Chicken-hackers] PATCH Re: slow polling

[megane]

Jörg F. Wittenberger  writes:

> Am 19.02.2016 um 22:39 schrieb Jörg F. Wittenberger:
>> ...
>>> I opened ticket 1259 for this.
>>>
>>> To make the kind reviewers job easier, I'll post diffs in piecemeal here.
>
> This patch goes after killing a single - but important - comment line in
> scheduler.scm:
>
> ;; This should really use a balanced tree:
>
> Now it does.
>
> This patch replaces the timeout queue with a balanced tree.
>
>
>It does not matter so much, which kind of tree we use.  But a
>linear list is really a bad choice.
>

Hi Jörg,

What kind of performance benefits did you see with this patch?

Do you think the performance gains are worth the added complexity to the
scheduler?

Did you consider binary heap as the priority queue implementation? It
can be implemented with a vector and has nicer cache performance than
search trees which your patch seems to use.

I did play with some heaps for a toy coroutine scheduler and binary heap
was faster than binomial heap and pairing heap in simple synthetic
tests. Less garbage too. The latter two implementations use separate
node structures which add garbage.

Regards.

___
Chicken-hackers mailing list
Chicken-hackers@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-hackers

Re: [Chicken-hackers] PATCH Re: slow polling

[Jörg F . Wittenberger]

I can only repeat: the all-in-one change did not fly neither will the
piecemeal approach.

We need to come up with a small API atop of which users can switch
scheduler implementations.

Am 20.05.2016 um 21:26 schrieb Peter Bex:
> On Fri, Feb 19, 2016 at 10:39:23PM +0100, Jörg F. Wittenberger wrote:
>> A "Betthupferl" is Bavarian (a German dialect spoken in some remote,
>> hilly areas) for the last, small mean given to the kids upon bedtime.
>> Contradictory to all teachings often a sweet.
>>
>> This patch is not supposed to do any harm.
>>
>> It refactors parts of the code to minimize the upcoming diffs.
>> Furthermore it basically takes srfi-18 out of the equation.  Only
>> whitespace/comment diffs left there.
> 
> I had a look at this patch, but it does too much and too little at the
> same time:
> 
> - The moving of unblock-threads-for-timeout is a good change, but it
>should be a separate commit.
> - You define fdset-clear as a no-op, so unless I'm missing something, it
>will never ever remove the underlying file descriptors from the sets,
>even if the fd is closed.  This is a recipe for disaster.

Can't say much about that anymore.  This code was written about 8 years
ago.  At that time it did work.  And it did so under a load which does
apparently stress chicken's i/o more than any other.  But hey, this was
tested on Linux only, ages ago.  Sure it's no proof.

> - Even if fdset-clear wasn't a no-op, this commit would be incompatible
>with select(), which is the reason we tear down and recreate the fdset
>from fd-list every time.  I am aware it's not very efficient (and I'd
>even admit to it being "brain dead" as you call it), but the way
>select() works is that it will mutate the input set in-place, so you
>can't rely on it maintaining a consistent state.  POSIX poll() is
>better designed in almost every way imagineable, but we do have to
>deal with the shit show that is Windows.  To keep things sane we do
>it in one consistent way for both select() and poll(), instead of
>having two code paths to maintain in code that is already very hairy.
> 
> I'll have to think about this, maybe we can come up with a way to avoid
> paying the price on UNIX for the shit Windows implementation.  Better
> would be to have a *proper* implementation on Windows, but nobody has
> stepped up to actually overhaul the entire code to make that possible,
> so far.
> 
> Cheers,
> Peter
> 


___
Chicken-hackers mailing list
Chicken-hackers@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-hackers

Re: [Chicken-hackers] PATCH Re: slow polling

[John Cowan]

Peter Bex scripsit:

> I'll have to think about this, maybe we can come up with a way to
> avoid paying the price on UNIX for the shit Windows implementation.
> Better would be to have a *proper* implementation on Windows, but
> nobody has stepped up to actually overhaul the entire code to make
> that possible, so far.

A huuge amount of the code in the Cygwin DLL is concerned with
faking Posix semantics for select(); I've heard that it's the single
most complex thing in the library.

-- 
John Cowan  http://www.ccil.org/~cowanco...@ccil.org
Unless it was by accident that I had offended someone, I never apologized.
--Quentin Crisp

___
Chicken-hackers mailing list
Chicken-hackers@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-hackers

Re: [Chicken-hackers] PATCH Re: slow polling

[Jörg F . Wittenberger]

Fixes for last patch.

Sorry, this had to happen sooner or later.

This patch just fixes use of outdates predicates.

Cheers

/Jörg

BTW: Interesting that this did work to some extend.  (#1 reason to begin
with the timeout queue was that the original code still uses fixnum
timeouts for backward compatibility).

Am 20.02.2016 um 18:54 schrieb Jörg F. Wittenberger:
> Am 19.02.2016 um 22:39 schrieb Jörg F. Wittenberger:
>> ...
>>> I opened ticket 1259 for this.
>>>
>>> To make the kind reviewers job easier, I'll post diffs in piecemeal here.
> 
> This patch goes after killing a single - but important - comment line in
> scheduler.scm:
> 
> ;; This should really use a balanced tree:
> 
> Now it does.
> 
> This patch replaces the timeout queue with a balanced tree.
> 
> 
>It does not matter so much, which kind of tree we use.  But a
>linear list is really a bad choice.
> 
>Assume you have a tcp-server alike: 100 client connections and
>you read the next input line.  It's probably (but not sure) already
>in the OS's buffer.  But chicken core will nevertheless establish a
>timeout.  The latter will so far traverse the (linear) timeout
>queue.  Chances are all those other timeouts are prior established
>reads using the same timeout too.  Thus you find the insert point
>right at the end.
> 
> 
> If you have an application which makes heavy use of chicken's core tcp
> unit (I don't use chicken's timeouts at all for this, I do use them, but
> only via thread-sleep!) I'd be interested to hear how much good or bad
> this patch does for you.
> 
> Cheers
> 
> /Jörg

>From 697b8780cb57a9720affc8216d194c211fdef49a Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=B6rg=20F=2E=20Wittenberger?=
 
Date: Sat, 20 Feb 2016 19:15:26 +0100
Subject: [PATCH] Fix missuse of predicate

---
 scheduler.scm | 8 +++-
 1 file changed, 3 insertions(+), 5 deletions(-)

diff --git a/scheduler.scm b/scheduler.scm
index 997668f..7081acf 100644
--- a/scheduler.scm
+++ b/scheduler.scm
@@ -334,8 +334,7 @@ EOF
 (let ((entry (make-timeout-list-entry tm (list t
   (##sys#setslot t 4 entry)
   (set! ##sys#timeout-list-head entry)))
-   ((fx> tm
-	 (prio-queue-node-index ##sys#timeout-list-head))
+   ((timeout< (prio-queue-node-index ##sys#timeout-list-head) tm)
 (let ((entry (timeout-queue-node-lookup ##sys#timeout-list tm)))
   (if entry
 	  (begin
@@ -346,8 +345,7 @@ EOF
 	  (let ((entry (make-timeout-list-entry tm (list t
 	(##sys#setslot t 4 entry)
 	(timeout-queue-node-insert! ##sys#timeout-list entry)
-   ((fx< tm
-	 (prio-queue-node-index ##sys#timeout-list-head))
+   ((timeout< tm (prio-queue-node-index ##sys#timeout-list-head))
 (timeout-queue-node-insert!
  ##sys#timeout-list ##sys#timeout-list-head)
 (let ((entry (make-timeout-list-entry tm (list t
@@ -535,7 +533,7 @@ dunno what to do
 	;; Sleep for the number of milliseconds of next thread
 	;; to wake up.
 	(let ((tmo (prio-queue-node-index (timeout-queue-next
-	  (##core#inline "C_msleep" (fxmax 0 (##core#inline "C_quickflonumtruncate" (fp- tmo now )
+	  (##core#inline "C_msleep" (fpmax 0 (##core#inline "C_quickflonumtruncate" (fp- tmo now )
 
 (define (##sys#thread-block-for-timeout! t tm)
   (dbg t " blocks for timeout " tm)
-- 
2.6.2

___
Chicken-hackers mailing list
Chicken-hackers@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-hackers

Re: [Chicken-hackers] PATCH Re: slow polling

[Jörg F . Wittenberger]

Am 19.02.2016 um 22:39 schrieb Jörg F. Wittenberger:
> ...
>> I opened ticket 1259 for this.
>>
>> To make the kind reviewers job easier, I'll post diffs in piecemeal here.

This patch goes after killing a single - but important - comment line in
scheduler.scm:

;; This should really use a balanced tree:

Now it does.

This patch replaces the timeout queue with a balanced tree.


   It does not matter so much, which kind of tree we use.  But a
   linear list is really a bad choice.

   Assume you have a tcp-server alike: 100 client connections and
   you read the next input line.  It's probably (but not sure) already
   in the OS's buffer.  But chicken core will nevertheless establish a
   timeout.  The latter will so far traverse the (linear) timeout
   queue.  Chances are all those other timeouts are prior established
   reads using the same timeout too.  Thus you find the insert point
   right at the end.


If you have an application which makes heavy use of chicken's core tcp
unit (I don't use chicken's timeouts at all for this, I do use them, but
only via thread-sleep!) I'd be interested to hear how much good or bad
this patch does for you.

Cheers

/Jörg


From 38c2b03e6a96097fa4fd4eeb4971305d084ae90f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=B6rg=20F=2E=20Wittenberger?=
 
Date: Sat, 20 Feb 2016 18:13:49 +0100
Subject: [PATCH] Use balanced a tree for the timeout queue

---
 distribution/manifest |   1 +
 llrbtree.scm  | 505 ++
 scheduler.scm | 333 ++---
 3 files changed, 777 insertions(+), 62 deletions(-)
 create mode 100644 llrbtree.scm

diff --git a/distribution/manifest b/distribution/manifest
index 1dd037f..3fc253a 100644
--- a/distribution/manifest
+++ b/distribution/manifest
@@ -28,6 +28,7 @@ posixunix.c
 posixwin.c
 profiler.c
 scheduler.c
+llrbtree.scm
 srfi-69.c
 srfi-1.c
 srfi-13.c
diff --git a/llrbtree.scm b/llrbtree.scm
new file mode 100644
index 000..4b19e4d
--- /dev/null
+++ b/llrbtree.scm
@@ -0,0 +1,505 @@
+;; #!/usr/bin/csi
+;; (C) 2008, 2010, 2013 Jörg F. Wittenberger.
+
+;; Redistribution permitted under either GPL, LGPL or BSD style
+;; license.
+
+;; (use extras)
+
+;; Changes
+;; Rewritten from the 2008 version; now in syntax-rules.
+
+;;* Left Leaning Red Black Tree
+
+;;** Code Generator
+
+;; Generate LLRB trees within arbitrary datastructures.
+
+(define-syntax define-llrbtree/positional
+  (syntax-rules ()
+((_
+  ;; The "features" is a list of symbols to control code
+  ;; expansion.  "pure" expands to an implementation, which never
+  ;; updates nodes.  "ordered" will enforce total order among the
+  ;; element.  "leftmost" will include code to maintain a leftmost
+  ;; value of the tree (not recommended, may be removed).
+  features
+  ;; The "update*" syntax must accept a node structure and
+  ;; key-value pairs.  Keys are color:, left: and right:
+
+  ;; "update" : If feature "pure" is set, "update" must expand
+  ;; to a newly allocated node, otherwise is MUST expand to a
+  ;; side effect full update of the original node.
+  update
+  ;; The following identifiers are bound in the expanded code.
+  ;; Pass #f for procedures not to be expanded.
+  init-root-node!		;; defined
+  t-lookup			;; defined
+  t-min			;; defined
+  t-fold			;; defined
+  t-for-each		;; defined
+  t-insert			;; defined
+  t-delete			;; defined
+  t-delete-min		;; defined
+  t-empty?			;; defined
+
+  ;; These syntax is used expand to code for comparision
+  ;; expressions.
+  t-k-eq?			;; key<>node-key "equal"
+  t-eq?			;; node-key<>node-key "equal"
+  t-k-node-key "less then"
+  t-node "less then"
+
+  ;; set-left!, set-right! and set-color! are unused, obsolete and
+  ;; will be removed in future version.
+  left set-left!
+  right set-right!
+  color set-color!
+  )
+ (begin
+   (define-syntax if/pure
+	 (syntax-rules (pure)
+	   ((_ kt kf) (if/pure features kt kf))
+	   ((_ () kt kf) kf)
+	   ((_ (pure . more) kt kf) kt)
+	   ((_ (kw . more) kt kf) (if/pure more kt kf
+
+   (define-syntax if/ordered
+	 (syntax-rules (ordered)
+	   ((_ kt kf) (if/ordered features kt kf))
+	   ((_ () kt kf) kf)
+	   ((_ (ordered . more) kt kf) kt)
+	   ((_ (kw . more) kt kf) (if/ordered more kt kf
+
+   (define-syntax if/leftmost
+	 (syntax-rules (leftmost)
+	   ((_ kt kf) (if/leftmost features kt kf))
+	   ((_ () kt kf) kf)
+	   ((_ (leftmost . more) kt kf) kt)
+	   ((_ (kw . more) kt kf) (if/leftmost more kt kf
+
+   (define-syntax cond-define
+	 (syntax-rules ()
+	   ((_ (#f . params) . body) #f)
+	   ((_ (id . params) . body)
+	(define (id . params) . body
+
+   (define-syntax root-node (syntax-rules () ((_ x) (left x
+
+#|
+Root pointers not yet working.
+   (define-syntax