freenode/#sicl - IRC Chatlog
Search
15:11:28
beach
I am now convinced that the formula for combining EDUs of several successors that I wrote in the Cleavir documentation is right, and so it is not linear. But it's OK, because I decided that I should do this will Kildall instead.
15:11:29
beach
If I systematically round the EDU down to the FLOOR of the combined value, iterations should stop quickly. Plus, if there are as few back arcs as my test indicates, and presumably some variables are used or defined inside loops, then there will be no iteration at all for those.
15:12:32
beach
So now I am studying what Bike wrote for the Kildall implementation. It is quite well written. I will just add a few comments and fix some others.
15:27:52
heisig
I was already wondering how this system could be made linear. Using Kildall sounds good.
15:29:24
heisig
I recall that the compiler I wrote for my university assignments used Kildall for almost everything. It is a great algorithm.
1:26:01
no-defun-allowed
This is the kind of crap "pinning" keys to hash table entries saves one from, I suppose. Guess I can still check if the key is the same after loading the value.
1:35:01
no-defun-allowed
Well, no, that leads to a situation (which is so unlikely that it's funny) where we do something like "get key, another thread replaces entry, get wrong value, another thread replaces entry with old key, get key again". Off to plan B then, which is to wrap each mapping in a CONS and swap out CONSes.
1:35:55
no-defun-allowed
So, it's sort of not really linear probing then, but there'd be only about 1 extra read.