freenode/#sicl - IRC Chatlog
Search
7:22:40
no-defun-allowed
Would (funcall (hash-table-hash-function ...) ...) be able to return an (unsigned-byte 64) value without boxing, if hash-table-hash-function is known to be of type (function * (unsigned-byte 64)) and we use call-site optimisation?
7:23:56
beach
That would require some trickery. First of all, call-site optimization works only for functions referred to by name.
7:23:57
no-defun-allowed
I suppose we won't be needing the two bits (or one, if I start allowing hash functions to return negative fixnums) lost to fixnums any time soon.
7:25:24
no-defun-allowed
Whoops, it takes an (unsigned-byte 64) offset and returns an (unsigned-byte 64) hash.
7:36:17
shka_
beach: would you be able to extend the call-site-optimization for handling the most frequent (specified ahead of time) callbacks to the standard CL functions?
7:38:24
shka_
function object, most of the time i am thinking about eql passed as :test to find and the likes
7:39:19
beach
Well, call-site optimization is really only useful for functions called through the name, and for which the association between the name and the function object can change at run-time.
7:40:15
shka_
yeah, but how can you inline function that is passed as an argument, and therefore strictly unknown?
7:43:37
beach
I mean, if you have (F ... :TEST #'EQL) where F can change at run time, then we can't know at compile time whether F is going to call #'EQL, store it in some data structure, or something else.
7:44:25
beach
And we can use the same technique for every such built-in function as we use for the sequence functions.
8:07:18
shka_
beach: yeah, sometimes i think that "sealed functions" would be useful feature for this purpose, but at the same time this would be very powerful gun pointing at your own feet
8:09:39
beach
Such a thing would be useful only if benchmarks show that there are a significant number of use cases. I am not going to include some complicated mechanism unless there is evidence for that. Now, call-site optimization as documented in the paper is going to be used A LOT, and it will save several memory accesses each time, so I know that it will be useful.
8:11:10
beach
shka_: What you are "suggesting" again raises my fear that, as soon as SICL is operational, some people are going to submit complicated code for special cases that are almost never encountered, and then I will either have to disappoint them by refusing the code, or accept it and increase the maintenance burden.
8:12:56
shka_
sealed functions would be complicated to implement, situational useful and would cause ultra-annoying bugs
8:13:02
beach
A traditional Common Lisp implementation like SBCL may need to handle all those special cases, because it is already full of special cases for things like data representation. I really want to try to use fewer, more general, mechanism in SICL, if I possibly can.
10:13:35
beach
This morning, I have been working on HIR-to-MIR. Specifically, I added code for translating boxing and unboxing instruction with type DOUBLE-FLOAT. Next in line is (SIGNED-BYTE 64). It is a bit more complicated because I need to insert tests for its value to determine whether to create a fixnum, a positive bignum, or a negative bignum.
10:14:29
beach
But it is very liberating that it is possible in HIR code to add calls to functions not previously seen, like MAKE-INSTANCE for example.
10:16:13
no-defun-allowed
Here is a ridiculous thought: could functions have multiple entry points, or some other way of communicating the word "layout" of the object returned? Say, we could have one for arbitrary tagged values, another for (unsigned-byte 64), another for double-float, and I think that's about it.
10:17:25
heisig
no-defun-allowed: That is a fun thought. The main problem is that the number of variants grows exponentially with the number of arguments.
10:18:12
no-defun-allowed
I was hoping to avoid it by just specialising by the return type, which would still be no good for REDUCE-like patterns (such as my hashing implementation - oops).
10:21:19
no-defun-allowed
I was mostly thinking of the (funcall (hash-table-hash-function ...) ...) case - we'd know H-T-H-F is of type (function * (unsigned-byte 64)) (n.b. * is known, but is irrelevant) and so we would arrange to use the entry point which somehow returns (unsigned-byte 64).
10:25:10
no-defun-allowed
And admittedly I don't know how easy it would be to generate the sort of code on the callee, to arrange for returning different word formats.
10:26:15
no-defun-allowed
But I think there are few enough cases for the return type that it's not absolutely pointless. You'd still have to do argument parsing and boxing with this change, so it's still not good for the function used to REDUCE.
10:26:26
beach
I think you would either have to duplicate the callee or add another (fast) function call for the boxed entry point.
10:51:46
beach
no-defun-allowed: Are you not convinced that a non-negative fixnum has enough precision for a hash value?
12:06:40
scymtym
::notify Bike i updated the pull request, but i can't currently test things properly because of a problem in the reaching definitions system. i think you already fixed it in the renovate branch. could you add the fix to master?
13:26:17
beach
So I guess of the two most significant bits of a 64-bit signed integer are the same, then shifting the number one position to the left will give the equivalent fixnum representation of that number.
13:30:34
beach
As I recall, the main reason for considering using fixnums was so that the code could be written using Common Lisp functions.
13:31:22
beach
But if (named) functions can take unboxed 64-bit integers and return such integers, then that reason may no longer exist.
13:37:15
heisig
If the limbs are stored in a specialized array, I see absolutely no problem with using 64-bit unsigned integers.
13:38:34
heisig
I see no reason why an individual limb should ever leave a function working on such a bignum.
13:38:52
beach
Well, if we do that, we either have to do all computation within a single function, or we need to make it possible for a function to return unboxed unsigned 64-bit integers.
13:41:28
heisig
Right. If we can efficiently return unboxed 64-bit integers, that is one more reason to use them to implement bignums.
13:44:05
beach
Each function that returns a full 64-bit number has two entry points. The default entry point just contains a call to the second entry point, and box instructions after the return.
13:44:23
beach
This call is going to be cheap compared to the boxing code, so there is no performance penalty.
13:45:39
beach
A call site can indicate that it is able to take either a boxed Common Lisp object as a value, or an unboxed value which is then either a double float or a 64-bit signed or unsigned integer.
13:50:18
beach
1. The caller accepts only boxed Common Lisp objects as values and the callee is not one of those special functions. Then the only entry point of the callee is called, skipping the argument-parsing prefix as usual.
13:51:11
beach
callee is one of those special functions. Then the call-site manager generates a call to the default entry point of the callee.
13:53:48
beach
3. The caller can accept either boxed or unboxed values, and the callee is not one of those special functions. Then the call-site manager generates a call to the only entry point of the callee, and at the end of the snippet, jumps to the return address that accepts boxed values, and the caller will then check the types and unbox them or call error or something.
13:55:37
beach
4. The caller can accept either boxed or unboxed values, and the callee is one of those special functions, and the value types match. Then the call-site manager generates a call from the snippet to the alternate entry point, followed by a jump to the address that accepts unboxed values.
13:56:35
beach
There is a 5 that happens when the caller can accept both, and the callee is special but the value types don't match. You get the idea.
13:59:35
beach
Definitely. One of my favorite applications is the analysis and synthesis of sound. And double floats would be the default data type then.
14:00:27
beach
And, as we said, if we want to implement the bignum code in Common Lisp with separate functions, then we need for unsigned 64-bit integers to be passed unboxed.
14:01:54
heisig
Also, double floats are the most common data type in scientific computing. And this is an area where performance matters, so boxing/unboxing is not an option.
14:03:19
beach
I want to be convinced that we can do this efficiently so that 1. I can include it in the paper so as to make the argument stronger, and 2. So that I can write this boxing/unboxing code for 64-bit integers and go on with HIR-to-MIR. :)
14:04:00
frodef
I suspect it will also be complicated to have unboxed floats everywhere, but I might be very wrong.
14:05:06
beach
Cleavir already allows for unboxed floats, and it emits box/unbox operations around array access to specialized float arrays.
14:06:39
frodef
My perspective (from video processing) has been that signal/float processing is a high performace activity that is best done by specialized functions, such as (somewhat higher-level) assembly etc, and the data exists mostly within specialized buffers.
14:07:39
heisig
I am still trying to parse the list of cases for the call-site manager. And I'm thinking about how this information could be encoded in practice.
14:08:29
beach
heisig: Each call site has a standard object that describes all this stuff associated with it.
14:10:25
frodef
seems to me high-performance signal processing is a very very different ball-game than what a general run-time should be optimized for.
14:10:45
frodef
..then again, if you can have the former without any penalty on the latter, then all the better :)
14:11:46
beach
frodef: I truly believe that the call-site optimization of the paper will give us function calls that are as fast or faster than those of a typical C++ implementation.
14:12:21
heisig
I think we should introduce the notion of an object encoding. Each encoding has, at minimum, a Common Lisp type and some methods for emitting a sequence of instructions to convert between that encoding and the canonical (boxed) encoding.
14:12:33
beach
Even in C++, if you have a shared library, function calls and accesses to global variables have indirections, and we can do better than that.
14:13:50
beach
heisig: There are very few object types that can exist both as unboxed and as boxed values.
14:14:35
heisig
There is the canonical encoding, specialized ones for double-floats and 64-bit unsigned integers, but maybe also encodings for certain SIMD data types.
14:15:13
heisig
I think the rule should be 'everything that fits into a single CPU register'. And this includes SIMD data types.
14:16:14
beach
I guess I need to hint something like that in the paper. But I really should be working on HIR-to-MIR, coding wise.
14:18:12
Bike
multiple values might also be conceived of in terms of boxing and unboxing. if the caller and callee can agree on how many values are returned you might be able to skip e.g. putting the number of values in a register. my vague understanding is that in haskell they do this by returning a sort of unboxed tuple or vector or something
14:18:13
Colleen
Bike: scymtym said 2 hours, 11 minutes ago: i updated the pull request, but i can't currently test things properly because of a problem in the reaching definitions system. i think you already fixed it in the renovate branch. could you add the fix to master?
14:21:34
Colleen
scymtym: Bike said 28 seconds ago: whoops, thought i merged renovate all the way already. done now.
14:26:27
Bike
i think reaching definitions is still broken in that it fails its tests, though it does load
14:44:09
beach
frodef: It would be great to have you on board. With your experience, it's an ideal fit.
15:03:43
scymtym
Bike: i updated the PR. those changes are enough to make everything (including test systems) compile and load in SBCL
15:15:38
scymtym
i don't know. if you at the diff, there are TODOs related to ctypes. i don't know whether the complete transition can already be made
16:11:47
Bike
cleavir-ctype is massively broken (or rather, not really used) and i'll have to figure out how to fix it... ech...
16:12:40
Bike
well, basically you can't use any of its operations without a system parameter, and not everything has a system parameter at all times
16:13:40
Bike
which works, but if you do that the system is kind of pointless since you can't customize it
16:17:52
Bike
i think the sensible solution would be to avoid computing type intersections in cleavir-env, and instead store the intersection in the local environment, so cst-to-ast can compute it
16:35:15
Bike
https://github.com/s-expressionists/Cleavir/pull/7/commits/f27c1d5744e3c1704e5c82ee2265eb5693fd7f70 we've been trying hard to avoid this kind of conditional - what trouble does sbcl have with the declaration?
16:41:08
beach
HIR-to-MIR passes, but there are a lot of FIXMEs in there, and I'll work on those incrementally. The good news is that processing time did not increase significantly.
16:46:37
scymtym
Bike: i think the "recursive" nature of the type is the problem. for me, this resulted in some obsolete instance update cycle that eventually landed in ldb
16:47:22
scymtym
may only happen because i use elevated safety so that SBCL inserts type checks for slots
16:49:32
scymtym
everything in the visualizer related to environments is also very wonky and should be redone properly in some way
16:50:37
Bike
if i do rewrite cleavir to use trucler that might go away, in that trucler's sbcl environment interface is probably less rotted than the one in Environment/Examples/ or wherever
16:52:42
scymtym
i use the environment to inject the policy chosen by the user. other than that, i just needed something that allowed compilation to finish
16:53:08
scymtym
but picking up global functions and variables from the host may actually make sense as a default