libera/#sicl - IRC Chatlog
Search
5:37:29
beach
I guess initially, I'll just make a cleaner version of the portable condition system, using special variables to store the dynamic environment. I would have preferred to have dedicated entries in the dynamic environment for handlers, restarts, etc., but I'll figure that out later.
5:44:25
jackdaniel
awhat is somewhat characteristic is that handlers and restarts are grouped in clusters in the dynamic environment (i.e list of lists) because of how corresponding operators are expected to handle them
5:45:32
beach
Yes, I think I figured all that out yesterday. In some ways, the situation is ideal for special variables.
5:47:16
beach
Using special variables, it is more expensive (in terms of performance) to establish a handler or a restart, and less expensive to search for it. With special entries, it is the other way around. But I don't think performance matters very much for the condition system.
5:48:47
jackdaniel
because it is usually slow some techniques are not often used, but handling partial results signaled from a busy loop is something I've incorporated in code a few times
5:50:20
beach
And I think it is more common to establish a handler or a restart than to actually search for one, so that's part of my preference for specific entries. But mostly it is just an aesthetic opinion.
5:52:15
jackdaniel
ecl implements clusters by binding special variables, but they have predefined position (like the nil symbol and a few other things) in the core structure
5:59:14
beach
How is the dynamic environment represented in ECL? Like how do you store TAGBODY tags, BLOCK names, UNWIND-PROTECT functions, etc.?
6:15:49
beach
My initial plan for SICL was to have entries in the dynamic environment encoded as a sequence of words in the ordinary stack frame, and to link those entries with some kind of pointer. But then I decided to make an ordinary Common Lisp list of entries consisting of standard objects. As I recall, Bike did some performance tests, and decided this representation does not impact performance in any significant way.
6:17:09
jackdaniel
an array based stack is better for cache but it is hard to argue with actual benchmarks
6:18:58
moon-child
presumably just an issue of hotness--no one is setting up unwinding in tight loops so it's of no consequence
6:20:49
beach
I was more concerned about binding and accessing special variables. SICL uses deep binding for those, so there are entries in the dynamic environment for special variables.
6:22:33
beach
But many special variables are used for I/O, and then binding and accessing is probably dwarfed by the operation itself.
6:23:51
beach
moon-child: You store the current value in the dynamic environment. With shallow binding, you store the current value in a fixed location, and the old values in the dynamic environment.
6:24:36
beach
But that fixed location is not easy to manage in the presence of threads. It basically has to be located in the thread object. And to find it there is nontrivial.
6:25:13
beach
If you are doing it wrong, you may take a hash-table lookup for each access to a special variable.
6:25:52
beach
In fact, I was the one who designed the way SBCL does it (or did it when Dan Barlow implemented it).
6:27:02
beach
So, first you need to access the thread object. Then you need to figure out an index in a table, specific to the symbol in question (which you can store in the symbol object). Then you need to access that table.
6:28:22
beach
With deep binding, binding is just pushing an entry onto the dynamic environment, and unbinding is a NOP.
6:29:10
hayley
You might be amused to hear that Java may well have a dynamic environment in the near future, with the ScopedValue class <https://download.java.net/java/early_access/loom/docs/api/jdk.incubator.concurrent/jdk/incubator/concurrent/ScopedValue.html>. Looks like they use deep binding.
6:29:20
moon-child
the way it works in sbcl now is that each special value is associated with one fixed global location (I think stored in the symbol), and one fixed offset in the thread-block. The latter is checked first; if it contains a sentinel value, then there is no thread-local binding, so the global one is consulted. This sounds more like what you describe as shallow binding
6:30:28
moon-child
(I was describing it because I don't know if it's changed; you implied that it might have)
6:30:49
moon-child
deep binding would seem to necessitate two dependent loads, where shallow binding only needs one
6:32:10
moon-child
(since the load from the shared location can be done in parallel with the load from the local location)
6:32:25
beach
moon-child: Deep binding also needs to search the dynamic environment. But the point is that shallow binding is much more expensive in terms of binding and unbinding. So again, it is a question of relative frequency of those operations, and of those operations compared to everything else.
6:36:37
beach
I guess with a loop, the access to the entry in the dynamic environment could often be done outside the loop.
6:44:23
hayley
I've been working on an interpreter for the...platform Gnuxie and I are designing. (I still don't know what to call it - it's not just an abstract machine, or a language, it's a combination of things.) Part of that includes implementing the dynamic environment, and designing a nice interface for it. But I'm not too sure how to design either the implementation or interface.
6:48:29
hayley
With regards to the interface - as moon-child has argued, (thread-)global bindings are quite nasty. So I've associated a function with each special variable, which is used to compute a default value for the variable on demand. I think it should be on demand, as there's no reason for a thread to compute the default values for special variables which the thread cannot possibly access.
6:48:54
jackdaniel
eulusp has separate operators to access the dynamic environment - if you believe that explicit is good then that'd be for the interface
6:49:49
jackdaniel
usually special variable defaults to symbol-value when there are no bindings - no function neede to compute it
6:50:52
hayley
In a system with first class global environments, the special variable may be in a different dynamic environment; in an object-capability system like ours, the special variable may not be reachable by the thread. So I suspect any given thread will not use most of the special variables in the system.
6:53:40
hayley
Because I want thread-local defaults. For example, a random number generator module should provide a separate generator for each thread.
6:54:09
moon-child
jackdaniel: you might, say, initialise a hash table or other structure; should be fresh per thread. Or, my queue has new threads inherit a sequence counter from their parent, as making a thread is a useful type of happens-before that doesn't fit nicely into po and rf
6:57:10
hayley
Laziness provides good time and space complexity - a thread only needs to compute and store the default value for the special variables it uses. But the most obvious data structure for a sparse mapping of special variables to default values is a hash table, which entails that a hash table lookup is required to find a default value. Maybe this isn't so bad, compared to having to search linked entries in the dynamic environment, but it is a bit
6:59:36
moon-child
I still think that the ideal is probably something optimistic based on access patterns
6:59:59
moon-child
what if it's a hash table w/inline cache, but transposed so you search for the thread id in the variable. And if the cache gets too big, then the variable is popular, so switch to a fixed offset in (all) thread-blocks
7:00:52
hayley
Right. Additionally we chose for bindings to be immutable, as we want mutable data structures to stick out like a sore thumb. But I created some bugs involving recursively trying to compute the default value, which would allow for more than one default value to be written. Laziness might also produce some other spooky-action-at-a-distance. So I'm still uneasy about that interface.
7:01:33
hayley
I read ScopedValue does some caching, but would have to double-check the OpenJDK implementation.
7:02:39
hayley
The documentation for ScopedValue mentions "Scoped values are designed to be used in fairly small numbers. get() initially performs a search through enclosing scopes to find a scoped value's innermost binding. It then caches the result of the search in a small thread-local cache. Subsequent invocations of get() for that scoped value will almost always be very fast. However, if a program has many scoped values that it uses cyclically, the cache hit
7:05:31
moon-child
you know what would be nice? Some sort of hardware-assisted interface for virtualised storage :)
7:05:37
moon-child
(c.f. https://outerproduct.net/boring/2023-03-22_cpu-compiler-gc-ohmy.html 'forwarding pointer')