It’s been two weeks since I started practicing coding problems to get ready for technical interviews. I’ve been solving questions like C and D on Codeforces. I have chosen Go to practice as well. So far, I’ve had a great experience with Go; I believe Go is even more intuitive than Python, at least for me. The amount of opinionated conventions you need to follow in Go is minimal, and almost all conventions are natural. You don’t need to look at the docs every time to remember how to do something in Go. I might write about the good problems I’ve come across later.
So far, the only shortcoming of Go has been the inability to do arithmetic on pointers (footnote: a nice post from Joel Spolsky about pointers). I wanted to implement doubly linked lists in Go with XOR. Instead of storing pointers to next and prev, you can store &prev XOR &next and then use that to compute neighbors. If you want to traverse forward or backward, you can XOR the address of the last node with the current node.
n1 <--> n2 <----> n3 <----> n4 <----> n5
0&&n2 &n1^&n3 &n2^&n4 &n3&&n5 &n4^0The main issue was that we can’t do XOR on pointers in Go. However, we can use the unsafe library to operate on pointers. But that library is recommended not to use and may cause issues. I was wondering if this is a design decision to prevent developers from complicating their code or if there is some underlying issue. It turns out it can mess up the garbage collector. Assume p is a pointer to some struct and we want to modify p. It is possible for the GC to clean the struct p is pointing to before writing the new value. What we can do is use atomic operations stronger than read and write; we can leverage Compare-and-Swap operations on pointers! However, we need to be careful to have a wait-free design. Back to the XOR linked list: actually, this is not an issue in that case since we are not modifying the pointers to nodes but some extra pointers.