freenode/#clasp - IRC Chatlog
Search
3:51:05
Bike
oh, on that note, something i should mention. we hit a show stopping performance problem with partial inlining; it takes like 80-something% of compilation time
3:51:27
Bike
the issue is that as it proceeds, it turns lexical locations into inputs to the residual function calls
3:52:02
Bike
which is itself fine, except, when you setf the inputs of an instruction, there are methods to keep the using-instructions and defining-instructions data consistent
3:53:15
Bike
These methods first loop through all the existing inputs and removes them (using cl:remove) from data's using-instructions. then it puts the new inputs in and pushnews them all to using-instructions.
3:54:11
Bike
there are a couple solutions. one is that for full inlining like we're doing we don't need to maintain the inputs to begin with.
3:55:31
Bike
i'm not sure how to characterize liveness with shared data, but it is another obvious idea, yeah
4:07:04
karlosz
is the new inlining algorithm just going to be running partial inlining to completion? one instruction at a time?
4:10:37
beach
Be careful with a special version though. As the paper points out, and as the bug reports of the SBCL compiler suggests, inlining is not trivial, contradicting common wisdom in the literature.
4:12:39
beach
The other thing you can perhaps do is to avoid updating the using-instruction information until the end.
4:13:00
Bike
yeah i thought of that too, but right now the consistency is baked right into the slot writers
4:13:31
Bike
karlosz: i mean, you're still copying everything. i think the main change is that the hash set of stuff you've already mapped over would be smaller.
4:14:18
karlosz
that, and if you did do liveness anaylsis it wouldnt have to be on instruction granularity
4:15:28
Bike
might also be desirable to stop inlining halfway through a block, though who knows about that
4:15:51
beach
karlosz: Liveness analysis is done once, ahead of time, so that should not be a problem.
4:16:23
Bike
if the paper got a sequel or errata or whatever, it should be about copying nonlocal exits, and definitely copying enclose, which took the most time and which i added a subsubsubsystem for
4:16:40
karlosz
any huge change to the instruction graph like inlining warrants a liveness recalculation right?
4:17:28
Bike
the copied instructions don't have any liveness information associated. it would have to be copied as well, but liveness is in an accessory table and all.
4:20:02
Bike
i mean, overall, i think we should put some more thought into large transformations, and preserving this kind of accessory information as we do so
4:21:08
beach
This is just a hunch on my part. I haven't done any benchmarks, nor even any significant thinking.
4:22:53
karlosz
for example if you delete instructions from some other transformation you can update the liveness information appropiately
4:25:03
karlosz
if you delete a statement like a = b + c, for example, if a was live out, you can make it live in there where it wasn't before
4:25:38
karlosz
since anaylses would have to be intricately tied together to update each others information
4:26:20
karlosz
usually these sorts of things are done with one worklist, and compilers dont usually consider hot swapping passes in and out like cleavir does
4:26:53
karlosz
it would be cool to have modular analysies that could optionally hook into each other
4:27:11
Bike
llvm does it too, though it has a "pass manager" thing to organize it. i don't know what it does past ordering
4:37:17
beach
It's too bad that Clasp is running into these compile-time performance problems now. I had really hoped to work on the quality of the generated code first, and concentrate on compile-time later. Improving the quality of the generated code will also benefit compile-time performance, so that it becomes more obvious later where the compile-time bottlenecks are located.
4:38:24
Bike
since it's written in common lisp instead of "lisp but only using structs" or whatever it's harder to optimize, i think
4:39:18
beach
Those kinds of optimizations would be "micro optimizations". It is usually way more productive to consider things like data structures and algorithms.
4:41:37
beach
One thing I do insist upon before we try to improve performance is that we should know that the part that we are about to improve is actually a significant part of what is taking time.
4:44:38
karlosz
does SICL have some sort of implementation independent data base of function information like, does not side effect/coommutes or something like that?
4:46:44
beach
I started with type information, but got disgusted because I couldn't figure out the interpretation of FTYPE information.
4:50:35
beach
I don't look much at code in existing implementations. I often find it ugly, and very often totally implementation specific.
4:52:56
karlosz
there's some good stuff in there that could definitely be implementation independent
4:56:10
beach
But yeah, a consistent CLOS-based protocol for that kind of information, and an implementation of it that is neutral with respect to the Common Lisp implementation would be a good thing.
14:24:34
Bike
my understanding is that ftypes don't actually refer to the function object itself. i sort of remember that conversation though.
14:26:07
Bike
i see. well, we can think about what other information we'd want in a "database" or extended type at least.
14:30:52
Bike
in sbcl the fun-info has, let's see... whether it calls arguments; whether it unwinds (marked as unused); whether any arguments escape; whether it can be constant folded; whether it can be eliminated if the value is discarded; whether a style warning should be signaled if the value is discarded; whether it's a predicate; whether it's recursive; whether it's commutative.
14:31:38
Bike
also since sbcl has transformations specific to function calls instead of only inlining, there's a lot or even most information implicit in transformation functions
14:33:48
beach
Bike: So that challenge would be to turn that information into something independent of SBCL, and perhaps make it extensible.
14:35:54
Bike
i think stassats was also working on something so that which arguments were called or dxable or so on particularly was specified, like as a lambda list type.
14:41:05
beach
Bike: SBCL might be limited by the fact that the compiler can not use generic functions.
14:43:30
Bike
I mean, did you have a limitation in mind? I was expecting this would be something like a type, probably returned by function-info. Which is already extensible but were you thinking of something additionally?
14:44:51
beach
Nothing more specific. Just thinking how an implementation might want to override the behavior or adapt it, or supply information about internal functions, etc.
14:52:11
Bike
there's a lot of stuff we could do really. ftypes probably aren't adequate for a lot of stuff and they're frankly pretty weird
14:57:09
Bike
Shinmera: by the way, extremely obscure documentation question- method combinations have their own documentation, but you can also specify documentation on the method groups. do you have a protocol for retrieving that?
14:58:54
Shinmera
I have been thinking about a general protocol for "local definitions" -- things that are not in the global namespace, but reside under a global definition. For instance restarts and special bindings. No idea how you'd go about discovering those things, but I've wished for documentation of such things for a while.
15:00:46
Shinmera
I mean, for Definitions it doesn't matter. If you have a definition instance, you just call DOCUMENTATION on it and it does whatever.
15:01:25
Shinmera
So if the implementation offers a way of retrieving the docstring then Definitions can just hook into that.