2021/04/18

mtqueue and channel

Thread-safe queues, <mtqueue> (ref:data.queue), can naturally be used as a ``channel'', a communication primitive between producer thread(s) and consumer thread(s). In fact, I totally assumed the two were equivalent, and didn't bother creating a ``channel'' datatype specifically.

But I realized there was one difference--a channel can be closed.

Suppose I have an in-process ``server''---a thread looping over requests sent via an mtqueue. Other part of the program inserts its requests with enqueue/wait!. The server thread reads it and process it. All the synchronization is done in the queue, and that's the beauty.

Now, sometimes, you may want to shut down such server. Once it is shut down, we don't want to allow callers to put a new request into the queue, for it will sit in the queue unprocessed forever. How to implement it?

We may have a separate flag in our <server> object and ask the caller to check it before queuing a request. But such check must be done atomically with queue insertion, for other thread may set the flag after you checked it but before calling enqueue. Hence you need a separate lock for the flag and the queue, even the queue itself is thread-safe. It's kind of waste.

With a channel, attempt to put a request on a closed channel would be rejected, and that check is done atomically inside a channel.

For Gauche, I decided to enhance <mtqueue> to have ``close'' state. It's a bit of divergence from a queue in the original sense, but it's simpler than making a separate channel class on top of <mtqueue>. The lock operation and flag check is intertwined so deeply that it's difficult to separate them cleanly.

An mtqueue can only be closed via the synchronized queue operations such as enqueue/wait!. Usually, if you want to shut down the service, you need a special message, so it's reasonable that you close the queue simultaneously when you send such termination message.

