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')
10:08:30
jackdaniel
bike: in bir are "no exit" (i.e non-local return-from) iblocks connected to the final exit node or they just hang as leafs?
12:10:54
bike
jackdaniel: "final exit node" meaning? an iblock can be terminated by an UNWIND for a nonlocal exit, and the UNWIND has a DESTINATION slot holding the iblock it exits to, as well as a reerence to the COME-FROM instruction establishing the exit point
12:15:46
jackdaniel
bike: "normal" control-flow graph has the entry block and the exit block; do you connected non-local control transfers to the exit block?
12:22:38
bike
a bir function may have a block terminated by a returni instruction, representing normal return from the function - is that what you mean by exit block? if so, there's no guarantee there's an exit block at all (for functions that always loop or NLX). if a function has an NLX and a normal return, the NLX is not connected directly to the normal return, but is indirectly connected through the predecesssor in the
12:38:04
bike
also, i think you mentioned earlier that while you were looking into the design, you weren't going to use cleavir in ecl. can i ask why?
12:39:30
jackdaniel
cleavir seems to be whole package, so I'd need to pull the reader, the ast representation and many other things and add ecl-specific bits - that'd be effectively dumping the compiler and replacing it with a new component (that seems to be more work)
12:40:30
jackdaniel
the second reason is that cleavir probably would be rather expensive to invoke, and that would add up with gcc invocation
12:41:54
jackdaniel
(that said I'm not saying that I'll never use cleavir in ecl, but that's rather out of the scope of what I'm doing right now)
12:42:45
bike
it should be possible to use the IR bits without using ASTs. i'm about halfway through a system to convert the cvm bytecode directly to IR. it's not done, so i can't honestly recommend it to you or anything, but i am working on making the IR and transformations usable by themselves
12:43:36
bike
as for expense to invoke, yeah, it's not too zippy, and making it faster is a low priority so far
12:44:23
jackdaniel
the main motivation of what I'm doing right now is to separate the frontend from the backend of the compiler, so I can output the bytecode and/or the web assembly
12:45:04
jackdaniel
(because the bytecodes compiler as it is does only a minimal compilation and not on all targets the c compiler is available)
13:25:30
jackdaniel
bike: here's another question - in compile-ast you stipulate that the function returns NIL for no values, :no-return or (list bir) -- is NIL used anywhere? if so, couldn't it be represented with a bir standing for 0 values?
13:51:08
bike
jackdaniel: that's "no values" in a sense different from (values) - it means for ASTs that conceptually do not return values, like set-constant-symbol-value
14:00:13
jackdaniel
this ast does not seem to have a documentation; what is an advantage of having ast nodes that do not return values but are not non-local transfer control?
14:05:15
bike
set-constant-symbol-value represents the setting part of (setf *special* value). it's generated by convert-setq-special-variable. if you check convert-setq.lisp, you can see it only generates it in the middle of a progn where it's OK
14:06:22
jackdaniel
I see; would it make a difference if it was handled as if it were returning 42 or anything else?
14:12:19
bike
i'm not sure exactly what that would mean. the equivalent instruction has no outputs, so it doesn't "really" return anything
14:13:55
jackdaniel
I was thinking whether there are some gotchas if I don't handle such special case myself, that's all. I think I have a gist of it, thanks
14:18:48
bike
there are few of the no-value ASTs and it might be a good idea to eliminate them to make things more regular.