4 ms·

I've not been conditioned to expect bad interview questions, so I'm gonna ask: in what way would/could this be a trick question?

542458 5y ago
I was waiting to see a weird gotcha about multiplication not being atomic or something. Actually, question for people with more low-level knowledge than me: is that solution atomic?
- db48x 5y ago
  All math operations on your ordinary everyday cpus are equally non–atomic. They read a value, potentially from memory or from cache, operate on it, and leave the result in a register. Then your program probably has to store the result somewhere, or perform more operations on the result. This is why the memcached software has an explicit locking mechanism; any operation on a cached value involves taking a lock, doing the operation, storing the result, and then releasing the lock.
  - josephg 5y ago
    Memcached shouldn't need an explicit lock to add. Unless I'm missing something, you should be able to use atomics. For example, for adding it should be enough to use an atomic Fetch-And-Add instruction: https://doc.rust-lang.org/std/sync/atomic/struct.AtomicU32.html#method.fetch_add https://doc.rust-lang.org/std/sync/atomic/struct.AtomicU32.h... Multiply doesn't have an equivalent. You can work around that by reading, multiplying and then using CMPXCHG to atomically update the variable if nothing has changed while you were processing. But you need to think about the ABA problem[1]. (I think in this case its safe, but I haven't thought about it enough. Lock free algorithms have subtle bugs.) [1] https://en.wikipedia.org/wiki/ABA_problem https://en.wikipedia.org/wiki/ABA_problem
    - stormbrew 5y ago
      Updating an entry in a database table (which is what a memcache entry is, in practice) is not usually as simple as just "change the value from X to Y". Locking is likely necessary no matter what.
    - jhgb 5y ago
      Is ABA an issue here? "Replace A by X*A" should be perfectly fine if an atomic swap gives you A back, since it means it was actually A at the time when you perform the swap. That it was B a moment go doesn't seem to matter.
gravypod 5y ago
I downloaded the code and had a look. For context, I've ramped up on quite a few code bases in my day in a bunch of different languages. Here was what I thought would happen in order of likelyhood: 1. The code would not build at all on a standard linux distro unless you knew exactly what packages to install. (I had an interview like this once) 2. Locking the key was going to be inexplicably linked to the operation (got very worried when I saw `add_delta` and `do_add_delta`). Turns out add_delta just calls do_add_delta wrapping it in a lock. The lock API is very simple. 3. There would be a massive amount of code duplication that would make it difficult to add this feature without doing serious refactoring. Turns out you basically just change `bool incr` for `math_op_t` or something and provide a way to map from binary/string input to math_op_t. This would be very easy. Depending on how comfortable I was with the editing environment they talk about elsewhere in the hn comments it wouldn't be too bad.
notreallyserio 5y ago
That's just it, I couldn't figure that out. There's "always" a trick, so I've read in some forums.

542458 5y ago

I was waiting to see a weird gotcha about multiplication not being atomic or something. Actually, question for people with more low-level knowledge than me: is that solution atomic?

db48x 5y ago
All math operations on your ordinary everyday cpus are equally non–atomic. They read a value, potentially from memory or from cache, operate on it, and leave the result in a register. Then your program probably has to store the result somewhere, or perform more operations on the result. This is why the memcached software has an explicit locking mechanism; any operation on a cached value involves taking a lock, doing the operation, storing the result, and then releasing the lock.
- josephg 5y ago
  Memcached shouldn't need an explicit lock to add. Unless I'm missing something, you should be able to use atomics. For example, for adding it should be enough to use an atomic Fetch-And-Add instruction: https://doc.rust-lang.org/std/sync/atomic/struct.AtomicU32.html#method.fetch_add https://doc.rust-lang.org/std/sync/atomic/struct.AtomicU32.h... Multiply doesn't have an equivalent. You can work around that by reading, multiplying and then using CMPXCHG to atomically update the variable if nothing has changed while you were processing. But you need to think about the ABA problem[1]. (I think in this case its safe, but I haven't thought about it enough. Lock free algorithms have subtle bugs.) [1] https://en.wikipedia.org/wiki/ABA_problem https://en.wikipedia.org/wiki/ABA_problem
  - stormbrew 5y ago
    Updating an entry in a database table (which is what a memcache entry is, in practice) is not usually as simple as just "change the value from X to Y". Locking is likely necessary no matter what.
  - jhgb 5y ago
    Is ABA an issue here? "Replace A by X*A" should be perfectly fine if an atomic swap gives you A back, since it means it was actually A at the time when you perform the swap. That it was B a moment go doesn't seem to matter.

gravypod 5y ago

I downloaded the code and had a look. For context, I've ramped up on quite a few code bases in my day in a bunch of different languages. Here was what I thought would happen in order of likelyhood: 1. The code would not build at all on a standard linux distro unless you knew exactly what packages to install. (I had an interview like this once) 2. Locking the key was going to be inexplicably linked to the operation (got very worried when I saw `add_delta` and `do_add_delta`). Turns out add_delta just calls do_add_delta wrapping it in a lock. The lock API is very simple. 3. There would be a massive amount of code duplication that would make it difficult to add this feature without doing serious refactoring. Turns out you basically just change `bool incr` for `math_op_t` or something and provide a way to map from binary/string input to math_op_t. This would be very easy. Depending on how comfortable I was with the editing environment they talk about elsewhere in the hn comments it wouldn't be too bad.

notreallyserio 5y ago

That's just it, I couldn't figure that out. There's "always" a trick, so I've read in some forums.