(If you think a channel as a pipe, then such termination message is not necessary; the input end can be simply closed, and the output end reads something like #<eof>. Queue, on the other hand, is expected to read something that's explicitly put.)

The feature is available in the next release, 0.9.11.

Tags: data.queue, mtqeueue, Concurrency

2020/07/22

A curious case of rational to flonum conversion

Tanaka Akira filed a curious bug report in Ruby: https://bugs.ruby-lang.org/issues/17037

He computed 1 + (k/100)ε in rational arithmetic, then converted it to a floating-point number, for k=0 to 100, where ε is FLT_EPSILON. If k=0 it's 1, and k=100 it's nextfloat(1), so somewhere inbetween the value switches from 1 to nextfloat(1). However, what he saw was that the value flips more than once:

...
[31, 1.0, (450359962737049631/450359962737049600)]
[32, 1.0, (14073748835532801/14073748835532800)]
[33, 1.0000000000000002, (450359962737049633/450359962737049600)]
[34, 1.0000000000000002, (225179981368524817/225179981368524800)]
[35, 1.0, (90071992547409927/90071992547409920)]
[36, 1.0000000000000002, (112589990684262409/112589990684262400)]
[37, 1.0000000000000002, (450359962737049637/450359962737049600)]
[38, 1.0000000000000002, (225179981368524819/225179981368524800)]
[39, 1.0000000000000002, (450359962737049639/450359962737049600)]
[40, 1.0, (11258999068426241/11258999068426240)]
[41, 1.0000000000000002, (450359962737049641/450359962737049600)]
[42, 1.0000000000000002, (225179981368524821/225179981368524800)]
[43, 1.0000000000000002, (450359962737049643/450359962737049600)]
...

Intrigued, I ran the same computation in Gauche. To my surprise, I got exactly the same result (0.9.9):

gosh> (dotimes (k 100) 
        (let1 d (+ 1 (* k 1/100 (exact (flonum-epsilon))))
          (print `(,k ,(inexact d) ,d))))
(0 1.0 1)
(1 1.0 450359962737049601/450359962737049600)
(2 1.0 225179981368524801/225179981368524800)
...
(31 1.0 450359962737049631/450359962737049600)
(32 1.0 14073748835532801/14073748835532800)
(33 1.0000000000000002 450359962737049633/450359962737049600)
(34 1.0000000000000002 225179981368524817/225179981368524800)
(35 1.0 90071992547409927/90071992547409920)
(36 1.0000000000000002 112589990684262409/112589990684262400)
(37 1.0000000000000002 450359962737049637/450359962737049600)
(38 1.0000000000000002 225179981368524819/225179981368524800)
(39 1.0000000000000002 450359962737049639/450359962737049600)
(40 1.0 11258999068426241/11258999068426240)
(41 1.0000000000000002 450359962737049641/450359962737049600)
(42 1.0000000000000002 225179981368524821/225179981368524800)
(43 1.0000000000000002 450359962737049643/450359962737049600)
(44 1.0000000000000002 112589990684262411/112589990684262400)
(45 1.0000000000000002 90071992547409929/90071992547409920)
(46 1.0000000000000002 225179981368524823/225179981368524800)
(47 1.0000000000000002 450359962737049647/450359962737049600)
(48 1.0000000000000002 28147497671065603/28147497671065600)
(49 1.0000000000000002 450359962737049649/450359962737049600)
(50 1.0 9007199254740993/9007199254740992)
(51 1.0000000000000002 450359962737049651/450359962737049600)
(52 1.0000000000000002 112589990684262413/112589990684262400)
...

To my knowledge, Gauche and Ruby don't share code regarding this feature. Whatever the issue is, it should be in the logic.

What Gauche did was basically converting the numerator and the denominator of the rational number to doubles, then did a floating-point division:

double dnumer = Scm_GetDouble(SCM_RATNUM_NUMER(obj));
double ddenom = Scm_GetDouble(SCM_RATNUM_DENOM(obj));

return dnumer/ddenom;

There's a case that dnumer and/or ddenom overflows that requires special handling, and also we have to make sure the floating-point division is done in IEEE double precision (as opposed to extended precision). I guess Ruby does the same, and that is the cause of the weird behavior. What's going on?

Let's look at the k=33. 1 + 33/100*ε is 450359962737049633/450359962737049600. This is closer to 1 than nextfloat(1), so it should be rounded down.

The numerator, 450359962737049633, consists of the following bits:

gosh> (format "~,,,5:b" 450359962737049633)
"1100,10000,00000,00000,00000,00000,00000,00000,00000,00000,00001,00001"
;;                                                             ^53bit 

Note that it requires more than 53bits to represent it accurately. If we convert it to double, the last 6 bits are rounded---since it is greater than the midpoint, it is rounded up:

1100,10000,00000,00000,00000,00000,00000,00000,00000,00000,00001,00001
  ↓
1100,10000,00000,00000,00000,00000,00000,00000,00000,00000,0001 * 2^6

Effectively, we now have 1 + 64/100*ε. So we get 1.0000000000000002 rather than 1.0. We can say this is another case of double-rounding.

When k = 32, the last 6 bits falls on the exact midpoint, so it is rounded down by the even-rounding rule.

k=35, 40 and 50 are anomalies---the rational numbers are simplified, so their numerator happened to fit within 53 bits and we didn't lose the precision.

The fix I've implemented is as follows:

• Scale numerator by factor S so that numerator * S > 2^54 * denominator.
• Compute integer division. The quotient has at least 54 bits.
• Look at the 54-th bits.
  • If it is 0, we can round down the quotient.
  • If it is 1 and there's any '1' in the following bits, or the remainder of the division is not zero, we can round up the quotient.
  • Otherwise, quotient is on the midpoint. We see the 53-th bit and round to even.
• Convert the quotient into double, then scale back.

If the result falls on the denormalized range, we have to adjust the significant digits, otherwise we'll get another double-rounding.

This solution involves lots of bignum allocations, so we want to optimize eventually.

Tags: Flonums, 0.9.10

2020/05/30

C API and promise

This ate up my whole afternoon so I write it down not to fall into it again.

I've got a really weird bug. We have a parameter (say P). P has a default value, but it may not be available at the initialization time. Basically, what we want is to delay evaluation of EXPR below until the value of P is actually taken:

(define P (make-parameter EXPR))

Simply wrapping EXPR with delay did't cut it, for the user of P expected it to contain a value which wasn't a promise. We couldn't go to every place where P was used to wrap it with force.

So we added a special flag in the parameter, which applies force on the value whenever the value is taken. The feature isn't available from the Scheme world, though. It's only through C API, for we're not sure if such feature is a good idea yet.

Anyway, P got such a flag, so we could also say (P (delay EXPR)) to alter the value of P, with the actual computation of EXPR is delayed. And it seemed working.

However, we ran into an issue when some code takes the value of P from C API. The internal of parameter object is a bit complicated, but you can assume there's an C API that retrieves the value of the given parameter. Through C API, however, P's value looked like #<closure ...>, whereas when I took P's value from the Scheme world, it returned the value of EXPR.

I started tracking it down and it was like a rabbit hole. Scheme interface eventually calls the internal Scheme procedure %primitive-parameter-ref, which directly calls C API Scm_PrimitiveParameterRef. I inserted a debug stub to show the result of C call. The C API returns the mysterious closure, yet in the Scheme world it returns the desired value. Does Gauche runtime intercept the return value from C world to Scheme world? Nope. It's directly returned to the Scheme world. I have no idea where this #<closure...> came from, neither how the value changes to the desired one.

Furthermore, I found that if I evaluate (P) second time, C API returns the desired value. But no code is called to actually replacing P's value!

I poke around C stub generators, VM code, parameter code,... in vain. Finally, I opened up the source of Scm_Force, the C API for force. And BANG! The answer was there.

C runtime doesn't like call/cc. C procedures return either exactly once, or never. So, when you call back Scheme code from C, you have to choose one of these two strategies:

• Restrict the called Scheme code to returns at most once. If a continuation captured within the Scheme code is invoked again later, and tries to return to the C code again, an error is thrown.
• Split your C code to two, before the callback (A) and after the callback (B). Both A and B are ordinary C function. A arranges B to be called after the Scheme callback returns. Effectively, you write it as a continuation-passing style. With this, a continuation captured within the Scheme callback can be re-invoked, which just calls B again.

Most of Gauche runtime in C adopts the latter strategy, so that call/cc works seamlessly. By convention, the C API functions that use the strategy are named Scm_VM***. The caller of such C API can't expect to get the final result as the C return value, since such function may need more calculation (Scheme code and B part) to get the final result.

Scm_Force is that type of function, too. I only forgot to name it as Scm_VMForce.

Scm_PrimitiveParameterRef casually called Scm_Force when it has the delayed evaluation flag, expecting that it returns the final value. But in fact, Scm_Force can only be used in conjunction of Scheme VM to obtain the final result.

Tag: BugStories

2020/05/22

Next release will be 0.9.10

We haven't reached what we expected for 1.0, but we've got quite a few useful changes so we're gonna put 0.9.10 out. Some notable features to be included:

• All libraries of R7RS-large Red and Tangerine edition. (Exact complex numbers aren't in yet.)
• Immutable pairs are supported natively.
• PEG parser library will be finally documented and ``offical''.
• Native string cursor support, thanks to @pclouds.
• Input editing feature is enhanced to include online key-binding help. Probably still early to make it default, but we'll probably add command-line switch to test it easier.

Tag: 0.9.10

2020/01/23

Remaining tasks for 1.0

In the last entry I listed a couple of items for 1.0. After that I remembered a few more, so I put them down here.

• Enhancement of extended pairs. Currently we only use extended pairs to keep source information (source code location and the macro input). One big drawback of extended pairs is that it is costly to check if a given pair is extended (occupies 4 words) or not (occupies 2 words). Currently we need to look up the allocation region table to see the size of the object.
  If we can make the check faster, we can let modifiers (set-car! and set-cdr!) check if the pair has some special attributes (while cost of car and cdr stays the same.) It opens up a few interesting possibilities:
  • We can implement immutable pairs. Just raise an error in the modifiers.
  • We can implement typed lists, that is, a list whose elements are guaranteed to have certain type. A constructor, say, (typed-cons type car cdr) can check if car is of type and cdr is of type List type, and modifiers can check the type constraint.

• Integrate pattern matcher into core. Most of my code now impors util.match. It's so fundamental and I think it should be supported as built-in.
  • An interesting possibility is to support pattern match in formal arguments by default.

• Support FFI. Currently there's a C-wrapper ( https://bitbucket.org/nkoguro/c-wrapper/src/default/ ) by Naoki Koguro. It'd be a good time to incorporate it.

Depending on how quick I can work on them, we might have another 0.9.x release.

Tag: 1.0