freenode/clasp - IRC Chatlog
Search
3:33:11
drmeister
!notify frgo I believe I fixed the problem that you encountered with swank-asdf.lisp.
3:39:10
drmeister
Bike: Are you online? Do you have a few minutes to talk about instructions, inlining and array operations?
3:40:47
drmeister
I implemented some of the fixnum arithmetic as far as I understood to see what kind of speed that provided. Quite a lot - that's where I get the 2x slower than SBCL when you do fixnum arithmetic.
3:41:11
drmeister
I haven't implemented other arithmetic or array operations with inlining, compiler-macros etc.
3:48:07
drmeister
The numerical stack is fully implemented in C++ but the problem with that code is that the dispatch on types is done in C++ - so it's not useful for type inference.
3:48:55
drmeister
I was thinking about breaking the code up into lots of little functions that are called from a C++ dispatcher for bootstrapping and then re-implementing the dispatch in CL, calling the little functions that do primitive operations written in C++
3:49:47
drmeister
LTO will inline the little functions - that are the primitive arithmetic operations.
3:50:34
drmeister
We just translate the C++ dispatcher using TYPEQ and the type inference will be able to use it.
3:53:49
drmeister
Yes. Some of the switch cases already call little functions - they can be exposed and called from Common Lisp with no over head/inlined.
3:54:05
drmeister
Others like Bignum_v_ratio https://github.com/drmeister/clasp/blob/dev/src/core/numbers.cc#L353
3:54:31
drmeister
They need to be bundled up into a function and called in this function and also exposed to Common Lisp.
3:55:21
drmeister
Then contagen_sub: https://github.com/drmeister/clasp/blob/dev/src/core/numbers.cc#L460
3:56:21
Bike
a bit of this would have to be adjusted. two_arg__PLUS_FF handles the bignum check itself
3:59:59
Bike
something like (defun row-major-aref (array index) (cond ((typeq array (array bit)) (primop:aref bit array index)) ...)) is what i'm thinking
4:03:47
drmeister
We can create these NativeVector_xxx_O types that contain a vector of any C++ class or type.
4:05:18
drmeister
I'm a little unclear on upgraded-array-element-type and what it does. Now seems a good time to learn.
4:06:44
Bike
well you have some limited repertoire of array storage types - you have the full thing that stores arbitrary objects, one that only stores doubles, and so on
4:07:18
Bike
but the repertoire varies between implementations and users don't want to care, so they just specify a lisp type, and you look at that and go okay, that fits in THIS array storage type, so i'll return this kind of array
4:07:56
drmeister
That's done by make-array though - isn't it? The U-A-E-T function can be implemented as:
4:08:00
drmeister
(defun upgraded-array-element-type (type &optional environment) (array-element-type (make-array 0 :element-type type)))
4:10:22
drmeister
Ok, but the point is if I say (make-array 5 :element-type 'double-float) clasp could return a NativeVector_double_O object.
4:11:21
drmeister
I'm not going anywhere with that - just confirming. There's not that many types that need to be supported are there?
4:12:26
Bike
the requirement on uaet is that uaet of bit is bit, uaet of base-char is base-char, uaet of character is character, and everything else does bla bla lattice thing
4:13:12
Bike
long story short, uaet of any subtype of bit is bit, uaet of any subtype of base-char is base-char, uaet of any other subtype of character is character, everything else is up to you and can be T.
4:15:40
drmeister
So if I (defstruct foo (x 0 :type (integer 0 100)) (y 0.0 :type 'double-float)) and then (make-array 5 :element-type 'foo) It could return a vector of compact structs of <int,double> ?
4:20:24
Bike
(let ((array (make-array 5 :element-type 'foo)) (foo (make-foo))) (setf (aref array 0) foo) (eq (aref array 0) foo)) => T
4:23:53
Bike
i don't think C++ has a concept of objects being equal if they're "the same object". there's pointer and reference equality instead.
4:24:12
Bike
which is pretty subtle and honestly i don't want to think about C++ that much, i have enough trouble with C.
4:24:31
Bike
if the requirement is too arduous you could define your own functions that don't preserve identities.
4:25:04
drmeister
I'm just curious how CL handles these things. Going back to implementing fast array operations - I see what you are saying about dispatch.
4:25:58
drmeister
What's the next step in type inference? Is it that clasp lags in fully taking advantage of it because it makes too many function calls?
4:26:59
Bike
the one that i pushed today is tracking values types, which after some finagling lets you infer types as you do and then extract the type of the function, which means you can put the inferred type in the environment for later analysis
4:28:33
Bike
knowing values types also goes some way to allowing multiple value returns in registers and inlining multiple-value-bind lambdas, which is why i started working on cleavir centuries ago
4:29:12
Bike
then you have more inlining, which yes would help, and also let you take advantage of inference, since eg right now there is absolutely no point to telling clasp that something is a single-float
4:30:13
Bike
algorithmically speaking, a smallish improvement i'll make at some point is tracking function types during inference, which will help results a bit by eg inferring the type of local functions and then actually using that information
4:30:56
Bike
and then there's what i'm mentally calling "backwards" inference, which just means inferring types in the opposite direction of control flow, which is tricky but could make it a lot better.
4:32:16
Bike
but of these inlining is probably the easiest and one of the most helpful. funcall instructions are useless to the inferencer and declared return types only help so much
4:35:05
drmeister
There are some cases where I'll have to switch from C++ virtual functions to a hand written dispatcher.
4:35:48
Bike
you could also provide an inline definition to cleavir and use a virtual function for the full call
4:37:32
drmeister
Yes, that is a good suggestion. So I wouldn't need to do much with the C++ code - just write a regular function and have the virtual function invoke it. Then invoke the regular one from the Common Lisp dispatcher that uses type-inference and inlining.
4:40:53
Bike
there's like a lot of little things to help. Having function types specify (values whatever &rest nil) will help the values types inference enormously even though it looks stupid... you could put a compiler macro on map and concatenate to wrap them in THE... plenty of things
4:41:11
drmeister
I'll implement contagen_add in Common Lisp - and a (defun row-major-aref (array index) (cond ((typeq array (array bit)) (primop:aref bit array index)) ...))
4:59:37
Bike
they're special operators, ie things the compiler deals with especially, but ones that the evaluator doesn't need to worry about.
5:00:13
Bike
like, in sbcl, the definition of car is (defun car (x) (car x)) or so. this is because 'car' is a special operator that the compiler deals with (in the function body), but also a function (as defined by the defun)
5:00:32
Bike
in cleavir the primitive operations are a bit finer, and named more distinctly, but it's the same idea.
5:01:52
Bike
the compiler operations on them are defined in Generate-ast/convert-primop.lisp. most of them have a distinct AST and instruction
5:02:34
Bike
generate-ast sees (CLEAVIR-PRIMOP:VALUES ...) and makes a special values-ast, and then ast-to-hir sees the values-ast and generates a fixed-to-multiple-instruction.
5:04:09
Bike
simple-t-aref, simple-t-aset, non-simple-t-aref, non-simple-t-aset, simple-bit-aref, etc
5:05:00
Bike
i asked beach and he agreed that they don't all need to be distinct asts and instructions, so i'm going to reduce it to one for aref and one for aset, and have it take an argument for the type like i did a couple minutes ago in my example.
6:03:54
drmeister
Bike: What about the boxing and unboxing primitive operations - are those ready for use?
6:06:09
drmeister
I'll ask beach - because that will strongly influence how these arithmetic operations should be constructed.
6:10:33
drmeister
beach: Are the xxx-float-box-instruction and xxx-float-unbox-instruction instructions useable at this point?
6:28:00
beach
drmeister: Accessing a specialized array using the AREF primop should return the unboxed value.
6:28:49
beach
So the function AREF (or ROW-MAJOR-AREF perhaps) needs to be implemented to use the AREF primop followed by BOX.
6:30:49
beach
drmeister: There is no way you can implement arrays containing structs in a conforming Common Lisp implementation.
6:33:50
beach
Now, if you need that kind of feature in order to be compatible with some existing C++ library, you can of course sacrifice the "conforming" part and live with the performance hit.
6:34:43
Bike
i can see how it would be nice to have something like a struct but without caring for identity... get some memory locality in the array and such
6:35:43
beach
But now, if you do the equivalent of (setf (aref a1 i1) (aref a2 i2)) you have to copy the struct. Hence the performance hit.
6:36:38
beach
I could also talk about the unreasonable semantics of that kind of array, but performance seems to be the only thing drmeister cares about, so I'll restrict my discussion to that.
6:37:19
Bike
i mean i'm thinking of it like fixnums, right? you "copy" them around all the time but it's just moves.
6:38:17
beach
Sure, but with fixnums, the Common Lisp HyperSpec specifically allows it. Also, a fixnum is meant to fit in a word, so you don't take a performance hit then.
6:41:15
beach
It would have been quite unreasonable to write the Common Lisp HyperSpec with exceptions such as allowing for identity not to be respected if the element type is a sufficiently small struct.
6:44:10
beach
I think the best way to express this kind of semantics is to have two parallel, specialized arrays. Then it is also clear that you don't care about identity, because there is no compound object there.
6:44:42
beach
But, again, if you want to be compatible with some existing C++ library, you just sacrifice conformance and live with the performance hit.
6:45:08
Bike
um, just to be clear i wasn't suggesting this happen with normal lisp arrays, because, yeah, obviously it's not conformant.
6:48:19
beach
As I frequently say, there is no way to write a C++ program that is both modular and fast. And the reason is the absence of automatic memory management, which in turn requires this kind of specialized array, which makes it necessary to copy objects much more often, and which ultimately makes the program slower.
6:48:20
beach
It is also questionable semantics to have several copies of some object floating around, possibly with different values of some members.
6:49:38
beach
The object representing drmeister could have a different address in different parts of the program.
6:51:36
beach
The way C++ programmers deal with this conundrum is to introduce smart pointers and reference counters, so that they can respect some reasonable concept of modularity.
6:52:48
beach
But then, a simple assignment such as a = b is now no longer a single MOV, but accessing memory to decrement and increment counters, and a test to see whether a counter is zero.
6:54:26
Bike
i do remember, since C++ was one of the first programming languages i "learned", hearing an experienced user talk about why there was an operator=, and that was how i realized i didn't know C++
7:02:53
beach
... and that is why the investment in terms of learning C++ is so great that many experienced C++ programmers react so violently when being told that what they know is not even a good way to make programs fast. This is the "fixed mindset" discussed by Carol Dweck, and what I called "performance-oriented" personalities in my essay.
7:04:43
beach
Yet here we are, the industry full of developers that are ignorant of basic things like computer architecture, memory management techniques, etc., making decisions about tools for significant software projects, using reasons such as "The C++ compiler is known to generate fast code, so let's choose C++ for this project".
7:05:37
beach
The worst part, in my opinion, is that after they have introduced their reference counters and such in order to make their code a bit modular, they are still convinced that it is fast.
7:30:26
beach
In my industry talks, I point out that a phrase that I often here, namely "We need all the speed we can get" really means "We are willing to spend an arbitrarily high amount of development and maintenance effort in order to gain even the tiniest speed improvement". But they often realize way too late that this is what the phrase really meant.
7:38:22
easye
I often describe try to divide functional vs. non-functional requirements for a client. I put speed in non-fuctional.
7:39:11
easye
It is a terrible distinction in many ways, but placing requirements in classes can often help the other party make a different kind of decision then they were going to make.
8:12:48
beach
Bike: Before we collapse all the AREF instruction classes and AST classes into one, we need to think about whether someone might want to dispatch on the individual classes.
8:13:37
beach
Bike: Perhaps a single class with subclasses and a constructor that selects the right subclass based on element type, simplicity, and whether the output is boxed or not.
8:14:21
Bike
but the subclasses are unknown. i mean that's the fundamental reason i thought of collapsing, we don't know the UAETs.
8:14:37
Bike
if there's an accessor for it, it's, you know, we'd be defining classes based on information from the environment.
8:16:42
beach
Because some arrays might be specialized to fixnum or character, and you would keep those boxed in the array.
8:17:51
beach
Otherwise, you would have to wait for the box (or no box) to determine whether the object is boxed or not.
8:18:27
Bike
hm. there's a point. i wasn't thinking about boxedness, so i figured an aref instruction would be inferred to output whatever the element type of the instruction was. but that's not correct.
8:20:40
beach
I think the fact that HIR allows unboxed Common Lisp objects is going to be important to optimization steps that work on the HIR level, such as the type inferencer, and this box/unbox remover that is planned.
8:20:56
Bike
i'm not immediately sure how to express the conversion from boxed descriptor to unboxed descriptor.
8:23:52
Bike
i mean, how i was thinking it would go is that there would be primop:aref, and the implementation would do (defun row-major-aref (array index) (cond ((typeq ...) (primop:aref foo ...)) ...)) where foo is a common lisp type and that's it, we don't need more. and the inferencer looks at the instruction, finds the smallest descriptor that fits foo, and that's the output.
8:26:05
beach
There is no reason for the person in charge of the Common Lisp implementation not to know the upgraded element type of its own arrays.
8:27:03
Bike
for example, sbcl has like nine different integer types that it can upgrade to. fifteen bit, sixteen bit, thirty one bit, whatever.
8:28:17
Bike
that's a type, not a descriptor. the inferencer only propagates descriptors. a very limited and fixed set of things.
8:28:52
beach
We should expect the implementation to add descriptors to the type inferencer, or (alternatively) provide more plausible descriptors.
8:31:15
beach
Cleavir should, as much as possible, allow the implementation to configure stuff like that.
8:31:35
Bike
no, not exactly... but it complicates the descriptor system quite a bit. right now descriptors are all symbols. join and meet are GFs but specializing on symbols is, you know, eh.
8:32:03
Bike
i was adding function types and it was not pleasant so i gave up (for now). the values descriptors i added are more complicated but they're also separate.
8:32:32
beach
I understand. I think it is legitimate to do something simple that works and then thing about how to generalize it later. But implementation-specific stuff should always be kept in mind.
8:33:20
Bike
basically there's no capability to do anything with a descriptor. you just send it along.
8:33:39
beach
For local functions it works, but for globally defined functions, it must be restricted to functions that we know can not change.
8:33:45
Bike
even something like "well, this describes an array, let's get the element type" would be an addition.
8:34:11
Bike
putting inferred types in the environment is something i'll figure out later and involves a lot more work with the environment etc.
8:34:52
beach
Anyway, the inferencer is fine, but we need to keep in mind how to generalize it to allow for implementation-specific types.
8:35:09
Bike
and i mean i've implemented the cl type system with classes and specialization and stuff before, that's not that hard to do, and it would be easier if it was a limited system where subtypep has no fudge room.
8:35:38
Bike
...but that's not really something i want to just have as part of the inferencer. seems like more of a "SICL" thing, to my limited intuition.
8:36:45
beach
If SICL (or SBCL or some other implementation) needs a different type inferencer from the one Cleavir provides, I think we have failed. No?
8:37:33
Bike
i meant, right now type descriptors is one file, actually two with values. because it's simple and private.
8:39:05
beach
I see what you mean. But such a general type system sounds like a way more ambitious thing than allowing implementations to configure the type inferencer with their own specialized arrays.
8:40:32
beach
I think we need to do this in reasonable steps, or we risk getting an over-engineered mess.
8:41:36
Bike
i guess there could just be a compound descriptor for "unboxed". turn unboxed-single-float into (unboxed single-float). or a struct to do the same.
8:41:50
beach
And we sometimes need to resist the pressure from drmeister in his quest for more speed if we don't know how to do something that is implementation configurable.
8:44:29
Bike
oh yeah sure. i mean it's not that complicated if you already know what boxing is, i just never looked at it at all.
8:45:22
beach
Speaking of which, do you think we will have the opportunity to discuss this at ELS2017?
8:48:18
Bike
well that's drmeister's thing; i don't know the process, but it's certainly not in the gank.