|
01:48
ilbot3 joined
06:57
ggoebel joined
07:37
zakharyas joined
09:29
zakharyas joined
11:10
edehont joined
11:30
brrt joined
12:43
Util joined
14:22
brrt joined
14:49
brrt joined
17:55
domidumont joined
18:05
brrt joined
18:40
FROGGS joined
18:57
brrt joined
20:05
zakharyas joined
20:36
brrt joined
|
|||
| brrt | good * #moarvm | 20:46 | |
| evening, in fact | 20:47 | ||
| timotimo | hey brrt | ||
| brrt | hey timo | ||
| hmm... i'm wondering what i'm going to do with my amazing amounts of free time after my study is really, really done | 20:48 | ||
| (i've had the $thesis back this week with things to fix :-() | |||
| after the JIT is completed and merged, of course | 20:51 | ||
| well, let's do that first, shall we | |||
| oh, i've a roadmap/plan for the register allocator coming up | 20:53 | ||
| i'd be grateful if you could have a look | |||
| dalek | arVM/even-moar-jit: 0ede936 | brrt++ | docs/jit/register-allocator.org: Roadmap for register allocator Will develop the register allocator based on linear scan, with 4 separate passes. |
20:57 | |
| brrt | ^ that thing | ||
| TimToady wonders if a JIT is ever really completed :) | 20:58 | ||
| timotimo | once the jit "engine" stands, all we need to do is add more data to its tiles and strategies and such | ||
| brrt | you're both right, of course | 20:59 | |
| well, there's some things that aren't handled well within the current expr jit design, especially involving loops | |||
| this is because it wasn't designed for that, of course | 21:00 | ||
| .... i wonder if there isn't a good way to resolve that, though... | |||
| (the expression jit doens't really need to resolve that, the tiler can) | |||
| github.com/MoarVM/MoarVM/blob/even...ocator.org <- comments welcome :-) | 21:01 | ||
| we should really cleanup the github issue log... | 21:03 | ||
| jnthn | brrt: Using the expr JIT to better JIT array access, bigint operations, etc. would go a long way :) | 21:18 | |
| brrt | aye, that is the plan :-) | 21:19 | |
| oh, interesting bit | |||
| i'd like to add a THROW node type | |||
| which is exactly like CALL, but doens't return | 21:20 | ||
| why? register allocation reasons | |||
| if you know you're not going to return, you a): know you have to store your values before and b): know you don't have to store intermediaries | 21:21 | ||
| jnthn | Of course, with some kinds of exceptions we may return :) | ||
| But yeah, with most of the control ones you know :) | |||
| brrt | adhoc exceptions are the ones i'm thinking off directly | 21:22 | |
| the well-formed excdeptions aren't much of a problem | |||
| jnthn | Yeah, those ain't :) | 21:23 | |
| brrt | i'm just short of the energy level required to start hacking at the register allocator right now | 21:27 | |
| what i have found, and which is interesting i think, is that the contrast between 'cheap' linear scan and 'serious' graph colouring algorithms is ehm... unsubstantiated | 21:28 | ||
| jnthn knows that feeling... | |||
| brrt | they are two sides of the same solution | ||
| jnthn | Which contrast? :) | ||
| ah :) | |||
| brrt | well, i don't know if you're familiar with the literature, but authors typically write: 'register allocation is /just like/ graph colouring.... in JITs were speed is more important than quality, linear scan can be used' | 21:29 | |
| well, the things about that are: | |||
| - linear scan and graph colouring insert spills in response to precisely the same conditions | 21:30 | ||
| - and because in both cases exhaustively trying all options is not feasilbe (graph colouring is NP complete), both rely on a heuristic to guide choices | 21:31 | ||
| - because you have in both cases the exact same information (locally) available, you can, in fact, make much the same choices | 21:33 | ||
| linear scan has the advantage that it actually uses the linear order imposed by the code to let conflicts 'pop up' automatically | 21:35 | ||
| the disadvantage that crawling through the full solution space for the spill decision has to be implemented in a separate, somewaht burdersome, phase, and is probably not worth it | 21:38 | ||
| this will be a blog post that hopefully makes more sense than what i'm saying now, i assure you :-) | 21:39 | ||
| jnthn remembers his compilers lecturer noting that "most of the problems we need to solve are NP complete or undecidable, but we do them fast anyway" :) | 21:43 | ||
| I guess whether it's worth it to do a little bit better is fairly contextual. | |||
| (Crawling through the solution space, that is) | 21:44 | ||
| If there's very little gain to be had anyway, then for Moar it's almost certainly not worth it. :) | 21:45 | ||
| Also "worse in theory" results don't always pan out as "worst in real use cases" | |||
| *worse | |||
| The dominance algo we implement is very much a case of that. It's N ** 3 when there's an N*LOG(N) algo available. But thanks to smart engineering of the former, to get its constant factor really low, it wins on all the problems you're likely to have anyway | 21:47 | ||
| brrt | what is N in that case | 21:52 | |
| i've wondered more than once :-) | |||
| but yeah, your lecturer was right | |||
| another minornote | |||
| jnthn | Number of basic blocks | 21:53 | |
| brrt | aha | ||
| jnthn | The breakeven point was around 30,000 iirc :) | ||
| And the worst I've seen in spesh logs so far is about 200 | 21:54 | ||
| brrt | i realised today that most of the NP complete problems, like k-graph colouring and travelling salesman, are that way because a choice in the beginning can completely change the costs incurred later | ||
| oh, wow | |||
| still, N^3 for 200, that sounds... pretty bad | |||
| so i wonder how bad the O(N log N) algorithm does | 21:55 | ||
| jnthn | I think it's N^3 worst case. | ||
| iirc it's a fixed point algorithm and it converges pretty fast on typical CFGs | |||
| brrt | oh, right | 21:56 | |
| fixed point algorithms.... weird that i never really realised these existed | |||
| the tiler table generator is also a fixed point algorithm, and it defeats the earlier brute-force algorithm by a large margin | 21:57 | ||
| we should also get money from mozilla: morepypy.blogspot.nl/2016/08/pypy-...a-for.html | 21:58 | ||
| just because | |||
| jnthn is < 10 hours off his current funding running out | 22:00 | ||
| brrt | aw.... | 22:01 | |
| :-( | |||
| jnthn | Or more precisely | ||
| Off the currently agreed number of hours being used up | 22:02 | ||
| I believe there's funding for another bunch of hours. | |||
| brrt | \o/ | 22:03 | |
| jnhtn: are you planning to go to any later meetups this year? | |||
| seeing as neither of us is going to YAPC::EU | 22:04 | ||
| jnthn | It's hard to say at the moment. | ||
| brrt | oh well, no pressure :-) | 22:05 | |
| i'm thinking i may be able to go to the london perl workshop | |||
| if they still allow me in, of course | 22:06 | ||
| timotimo | jnthn: there's currently no osrpoint inside regexes; should we put some in some places? | 22:32 | |
| jnthn | timotimo: Hmm...maybe | 22:33 | |
| timotimo | maybe it'd be more important once we have noticable improvements in spesh that target regexen in particular | ||
| jnthn: how do we feel about an op in moar that strips a string of all of its marks? i.e. baseordat over a whole string | 22:37 | ||
| jnthn | What'd we use it for? :) | ||
| timotimo | ignoremark | ||
| in regexes | 22:38 | ||
| jnthn | I need to look at that ignore case thing but...we really shouldn't be having to fc a whole string up front... | ||
| We should provide ops that just take regions to compare, really | |||
| Allocation-free | |||
| timotimo | right | ||
| we do have an op that compares a region but currently it's implemented as lc-ing both strings fully and then comparing the results | |||
| jnthn | That's just asking for somebody to do better ;) | 22:48 | |
| timotimo | tbh, i still prefer what i did in the code gen, because it allows us to get index instead of having to scan | ||
| but i had to rip out the other part again; that one could still benefit from the improvement to that particular op | 22:49 | ||
|
23:20
BinGOs joined
|
|||