Hacker News Reader

Comment by pslam | Hacker News Reader

This sounds wrong to me, too. For the single core case, there's no such thing as an atomic byte store - the underlying mechanism reads a cache line and modifies it. The same goes for a bit operation (possibly needing more instructions).

For the multi-core case, there's always going to be cache line thrashing regardless of size. Cache lines will evict/transfer between cores as each accesses them.

Probably best to go with single bit, unless it can be shown that the overhead of generating a bit mask and the r/m/w is far more expensive.

View on HN

The referenced paper is a bit vague about this:

An alternative to side bitmaps is a bytemap, a bytegrained data structure on the side. Bytemaps trade an 8× space overhead to avoid synchronizing on each set operation (if we assume support for atomic byte-grained stores).

I think the idea is that, since a bytemap is less dense, two cores less frequently access the same cache lines, leading to fewer invalidations. Though, I wonder if it pays off, since it also gives less locality.

No, it is referring to the fact that the least unit that can be written to memory isn't a bit but a byte. To write a bit the whole byte must be read, modified and then written back.

Sure, but in both cases if a mark needs to be changed 'the whole byte needs to be read modified and written back', bitmaps or bytemaps.

Isn't the atomic part of that sentence referring to that they are changing bits separately, which is a bit inefficient since most architectures simply doesn't allow that. To set a single bit the writer must read the whole byte, modify it and then write the whole byte back. This is slower than simply writing the whole byte.

That is, I don't think they are referring to the same concept of atomicity as you are.

Aren't they agreeing with your single bit approach? If so, why does it sound wrong to you?

The point is atomicity doesn't work like this on x86, ARM and most architectures. It's the right conclusion from the wrong analysis. The difference in speed will be the time consumed by managing a packed bitmap, not due to the atomicity being any faster.

Reply on news.ycombinator.com