:Hold

[paulmansour]

Is :Hold FIFO or LIFO or neither?

[petermsiegel]

AFAIK, if you :HOLD a token, say 'A', anywhere in the workspace, then any attempt to :HOLD 'A' within the scope of this first :HOLD, whether in the current function or in a called function, will simply block (if there's no :ELSE) or fail ("catchable" via the user-provided :ELSE).

OTOH, if an in-scope :HOLD is attempted with a different token (or tokens), not otherwise held, e.g. :HOLD 'B', it will be held after and must be released (by going out of scope) before 'A' can be released.

In either case, it's technically LIFO (last hold executed is the first-hold released) insofar as any successful holds are released "inside out," i.e. from lower in the nesting of holds as long as consistent with the proviso above.

Happy to be corrected by others...

[paulmansour]

Thanks for the reply.

Interesting. I was not thinking about nested holds.

I was considering the case of a single hold in a single function. Consider a bunch of threads running that stack up waiting for the hold to be released so they can proceed. Only one can proceed at a time. Which one? My experience indicates that the last thread to run :Hold goes first, which seems counter-intuitive to me. I would have thought it would FIFO. If it is indeed LIFO, then clearly the situation could happen that some threads may never acquire the token, or could take take an inordinate amount of time to acquire the token.

I have a very vague feeling I discovered this 10 years ago and have forgotten, and that's why I don't use :Hold.

[PeterM|Dyalog]

Hi Paul,

There is no guaranteed order in which the :Holds will succeed.

And due to the fact that a single :Hold can hold multiple tokens, a strict FIFO (or LIFO) order would be tricky.

Assume for example that thread 1 :Holds 'A', and then thread 2 tries to :Hold 'A' and 'B'. Thread 2 has to wait because 'A' is held by thread 1.
If another thread now performs a :Hold 'B', it will succeed, and therefore hold the 'B' that thread 2 was "first in line" for.

Anyways, I believe the LIFO order you have observed is an implementation detail of how threads are scheduled in the interpreter, which in this case depends on the order of which the threads were started, and not the order of the :Holds. See the following example which demonstrates this:

Code: Select all

∇test dl
 ⎕DL dl
 ⎕←'Trying to :Hold ''A'' on thread: ',⍕⎕TID
 :Hold 'A'
     ⎕←'Holding ''A'' on thread: ',⍕⎕TID
     ⎕DL 1
 :EndHold
∇

This looks like LIFO.

Code: Select all

      test&¨5÷⍨⍳5
Trying to :Hold 'A' on thread: 1
Holding 'A' on thread: 1
Trying to :Hold 'A' on thread: 2
Trying to :Hold 'A' on thread: 3
Trying to :Hold 'A' on thread: 4
Trying to :Hold 'A' on thread: 5
Holding 'A' on thread: 5
Holding 'A' on thread: 4
Holding 'A' on thread: 3
Holding 'A' on thread: 2


And this looks like FIFO

Code: Select all

      test&¨⌽5÷⍨⍳5
Trying to :Hold 'A' on thread: 10
Holding 'A' on thread: 10
Trying to :Hold 'A' on thread: 9
Trying to :Hold 'A' on thread: 8
Trying to :Hold 'A' on thread: 7
Trying to :Hold 'A' on thread: 6
Holding 'A' on thread: 9
Holding 'A' on thread: 8
Holding 'A' on thread: 7
Holding 'A' on thread: 6


In both examples, the order in which the :Holds succeed is opposite the order in which the threads were created (except the first thread), as indicated by their thread ID. That shows it has nothing to do with the order in which the :Holds were started. But to be clear, it is an implementation detail, and not a guarantee.

I hope that helps!

[paulmansour]

Hi Peter,

Thanks... very informative. Basically :Hold then is an "unfair" mutex, which can lead to thread starvation. It seems that fair mutex implementations are not common in other languages. I believe that implementing :hold using ⎕TPUT and ⎕TGET also yields an unfair mutex.

I think it would be useful if the documentation explicitly noted this both for :Hold and ⎕TGET.

I'm also curious what the downside is to a fair implementation in Dyalog. The literature for other languages and operating systems seem to suggest that fair implementations are less efficient in some way. They also mention that there would be an issue with high-priority threads. It seems the Dyalog implementation prioritizes threads in reverse order of creation as you note (Implementation detail - not a feature). I would not think that the fact that :Hold (and ⎕TGET) work on multiple tokens would be an design issue for a fair mutex from the the APL programmers perspective, though maybe hard to implement in the interpreter.

I'm also curious if it is possible to implement a fair mutex in APL on top of :Hold or ⎕TGET.... I assume it is.

Anyway, no obligation to respond to these comments, but again I think it would be very useful to note this in the docs.

[Josh|Dyalog]

I'm also curious if it is possible to implement a fair mutex in APL on top of :Hold or ⎕TGET.... I assume it is.

I played around with this and it is simple enough to come up with your own fair mutex in APL using ⎕TGET. The key is, instead of waiting on an actual ⎕TGET, we have a cover function TGET which waits on a globally unique token for each request (GUID or can be done with ⎕TALLOC), and have a scheduler layer on top that keeps a running list of requests, and frees the earliest requested TGET thread on each TPUT of the actual token.

https://github.com/JoshDavid/FairToken

Caveats:
- Waiting for multiple tokens in one shot not implemented
- Timeouts not implemented
- Negative TGETs not implemented

I suppose you could also implement priorities quite simply with this architecture -- it could just be another property of a request.