freenode/#sicl - IRC Chatlog
Search
9:53:09
heisig
One thing I haven't understood yet about register allocation in SICL - why don't we start by defining a register allocation interface and providing a simple default implementation?
9:55:16
beach
That's pretty much what I am doing, but for x86 only. I have abstracted out EDU, and "allocate a new register". The rest is imposed by the x86 constraints.
9:58:13
heisig
Could these constraints be formulated in a way that is independent of the architecture?
10:00:08
beach
That is also what I am doing. I am currently translating MIR instructions such as c <- a op b into r <- r op s where a and b are lexical locations or immediate inputs, c is a lexical location, and r and s are register.
10:00:47
beach
So the architecture-independent description is that the destination must be the same as the first operand.
10:03:01
beach
Er, s can also be an immediate of course. But I am currently simplifying so that s can not be a stack location.
10:09:48
heisig
I was thinking about using a domain-specific logic programming language. (But I admit I don't have much experience with logic programming)
10:15:59
beach
Logic programming is usually a great way to turn a polynomial algorithm into an exponential one.
20:36:53
no-defun-allowed
I had an idea for handling a metadata table with a concurrent hash table. When adding a new mapping, if we have to use the next group, because the first is full, we set a bit somewhere indicating the first group was full, instead of trying to observe if the group is empty when removing, and CASing entire groups.
20:41:25
no-defun-allowed
This trick is an application of the "if a tree falls in the forest..." thought experiment, as we only track when a group is observed to be full. So a group that is filled, and then has some mappings removed, without another insert operation observing that the group is filled, will not be marked as filled.
20:46:50
no-defun-allowed
Around 47:26 in the Cppcon talk, Kulukundis discusses a group which fits into a cache-line, using 7 hash bytes, 7 presence bits, and 1 "ever full?" bit.
20:51:56
no-defun-allowed
Also, in the comments, he says he didn't see a benefit from using 32 byte groups (think 256-bit, AVX2 instructions) over 16. Implementing the latter group seems hard though, both with general-purpose instructions fooled into byte-parallelism and with SIMD instructions.