Perl 6 - the future is here, just unevenly distributed

IRC log for #moarvm, 2016-08-09

| Channels | #moarvm index | Today | | Search | Google Search | Plain-Text | summary

All times shown according to UTC.

Time Nick Message
01:48 ilbot3 joined #moarvm
01:48 Topic for #moarvm is now https://github.com/moarvm/moarvm | IRC logs at  http://irclog.perlgeek.de/moarvm/today
06:57 ggoebel joined #moarvm
07:37 zakharyas joined #moarvm
09:29 zakharyas joined #moarvm
11:10 edehont joined #moarvm
11:30 brrt joined #moarvm
12:43 Util joined #moarvm
14:22 brrt joined #moarvm
14:49 brrt joined #moarvm
17:55 domidumont joined #moarvm
18:05 brrt joined #moarvm
18:40 FROGGS joined #moarvm
18:57 brrt joined #moarvm
20:05 zakharyas joined #moarvm
20:36 brrt joined #moarvm
20:46 brrt good * #moarvm
20:47 brrt evening, in fact
20:47 timotimo hey brrt
20:47 brrt hey timo
20:48 brrt 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 brrt (i've had the $thesis back this week with things to fix :-()
20:51 brrt after the JIT is completed and merged, of course
20:51 brrt well, let's do that first, shall we
20:53 brrt oh, i've a roadmap/plan for the register allocator coming up
20:53 brrt i'd be grateful if you could have a look
20:57 dalek MoarVM/even-moar-jit: 0ede936 | brrt++ | docs/jit/register-allocator.org:
20:57 dalek MoarVM/even-moar-jit: Roadmap for register allocator
20:57 dalek MoarVM/even-moar-jit:
20:57 dalek MoarVM/even-moar-jit: Will develop the register allocator based on linear scan, with
20:57 dalek MoarVM/even-moar-jit: 4 separate passes.
20:57 dalek MoarVM/even-moar-jit: review: https://github.com/MoarVM/MoarVM/commit/0ede936969
20:57 brrt ^ that thing
20:58 * 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
20:59 brrt you're both right, of course
20:59 brrt well, there's some things that aren't handled well within the current expr jit design, especially involving loops
21:00 brrt this is because it wasn't designed for that, of course
21:00 brrt .... i wonder if there isn't a good way to resolve that, though...
21:00 brrt (the expression jit doens't really need to resolve that, the tiler can)
21:01 brrt https://github.com/MoarVM/MoarVM/blob/even-moar-jit/docs/jit/register-allocator.org <- comments welcome :-)
21:03 brrt we should really cleanup the github issue log...
21:18 jnthn brrt: Using the expr JIT to better JIT array access, bigint operations, etc. would go a long way :)
21:19 brrt aye, that is the plan :-)
21:19 brrt oh, interesting bit
21:19 brrt i'd like to add a THROW node type
21:20 brrt which is exactly like CALL, but doens't return
21:20 brrt why? register allocation reasons
21:21 brrt 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 :)
21:21 jnthn But yeah, with most of the control ones you know :)
21:22 brrt adhoc exceptions are the ones i'm thinking off directly
21:22 brrt the well-formed excdeptions aren't much of a problem
21:23 jnthn Yeah, those ain't :)
21:27 brrt i'm just short of the energy level required to start hacking at the register allocator right now
21:28 brrt 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...
21:28 brrt they are two sides of the same solution
21:28 jnthn Which contrast? :)
21:28 jnthn ah :)
21:29 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 brrt well, the things about that are:
21:30 brrt - linear scan and graph colouring insert spills in response to precisely the same conditions
21:31 brrt - 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:33 brrt - because you have in both cases the exact same information (locally) available,  you can, in fact, make much the same choices
21:35 brrt linear scan has the advantage that it actually uses the linear order imposed by the code to let conflicts 'pop up' automatically
21:38 brrt 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:39 brrt this will be a blog post that hopefully makes more sense than what i'm saying now, i assure you :-)
21:43 * 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 jnthn I guess whether it's worth it to do a little bit better is fairly contextual.
21:44 jnthn (Crawling through the solution space, that is)
21:45 jnthn If there's very little gain to be had anyway, then for Moar it's almost certainly not worth it. :)
21:45 jnthn Also "worse in theory" results don't always pan out as "worst in real use cases"
21:45 jnthn *worse
21:47 jnthn 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:52 brrt what is N in that case
21:52 brrt i've wondered more than once :-)
21:52 brrt but yeah, your lecturer was right
21:52 brrt another minornote
21:53 jnthn Number of basic blocks
21:53 brrt aha
21:53 jnthn The breakeven point was around 30,000 iirc :)
21:54 jnthn 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
21:54 brrt oh, wow
21:54 brrt still, N^3 for 200, that sounds... pretty bad
21:55 brrt so i wonder how bad the O(N log N) algorithm does
21:55 jnthn I think it's N^3 worst case.
21:55 jnthn iirc it's a fixed point algorithm and it converges pretty fast on typical CFGs
21:56 brrt oh, right
21:56 brrt fixed point algorithms.... weird that i never really realised these existed
21:57 brrt the tiler table generator is also a fixed point algorithm, and it defeats the earlier brute-force algorithm by a large margin
21:58 brrt we should also get money from mozilla: https://morepypy.blogspot.nl/2016/08/pypy-gets-funding-from-mozilla-for.html
21:58 brrt just because
22:00 * jnthn is < 10 hours off his current funding running out
22:01 brrt aw....
22:01 brrt :-(
22:01 jnthn Or more precisely
22:02 jnthn Off the currently agreed number of hours being used up
22:02 jnthn I believe there's funding for another bunch of hours.
22:03 brrt \o/
22:03 brrt jnhtn: are you planning to go to any later meetups this year?
22:04 brrt seeing as neither of us is going to YAPC::EU
22:04 jnthn It's hard to say at the moment.
22:05 brrt oh well, no pressure :-)
22:05 brrt i'm thinking i may be able to go to the london perl workshop
22:06 brrt if they still allow me in, of course
22:32 timotimo jnthn: there's currently no osrpoint inside regexes; should we put some in some places?
22:33 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
22:37 timotimo 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? :)
22:37 timotimo ignoremark
22:38 timotimo 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...
22:38 jnthn We should provide ops that just take regions to compare, really
22:38 jnthn Allocation-free
22:38 timotimo right
22:38 timotimo 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
22:48 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
22:49 timotimo but i had to rip out the other part again; that one could still benefit from the improvement to that particular op
23:20 BinGOs joined #moarvm

| Channels | #moarvm index | Today | | Search | Google Search | Plain-Text | summary