00:25 colomon_ joined 02:05 colomon joined 02:52 colomon joined 06:32 domidumont joined 06:53 domidumont joined 06:58 domidumont joined 07:10 zakharyas joined 08:06 domidumont joined 09:32 Ven_ joined 10:11 domidumont joined 11:29 brrt joined
brrt ehm, you may with reason not believe me 11:41
jnthn yeah, right
brrt but i think i finally, really, truly know how to implement the register allocator 8-)
jnthn \o/
brrt so now the issue is to make time for it 11:42
one of the interesting bits is that i think i've discovered that linear scan (known as fast) is a subset of graph coloring 11:43
that is going to be a blogpost soonish
graph coloring is known as slow, because a): graph coloring is .... whatsitcalled? traveling-salesman-equivalent complexity 11:44
and linear scan is known as fast because linear
but in reality linear scan is just a special version of graph coloring 11:45
timotimo NP-complete is the word you're looking for? 11:46
brrt i.. think so
yeah, thanks :-)
arnsholt That is indeed NP-complete 12:02
When I took a databases class some years ago, we spent quite a bit of time discussing serialization algorithms/strategies (that being rather important for databases) 12:03
brrt uhuh
arnsholt First we discussed locking, which has some obvious drawbacks, then we covered something called view-serializability (IIRC)
brrt (fwiw, i'm not sure a live range in this model can still meanigfully live in two registers.... that just has to go then)
arnsholt Think we spent like two lectures on it
brrt do continue 12:04
arnsholt And then at the end they just casually drop, "but this turns out to be NP-complete"
>>>>>>.<<<<<<<
brrt lol
yeah, sucks when that happens
that basically happened to my idea of 'let's find the ideal combination of renewable generators for a given area' 12:05
'this is going to be easy, just fill them up with the most ideal spots first... oh wait'
arnsholt Yeah, turns out a rather large fraction of interesting problems are NP-complete
brrt or solved by union-find 12:09
timotimo when you get a job, you better find a union to join ... 12:10
brrt :-) 12:45
okay, i'm off, i have to write thesis reports and stuff
see you later
16:27 FROGGS joined 18:56 domidumont joined